CSP-S 2024 游记

· · 生活·游记

做高铁去南京，车上写了两道简单数数题。

中午一直在水群，希望考场上别睡觉。

到考场发现我对面是续期文，虽然他不认识我，是不是该来点运气加成！

旁边是一个五年级老哥，而且上个赛季也参赛了，羡慕能打8年oi。

T1简单贪心，肯定是从小往大进行操作，堆模拟即可。

T2硬套了一个物理背景，第一问是容易的。

第二问转化为：给你若干区间，取尽可能少的点，使得每个区间至少有一个点被选中。

按照右端点排序，每次选右端点贪心即可。

T3把整个序列划分为若干连续的01段，已经是经典的不能再经典的dp模型了。

设 f(i, 0) 表示钦定 i 染成 0 的答案，显然是枚举包含 i 的连续段左端点，从某个 f(j, 1) 转移。

问题在于 $j + 1$ 的贡献，我们并不知道上一个 $0$ 在哪个位置。 不妨讲 $i + 1$ 的贡献提前计算，即设 $f(i, 0)$ 表示钦定 $i$ 是 $0$，$i + 1$ 是 $1$，$[1, i + 1]$ 的答案。 那么：$f(i, 0) =\left[a_{i + 1} = a_j\right] \times a_{i + 1} + f(j, 1) + s_i - s_{j + 1}$，其中 $s_i = \sum_{j = 2}^i a_j \times [a_j = a_{j - 1}]$。 经典把 $i, j$ 贡献拆开，要做的只有全局max，单点修，单点查，一个数组即可做到线性。 T4读懂题意花了一年，没有爆搜外的任何想法，此时只剩40分钟了，10分暴力保命。 预估分数 $100 + 100 + 100 + 10 = 310$，希望大样例够强。 还有，表扬nfls的机子，比我本机还快。 *** 竞赛生涯的第二场csp，也是最后一场，算是发挥了正常水平吧，唯一遗憾在于t4没多冲点部分分。 去群里一看，大家都是360+，磕头了。听说WC只取全省前50，最后一年，到底能不能去一次现场。 今年代码有加密，但是noi2020rk51 + 前几天ccsp铜首只花一个晚上就把江苏的爆破出来了，非常牛。 问兔子要到了自己的代码，洛谷一测，怎么有328的。 我好像把性质A拿满了，再看一眼题面，这个A不就是暴搜吗！只不过多组询问要记忆化。 暴毙了，没写记忆化，官方数据应该还是10分。不懂这一档分出出来的意义是什么，考选手会不会记忆化吗！ 现在只剩noip，以及去jsoi走下过场。最后了，希望能有突破。