第一次线下参加 noiwc，好耶。
1.13
下午从 YT 飞 HZ，天黑得好快。打车到了 SX，入住酒店，点了份外卖，洗洗睡。
1.14
上午起床，吃早饭，出发去学校，开营仪式。大型开盒现场？看到了好多大佬，膜拜。
中午食堂过于抽象了，打个饭排这么长队，饭菜质量也一般。
午休。进考场，试机题目一个是上次 pkuwc 的签到题，一个是经典题元旦激光炮。第一题忘了咋做了，只写了第二题交互。OpenJudge 还是很感人啊。
考前十分钟默写多项式板子，结果 NTT 写错了死活看不出来错。
开始考试。还是要有自信的。必须得秒个题！"军八变军七"
开题。怎么有博弈？？是人能做的？？？还一个数据结构，自闭了啊！
还是开 T1 吧，毕竟输入俩数输出一个数的题还是较为容易的。
这个题目条件必须要转化，我得构造一个最劣的情况？注意到和最大独立集十分相关，然后咋做呢？会了 a>b+1 的情况，两两配对就好了。多个的时候希望用最少的边让 mis 很小，应该咋办呢？猜了个大概是一堆团的形状，就可以 dp 了。
不过朴素 dp 是三方的。不难猜到结论：最大的数减最小的数不超过 1，因此我 dp 的时候只需要枚举加所有不超过 i/j 的情况就好了。复杂度 n^2log。
在 0:11 过了 T1。感觉 T3 根本不可做，先把 T2 过了再说。但是一点思路没有啊？？？
有点 noip t4 的感觉。有个启发式合并+点边容斥的想法，可是感觉还是不可做啊？？？
可是没有其它想法，顺着这个想吧。不知何时想到了长剖，但是还没啥用啊？终于意识到了，(u,x) 和 (fa[u],x+1) 高度相似！！！因此把 x 也当作一维，似乎就可以拆成 O(n) 个立方体加？复杂度 (n+q)log^2？？？感觉很对啊，长剖这么牛的吗，开写。
写着写着发现假了。。。。。合并是集合合并，不是单点，完全没法优化。只能把区间个数改成 nlogn，复杂度就 nlog3n+qlog2？？？？？感觉完全不可过啊。
继续思考，无果。只能写这个了，碰碰运气。
后来写完了，慢慢优化成三维偏序。提交，41 分。。。
再咋卡常呢？发现排序很多余，改成了归并，对就是那个一堆 pair
尝试按题意写一个暴力 dp。感觉 3000 显然是给 bitset 优化 dp 的。感觉可以 f[i][j][0/1]？？？哦不对，想了一会，发现只要 f[i][j] 表示先手怎样就完了。然后转移也不难，一堆 bitset and。在 1h56min 拿到了 20pts。
之后咋办啊。感觉做不动了。AB 性质似乎还没那么难？好像对刚才那个 dp 换个维度基本就好了，然后一个点的转移完全包含它后继点的。因此分别记录奇数和偶数最优解就完了。状态数线性，转移也不难。在 2h15min 拿到了 50pts。
接下来自闭了。完全想不明白怎么去扩展这部分暴力。不过缩点肯定是要的，注意到一个 SCC 内的 dp 状态显然全相同。因此一起转移就完了？内部要特殊考虑下，从大到小排个序再类似转就好了。在 2h45min 左右拿到了 75 pts。感觉赢麻了，胜券在握？最后一部分分似乎套个二分就好了啊。
争取 3h 前 AK。结果发现要把一堆集合拼起来排序做，复杂度爆炸了啊？？？？先把这个暴力打完，删掉之前的 3000 暴力，分数没降。
试图分析这个 dp 过程的性质。一般来说，想法基本都是取极值的诈骗，因此尝试考虑最小值是否会被选。如果没选，那它 +1 一定被选了，以此类推，一个连续段基本是一体的。注意到最大只需要考虑到 min(f0[x],f1[x])-2，因此暴力基本可以打出来了。考虑每个连续段末尾点（t 选 t+1 不选），一直 -2 到前面位置，更新对应的 dp 值。可是 wa 了啊？？？
试图用之前写的对拍找错，但是拍不出来一点。改来改去，都过不了，交了好多发。争取改得更暴力写，发现还是过不了？？？？？？？这时候开始急了。
注意到一个小错，改掉了，暴力终于又对了。找连续段去转移，也没问题了？可是还是不会做啊。。。这东西只会平方，只找最小也只会二分+二分，俩 log 啊。
算了没多少时间了，果断猜结论。找一个最小的段，另一个奇偶性的不管了，这居然没 wa？？？不过 TLE。
改成二分+二分，咋还 TLE？？？我觉得这个常数并不大啊，所以哪里错了。没想出来，只能再去优化。
又上了个厕所，发现可以主席树。这时候只剩 30min 了，赶紧码。怎么又 wa 了？？？？
调不出来，想死。这时候都交了 20 发了可能。改成暴力，还是 wa，完全不知道自己改哪里就寄了啊。
瞎改，瞎交。终于找到了错，没取 min。信心满满去交，准备迎来 AK，结果当头一棒——超时。
只有十五分钟。奇迹能否出现？尝试卡常，把 vector 改成了只保留一个数。CE 了。这很重要，因为我发现还有一个地方是平方的忘优化了！！！
这部分咋做啊。好像是二分？赶紧把 vector 拆成了两个，分别二分去转移，可是还是 wa 啊。怎么第一个 sub 都 wa 了？
又改成了暴力，结果又 wa，交了一堆 assert，没区别。好像都二十五六发了，还是完全意识不到错误，咋办啊。。。
我去，发现了逆天错误，我按奇偶性分居然是按 b[i]%2 分的，我分了个寂寞？（应该按 i%2）
开心死了，终于找到问题了，再改，还过不去吗，不可能！交！（第 28 发）
很好，又双叒叕 wa 了。这时候已经绝望了。又 assert 了下，没区别。
这时候一定要冷静，时间也没那么缺了，最缺提交次数，只有三次机会了啊。终于发现，二分完完全全就是不需要的，我不取最小值取啥啊？
改完了，其实都不需要这些向量和二分，直接找最小转移就完了呗。交！
wa……这次一个 sub 都没过，哭麻了。
做个代码比对。欸，我是不是根本没判可行就转移了啊？改，再交！（第 31 发，只剩一次机会了）
哇偶，终于过掉了！！！3h53min。激动得拍了手。也是 pkuwc AK 选手了。
最后五分钟尝试调我的 ntt 板子，无果。
出考场开心死了，以至于都不愿意藏分了。老规矩，回去代码拍了照准备复写。直接说出了每题分数，可能会被卡常？
结果发现一车人 AK，吐。。。终于意识到，自己就一普通人，哪来的那么多唯一、特别。
不过还是很开心的。day2 加油！
标签：二分,暴力,wa,PKU,WC2025,感觉,改成,游记,dp From： https://www.cnblogs.com/maihe/p/18671843