THUPC2025 游记

· · 生活·游记

\text{Day}\ -1

与 @jiazhichen844 和 @rsy_ 组队

经过讨论后确定了队名：\text{Milk Dragon Dream! It's MyGO!!}

突然发现最后一个叹号没显示出来（，寄

我真的能在患有痴呆症的情况下在 \text{THUPC} 中打出非负贡献吗？这真的可行吗？这真的能被完成吗？

\text{Day}\ 0

我们队下午三点半才开始打试机赛

看了一下排行榜，然后决定我开 \text{T1}，@jiazhichen844 开 \text{T2}，@rsy_ 开 \text{T4} 和 \text{T5}

然后看了一下 \text{T1}，发现是弱智扫描线，然后在 15:35:37 时过了，@rsy_ 大佬在 15:31:20 时过了 \text{T4}，15:45:30 时过了 \text{T5}

但是此时 @jiazhichen844 还不会 \text{T2}，于是我们队一起开始讨论 \text{T2}，

最好笑的是我大胆猜测 c 一定为 0 或 1，其他人都没发现样例有一个 c=3 的，而且我打了个暴力跑了几十组数据没跑出来 c=1 无解的情况，并对 c=3 的情况跑出了一组 c=1 的答案（

于是开 $\text{T3}$，首先对于快速求序列的值这部分通过原题机搜到了 [CF1975C](https://codeforces.com/problemset/problem/1975/C)，并打开题解发现答案是连续三个数的中位数最大值，且这个结论在这道题也可以用（直接看题解是因为我懒得想），然后考虑一个经典的 $\text{trick}$，在所有大于序列的值的位置统计他的贡献，对于计算序列的值小于 $val$ 的方案数，发现不能有两个大于等于 $val$ 的数距离小于 $2$，于是直接 $\text{DP}$，设 $f_{x,0/1/2}$，状态含义显然，转移就根据 $val$ 和当前区间的关系，分三种情况，然后随便转移 然后考虑怎么扩展到 $l_i$ 和 $r_i$ 都很大的情况，先把所有 $l_i$ 和 $r_i$ 放到一起排序，然后对于排序后相邻的两个数构成的左开右闭区间，这区间中的每个数的与 $n$ 个区间的关系都是相同的，也就是说答案为一个不超过 $n$ 次的多项式函数，我们要算这个多项式函数在一段区间中的和，这个和显然为一个不超过 $n+1$ 次的多项式函数，于是取 $1\sim n+2$ 时函数值的前缀和，直接拉格朗日插值即可，时间复杂度 $O(Tn^3)$，在 $18:22:42$ 时过掉了 $\text{T3}

赛后才发现我写的这个东西就是拉格朗日插值优化 \text{DP}，我在不知道拉格朗日插值优化 \text{DP} 的情况下自己把它造出来了/jy

四道题一发罚时都没有，惊讶

试机赛结束时一共有 11 个 \text{AK} 的，我们队 \text{rk}30，希望我第二天初赛也能发挥出这样的水平吧

\text{Day}\ 1

爆炸