NOIP2022游记

bobo2007 · 2022-11-26 20:21:30 · 个人记录

CCF题目排序一般是顺序——zxy

作为今天挂得最惨的人，还是写一篇游记。

先来个开幕雷击，infoj 分数18+?+10+20=48+?

Day -1

CF Div4 喜提F题挂掉，失去信心。

Day 0

线段树2打了1h，老年人手速。

Day 1

8:00

早上八点钟到比赛现场，进去之后找不到 VSCode ，翻了好久才找到。

8:35

第一题大致题意是要从图中统计C和F的数量于是秒了，非常自信的没打拍子（赛后吐槽：~~然后挂到十几分~~），设f_{i,j} 表示从第 i 行第 j 列往右有几个空，倒着枚举 j 快速求解。

则对于每个 C 枚举第一条横线，对于第二条求后缀和。

对于每个F 还是一样，只不过要加上”杆子”出头的部分。

于是非常自信的写完了，然后就挂在了 F 上，原因如下图：

显然三个横着的二选一，然后下面出头，但是由于对于一个 i 我统计的是下面所有的横着的杆子的方案和，竖着的长度可能超不过横着的，于是喜提挂82pts。

9:20

开T2，题意较为复杂，大概就是一个序列，依次将其中的数字加入若干个栈里，相同的数字在栈顶可消去，在不同栈底数字相同的牌也可消去，问怎么消才能消完。设牌种数为 k 栈 n 个，满足 n = 2 \times k - 2 或 n = 2 \times k - 1.

首先对于前一种，我们将数字种类两两分类，丢到 n-1 个栈里，然后对于新加的数吗，当那一类栈里的数字个数为2时，如果它与它那一类的栈顶相同，则直接丢进去消掉，否则把它丢空栈里，这样可以消去栈底，栈的大小无论无何都会减少1，个数小于2时，直接丢到栈顶能消就消，得到了15pts的好成绩。

对于后一种，首先的想法是将它丢到第一个栈里混合，接着发现并不能解决，于是咕咕咕了。。。

10:00

看做太久了，先打T4暴力，然后觉十分的CF，大概是在 l 到 r 中选择两个 i,j ，答案累加 (max_{k=i}^j a_k) * (max_{k=i}^j b_k) 用前缀和打了个 O(n^2+nq) 的暴力，+20pts。

10:10

转战T2,想了另一种奇怪的思路，就是将多余的找一个插上，然后用其他的调整，但是不知道具体放哪个，于是又咕咕咕了。

10:25

本场比赛中最残的决定。

终于开T3了，大概是一个无向连通图，每个点都可以成为关键点，每条边可以成为关键边，要求赋关键点和边的方案数，满足断掉任何非关键边，所有关键点依然可以互相到达。

这不纯纯的缩点加树形DP吗？

脑袋里装着大大的疑惑的我认为可做，一想T3都可做那T2不是。。。

好的又去看T2了。

11:30

依然停留在调整上，接着看了样例，发现均匀的铺在下面貌似更有可能，然后就差不多想到正解了。

我们可以尝试维护一个东西，每次里面每种数字最多出现一次

先来个 n=2 ,k=3 的例子。

序列 a=1,1,1,2,1,1,3,2,1,2,3,2

首先对于相邻两个相同的我们完全可以消掉。

于是简化成了

a=1,2,3,2,1,2,3,2

先把前两个加进去，栈变成

|.|.|
|.|.|
|.|.|
|1|2|

考虑加入第三个，发现如果加到第二个栈里，就无法把2消掉，于是加入第一个。

|.|.|
|.|.|
|3|.|
|1|2|

接下来愉快地将2消掉，变成

|.|.|
|.|.|
|3|.|
|1|.|

又发现1也可以消掉，变成

|.|.|
|.|.|
|.|.|
|3|.|

此时接着做下去即可实现一定有解。

好的开始打，发现十分困难。。。

11:55

犹豫了一下，打T3暴力，树形DP。

设 $k \in son_i$ ，`i` 及其子树内有 $sz_i$ 个点转移不难得到 $f_{i,0,0}=2^{sz_i}

f_{i,1,1} = \prod_k f_{k,0,1}+f_{k,1,1}+2 \times f_{k,0,0}

f_{i,0,1}=f_{i,1,1}-f_{i,0,0}

最终枚举所有点，答案为

ans= \sum_{i=1}^n f_{i,1,1}*2^{n-sz_i}

以为get 25pts

结果赛后小丑，10pts，不知到挂哪。

12:25

复盘T2，又双叒叕想了一下，n 为2以上貌似也能这样做，于是开打。

12:55

不出意料没有调出来，但是发现了要输出答案个数，火急火燎地改了交上，15pts遗憾离场。

以下为吐槽，发电，emo区

13:10

在得知大家都寄了时，我知道我又被阻击了，当时的我还不知道挂T1了。

吃完饭拍完照回家后，我睡了3h

17:50

Warning:一下内容可能会引起身体不适，慎重观看

infoj上有数据了，交了发T3，发现挂分了。

怀着忐忑地心把T1交上去，拍了几页队。

我永远不会忘记那个橙色刺眼的

\huge\color{orange}18

我一拳下去电脑死机了。。。

重启之后查错，错误如上文所写。

100 \rightarrow 18

我还是无法相信。

如果你正在看着（包括我自己），那么请永远记住：

永远不要过于自信

老老实实打对拍吧。

还有就是

麻烦先做会做的题吧，什么**顺序开题

不要让到手的分数飘走。

没什么好说的了。

挂都挂了。

18+15+10+20

这个分数AK了省选都救不了。

明年再接再厉吧。

要回归文化了。

希望以后再也不会出现这种情况。

emoing