Rating-=27

挂分挂得最“爽”的一次。

T1 可是啊

本题思路小总结：

• 注意到两人吃瓜数量形成等差序列，那么我们不妨设两人最后一次吃瓜的数量为 $x$，输入的西瓜总数为 $y$。
• 我们利用等差数列公式求出 $x$ 与 $y$ 之间的关系，可以得到：对于先手阿瓦，$x=2\sqrt y-1$，再次通过等差数列公式，可以求得阿瓦能坚持的次数为 $\lfloor \frac{x}{2} \rfloor$，进一步可以求出这个次数与 $y$ 的关系；对于后手烤乐滋，$x=\sqrt {4y+1}-1$，进而求出次数与 $y$ 的关系。

100pts（实际得分100pts）

T2 世界线交汇

本题思路小总结：

• 注意到这是一道给了递推式只需要加记忆化的签到题（挂分除外）

然后这题就做完了

100pts（实际得分120pts）

T3 终究是一场梦

这题挺应景的。

本题思路小总结（。？）：

• 注意到本题的循环右移操作其实等价于将任意一个数向前移动
• 那么我们只需要把前 $k$ 小的数移到前面就可以了。。。

吗？

55pts（实际得分82.5pts）

没错，蒟蒻的分就是这么挂的。（也太轻敌了吧啊喂）

也不知道自己怎么想的，居然能把T3的思路想成签到题的难度，自己也没觉得有什么不对劲。

唉，终究是一场梦~

那么，本题的正确做法是怎样的呢？

本题贪心思路小总结（这次是真的）：

• 我们定义一个指针 $head$ 指向原数组中第一个还没有被纠正过位置的数，并定义一个答案序列 $ans$，再定义一个数组 $pos$ 存储每个数字在数组中的位置。
• 遍历所有数 $1\dots n$（注意不是下标，而是值），每遍历一个数，将其加入答案序列，标记为已纠正位置（用bool桶维护），分两种情况讨论：当 $head$ 指向当前的数（即 $pos[i]=head$ ）时，我们 ++head 直到其指向下一个未被纠正的数；反之不移动 $head$ ，并 -k ，等价于用一次操作将此数移到序列的前面。
• 最后将数组中未被纠正的所有数依次加入答案序列，输出答案序列。

订正

T4 大家会再次相遇吗

这题没挂分。

但是呢不知道如何判断大数是否为 $2$ 的幂次，便打了个暴力。

15pts（实际得分30pts）

本题思路小总结：

• 将 $2$ 的非负整数幂按十进制长度分为两类：长度 $\le 19$（即 $2^0 \sim 2^{63}$）和长度 $\ge 20$（即 $2^{64} \sim 2^K$，$K\approx 3.32\times 10^6$，保证位数不超过 $10^6$）。
• 短模式使用 AC 自动机构建 Trie，插入所有短 $2$ 的幂的十进制串，并统计文本中所有出现次数（自动处理重叠且无需关心前导零）。
• 长模式数量极多，不能建自动机；预处理所有长 $2$ 的幂的十进制串的模 $998244353$ 哈希值和长度，用自定义开链哈希表存储（键为哈希值，值含长度和完整哈希）。
• 对每个文本子串，若长度 $\ge 20$，计算其哈希，在哈希表中查找是否存在相同长度和哈希的 $2$ 的幂，同时检查该子串最高位不为 $0$（排除前导零），若匹配则答案加 $1$。
• 两部分计数相加即为最终答案，总复杂度 $O(\sum n + K)$，满足 $\sum n \le 2\times 10^6$ 的数据范围。

订正

T5 大家仍会记得我吗

没错。

本蒟蒻又挂分了。

因为二进制优化不会多个容量，单调队列优化不熟，于是写了个枚举物品数量的多重背包暴力，按道理来说是能拿到 $c=1$ 的情况的15分的，并且运气好还能再拿一点分。

诶 您猜怎么着

0pts（实际得分0pts）

那么为什么会光荣地拿到0分呢

以上是我枚举物品数量时写的循环代码。

对，你没看错，本蒟蒻并没有枚举物品数量为 $0$ 的情况。

于是就挂分了QAQ

本题思路小总结：

• 每种牌视为多重背包，但周期奖励 $b_i$ 只在凑满 $l_i$ 张时触发，不能简单拆分。
• 设总张数 $c$，完整周期 $q=\lfloor \frac c l \rfloor$，余数 $r=c\bmod l$。若直接拆分完整周期包和剩余单张，会导致剩余部分可组合出超过 $r$ 张，破坏约束。
• 修正：保留一个完整周期，令周期数为 $q-1$（若 $q\ge1$），剩余张数 $y=l+r$。将前 $q-1$ 个完整周期二进制拆分做多重背包。
• 对剩余 $y$ 张牌，枚举取 $t$ 张（$0\le t\le y$），每种 $t$ 是互斥选项，用分组背包更新，只有 $t\ge l$ 时才加一次 $b$。
• 若 $c<l$，无周期奖励，直接二进制拆分单张。
• 零消耗牌直接累加伤害。
• 核心：剩余部分作为一组互斥项处理，避免超周期组合。

订正

T6 早安。

0pts（实际得分0pts）

不知道啊，我写了个高精度暴力，结果交上去就全T了

赛后用评测样例测了一下发现实际好像是RE了。。。

本题思路小总结：

• 定义“好数”为十进制串 $x$ 中，子串 $n$ 出现的位置染蓝后，蓝色连续段数恰为 $k$。
• 对每个 $k\in[0,m]$，求 $[l,r]$ 内好数个数，容斥为 $F(R)-F(L-1)$，其中 $F(y)$ 统计 $[0,y]$ 的答案。
• 数位 DP 按位枚举，用 KMP 维护当前已匹配的子串 $n$ 的前缀长度 $ps$，状态为 $(lim, lead, cnt, bk, pos, ps)$。
• $lim$ 表示是否受上界限制，$lead$ 表示前导零，$cnt$ 为当前蓝色段数，$bk$ 为上一蓝色段末尾位置，$pos$ 为当前枚举位。
• 转移时枚举数字 $d$，更新 $ps$；若匹配到完整 $n$，则产生新蓝色段，若 $pos-1 \le bk$ 则连续，否则 $cnt$ 增加。
• 记忆化搜索，空间压缩为 $2\times2\times(m+1)\times(len_n+1)\times(len_y+1)\times(len_y+1)$，注意 $cnt$ 上限为 $m$。
• 最后输出 $m+1$ 个答案，对 $998244353$ 取模。

订正