[learning notes] agc008

Tetromino Tiling

Black Radius

• Clever topic
• sb Translation makes me think for a long time
• set up $f(x,d)$ Represents the distance $x$ Less than or equal to $d$ Set of points for
• If $f(x,d1)=f(y,d2)$
• So for any $x\to y$ Points on the path $z$, There is $d$ Satisfy $f(z,d)=f(x,d1)=f(y,d2)$
• also $d$ Value is $V$ Type （ It's really hard to prove qwq
• Prove that $f(x,d)$ Uniqueness
• So for some isomorphic $f(x,d)$, We only in $d$ Count at the lowest value
• If $d$ The smallest is the smallest , Then it should be satisfied for arbitrary and $x$ The adjacent $y$,$f(x,d)\ne f(y,d-1)$
• set up $sz[x]$ From $x$ The longest starting chain length ,$sz2[x]$ From $x$ The length of the next long chain
• $mx[x]$ Representation node $x$ The biggest legal $d$
• that $mx[x]=\min (sz[x]-1,sz2[x]+1)$
• The answer is $\sum (mx[x]+1)+1$
• What if only some points can be used as roots
• Consider for those smallest $d$, Find the best alternative
• It's not hard to find out $d$ Monotonicity
• set up $lw[x]$ Representation node $x$ The smallest one can find a substitute $d$
• If $f(x,d)$ Can find alternative points , Then exist and $x$ The adjacent $y$, Satisfy $f(x,d)=f(y,d+1)$
• that $lw[x]={\min }_{y\in son[x]}(\max (sz[y]+1,lw[y]-1))$
• Obviously we need to change the root
• And then it's done
• The answer is $\sum (mx[x]-lw[x]+1)+1$
• Complexity $O(n)$

Division into Two

• pull oneself together
• Ingenious restrictions on transformation
• You might as well Abstract any scheme into a $01$ Sequence
• Direct transfer is disgusting
• Rather give up direct transfer
• Might as well set $A\ge B$
• First, according to the pigeon nest principle , For any $i\ge 3$ Yes $s[i]-s[i-2]\ge B$
• With this property, we can transfer
• $dp[i]$ Before presentation $i$ Number , The first $i$ The number is $X$ Number of schemes in the set
• Obviously legal transfer $[l,r]$ You can use prefixes and optimizations
• Complexity $O(n)$

Rectangle

• Pigeon nest principle construction
• It should not be difficult
• Obviously, we need to estimate the range

Sequence Growing Easy

Sequence Growing Hard