Travel「NOIP 2024 游记」
denominator · · 生活·游记
上一次：CSP 2024
游记全集
Day 0
考前还担心保龄。
Day 1
老规矩，code length：
| 题目名称 | edit |
assign |
traverse |
query |
|---|---|---|---|---|
| 码长（Bytes） |
默认 T1 是橙，开题后：怎么一点都不会啊？？？麻了麻了，不会真保龄吧。
- 第一眼：随便搞搞，但是怎么搞想得不完全；
- 第二眼：写个 dp？设
\text{dp}_{i,0/1,0/1} 表示交换[1,i] ，s_1 /s_2 的后缀是0 /1 ，测大样例，寄！！！差点怀疑大样例错了。（详细的在这里） - 第三眼：哦哦我寄了，可以从远处掉过来。随即想到一个贪心：将
s_1 与s_2 划分为若干能自由交换的区间，从前往后扫，能匹配即匹配。本来写一发只是图一乐，结果发现，莫名过了大样例！
当时想，T1 好难啊，我是不是过了 T1 就赢定了？
T2 开题，好水啊，怎么还 T1 > T2 的说？
- 第一眼：简单计数，看小样例秒之！有一个数被重复限制即为
0 ，否则相邻两数都有限制乘v^2-v+1 ，否则乘v^2 ，结果发现，过不了大样例 2 的一组测试点！怀疑大样例错了，测大样例 3，错得更多！ - 第二眼：发现忘记有连环限制了，最后过了大样例。
T3 开题，好水，随便推推性质应该就出来了。于是推不出性质。顺便数了下，题面有 5 页。
T4 开题，好水，一眼莫队，而且很板。但是我不会莫队啊啊啊，，，挂大分了！！1
- 第一眼：三维数点？莫队二次离线？（出考场发现不是）在代码中整了个活，开写
n,q\leq 5\times10^3 。 - 第二眼：一开始甚至写离线的
\mathcal O(n^2+nq) ，写时发现在线就可以了！！！也因此没写k=r-l+1 。
时间只有 1h，但是 T3 还是
- 链：纸上推了一下，发现答案全是
1 ，想着就这样不会有大样例了吧，结果发现有（（（，答案确实是全1 。（（（ - 菊花：发现简单计数，默认
n\gets n-1 ，答案是(n-2)!\left(k(n-k)+\dfrac{k(k-1)}{2}\right) ，结果没过样例 10！怀疑大样例错了，结果有一处没加 long long……加了就过了。（甚至特判n=2 ） -
- 边将树分裂为两部分，每部分以连上边的节点为根； - 答案是 $\prod\limits_{u\in T}f(\text{sons}_u)$，最初做时很 naive 地以为 $f(n)=\begin{cases}1&n=0\\n&\text{otherwise}\end{cases}$，但是因为图没清空，栈开多大都 RE，没测样例 3。 - 发现问题后，测样例 3，不过！
最后只有 3min 了！于是开始盲猜。
- 猜
f(n)=\begin{cases}1&n=0\\2&\text{otherwise}\end{cases} ，不过！ - 猜
f(n)=n! （其实是发现是），总算过了。手抖了。
场上咕分
（现在担心，整活真整出事来就完了
Day 6
出分啦出分啦，我来康康得了多少？