[learning notes] structure

No brains

Most structural problems are very new , So it is not easy to solve them .

Nastia and a Beautiful Matrix

lose the first battle

Make sure you can fill in as many as you can , It's like this .

You can fill in any odd line , So he went straight ahead , then wa 了 .

First of all, judge that the outstanding number cannot exceed $n\times \lceil \frac{n}{2}\rceil$ Time .

Then observe the diagonal .

Flatten the given number into a sequence . If there are many occurrences, fill in , The mode comes first .

1. Fill in the blank , List as my lattice
2. Fill in the blank , The odd grid
3. Fill in the line , The odd grid

This must be legal .

Off by One

Can't .

It should not be difficult to think of the first step of transformation .

If we connect the two points that can be eliminated , This is to find the largest edge independent set of an undirected graph , And the number of sides is O(n^2) , Send .

If we Point to edge , The background of the problem is very familiar .

Run the spanning tree directly .

One-Four Overload

Construction question （x）
Guess the conclusion （v）

After the judgment of no settlement , It is easy to guess that this problem must have a solution .

For the case of four positions , Limit the number of adjacent two points to be different .

Then we can happily dye the bipartite graph .

It can be proved that there is no odd ring .

It is not difficult to prove . Consider Euler's loop .

Johnny Solving

For undirected connected graphs .

Naturally think of running DFS Trees .

If the leaf node depth >=n/k , So the output path .

Otherwise at least k Leaf node . Consider constructing a ring for each leaf node .

Cohesion >=3 It can be done .

This question sums up Pairs of Pairs The test is all about the same thing .