[learning notes] agc041

Domino Quality

• atcoder Concise questions are highly praised
• Be patient when doing structural problems
• What a hell problem ...
• set up $(A,Q)$ Indicates that the quantity of each row and column is $Q$ Of $A\times A$ Matrix of size
• If we knew $(A,Q)$ as well as $(B,Q)$ Construction method of , We can construct $(A+B,Q)$
• The specific method is to put the two matrices in the upper left corner and the lower right corner respectively , The rest is empty
• Obviously consider $Q=3$ The situation of Not obvious
• Obviously you can put $(4,3),(5,3),(6,3),(7,3)$ All were searched out
• Obviously, you can type a watch Anyway, the test site of this question is not here
• EH n=7 Why can't violence escape
• Alas, with the addition of metaphysical pruning, how can it run fast
• A pile of code is very ugly, and even the output is very ugly

Unique Path

• Wonderful construction problem Although I still can't do it
• Obviously, delete all edge weights as $1$ The edge of , There is a unique simple path for two points in each connected block
• Don't rush to shrink each connected block , First, we select a point from each connected block , Then connect them into a ring , In this way, there are at least two simple paths for points that are not in the same connected block
• Let the number of connected blocks be $k$（ The above structure is just connected $k$ side , Form a base ring tree ）, Then the number of edges across connected blocks will not exceed $\frac{k(k-1)}{2}$, Otherwise, a connected block cannot maintain its independence
• So we just have to judge $m$ Whether the size of is within the range .
• Complexity $O(n)$.
• summary ： Consider the answer Up and down

Wide Swap

• Rabbit's solution
• Consider a good problem transformation
• set up $Q[i]$ Express $i$ Position in the original sequence
• Then exchange $Q[i]$ and $Q[i+1]$ Is the condition of $|Q[i]-Q[i+1]|\ge K$
• If $i<j$,$|Q[i]-Q[j]|<K$ that $Q[i]$ and $Q[j]$ The relative position of will not change , let me put it another way $Q[i]$ Forever $Q[j]$ Before
• So let's make $Q[i]\to Q[j]$ In this way, the topological order must meet the limit
• At the same time, we need to $P$ The order of the dictionary is the smallest , Turn it into $1$ stay $Q$ Top of the list , stay $1$ Let... Under the premise of the most front $2$ Top
• This is a classic question Don't be classic anymore. I'm all wa Go over it It can be solved by reversing the graph and running the maximum topological order
• You can consider from small to large according to the number $Q[i]$, We found that as long as we found $Q[i]$ The largest precursor number and the largest subsequent number can be connected .
• Complexity $O(n\log n)$

Nondivisible Prefix Sums

• Hint1： The sum of all elements cannot be $P$ to be divisible by obviously
• Hint2： Mode occurs no more than $\frac{n}{2}$ The sequence of is legal （ You can think backwards
• Hint3： There is a clever transformation . Let the mode be $x$, Multiply all elements $x^{-1}$, Then the prefix and will also multiply $x^{-1}$
• Hint4： Clever observation Notice every step $P$ Will consume at least one not for $1$ The number of
• Why not $1$ At least $\frac{{\sum }_{i=1}^n{y}_i}{P}$ individual
• Consider the construction scheme , First put all the numbers $1$ run out , Then for the rest, as long as we let it not arrive $P$
• Obviously, there is a solution after removing the mode