NOI 2021 同步赛 游记
SSerxhs
·
·
个人记录
upd:
退役选手瞎划水（）
Day 0
下黄了，乐了
Day 1
CCF 日常咕，咕到 10: 00 才开考。
A 看了看没啥思路，感觉要维护一个毛毛虫类似物，但不会这个。
想了半天用子节点维护边是否轻重的做法，发现完全不懂，开 B。
B 题意很长，看完感觉完全不会，一点思路都没有，又去开了 C。
C 给了一个 x\to z\land y\to z\Rightarrow x\to y\lor y\to x，以为 \to 在描述连边，联想到之前看到这个性质也没推出啥结论，就没往这方面想。看了下部分分感觉可以写写，就开始写树的部分分。由于并没有看出是外向树，写了大量分类讨论才做完 k=0，但这个部分分并没有样例。当天还有牛客多校，准备弃赛跑路。
后来队友决定咕掉牛客，我看了下时间还多，接着写 k=1。感觉分类讨论很麻烦，就写了个树剖暴力覆盖，调了半天才调过大样例，艰难拿到 8 分，此时 100min。然后再看 n 小的情况，发现是个 tarjan，但 O(mq) 说不定会 T，想了想可以用 bitset 暴力维护可达性，优化到 O(\dfrac{nq+nm}w+n^2)。写了写发现 k=2 又是一个大分类，但由于没有 k\le 1 的部分分，只能硬着头皮写完调过样例，此时 137 min，+28。
先想了想 B $k=2$ 的部分分，就是问逆序对数是偶数和奇数的排列方案数的差值，忘了不是完全图交了一发读入 + `cout<<(int)(n==1)<<endl;`，想了想发现不对，并不是所有匹配都是合法的。模拟了一下爆搜的过程发现是一个行列式求值，先写了直接求行列式的分交了一发，+35。看了下特殊性质 A，发现可以分别求再乘起来，改了改再交了一发，+40。
转回去看 A，写了写 A 的暴力交了一发，+30。再回去想 B，非常自然地想到把矩阵相乘，想了想发现是对的，但是输入格式太麻烦导致写了很久才调过大样例，+25。最后只剩大约 30min，写了 A 的链分，调了调 B 矩阵乘法的枚举顺序。
洛谷得分：$60+85+44=189$，B 数组开 $100$ WA 了。
### Day 2
CCF 继续咕到 9: 00。
读了读 A，感觉和之前一道 GDOI 题很像，很快确定每 $16$ 位做一次的思路，但是实现得略有些麻烦，60min 才调过大样例，+100。接下来通读了 BC，感觉还是 B 可做，去看了看 B。
B 题看题面就感觉要维护矩阵，一开始设向量 $\begin{pmatrix} x&\frac 1x\end{pmatrix}$ 发现并不是线性变换，疑惑了一会为什么会有分数输出，发现分母可能是 $998244353$ 的倍数，进而想到真正的向量是 $\begin{pmatrix} x&y\end{pmatrix}$，算了下发现很快写出线性变换，感觉合理，看了看 `W` 操作发现是个更合理的矩阵，再看看 `E` 感觉分类讨论极其不合理，而且居然没部分分，肯定不是难点，算了下发现分类是假的，只有一边有用，也写成了矩阵，发现这两个矩阵甚至互为转置，只需要维护两个连乘。写了个线段树上去发现过不了样例，然后一调发现矩阵求错了，乘法顺序反了。按正确的顺序重新算了一下，矩阵不再互为转置了，仔细算了算感觉合理，就要维护 $4$ 个信息了，改了改过了只有 `APPEND` 的点。先交了一发然后开始写 splay，基本上把线段树的内容复制进去就差不多了。很快调过了全部样例，交了一发，此时只剩 45min 了，但 +100 感觉很稳。
C 还是没啥思路，先写了写 $n=m=1$，然后搞了下无 `R` 的，不过事后证明是错的。$m=1$ 的情况写了特判 + $3^n$，这时大概只剩 10min。突然发现 $3^n$ 完全不合理，但没空想了，只能给 $n\le 8$ 写了个 $O(3^nn\log n)$ 的完全暴力，压线交了上去。
洛谷得分：$100+100+12=212$，总分 $401$，似乎压线金了？
真分数等 CCF 公布吧。