2024“钉耙编程”中国大学生算法设计超级联赛（4）

Claris Round, Random Round

我不敢苟同你的观点，我个人认为这个BOSS的血条就应该有很多层，因为这个矩阵的周期，它很容易会直接影响到最优K子段，你知道吧。你往里砸的时候，一瞬间它就会产生大量的魔法卡牌，俗称找环，会严重影响寻找宝藏，甚至对这个序列以及更新都会造成一定的核污染，你知道吧，啊？再者说，根据这个勾股定理，你可以很容易地推断出人工饲养的​黑白边游戏它是可以捕获野生的超维攻坚的，所以说这个这个这个这个，你不管昵称检索的切面是否具有放射性啊，分组的n次方是否含有沉淀物，都不影响这个P跟E会延时操控汇合。

Problems	AC
7469. 超维攻坚
7470. 黑白边游戏
7471. 最优 K 子段	⊕
7472. 分组
7473. 多层血条	○
7474. 延时操控	⊕
7475. 序列更新	⊕
7476. 魔法卡牌
7477. 昵称检索	○
7478. 矩阵的周期
7479. 找环
7480. 寻找宝藏	待补

1003

二分答案，问题转化为判断能否划分出 k 个不相交子段使得每段长度都是质数且权值和至少为 mid。

从左往右贪心划分，维护一个 set，不断把前面的 {sum[j], j} 加入 set。假设当前在 i，如果此时 set 里面存在一个 j 满足 sum[i] - sum[j] >= mid && isPrime[i - j]，那么说明可以划出一个子段，清空 set。重复这个过程即可。

如何判断是否存在？按 sum[j] 从小到大遍历 set，在前若干个里面遇到一个 i - j 是质数就停了。根据质数的密度这样不会太多，是 log 级别的。总复杂度 O(n logn log ans)

1005

签到

1006

关键转化：由于己方和敌方之间不会互相成为障碍，可以 将 m - k，转化为一个两个人一起走路的问题，最后再让自己游走 k 步。

那么可以考虑一个 DP。需要记录的状态有 当前轮次，双方坐标，对方血量。

这样的话状态数是 n^4 * m * hp 的。无法通过。

这时候有个性质，因为双方是一起移动的，所以位置差不会改变。除非撞墙了，撞墙会让坐标差 +-1。

因此对方的坐标只要存因为撞墙产生的差值即可。m * n ^ 2 * hp ^ 3

1007

随机数据题，根号分治。

设 lim 为 b 中第 x 大元素，对于每次操作，考虑以下两种维护手法:

• 找到 a 中所有值小于等于 lim 的下标 i，用 b 更新
• 找到在 b 中所有大于 lim 的下标 i，用它更新 a。复杂度 O(x)

由于更新的复杂度是 O(1) 的，对于操作二而言，有 x 个需要更新的，所以是 O(x)。

那么对于操作 1 我们的复杂度是多少呢？由于数据随机，考虑计算 a 中一个位置期望需要经历多少次第一类操作，它的值才会大于 lim。假设经历了 i 次操作仍然小于等于 lim，那么就是说 i + 1 个随机数均不超过 lim，概率就是 (1 - x/n)^(i + 1)。所以期望操作次数就是:

$$
\sum_{i \geq 0}\left(1-\frac{x}{n}\right)^{i+1} \approx \frac{1}{\frac{x}{n}}=\frac{n}{x}
$$

所以期望的时间复杂度就是 $O(q(\frac{n}{x} + x))$，其中 $\frac{n}{x} + x \ge 2\sqrt{n}$，当 $x = \sqrt{n}$ 时取得边界。

1009 字符串

稍微有点实现细节的签到。