WC 2021 && SCOI 2021冬眠记

zhangboju · 2021-02-03 17:25:02 · 个人记录

\texttt{Begining}

四川迷惑选了 \texttt{A+B} 即 \texttt{NOIp} \ 60\% + \texttt{WC} \ 40\%

一番权衡以后，我还是报名了CCF 2021 冬令（眠）营，同时获得了参加 \texttt{SCOI 2021} （雾）的机会

上图为敬：

还是很怀念以前的 WC 的（虽然我也没去过），包吃包住还有文艺汇演

线上就什么也没了，收费还一样

\texttt{Day 1}

上午的随机算法听课体验非常好，不愧是北大老师

下午画风突变

zyy txdy!

一下午17题的神奇速度，一直在掉线和通往掉线的路上

竟然把 Mushrooms 那道国家队都没做出来的题讲了

记住了名言

随机化算法没有前途

那我上午学了个寂寞？

\texttt{Day 2}

上午本来想听网络流的，但一开始第二课堂一直进不去，就去听了《IOI题型与去向分析》

听到了很多 IOI 花絮，发现 OI MO化了

11:30 去了第二课堂，有点跟不上

下午蒋明润讲的开始勉强跟得上

中途我们疯狂造梗，把蒋明润笑的不轻

\texttt{Day 3}

为什么考 WC 还要做核酸啊

做了核酸，才急匆匆赶去听课

上午好好的《浅谈 OI 中的数学问题》变成了《深谈高数中的 OI 应用》

开幕雷击：复数+三角函数

两个分开还行，合在一起必须自闭

大概感受一下：z=r(\cos \theta+ \mathrm{i}\sin\theta)=re^{\mathrm{i}\theta}

终于知道为什么 e^{\mathrm{i}\pi}+1=0 了

然后卷积，生成函数，微积分那些我就废了

下午开始讲了三道 IOI 题，可以算是 快 乐 时 光

然后开始矩阵，一开始还强制在线，后来强制离线了

直接 404 Not Found

自闭了两个小时

感觉后面一个小时就是他在自言自语了

果然 IOI 是用来平衡难度的

\texttt{Day 4}

上午讲逻辑

一开始感觉还可以，后来开始希腊字母课之后就开始掉线

[WC2021]希腊字母、[WC2021]形式化证明、[WC2021]逻辑

（泄题禁三）

然后研究了一会交互

还是感觉后一个小时就是他在自言自语

下午就和 \color{black}{查}\color{red}{无此人} 巨佬一起去了成都

去踩了一下点，我堂堂大四川的青少年科普基地竟然在一个偏僻的写字楼里？还没有招牌？

SC 历年不让试机

果然这种地方平常都不开门的

晚上水了一会，就休息了

\texttt{Day 5}（比赛日）

上午起来时间感觉有点紧？

碰到了 sjx，RP++

抱着看一个小时题，冬眠四个小时的心态进了考场。（flag*1）

组委会统一配发口罩是 smg？

进了考场，感觉体验非常良好，老师很贴心

允许吃东西好评

电脑是 ThinkPad，亏得之前适应过那个诡异的键位，i5 CPU 好评，就是没有小键盘让我打 + 号非常不爽。

一直静坐，直到开题

密码是 XinNianKuaiLe（新年快乐）

然后写了个快读，把题扫了一遍

T1 感觉非常不可做的样子，暴力都不知道怎么写，那个环太难处理，盯了一会部分分（flag*2）

T2 又是表达式，CSP J 的那个表达式我就只有 30 pts ，这个题估计也好不到哪去，但大概有个想法，就先去看T3

这个时候已经 9:30

T3 感觉还是非常友好，似乎部分分被我看穿

大概就是第一档留给暴力，第二档是一个同余，第三档是用 exCRT 拆一步，最后一档大概要考虑其它？（flag*3）

然后瞬间口胡了一个 斐波那契通项公式+exBSGS 的做法，结果发现背不到通项公式.jpg （flag*4）

于是成功的把公式写成了 f_n=\dfrac{(1-\sqrt{5})^n+(1+\sqrt{5})^n}{2} （flag*5）

当场把 n=2 带进去就不对，于是就懵了，开始推公式

有模有样的设了两个未知数，方程列不出来

然后我就试图找循环节

随便写了一个，发现输出非常不友好，感觉循环节似乎没什么规律（flag*6）

就开始找 m 是质数的时候的规律，找了半天发现基本都是一个数开始往下减 m/2 ，还不知道上下取整，但似乎那个数都在 m 以内，观察大样例也是这样（flag*7）

试图凭借我找规律带师的水平死推，推不出来

这个时候已经 10:30

权衡再三决定去写 T2

枚举问号显然是 O(2^t*|E|) 的，绝对要炸

然后就一直很懵逼，有暴力做法但一直不敢写

直到我发现了 m\le 10，m 代表数组数量

于是开始 rush 没有问号的部分分，一看有 65pts，我说我赚翻了

一开始忘了表达式用栈怎么计算，推了一遍

于是开始预处理 O(nm^2)，计算 O(|E|) 乱写

发现假了，于是去了预处理，直接计算 O(n·|E|)，这样只有 50pts，但差不多够

然后写完，过了我手造的小样例，却一直过不掉下发的样例2

由于极其不信任 Dev-C++ 的调试，手动调试

一开始是发现我内外层循环变量都用的 i，这种初学者的错误我还在犯，也是醉了

然后还是不对，一直手动追踪到 i=18 时发现我的 s[1].x 莫名其妙的被改了？

我并没有改变他的值啊？

直到我发现 std::pair<ll*,int>s[N];

第一维开的是指针，我为了好写用了个 std::pair，赋值的时候还装逼用的指针，导致一系列没有解引用之类的事，导致我改变了它指向的那个数组

于是改用了结构体，还好过了

已经 11:50 了

然后返回去看 T1

一直认为前面不能 DFS 去搞，因为有环，BFS 又不知道如何方便的处理括号序列，就瞄向了 m\le n-1 的部分分

以为这是一棵树（flag*8）

然后一开始一直在想怎么做，有一个 O(n^3) 的 zz 做法，但他没给

然后我发现这个做法如果树均匀的话是期望 O(n^2\log n) 的

最后发现我太 naive 了，直接每个点做一遍 DFS 就 O(n^2) 解决了

然后注意到图可能不连通，以为这就是多颗无根树（flag*9）

于是根据 CCF 的广告，加边加边加边，并查集查询！(flag*10)

于是我发现我都队每个点 DFS 了为什么还要并查集 (flag*11)

于是写了一个 O(n^2) 跑路

返回去 T3，决定写 O(nm) 的 20pts

一直在犹豫循环到 10000 还是 m ，最后折中了一下写的 5m（flag*12）

rush 完了，以为自己有 12+50+20=82 \ pts，这么个分感觉在 WC 还不错，就没打算再要（flag*13）

放在虚拟机下测了一遍，T1，T3 倒是没什么问题，但 T2 一直 Segmentation fault

13：15，很慌

一直发现不了我哪错了，最后在 NOI Linux 下的 Guide 调试了一发才发现自己一个函数在表达式结尾会一直增长

好你个 Windows，这都不 RE ?

慌忙改了过来，想起自己冬眠营还没标准结局，于是马上开了一个扫雷

删了多余文件，收卷了

出来电子科大发了一个纪念提兜可还行

感觉 5h 不过如此

出来听大家讨论，发现很多看起来初一初二的都比我分高

而且人均会 T1 暴力 32pts

非常不爽，出来后又到处乱晃，发现大家说暴力拿满有 102 \ or\ 122 \ pts

于是一路自闭

在车上查了一下斐波那契通项公式，长这样： f_n=\dfrac{(\frac{1+\sqrt5}{2})^n+(\frac{1-\sqrt5}{2})^n}{\sqrt5}

感觉我只差一点···

中途看到有直播讲题，窜进去发现 T1 讲完了，T2 讲了一大半

突然讨论区有人问会不会有空括号？

ctmd，()()((0))<(0)(()) 送我见祖宗

现在 T2 没了

T3 一开始放 PPT 我就知道我判断错了

发现我验证的时候只循环到了 m

开了 5m 岌岌可危

而且发现 40 pts 非常好做，移项逆元即可。

最后又翻洛谷，看到讨论区里面有人问 T1 m\le n-1 图连不连通

发现不连通时可以是一个类似于 DAG 的东西

恐怕只有我一个人想到了图不连通还把它当成多颗无根树来做的吧

然后有人告诉我 T1 就是类似于 加边加边加边，并查集查询！

至此，T1,T2,T3，全部挂翻

估分 [0,16]+[0,50]+[0,20]=[0,86]

人没了，\texttt{Cu} 无望

\texttt{Day 6}

上午的国家队答辩一如既往的选了前四名

还有 dzd 提的问题都好刁钻啊

下午出分了

感谢 CCF 不杀之恩

T1 就是树

T2 没有多余括号，但是还是少了 15pts

T3 循环节 5m 错误的通过了 20pts

菜是原罪。

OI 果然还是要多练题，多复习

这次考场上太 zz 了， 3h 可以做完的工作量用了 5h，还是太久没碰的原因

学而时习之，不亦说乎？