NOIP2021游记(Noip2021 travel notes)










想得状态时\(f_{i,j,k,S}\)表示序列确定\(i\)个位置的值,最大的值是\(j\),目前的和\(\mod 2^j\)在二进制下有\(k\)个1,\(S\)表示目前的和除以\(2^j\)(向下取整)

转移方程为\(f_{x,j+1,k+((s+x-i)\&1),(s+x-i)>>1}+=f_{i,j,k,s}\times v_{j+1}^{x-i}\times C_x^{x-i}\)











Students in the same computer room: lzqy_

November 8th to 9th

The mid-term exam burst, and then began to train in the computer room at night.

November 20th

First, I read the questions for 30min. The general feeling is as follows:

T1 is something similar to the Elsevier sieve, T2 is the count DP, T3 should be the data structure, T4 should be difficult, but the violent search should be easy to write.

After writing T1 in 10min, I used and searched the set to maintain the answers, then measured the re in the fourth example, and then began to adjust.

Then it was directly adjusted for 1h, and then it was determined that the error was in merging and searching the set (I didn’t expect it before), and then it was found that the recursive stack exploded (this problem won’t happen under Linux, that is, I wasted 1H)

After discovering this problem, I had a very good attitude. After writing the shooting program, I opened T2.

When the desired state is obtained \ (f_{i, J, K, s} \) indicates that the sequence determines the value of \ (I \) positions, and the maximum value is \ (J \). The current sum \ (\ mod 2 ^ J \) has \ (K \) 1 in binary, and \ (s \) indicates that the current sum is divided by \ (2 ^ J \) (rounded down)

The transfer equation is \ (f {x, j + 1, K + ((s + X-i) \ & amp; 1), (s + X-i) & gt; & gt; 1} + = f {I, J, K, s} \ times V {j + 1} ^ {X-i} \ times C _x ^ {X-i} \)

After that, I found that the second example had not been passed, and then I began to adjust it. I suspected that my transfer equation had been passed, and I went outside to calm down. After 1h, I found that \ (= \) was written as \ (= \), and all the examples were changed, and there was only 1H left to write the matching program.

After that, I decided to turn on T3, but I didn’t see that it was a differential array to exchange two positions. After pushing persimmon for a while, I decided to write violence. After writing a DFS, I found that the second example was TLE, and then I wrote a simulated annealing. The third example didn’t pass. I felt that I couldn’t write T4 in the last 20 minutes, so I used it to adjust parameters.

Estimated score: \ (100 + 100 + [12,48] + 0 = [212248] \)

According to the \ (100 + 100 + 28 = 228 \) measured by Luogu, T3 gives face


In fact, I did a good job this time. My mentality is much better than that of CSP, but I still have problems in timing.

When doing T1, I was wasted 1H by the recursive stack, but if I changed to preprocess the answer in a recursive way, I might not have this problem. This shows that I should think about whether there is a better implementation method before writing code, and I can use another writing method to take small data during debugging.

It took 1h to adjust the small details of \ (= \) when doing T2, which shows that you can first look at the code details and find the wrong place by hand when adjusting the code.

I spent a lot of time debugging the first two questions this time. In fact, I can choose to write the following questions first, especially when it is determined that some points in the back are particularly easy to get (such as the explosion search of T4 this time).