PKUWC / NOIWC 2024
Sktn0089
·
·
个人记录
Day\space 0
直接跳到正文部分。
Day\space 1
早上开营仪式，下午测试。
13:00
测试开始。
看 t1，这是什么东西？神秘博弈论？
开头是 L 或结尾是 R 的可以直接排除，然后 RL 交替出现的序列也可以直接排除。
所以考虑所有连续段？把所有的连续段提出来之后，猜结论？是不是把连续段继续递归？
感觉很对但也不是很对的样子？不管了，先写吧。
写完以后发现所有结论均错误。这时有点慌了，先看 t2。
枚举完后，考虑每个位置的贡献，是方程组，可以高斯消元。
当我写完代码调试时……？？？？怎么还有自由元？？？好，写完 $11pts$ 暴搜跑路。
这时候很慌，$t1$ 都还没过，还是选择看 $t3$。
$h\le 4$ 时点数不超过 $16$，直接枚举点集然后做个 $sos dp$ 可以做到 $O(2^{2^h}h)$，每次询问同样枚举点集，有 $20pts$。
然后……不会了！重新看 $t1$，先写了区间 dp 和优化，可以做到 $O(n^2)$，然后呢？
发呆看 $t1$ 看到测试结束。
$73+11+20=104
甚至不如去年。
别人的分数都很高，130 到 160 不等。
输了。
Day\space 2
仍然看 t1。
可以证明 4 必须直接贪心和 1,2,3 分别匹配，但是 3？
忘了写了什么代码，发现 3 不能直接和 2 匹配，想象 1 很多的时候 3 要和 1 匹配。
所以？怎么那么多情况啊！！！
先写了个 dp，记录 1,2,3 个数，做到 O(n^3)。
然后思考如何处理。发现两个 1 一起匹配的时候相当于一个 2，那么我们可以把若干对 1 转化为 2，此时 1,2 只剩下两种匹配情况了。
那么很好处理，这是一个单峰函数，可以二分。
调试……二分出问题了？原来这不是严格单峰，相邻两个数可以一样。
那么三分是可以的。不对啊？直接枚举不就行了？？？
于是 t1 做了 2h。
$t3$ 是一个比较常规的数据结构？先看没有弹栈操作的部分分，考虑分块，然后每个位置和块维护压栈和弹栈，这空间不会爆？不敢写，写了个主席树，发现调不出来，寄了。
第三档是吉司机，很久没写过了，完全不会写。
$100+28+18=146
两天加起来刚好 250，自闭了。
别人都比我高 100 分。
Day \space 3
不知道是不是前几天的伙食问题，早上起来胸口很难受，吐了。
一天都不想吃饭，没胃口，头很晕，很难受。
明天就 wc 了，不知道怎么办。
Day\space 4
早上舒服了。
今天报道 + 开幕式，我比较社恐，听说是住宿，比较紧张。
第一次见到 cjh 大神，有点尴尬。听说他们三个之前与其见过很多次
下午看他们打球，和一名陌生的外省同志一起打了一会儿羽毛球。
晚上是开幕式，我永远忘不了那一幕元神。
启动！
宿舍阳台很小，跟一张小床一样大（真的。洗手池更小，都不知道这里的学生是如何经受如此虐待的。
晚上可以无限制筹集，很爽。
Day \space 5/6
上午听讲座，下午听讲座，讲座内容非常逆天。简单来说是坐牢。
晚上颓废。
Day\space 7
$t1$ 是正版签到，不知道出题人在想什么，历年来第一次出橙 $t1$，只要会 $01$ 背包就会做。
$t2$ 是一个区间数数题。
当我们确定了每个数的操作方式（取反/不取反）后，其实就能确定 $2L$ 的取值范围了，并且范围是一个开区间。
合法的条件是这个范围有解。
枚举左端点，往右边扫右端点，考虑 $\text{DP}$。设 $f[j,0/1]$ 表示第 $j$ 个位置不取反/取反时区间 $[i,j]$ 合法的最小的 $2L$，$g[j,0/1]$ 则为最大。
然后直接转移做到 $O(n^2)$。
已经有 $44pts$，尝试看 $t3$。
一开始想了个假做法，考虑直接树形 $dp$，设 $f[u,0/1/2]$ 表示点 $u$ 考虑子树后，不确定/不因父亲确定/因父亲确定的方案树。
然后过不了大样例，发现一个区间的和不一定必须知道其在线段树上的点的值，而是可以通过各种容斥求得。考虑容斥本质是前缀和相减，确定一个线段树上的点 $[l,r)$ 相当于把 $l,r$ 两点合并，计算满足有 $m$ 对点，每对点连通的方案数。
然后发现这个假做法其实就是特殊性质的做法。
正解看起来无从下手。
思考片刻后还是看回 $t2$。区间个数似乎可以双指针，但是难以 check，这个 dp 似乎能用矩阵乘法的形式表示？转移都是 chkmin 和 chkmax 的形式，考虑这种形式有什么特点。
如果一个数通过一系列 chkmin/chkmax，结果如何？设这些操作中 chkmin 的最小值为 $y$，chkmax 的最大值为 $x$，若 $x\le y$，那么最终的取值
$$
v_1= \begin{cases}
x & v_0<x \\
v_0 & x\le v_0\le y \\
y & v_0>y
\end{cases}
$$
若 $x>y$，那么最终取值唯一。用一个二元组 $(x,y)$ 表示这样的一个操作过程，若 $x\not =-1$ 则 $x,y$ 与上述含义相同；若 $x=-1$，则最终取值唯一，为 $y$。两个二元组可以合并，也可以取 $\min /\max$，因此直接用矩阵乘法优化就行。
双指针还要套一个线段树，不如直接分治，每次从 $mid$ 往两边扫，维护一边的矩阵乘积，然后双指针维护即可，$O(n\log n)$，常数比较大。
把 $\min /\max$ 宏优化后极限数据能跑 $1s$ 了。
看 $t3$，尝试写一下 $M=1$ 的做法。
分类讨论，根据区间内关键点数量 $0/1/2$ 来分别 dp，但是状态多，细节多，分讨量大，直接放弃。
剩下 $20min$ 基本发呆了。
下午看成绩，左边的 fxt 大神直接暴砍 $265pts$，orz。
$100+100+25=225$，应该……有银了吧？
实话说 $t3$ 这个部分分真的比较差，讲评说 $M=1$ 直接做，但具体仍然不知道如何 dp，然后说 $M\le 5$ 的时候状压就行。
但我仍然不知道怎么 dp。
考都考完了，可以放心颓废了！
乒乓打得挺爽，下次还要！
## $Day\space 8
坐牢。
想家了。
好想回佛山啊！