【codechef】【May Challenge 2019 Division 2】【Binary Movements】题解
nekko
2019-05-06 20:38:06
[题目链接](https://www.codechef.com/MAY19B/problems/BINARY)
### 题目描述
你有一个长度为 $n$ 的 $01$ 序列，假设它叫做 $a$，下标从 $1$ 开始
你一共要进行 $k$ 轮操作，在每一轮中，你需要求一个 $b$ 序列，满足：
若有 $a_i=0$ 且 $a_{i+1}=1$，则 $b_i=1$ 且 $b_{i+1}=0$，否则 $b_i=a_i$
之后用 $b$ 序列替换 $a$ 序列
换句话说，你可以把这个 $01$ 序列想象成一堆士兵站在一条序列上，其中 $1$ 的地方有一个士兵，$0$ 的地方是空的
每一时刻某个士兵如果能往前走，当且仅当前面是 $0$，且只能走一格
走路是同步进行的，也就是如果有相邻的两个 $1$，则后面那个 $1$ 不会动
输出第 $k$ 轮结束后每个位置上是否有士兵
其中 $1 \le n,k \le 10^6$
举个例子：
``` plain
0 1 1 0 1 1 （初始局面）
1 0 1 1 0 1 （第一轮）
1 1 0 1 1 0 （第二轮）
1 1 1 0 1 0 （第三轮）
1 1 1 1 0 0 （第四轮）
```
### 题解
~~搬题赚大钱~~
之前某次模拟赛考过这个题的弱化版，即求至少多少轮后没有士兵会再移动，也就是多少轮后使得序列变成 $11 \cdots 1100 \cdots 00$
当时不太会做，于是就开始疯狂打表找规律
然后还真找出来规律了
考虑先把已经归位的 $1$ 给删了，也就是把序列一开始的前缀 $1$ 都删掉
那么对于每一个士兵，都有一个目标距离，即最终序列的位置
显然这个最早的归位时间是最后一个士兵的归位时间
对于一个士兵，他前面每有一个士兵，则会对他产生晚归位 $1$ 单位时间的影响
反之，他前面每有一个空格，则会对他产生早归位 $1$ 单位时间的影响
于是就有一个求得最晚归位时间的代码了，当然也同时可以得知每个士兵的归位时间
``` cpp
int getlen() {
int res = 0;
for(int i = 1 ; i <= n ; ++ i) {
if(mp[i] == 0) {
int tag = 0, tot = 0;
for(int j = i ; j <= n ; ++ j) {
if(mp[j] == 1) {
++ tot;
res = max(res, (j - i + 1) - tot + tag);
}
if(mp[j] == 0) {
-- tag;
} else {
++ tag;
}
if(tag < 0) {
tag = 0;
}
}
break;
}
}
return res;
}
```
那么可以发现一个性质：一个士兵的晚归位时间是 $O(n)$ 级别的
回到这个题，利用之前的打表程序再发掘一下性质……
不妨让每个人互不相同，也就是标上标号：
``` plain
0 1 2 0 3 4 （初始局面）
1 0 2 3 0 4 （第一轮）
1 2 0 3 4 0 （第二轮）
1 2 3 0 4 0 （第三轮）
1 2 3 4 0 0 （第四轮）
```
去掉 $0$：
``` plain
1 2 3 4 （初始局面）
1 2 3 4 （第一轮）
1 2 3 4 （第二轮）
1 2 3 4 （第三轮）
1 2 3 4 （第四轮）
```
显然有一个规律，对于数字 $i$ 的最后位置的这一竖条，考虑转移到 $j=i+1$，那么就相当于先从 $(1,j)$ 往左下角一直走，直到撞上 $i$，然后把 $i$ 剩余的一段往下平移一格，然后往右平移一格
显然这个是对的，因为最终的路线一定是先撞上上一个人，然后和他错开一个时间格后如此操作
那么也就可以解释一开始的打表的规律了——空格会代替你撞上一次，非空格就会让你撞上一次
虽然说是要平移，但考虑每次只平移一格，而且总的轮数不会超过 $O(n)$，所以可以用一个线段树来维护这个东西，同时用一个 $offset$ 维护一下当前区间，于是只需要支持区间赋值上一个等差数列，区间加一，单点查询
对于查询第一次撞到哪，既可以在线段树上维护最大值，也可以二分后在线段树上跑（虽然是 $O(\log^2 n)$ 的，但也是过了……）
写起来比较恶心，对拍是个好东西……
附上算法：
``` plain
1. 找到 1 <= j <= len，满足 i - j + 1 == a[offset + 1 + j] + 1
2. 把 a[offset + 1] ~ a[offset + j] 按照 i, i - 1, i - 2, ... 的值填充
3. 把 a[offset + j + 1] ~ a[offset + len] 都 +1
4. ans[a[offset + k + 1]] = 1
```
然后你发现这个玩意实际上是模拟双端队列
手写一个 $deque$ 就行了，时间复杂度 $O(n)$