[AGC011D] Half Reflector 题解
题意:
有 NN 个装置排成一排,组成一个系统。每个装置有两种状态 AA 和 BB 。具体地,假想有一个小球从最左侧进入这个系统,则两种状态的行为如下:
- AA :将球反弹回原方向。
- BB :让球通过,不改变方向。
当然,每当一个小球经过一个装置后,无论是以 AA 状态还是 BB 状态经过,装置都将改变原来的状态 (即 AA 变 BB ,BB 变 AA )。现在给定初始情况下所有装置的状态,求 KK 个小球经过后装置的状态。
输入格式:
第一行包含两个正整数 N,K(N≤2×105, K≤109)N,K(N≤2×105, K≤109),分别表示装置的个数和经过的小球数。
第二行包含一个由 AA 和 BB 构成的字符串 S(|S|=N)S(|S|=N),其中第 ii 个字符表示左起第 ii 个装置的状态。
输出格式:
输出一行,包含一个字符串 SKSK,表示 KK 次小球经过后状态的状态,具体格式同输入。
可以发现,对于很多情况,小球会来回弹来弹去,以至于对原串进行了类似于翻转的操作
不妨对 S1S1 的情况进行讨论,方便起见,称 AA 为「墙」,BB 为「地」。
若 S1S1 为「墙」,此时小球弹回,S1S1 变为地。
若 S1S1 为「地」,通过对较小情况的尝试,不难发现一个结论:记 ˉx¯x 为与 xx 相反的状态,
则当 S1S1 为「地」时,SS 的新状态 TT 有 Ti=¯Si+1(i<n)Ti=¯¯¯¯¯¯¯¯¯¯Si+1(i<n) , TnTn 为「墙」,且小球一定从右边离开系统。
尝试证明这个结论:
对 |S||S| 归纳证明。显然当 |S|≤3|S|≤3 时成立。于是设 |S||S| 在 n−1n−1 处成立,尝试验证 |S|=n|S|=n 的情形
不妨考虑 S2S2 的情况。
若 S2S2 为「墙」
(图例:
>>>
表示向右运动的球,<<<
表示向左运动的球,|
表示「墙」,_
表示「地」)none(a) >>> _ | …… (b) | >>> | …… (c) | <<< _ …… (d) _ >>> _ ……
(d) 表明了之后 T1=¯S2=T1=¯¯¯¯¯¯S2= 「地」,考虑到右边 n−1n−1 个位置
而他们恰好构成原问题的大小为 n−1n−1 的子问题,由归纳法可知 T2,T3,⋯TnT2,T3,⋯Tn 亦均满足结论。
若 S2S2 为「地」
none(a) >>> _ _ …… (b) | >>> _ ……
同样的,(b) 显然已经满足命题条件了,从而可以用归纳假设,且 T1=¯S2=T1=¯¯¯¯¯¯S2= 「墙」,从而该情况成立。
综上,由归纳原理知,原命题成立。◻□
于是我们要快速模拟这个过程。考虑到每次小球移动,要么是将 S1 翻转,或者整体平移一位
显然这个翻转是不用进行实际操作的,当且仅当进行了奇数次平移最终答案才会翻转。
而在平移的过程中,后面补充的字符依次为「墙」「地」「墙」…(交替出现)
因此我们考虑如何计算平移的次数。
对于 S1 是「墙」,则不会发生平移,而 S1 是「地」时会发生平移
那么只需要统计每个位置是否是「墙」即可。
注意,由于我们取消了取反操作,所以应该判断奇数位是否为「墙」,偶数位是否为「地」
特别地,对于 k≥n 的部分,不难发现,当 n 为奇数时两步一平移,否则一步一平移,可以 O(1) 计算
时间复杂度 O(n)
代码:
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(2e5 + 15))
int n,k; char s[N],t[N];
int get(int x) { return (x < n ? (int)s[x] : (x ^ n)) & 1; }
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
int i, j, c; cin >> n >> k >> s;
for(i = 0; i < n && k; ++i)
{
c = 1 + ((i ^ (int)s[i]) & 1);
if(k >= c) k -= c; else break;
}
if(i == n && k) { c = 1 + (n & 1); i += k / c; k %= c; }
for(j = 0; j < n; j++) t[j] = get(i + j);
for(t[0] ^= k, j = 0; j < n; j++) t[j] = (i & 1 ? 'A' + t[j] : 'A' + 1 - t[j]);
cout << t << '\n';
return 0;
}
参考文献:
[1] https://yhx-12243.github.io/OI-transit/records/ac2340%3Bagc011D.html