10.8
上午
早读爽睡 30min，闭眼到机房。
然后发现有人打开了我的浏览器打开了duel点击了加入比赛点击了准备。
就是这场。
嗯。最近大家打 duel 的热情好像很高。那我也打吧。
于是绷不住开始打。
C cf1849C
完美的降智题。
用于攻击：“对于简单的题，想出来对的做法就磕，而不是再思考出符合此题难度评级的方法” 的选手。
于是我被攻击 1h+。
题意：给你一个01串，\(m\) 次操作，每次排序区间 \([l, r]\)，操作不延续。求 \(m\) 个操作得到的串中有多少个不同串。
由于操作不延续，容易想到哈希。
那么问题来了，如何去哈希。
正常的想法是直接做普通的字符串哈希，预处理 全0/全1 串的哈希值即可。
而我考虑将每一个连续的0/1段刻画为 \({len, 0/1}\)，对其进行哈希。
并且将这个方法写出来了。其中包含巨量分讨和细节。我大喊一声这题他妈是绿，并且获得 300pts。中午才发现我降智了。
这题写到这里结。
其实我赛时只做了这个题，而 hwl 把 F 切了。于是拿到抢 D 局面。最后残念败北。
有点对不起他（？）正常做的话应该是能在对面之前拿到 B 直接胜利吃分的。
duel 到 11：15，教练发现上午一个人都没在作业订正里交题。
下午
对短时赛的厌恶超过了对 oi 赛制坐牢的慌张。
——来自实时评测赛制苦手。
本场比赛的成绩表很分段。题目难度也很分段。
A
观察数据范围得到：使用 floyd 预处理 \(dis\) 后，无脑状压 dp。
手速题，据大手子描述，他在没看范围卡了一万年后写出代码并提交，并且拿到首 A。约比我快半分钟。
这里我们可以发现，在想出简单题目的方法后，我的实现并不是很慢。
第一题如此绷不住，我想象这场大概是周赛难度，而后被惩治。
C
lyy 开场做 C，飞速拿到首 A，于是猜测 C 题可做。
哦对，我在可以看榜的比赛中一般严格按照 lyy 做题顺序思考。
这个策略于我：约有 \(70%\) 的概率拿到同样的 AC 数，并有 \(100%\) 的概率在最后因为所花时间过多暴力没想出来拿不满而在总分落败。
执行这个策略时，明显感觉到思考速度差距。/dk
看看这个题，在原图上权值存在二进制包含关系的点之间连单向边，求单源最短路。所有边权为 \(1\)。
基本的思路是求出原图上的最短路后，考虑将新的边加入后对最短路作出修改。
由于权值的值域为 \([0, 2^20]\)。于是考虑将权值相同的点划作一块。
那么不在原图上的边现在就是块与块之间的。
块与块之间的连边比较好处理。
将二进制包含的条件转化为将 块\(i\) 与 块“\(i\) 在二进制下扣掉一位 \(1\)” 连边。
这玩意应该只要从大往小跑类似高维后缀和的东西就可以维护。
由于块内部可以到达。记块内最小值 \(f[i] = min{dis[v]}\)。
则对于所有 \(v\)，满足 \(w[v] = i\) 时：\(dis[v] = min(dis[v], f[i] + 1)\)。
可是这样子写出来是错的。
以为是哪里写挂了，还真看出来几个不太关紧要的错误。
实际上：我们没有考虑在 \(dis[v]\) 被 \(f[i]\) 刷新后，原图上 \(v\) 连出的边造成的对其他块的刷新。
这个东西就是较为正常的松弛操作，使用 dijk 维护即可 AC。
实际写出来的 dij 分两个部分分别松弛，即”包含关系的边“与”原图上的边“。
这么一看好像很符合逻辑。可是一开始就是想不完全。
观察提交记录得，本题从开题到 AC 使用了 1h。
其间许多人 AC 了本题和 B 题，压力不断增加。
通过此题后向隔壁的人询问我是否可以根据十一次提交获得顽强拼搏奖。
此时他还没 AC，向我展示了 \(11\) 次 WA 的记录，声称奖怎么也是他的。
我询问：你如何断定你能在最后通过此题。
他回答：肯定会的。
我觉得我缺少这个心态。
B
题意转化后发现是有顺序依赖的 01 背包。
具体来说，选择一个物品的贡献与在第几位选有关。
由于估计题目难度不高。一开始考虑贪心的规定一个顺序。尝试了好几种发现都不太对。
于是考虑什么样的 dp 状态能维护这个顺序的限制，发现完全做不到。
当场破防。
然后才想起来尝试发现性质了。
注意到由于时间限制，选择物品可以看作统计一个排列的有效贡献。
又发现，最优的答案中，肯定是这个排列的一个前缀有贡献。
因为如果中间有无贡献的位置，将后面有贡献的移过来一定更优。
然后发现，当有贡献的集合确定时，按照 \(q[i]\) 排序一定不劣。
因为这个前缀最后一位的贡献时间是 \(\sum p[i] + q[i]\)。
所以最后还是按照 \(q\) 决定顺序后 dp。
本场比赛让我明显发现。我思考较为简单的题目，速度还是较慢。
体现在 noip 中，则表现为留给我打暴力的时间极大变少。
感觉这对一等是比较大的阻碍。
要考虑在剩下的时间锻炼这种能力了。为什么有些人一下就能走向对的思考方向呢？
要减少思考过程中的掉头。
关于如何锻炼，要不打打 \(2000\) 分左右的duel？