NOIP-2021（SC）游记

Day -1

2021.11.18 早上七点半到学校，统一模拟考了套组合题，听说是信心赛

T1 Luogu P5837 一眼看去费用流，30分钟码完过了小样例，一测大样例WA了，稍微改了改就过了，但是一直感觉不对劲，没怎么想就去做T2了

T2 Luogu P5836 简单的树上LCA，先dfs一遍求两种奶牛出现次数从根节点开始的前缀和，然后每次询问用两个询问节点的前缀和加起来再减去两倍LCA的父节点的前缀和，看有没有询问的奶牛出现就行了，码了40多分钟才码完，倍增求LCA一开始写挂了，有点慢

T3 Luogu P5838 T2的加强版，奶牛种类从 \(2\) 种增加到了 \(n\) 种，继续T2做法肯定要MLE+TLE，去厕所冷静了一下，发现维护前缀和可以主席树优化，每个节点插入和空间都是 \(\log n\) 的，每次dfs到一个节点就从它父节点的版本上更新然后创建一个新节点就行

在T2代码上面改没花多久就码完了，准备调试的时候发现我新建了一个cpp然后在T2代码上改了而且保存了！我T2代码没了，不过不慌，T2是T3弱化版，用T3代码也能过，不过还好没有关闭过IDE，反复Ctrl+Z代码又回来了，试了试样例WA飞了，调了一下发现原来是统计答案的地方错了，T2T3全都是错的（T2水大样例害人不浅），不过还好问题不大，改了一点点就对了，又看了一遍感觉没什么问题就去做T4了，还剩大概一个小时

T4 AtCoder ARC-069 D 一看完全不会没有思路，想码个 \(\Theta(n\log n\cdot2^n)\) 暴力，结果一看部分分 \(n\le100\)，乱写了个贪心然后特判了一下 \(n\le20\) 的时候用暴力就放掉了

考完了同机房神犇们说T4是2-SAT，但是我完全不知道什么是2-SAT，又被吊锤了，T1事后立马发现算法错的，就一个简单的Dij跑个最短路就完了，问了一圈疑似所有人都A了就我没A，期望得分： \(0+100+100+0=200\)

实际得分：\(30+100+100+23=253\)

T2T3没挂分很满意，T1假算法还是A了3个点，最震惊的是T4这个贪心居然过了6个点，不得不说数据有点过水

下午把T1改了，学了下2-SAT，感觉真是个神奇的算法，就是像 \(\text{Tarjan}\) 一开始不好理解，晚上做了两道2-SAT的板子题，又练了一下一堆基础板子，然后就是教练一直在说考前注意事项了，之前还没发现，现在突然感觉好紧张，停课了这么久，希望能有个好结果吧……

Day 0

2021.11.19 考前最后一天，机房里的神犇都在卷各种板子，然而我发现甚至好几个板子我都从来没写过，什么AC自动机之类的，火速爬去卷了一上午各种板子，下午去考场试了试机，就在本校考非常舒适，教练在说恢复文化课的事情了（暗示考完立马退役），文化课落下了好多，一想到要补就好烦

明天就考了，祝所有OIer NOIP2021rp++

Day 1

(Waiting for updating)