[learning notes] agc010

Do more AGC Long brain

No samples , Just rely on your brain

Rearranging

• Consider if two numbers are not mutually prime , Then their relative positions in the final sequence remain unchanged
• So for two numbers that are not coprime , At the same time, orient each edge DAG
• The answer is the largest topological order , Because considering that a point can be exchanged with any other point without entering
• Greedy structure . Start from the point with the lowest number dfs , Find the edge with the lowest node number every time , It can be understood as constructing a tree .
• Then simulate it （

Tiling

• Greedy to consider how to maximize the grid
• Obviously, the mesh is divided into several 2x2 The matrix of is optimal
• The leftover materials are paved with corresponding horizontal bricks or vertical bricks
• This will definitely maximize the number of bricks
• Hand play discovery n=3,m=3,A=2,B=2 There will be problems （ Here hack Data is the difficulty
• That is to say, for the last 2x2 Of the lattice , There is one horizontal brick and one vertical brick left , Theoretically, it can lay two bricks , But due to the shape, only one piece can be paved

• Notice that there is a space in the lower right corner , You can put it down by adjusting .

• There are two schemes directly check that will do .
• Notice the grid problem Nastia and a Beautiful Matrix , from Maximize the use of grid space Starting with , Find the local optimum , Then the global optimal solution is constructed .

Three Circuits

• The degree of each point must be even
• The title gives that this is a connected graph , So there must be an Euler circuit
• If there are degrees of points >=6 , Then there must be a solution （ Consider proving from the perspective of Euler loop
• Count the degree = 4 The number of points is cnt
• If cnt=0 , Then only one ring can be constructed at most
• If cnt=1 , Then only two rings can be constructed at most
• If cnt=2 , So there are two situations （ Drawing perception ： It is possible to construct two rings or three rings
• If cnt>=3 , Then remove a simple ring and conclude cnt=2 The situation of , At least three rings can be constructed

Decrementing

• If there is $a_i=1$ , So judge $\sum (a_i-1)$ Parity .
• Definition $\sum (a_i-1)$ Odd numbers are wins , Even numbers are negative
• If the person currently operating wins , So no matter what the other person does , At present, this person will win
• Because if you don't divide all numbers by the greatest common divisor ,$\sum a_i$ The parity of does not change , that $\sum (a_i-1)$ The parity of will not change , The outcome is fixed
• Now it's equivalent to $\sum a_i\to \frac{\sum a_i}{x}$ , If and only if $x$ It's even and $\frac{\sum a_i}{x}$ Only when it is an odd number
• Note that the number of odd numbers in the sequence is cnt , At first, because of mutual prime cnt>=1 , Then two people take turns , Those who are behind can never let cnt=0 （n>=3 when ）
• If the current operation fails , Then operate on the only odd number , This may reverse the outcome .
• So direct simulation . Not more than $\log a$ Time .