模拟赛题解/2025.10.20 模拟赛

T1-染色（color）

题面

有一个长度为 $2n$ 的序列 $a$，你需要对这个序列进行染色。定义一种染色方案为，对于序列中的每个数赋一个大小在 $[−10^6,10^6]$ 范围内的值，且不能赋值为 $0$。

小 P 认为染色后 $a$ 序列价值为 $(a_1\times a_2)+(a_3\times a_4)+\dots+(a_{2n−1}\times a_{2n})$。小 Q 认为染色后 $a$ 序列价值为 $a_1\times(a_2+a_3)\times(a_4+a5)\times \dots\times(a_{2n−2}+a_{2n−1})\times a_{2n}$。

现在你需要找出一种染色方案，使得小 P 认为的价值和小 Q 认为的价值相等，并且不为 $0$，请你输出这样的一种染色方案。

可以证明，在本题给定的数据范围下，保证所有数据均存在一种染色方案。

形式化的，即你需要找到出一个长度为 $2n$ 的非零整数序列：$\sum^n_{i=1}a_{2i−1}a_{2i}=a_1a_{2n}\prod^n_{i=2} a_{2i−2}+a_{2i−1}\not=0$。

$2\leq n\leq 10^5$。

题解

考虑先钦定前 $2n-1$ 位，然后直接得出 $a_{2n}$ 的值。

注意到乘法会使值的增长速度很快，所以乘法要尽量 $\times1$，考虑用 $2$ 和 $-1$ 构造。

于是钦定 $a_1=1,\forall i\in[2,n],a_{2i-2}=-1,a_{2i-1}=2$，可得 $a_{2n}=2n-3$，一定有解。

T2-超速检测（detect）

题面

由于小 D 被大运创飞了，上司派小 P 重新设置检测点。

有 $n$ 辆大运，第 $i$ 辆大运从 $l_i$ 处进入国道，从 $r_i$ 处离开。

大运在行驶过程中，全程超速。小 P 想知道至少要设置多少个检测点，使得每辆大运都会被检测到超速。

具体地，在 $i$ 点放置一个检测点，可以检测经过 $(i,i+1)$ 区间的大运。

同时，小 P 不想被创飞，所以他也想知道所有的使得检测点最少的方案的数量，以备不时之需。你能帮帮他吗？

由于方案数过大，请输出对 $10^9+7$ 取模后的结果。

$1\leq T\leq 100,1\leq n,\sum n\leq 10^6,1\leq m\leq 10^9,1\leq l_i<r_i\leq m$。

题解

令 $f_i$ 表示强制选择第 $i$ 个点的最小值，$g_i$ 则表示方案数。发现前面如果有一个区间 $[l, r]$ 没有被 $i$ 覆盖则 $f_i = \min_{k=1}^{r} f_k + 1$。

上面这个 dp 显然是可以线段树优化的，时间复杂度 $O(n \log n)$，常数较大，期望得分 80 $\sim$ 100 分。

并且注意到 $f_i$ 单调不降，所以 $k = l$ 的时候一定最优，而这个 $l$ 可以通过单调队列维护，注意需要合并相同的 $f_i$ 用来统计方案数，时间复杂度 $O(n \log n)$。瓶颈在于排序，期望得分 100 分。

T3-决斗（duel）

题面

小 P 在和怪兽决斗，它们在一个 $n$ 个点，$m$ 条边的有向图上，小 P 在起点，怪兽在终点，小 P 要去打败怪兽。

小 P 相信玄学，所以他必须经过正好 $d$ 条边，再去打败怪兽。同时，小 P 在路途中，不能回到起点，也不能到达终点。

他想知道他有多少种去打败怪兽的方法，答案对 $z$ 取模。

$2\leq n\leq 100,0\leq m\leq n(n − 1),1\leq q\leq 5\times 10^5,2\leq z\leq 10^9,1\leq u_i,v_i\leq n,u_i\not=v_i,1\leq d_i\leq 50$。

题解

设 $f_{i,j,k}$ 表示从 $i$ 出发，恰好走 $k$ 条边，最终走到 $j$ 的方案数。$h_{i,j,k}$ 表示从 $i$ 出发，恰好走 $k$ 条边，最终走到 $j$ 且路径中间没有经过 $i, j$ 的方案数。$g_{i,j,k}$ 表示表示从 $i$ 出发，恰好走 $k$ 条边，最终走到 $i$ 且路径中间没有经过 $i, j$ 的方案数。

则有：

$$f_{i,j,k} = \sum_{(l,j) \in E} f_{i,l,k-1}$$ $$h_{i,j,k} = f_{i,j,k} - \sum_{d=1}^{k-1} (g_{i,j,d} \times f_{i,j,k-d} + h_{i,j,k} \times f_{j,j,k-d})$$ $$g_{i,j,k} = f_{i,i,k} - \sum_{d=1}^{k-1} (g_{i,j,d} \times f_{i,i,k-d} + h_{i,j,k} \times f_{j,i,k-d})$$

时间复杂度 $O(n^3 d + n^2 d^2 + q)$，期望得分 100 分。

T4-擂台游戏（arena）

题面

小 P 要举办一场擂台游戏，这个擂台上有 $n$ 个依次排列浮岛。开始时，小 P 会决定这些浮岛的沉浮状态。$0$ 表示浮，$1$ 表示沉。

游戏开始后，对于每一轮，选手可以选择两个相邻的浮岛使它们的状态全部变为浮。在选手选择结束后，小 P 可以选择任意三个浮岛使它们的状态全部变为沉。若浮岛数量不足三个，也可以选择小于三个浮岛使它们的状态全部变为沉。

当所有浮岛全部为沉时，选手就会掉进岩浆，游戏结束。

小 P 想知道，当双方都采取最优策略时，选手最多可以存活的轮数。

$1\leq T\leq 10,1\leq n\leq 10^6,1\leq \sum n\leq 3\times 10^6,a_i\in \{0,1\}$。

题解

算法一

由于所有的状态数只有 $2^n$ 种，所有可以直接记忆化所有状态，时间复杂度 $O(n^32n)$，期望得分 20 分。

算法二

特殊性质 A：这个时候，选手可以贪心地先选择所有编号为奇数的浮岛，这样小 P 每次只能消除一个 1；直到选手只能往 1 空隙中改变状态为止，时间复杂度为 $O(\sum n)$，拼上算法一期望得分 40 分。

算法三

考虑选手的每次将相邻浮岛的状态变为浮的过程，按照时间推移，这个过程形如：

• A 部分：若干次连续消除两个 1。
• B 部分：若干次消除一个 1。
• C 部分：若干次连续消除两个 1。

因为 A 部分和 C 部分每次都是后一轮比前一轮多一个沉的浮岛，所以说我们只需要计算出 B 部分的轮次数就是对的。

对于 A 部分：先贪心地模拟选手，每次消掉两个连续的 1，并直接算出它所需要的轮次。在 A 部分，显然小 P 的最优策略是在保证任意两个 1 不连续的前提下，尽可能的使更多的浮岛的状态为 1，这个部分可以用 dp 求解。

考虑 B 部分应该怎么做：由于选手每次都会采取最优策略，所以说小 P 每一次将选手设置状态为 0 的浮岛的状态重新设置为 1，这一定是最优的。

但是这样会存在一些特殊情况，即不管怎么样选手第一轮无论怎么选择都比较劣，形如 010000001000，这种情况可以直接扫一遍判断。对于剩下来的时间，每一轮小 P 显然每次可以增加 2 个状态为 1 的点，所以也是好做的。

在 A 和 B 两段都做完的情况下 C 段可以直接求解，时间复杂度为 $O(\sum n)$，期望得分 100 分。

$n \leq 2000$ 的部分留给知道整个过程是怎么做的但是暴力枚举的选手，特殊性质 B 给一些正解少判了情况下的选手。