9.21

初赛，两场都报了。

上午四十多分钟写完了，除了格雷码觉得自己都会了。

相当放松，最后半个小时推了一道高数大题（？

估分 98。

中午和教练吹，说自己只有一题不会，教练突然炸出名句

你会的又不一定拿到分。

实际阅读程序挂一堆，92.5，不稳过。

下午选择很普通，一到阅读程序就不对劲了。

手推哈希？？

还好完善程序没挂，场上估分 70 左右，实际 66.5。

出考场怎么全都在骂啊。

10.26

前一天晚上十二点才睡，早上六点半被叫醒，开车狂奔一小时返校。困。

J

冷水洗脸后准时进场。

T1 set 存字符串，计个数用 52 减，秒了。用时 3min。

T2 循环模拟移动，开 bool vis 记录，用时 15min。

T3:？？？这么难？

想了一会后决定枚举答案的数，先想到 [1, n]，当然样例都过不去。

考虑权值。注意到每个数所需的木棍数量集合恰为 [2, 7]，从而长度为 l 的数所需木棍数量集合为 [2l, 7l]，于是得到最小长度为 \lceil \frac {n}{7} \rceil。

确定长度后，对于每一位从小到大枚举，如果一个最小的值填入该位使得剩余的木棍在其右侧的数位中有解则填入。

注意到第一位不能填 0，提到递归外面，顺便特判无解。差不多十点半过了。

差点多测没清空（

T4 更为困难，但想到每年这个位置都放 dp（？

数据范围 r \leq 10^2，极有特点。

考虑设 f_{r, c} 表示对于询问 (r, c) 解的情况。

然后容易发现不用 dp，直接压状态跑 bfs 即可。用 map 存储有解的询问。

具体来说，我们存储三元组 (x, y, d) 表示搜索到第 x 行第 y 个数，r = d 的状态。

转移考虑枚举每一个不在第 x 行但值与第 x 行第 y 个数相等的位置，用 d + 1 向该位置转移。

特别地，当 d > 10^2 时直接结束。

预处理将每一个值的位置用 map 套 vector 存下来。

时间复杂度是 r\sum l_i的线对，需要 10^7 过线对，但时限两秒，有概率。

实现过程中不知道 map 要求键具有比较运算符，然后对于三元组随便写了一个，然后一直挂，调不出。

最后十分钟认真写了一个比较运算符，一发过样例，11:56 通过。

11:59 比赛结束。出去一问一堆 300pts，赢麻了。

下午猛然想起 T4 多测没清空，但是位置存储的是 vector 的相对位置，且数据不超过 5 组，不会 WA 也不会MLE。

估分 400pts。大获全胜，中午吃饭的时候非常兴奋。

S

有点困，第一个进场。

T1 和去年一个风格简单，但是没有想到最简实现，排序后开小根堆依次压入，如果堆顶比当前数小就弹出。用时 5min。

先开了 T3，一眼 dp。设 f_{i, j} 表示前 i 子串，上一个红在 j 的答案。

不难发现上一个也是红时无法算出上一个蓝的位置，又不想打部分分，放弃。

考虑 T2，第一问二分秒了。

第二问想到最小点覆盖。

给定在一条直线上的若干线段，你要在该直线上放置若干个点，使得每条线段中（含端点）至少包含一个点，求最少点数。

一眼 dp，但是懒得想，于是随意胡贪心。大约三点时注意到答案不受线段关系影响。

只需要原先的起点仍然是一条线段的起点，原先的终点仍然是一条线段的终点，那么当前的答案与原来的答案必然相同。

（不保证正确）

考虑每一次出现终点时将其与之前最靠近的起点配对，如果有一条线段中不包含任何其他点，那么该条线段中必须存在一个点，计算一次贡献。反之该线段必然包含加在其他线段上的点，无须计算。

可以证明不存在起点和终点交错使得贡献被卡掉。

大概写到三点半，发现一个点同具有大量起点和重点非常难处理，尝试一会遂放弃贪心。

考虑 dp，先对所有线段按左端点第一关键字，右端点第二关键字升序排序。设 f_i 表示前 i 条线段的答案。

考虑找出在 i 之前与其首条不交的线段 j，显然二者不交是无法重复使用一个点的。所以从 j + 1 到 i - 1 选取最小的 f_k，最后加上该线段内的 1 贡献即可。

这似乎是有漏洞的，但考场上没办法了，直接打。使用一棵线段树维护不交的线段，另一棵维护 \{f_i\}。

写到五点多，线段树挂一堆，调到五点四十多过了前三个样例，最大一个样例跑了 1.3s，后面的有一些大样例第一问挂了（？

绝望了啊！

没得选了，直接关代码打 T3 暴力。大脑过于混乱导致除了正解之外直接想了 NP，没有想其他部分分，痛失大众分 65。

六点过了，开 T4，注意到 2^k 似乎很好打，而且真的有部分分。

小 S 希望你帮忙对于每个 c_i 求出，在只收到前 c_i 位选手的报名信息时，这个问题的答案是多少。

瞬间脑子炸了，以为 c_i 并不保证均为 2^k，破防。

实际上特殊性质 A 保证每一个 c_i 均为 2^k，似乎是可以打的。

最后二十分钟就是乱测 T2，然后随便修改，使我的代码最终能过尽量多样例。

结束了。

估分 100 + [0, 100] + 20 = [120, 220]。

结束了。

出考场了。

我对得起一个多星期的半停课吗？

回教室拿作业，和同学一起回家。

我好像睡着了。我什么都说不出。

巴山楚水凄凉地，二十三年弃置身。

怀旧空吟闻笛赋，到乡翻似烂柯人。

沉舟侧畔千帆过，病树前头万木春。

今日听君歌一曲，暂凭杯酒长精神。

11.4

晚自习后来到机房看成绩。

J

其实 T4 本来也假得不行了，不出意料。算是正常收尾吧。 ## S $100 + 0 + 20 + 0 = 120$。 T2 提交到洛谷 CE。排查后发现 `upper_bound(p + 1, p + m + 1, d[i] + mov) - p - 1` 返回的是一个类型为 `long int` 的东西（`p` 为 `int*`，`d[i]` 为 `int`，`mov` 为 `long long`），在 Windows 下被 `min` 视作和 `long long` 为同一类型，但 Linux 不将二者视为同一类型，从而在 `min(long long int, long int)` 中 CE。 强转 `int`，得到 60pts，剩余 WA。 11.6 发现第一问二分中将速度等于 $V$ 的部分情况也判为超速，修改取整方向后 AC。 原来我的做法是对的！ 甚至去掉维护 $f_i$ 的线段树后直接线性转移仍然具有正确性。 我可以在赛时想到一个至少蓝色的 trick！ 我从来不知道自己这样厉害！ 但是，得分是多少呢？ 想到了又有什么用呢？ 我从来不知道自己这样愚蠢！ 我的大脑空白了。椅子向后倒去了。我狠狠地摔在了地上。 我狠狠地摔在了地上。 我不再有笑容了。期中考和这样的挂分一同羞辱着我。 结束了。 我曾经以为，四个小时是那么长。 我曾经以为，挂分再正常不过，不必有情绪波动。 我曾经以为，OI 不是众人口中的残酷，而是想到了做法就能得到分。 我曾经以为，会被一次失败击倒的人是那样的脆弱。 我曾经以为，主动结束自己的人是那样的愚蠢。 我曾经以为，我可以轻松做到她说的“为自己的热爱奋斗终生”。 我曾经以为，情感不能改变我分毫。 我曾经以为…… 我曾经以为，我会赢。 > 潭中鱼可百许头，皆若空游无所依。