7.27 simulation summary

Mirs spread their wings on the edge of breaking their mentality again

Find yourself having a problem ： Last game was average -> This one is eager to make a high and unreasonable score on a certain problem -> Occupy a reasonable time for other questions -> Send

And it seems that there is a strange bias at the beginning of the competition ）

There are also official competitions I especially don't want to do the parenthesis sequence when saving the election ） I especially want to do it seriously for a while I didn't even feel sleepy today ）

And it seems that the reliance on the examples given by the topic is too strong ）

today T2 Hang up 25 T3 Hang up 20

A particularly bad place ：

T1 After making it up for a long time, it was still violent
T2 Reasons for scoring ： Modulo on index should be modulo phi(x)

Time arrangement

8.30-9.30

Look at the question T1 Tree form dp T2 I feel I can divide and conquer by root sign T3 Don't understand, （ When you see the brackets, you start to look big

Thought about it for a while T1 I don't know if it's true dp But complexity $n^5$ about And I feel that the space cannot be opened

9.30-11.10

Write T2 Test sample after writing Find that the sample can start to print the table

At the same time, it optimizes

And sort it out T2 Table of Stuck in 12kb

11.10-11.40

Write T3 The violence of

11.40-12.10

Write T1 The violence of

Topic analysis

T1

I feel I can move the edge right to the point right Difference from bottom to top Then consider A pair of chains $x,y$ The operation of

1. If $x$ yes $y$ Our ancestors $x$ spot -1 $y$ +1

2. set up lca by $z$ ,$z$-2 ,$x$+1 $y$+1

The last difference array and dp Arrays are equal

$f[x,i,j,k]$ Indication point $x$ In the subtree Yes $i$ Points up and no matching left point $j$ Points up and no matching right point $k$ The number of schemes when there are no matching points around

Two points can be considered when transferring $x$ by lca perhaps $x$ Merged with the following point

（ I don't know Not written ） I don't know the complexity GA ） Should be n^3?

upd

The clam can't live I ordered violence for a long time Finally, I found that when I ordered violence, I deduced the positive solution ）

$g[x,w]$ It means that $x$ There are $w$ Number of schemes of color blocks

Then the difference between positive solution and violence is

Violence enumerates the color blocks represented by the father side How many left and right

The positive solution is to put it directly into the tree backpack and do it together

My violence is that I don't need to be a tree backpack But the discovery will be 3344 In this way hack Then I looked at the code and suddenly realized ）

honestly Someone really wrote it 60 Do you

I feel as long as I notice the tree backpack It is very obvious to convert the father side Consider the father's request to have one on each side So the number of voids is less Let's remove the left and right and leave $v$ individual Merge $x$ individual So the solution is $C_{v+1}^x$ Nothing else changes

T2

Consider less than 80 When Only 2 3 5 7 , So these numbers are stored in the status Other binary maintenance

T3

The practice of examination is too sloppy ） The feeling is that the brackets match the questions of the series Simulation game / I didn't take the exam too much, and then I felt numb at first sight ） I feel very bad

Correct method of violence ： Consider putting all operations on the stack and simulating ） Be sure to simulate that bracket ！！！