P9112 [IOI2009] Archery
Alex_Wei
·
·
题解
P9112 [IOI2009] Archery
通过样例提示或手玩几组小数据，我们发现有些选手一定的轮数后不再移动，而其它选手按从 n 到 1 的顺序环状移动。
- 考虑选手 1，他最终会在靶 1 停下来。
- 考虑选手 2n，他最终会在某个非靶 1 的位置停下来，因为他无法打败任何人，所以一旦进入某个非靶 1 的位置，他就永远无法离开了。
- 考虑选手 2n - 1，他最终会在某个不是选手 1 或选手 2n 停下来的位置停下来，原因同理。
以此类推，可知不移动的选手为 1 和 n + 2\sim 2n，而环状移动的选手为 2\sim n + 1。我们将 n 个靶位按编号排成圆圈。
我们探究什么时候所有选手会有规律地移动。一个直观猜测是，等选手 1 进入靶位 1 后，选手 n + 2\sim 2n 会在不超过 n 轮后停在靶位 2\sim n。因此，至多 2n 轮后整个局面会以 n 为循环节循环。
> **$n + 2\sim 2n$ 会在不超过 $n$ 轮后停在靶位 $2\sim n$**。
>
> 证明：考虑某个靶位 $i$（$2\leq i\leq n$）且 $n$ 轮后没有 $n + 2\sim 2n$，那么 $i$ 从来没有被这样的选手经过，因为一旦经过就一直存在，无论留下的选手编号是什么。
>
> 在第一轮时，$i$ 左侧的靶位（靶位 $i - 1$）至多剩下一名 $n + 2\sim 2n$。
>
> 在第二轮时，$i$ 左侧的两个靶位总共至多剩下两名 $n + 2\sim 2n$。
>
> 特别地，在第 $i - 1$ 轮时，靶位 $1\sim i - 1$ 至多剩下 $i - 1$ 名 $n + 2\sim 2n$，且如果剩下 $i - 1$ 名，则靶位 $1$ 上至少有一名，此时我们再等一轮，第 $i$ 轮时，靶位 $1\sim i - 1$ 至多剩下 $i - 2$ 名 $n + 2\sim 2n$。
>
> 以此类推，可知第 $n$ 轮时，$i$ 左侧的 $n - 1$ 个靶位（也就是除了靶位 $i$ 本身的其它所有靶位）至多剩下 $n - 2$ 名 $n + 2\sim 2n$，但总共有 $n - 1$ 名 $n + 2\sim 2n$，这与靶位 $i$ 上没有 $n + 2\sim 2n$ 矛盾了。$\square
这样，我们将 R 替换为最小的 R'\geq n（或 2n）且 R\equiv R'\pmod n，答案不会改变。这给予我们 \mathcal{O}(n ^ 3) 的模拟做法。
考虑优化单次 \mathcal{O}(n ^ 2) 的模拟。我们观察到，若主角的技术水平为 S_1，则在模拟的过程中，所有 > S_1 的选手是等价的，称为 2 类选手；所有 < S_1 的选手是等价的，称为 0 类选手。并且，根据移动规则，类似上述证明，若有 2 类选手进入靶位 2\sim n，则该靶位一直有 2 类选手；若有 1 类选手进入靶位 1，则该靶位一直有 1 类选手。
因此，只要我们能够对于靶位 2\sim n 求出第一次有 2 类选手的时间 t_2\sim t_n，对于靶位 1 求出第一次有 1 类选手的时间 t_1，即可在任意时刻确定每个靶位上选手的类型，从而只维护主角的移动而不需要维护其它选手的移动。
- 如果 $j$ 到 $i$ 不经过靶位 $1$，则 $j$ 移动到 $i$ 的充要条件是 $i\sim j$ 至少有 $j - i + 1$ 个 $2$ 类选手，即 $s_j - s_{i - 1} \geq j - (i - 1)$，且 **恰好在第 $j - i + 1$ 轮到达靶位 $i$，每一步都向前移动 $1$**。又因为每个靶位上至多有两个 $2$ 类选手，所以符合条件的最小的 $j$ 一定满足 $s_j - s_{i - 1} = j - (i - 1)$ 或 $j - (i - 1) + 1$。实际上，特判掉靶位 $i$ 本来就有 $2$ 类选手的情况之后，$s_j - s_{i - 1}$ 只能等于 $j - (i - 1)$。
- 如果 $j$ 到 $i$ 经过靶位 $1$，那么稍微复杂一些。首先，$j$ 移动到 $i$ 的充要条件是 $i\sim j$ 至少有 $j - i$ 个 $2$ 类选手，即 $s_j - s_{i - 1} \geq j - (i - 1) - 1$。类似地，除了靶位 $n$ 没有 $2$ 类选手，靶位 $1$ 有两个 $2$ 类选手的情况，$s_j - s_{i - 1}$ 只能等于 $j - (i - 1) - 1$。但是，$j$ 并不一定恰好在第 $j - i + 1$ 轮到达靶位 $i$：如果 $j$ 在到达靶位 $1$ 时，靶位 $1$ 有两个选手，那么 $j$ 会在这里停顿一下，使得 $j$ 在第 $j - i + 2$ 轮到达靶位 $i$。易知其充要条件为靶位 $1\sim j$ 初始全部有两个 $2$ 类选手。
求出 $t$ 之后，单次模拟的时间复杂度就可以做到 $\mathcal{O}(n)$。
因为超过一个 $2$ 类选手只能打败他，所以在靶位 $2\sim n$ 上，相较于靠前的起始位置，靠后的起始位置总要打败更多的 $2$ 类选手。而在靶位 $1$ 上，两个不同的起始位置可能等到相同的轮数才回到 $n$，但靠后的起始位置一定不会在靠前起始位置之前（更少的轮数）回到 $n$。因此，如果我们在线性的尺度下观察整个过程，设 $f_i$ 表示初始位置 $i$ 在线性尺度下的最终位置，即 $i$ 减去主角从 $i$ 出发经过 $R$ 轮的移动次数，那么对于 $i < j$，$f_i\leq f_j$。
因为 $R = \mathcal{O}(n)$，所以 $f_n - f_1 = \mathcal{O}(n)$。我们枚举 $[f_1, f_n)$ 的所有 $n$ 的倍数 $kn$，总共 $\mathcal{O}(1)$ 个，二分求出第一个 $i$ 使得 $f_i > kn$，则初始位置 $i$ 以及对应的最终位置才有可能更新答案。时间复杂度 $\mathcal{O}(n\log n)$。
```cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
bool Mbe;
constexpr int N = 4e5 + 5;
int n, R, a[N], b[N];
pair<int, int> ans = {N, 0};
auto simulate(int p) {
for(int i = 1; i < 2 * p; i++) a[i] = b[i + 1];
a[2 * p] = b[1];
for(int i = 2 * p + 1; i <= 2 * n; i++) a[i] = b[i];
static int t[N], s[N], buc[N << 1];
memset(s, 0, N << 2), memset(buc, 0x3f, N << 3);
for(int i = 1; i <= 2 * n; i++) if(a[i] == 2) s[i + 1 >> 1]++;
for(int i = 1; i <= n; i++) s[i + n] = s[i], t[i] = 1e9;
for(int i = 1; i <= 2 * n; i++) s[i] += s[i - 1];
for(int i = 0; i <= 2 * n; i++) s[i] += N - i;
for(int i = n + 1; i > 1; i--) { // i 从 n + 1 开始，特判特殊情况
if(s[i] >= s[i - 1]) t[i] = 1;
else t[i] = buc[s[i - 1]] - i + 1;
buc[s[i]] = i;
}
memset(buc, 0x3f, N << 3);
for(int i = 2 * n; i > 1; i--) {
if(i > n) buc[s[i]] = i;
else {
int p = buc[s[i - 1] - 1];
if(p < N) t[i] = min(t[i], p - i + (s[p] - s[n] == p - n ? 2 : 1));
}
}
int fir = 0, cur = 0, fin;
for(int i = 1; i <= 2 * n; i++) {
if(a[i] == 0 && !fir) fir = i + 1 >> 1;
else if(a[i] == 1) fin = cur = i + 1 >> 1;
}
for(int _ = 1; _ <= R; _++) {
if(cur == 1) {if(fir <= _) cur = n, fin--;}
else if(t[cur] <= _) cur--, fin--;
}
ans = min(ans, {cur, -p});
return make_pair(cur, fin);
}
bool Med;
int main() {
fprintf(stderr, "%.3lf MB\n", (&Mbe - &Med) / 1048576.0);
#ifdef ALEX_WEI
FILE* IN = freopen("1.in", "r", stdin);
FILE* OUT = freopen("1.out", "w", stdout);
#endif
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> R, R = n + R % n;
for(int i = 1; i <= 2 * n; i++) cin >> b[i];
if(b[1] == 1) cout << n << "\n", exit(0);
for(int i = 2; i <= 2 * n; i++) b[i] = b[i] < b[1] ? 0 : 2;
b[1] = 1;
auto fst = simulate(1), lst = simulate(n);
for(int i = fst.second; i < lst.second; i++) {
if(i != fst.second && (i % n + n) % n != 1) continue;
int l = 1, r = n;
while(l < r) {
int m = l + r >> 1;
auto dat = simulate(m);
if(dat.second >= i) r = m;
else l = m + 1;
}
int v = simulate(l).second;
r = n;
while(l < r) {
int m = l + r + 2 >> 1;
auto dat = simulate(m);
if(dat.second <= v) l = m;
else r = m - 1;
}
simulate(l);
}
cout << -ans.second << "\n";
cerr << 1e3 * clock() / CLOCKS_PER_SEC << " ms\n";
return 0;
}
```