NOIP2021游记(Noip2021 travel notes)

同机房同学的:lzqy_

11月8日至9日

期中考炸裂,之后开始在机房晚上集训。

11月20日

先用30min看了看题,大致感觉是这样:

T1是类似埃氏筛的东西,T2是计数dp,T3应该是数据结构,T4应该很难,但是暴力搜索应该很好写。

之后用10min写完T1,我用了并查集维护答案,然后测第四个样例时RE了,之后开始调。

然后直接调了1h,之后确定了错误是在并查集(之前没想到),然后发现是爆递归栈了(在Linux下不会有这个问题,也就是我浪费了1h)

发现这个问题之后我心态居然很好,写了对拍程序之后开T2。

想得状态时\(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}\)

之后发现第二个样例没有过,然后就开始调,中途还怀疑自己的转移方程过,也去外面冷静过,1h后发现\(+=\)写成\(=\)了,改了就过了所有样例,写好对拍程序就只剩1h了。

之后决定开T3,没看出来是差分数组交换两个位置,推了一会柿子之后决定还是写暴力,写了个dfs发现第二个样例就TLE,之后写了一个模拟退火,第三个样例没过,最后20min感觉写不了T4,就都用来调参了。

预计分数:\(100+100+[12,48]+0=[212,248]\)

洛谷测的\(100+100+28=228\),T3算给面子了

总结

这次做的其实还算好,心态比CSP的时候好很多,但是还是在时间把握上有问题。

在做T1的时候就被递归栈给浪费了1h,但是如果我改成用递推的方式预处理答案的话我也许就没有这个问题,这说明,我应该在写代码前想想有没有更好的实现方法,调试时可以用另一个写法来对拍小数据。

在做T2的时候被\(+=\)这种小细节用了1h来调,这说明调代码时可以先看代码细节,找到手误打错的地方。

我这次前两题都用了大量时间来调试,其实可以选择先写后面的题,尤其是在确定后面有些分特别好拿时(如这次T4的爆搜)。

————————

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

summary

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).