【题解】「SFMOI」Round I

· · 题解

如果需要 std 来对拍，私信 @Starrykiller 即可。

A

Subtask 1

A 一定能够获得唯一的一个格子。直接输出即可。

Subtask 2

可能是给暴力枚举策略的做法的分。

Subtask 3 & 4

给某些神秘做法的分。

Subtask 5

我们断言：在最优策略中，A 一定只会向下移动，B 一定只会向右移动。

如果 A 向右移动，一定不优，对于 B 同理。

利用这个结论，结合 A 是先手，可以发现：当且仅当 x\le y 时，一个位置才对 A 有贡献。

据此统计即可。时间复杂度 \Theta(k)。

B1

部分分做法

给奇怪的做法的。可能也有人由于实现不好，双模数 CRT WA 了，就写了多模数的 CRT。

满分做法

首先一定可以 CRT（或者 exCRT），但是由于这里方程数量很少，我们有更优的解法。

具体地说，不妨取 x_1=4 \times 10^8，x_2=x_1-1，我们询问 a =m \bmod x_1 和 b=m \bmod x_2。

令 m=k_2 \cdot x_2+b=k_1 \cdot x_1+a。由于 k_1=\lfloor m/x_1\rfloor,k_2=\lfloor m/x_2\rfloor，k_1,k_2 相差至多为 1。

分类讨论：k_1=k_2=k 时，得到 k \cdot x_1+a=k \cdot x_2+b。一定有 a\le b。

此时，得到 k \cdot x_1+k+a=k \cdot x_1+b，即 k=b-a。

否则，k_1=k,k_2=k+1。得到 k \cdot x_1+a=k \cdot x_2+x_2+b。一定有 a>b。

此时，得到 k \cdot x_1+k+a=k \cdot x_1+x_1-1+b，即 k=b-a+x_1-1。

据此求解即可。每组数据只会用到两次询问，时间复杂度 \Theta(T)。

B2

部分分做法

当 x\ge m 时，x\bmod m\lt m\le x。据此二分答案即可。

满分做法

考虑到一个事实：当 x 足够大的时候，X=x-x \bmod m 一定是 m 的正整数倍。

且此时，(X-1) \bmod m 一定等于 m-1。

据此询问即可。每组数据只会询问两次，时间复杂度 \Theta(T)。

C

Subtask 1

### Subtask 2 给某些假掉的做法的分。也可以由此启发正解。 ### Subtask 3 留给神秘做法的分。 ### Subtask 4 把 $a_i=b_i$ 的位置全部删掉。设新的字符串为 $a',b'$，长度为 $N$，相应地更改操作的 $l,r$。 - 令 $c_i=[a'_i>b'_i]$（$1\le i\le N$）表示第 $i$ 个位置的最优策略（交换/不交换）。 - 令 $\mathrm{rev}_i$ 表示我们的实际操作。 - 对于每个操作 $l,r$，连无向边 $l \leftrightarrow r+1$，得到图 $G$。这张图有 $(N+1)$ 个节点。 我们断言：**能够交换区间 $[l,r]$ 且不影响别的位置，当且仅当节点 $l,r+1$ 在同一连通块中。** > 证明：这意味着存在一条 $l\to r+1$ 的路径。不需要考虑走到编号小于 $l$ 或者大于 $r+1$ 的节点的情况，因为如果走过去了必然会走回来，偶数次操作会 $[l,r+1)$ 外的所有位置的影响抵消。 由于我们要求字典序最大，从小到大考虑 $i=1,2,\ldots,N$。 **我们想要尽量让 $\mathrm{rev}_i=c_i$。** - 若 $\mathrm{rev}_i=c_i$，无事可做，直接跳过。 - 否则，令 $k=\max\{u|u\text{ is reachable from }i\}$。即 $i$ 能到达的点中编号最大的。 - 若 $k=i$，这意味着 $\mathrm{rev}_i$ 无法被改变。 - 否则，我们操作 $[i,k)$。将 $\mathrm{rev}_i \sim \mathrm{rev}_{k-1}$ 全部异或上 $1$。 视 $n,m$ 同阶，这样我们就在 $\Theta(n)$ 或 $\Theta(n \alpha(n))$ 或 $\Theta(n \log n)$ 内解决了本题。 > **证明**： > 根据贪心性质，我们需要**优先满足较低位**上的 $\mathrm{rev}_i=c_i$。 > > 在需要操作且可操作的情况下，必然存在若干决策点 $k_1,\ldots,k_p$，不妨令 $i<k_1<\ldots<k_p=k$。**显然它们都在同一个连通块里。** > > - 必然存在一个 $1\le j\le p$ 使得操作 $[i,k_j)$ 是最优的。我们操作了 $[i,k_p)$ 后，可以在 $k_j$ 处操作 $[k_j,k_p)$ 来抵消影响（可以理解为**反悔**）。 > - 同时，操作 $[i,k_p)$ 不会影响到之前位置的状态。 > > 综上，这样的解法是正确的。 ## D ### Subtask 1 显然 `puts("Dino!");` 即可。 ### Solution 1：二分 + DP（By Firmino） 首先可以二分答案，这样就只要判定能否避开所有障碍。 dino 每次跳跃一定至少跨过一个仙人掌，否则可以不跳。仙人掌把整个数轴分成若干段，考虑从右往左 dp，$dp[i]$ 表示若 dino 从第 $i$ 段左端点出发，能使 dino 避开后面所有障碍的最靠右的起跳点。 考虑如何转移。所有障碍都对 dino 的起跳点作出了限制，即对于每个障碍，dino 不能在某一个或两个闭区间内起跳。取这些区间并集的补集就得到 dino 可以起跳的区间集合。枚举每一个可起跳的开区间 $(l,r)$，$(l,r)$ 和 $(l+2d,r+2d)$ 分别属于同一个被仙人掌划分成的段内，设这两段编号分别为 $i,j (i<j)$。若 $j$ 是最后一段（即后面没有仙人掌），则 $dp[i] \gets \max(dp[i],r)$；否则若 $l+2d < dp[j]$，则 $dp[i] \gets \max(dp[i],\min(r,dp[j]-2d))$。最后看 $dp[1]$ 是否 $> 0 $ 即可（注意由于可起跳的区间是开区间，这里的 dp 值均不能取到，因此必须 $>0$ 才合法，同理前面 $l+2d$ 必须小于 $dp[j]$）。 实现上为了避免浮点数的精度问题，可以把所有障碍物的横坐标和跳跃参数 $d$ 乘上 $h$，这样限制区间和可起跳区间的端点均为整数。 设 $n=b+c$，根据具体实现，总时间复杂度为 $O(n\log^2n)$ 或 $O(n\log n)$。 ### Solution 2：利用 $\texttt{set}$ 维护贪心（by Blue_Loneliness） 令 $k=\dfrac{h}{d}$。 对于飞鸟（令 $u=\min(u,h)$），可以拆成如下不能跳跃区间：$[x-k(2h-d),x-k(2h-u)],[x-ku,x-kd]$。 对于仙人掌，可以拆成如下不能跳跃区间：$[x-2h,x-2h+ku],[x-ku,x]$，以及一个无法到达区间 $[x,x+ku]$。 维护当前能够到达的最远距离 $far$（对应代码的 `farthest`），那么在实际进行游戏时的流程为： 1. 维护当前位置的覆盖情况 2. 进行跳跃判定 3. 向前走 对于跳跃判定： - 如果当前位置（设为 $now$）不被覆盖，那么进行跳跃。此时有 $[far,now+2h]$ 为不可到达区间（如果 $now+2h>far$）$^{[1]}

由于在扫描的过程中并不是所有的点都具有意义，所以需要把所有有意义的点扫描到。容易想到所有有意义的点均为在上述过程中产生的所有区间边界，因为对于非区间边界的点，找到其左侧最靠右的点，进行相同操作，此时一定不劣。

由上述流程可知每段最多会产生一个区间（两个有意义的点），因此总有意义的点的个数为 $O(b+c)$，整个算法的复杂度为 $O(T(b+c)\log(b+c))$。 一些细节： - 由于需要保证 Dino 最早开始跳跃的位置为 $0$，而上面的区间可能出现坐标为负数的情况，为了简化讨论，强制 Dino 从 $-\infin$ 开始，并将 $(-\infin,0]$ 用不可到达区间覆盖。