【模拟】10-15 题解 trans

Trans

题目描述

Tgopknight决定使用他的幸运数字2和3来进行这个游戏，他一开始有n个数字，记为{d_n}需要进行k次操作，每次操作找到最小的x使得d_x = 2并且d_x+1 = 3，此时如果x为奇数，则令d_x+i = 2，反之令d_x = 3,若没有这样的x则数字不变。

Tgopknight现在想知道进行完所有操作后这些数字变成了什么。

输入输出

input

本题有多组数据。

每组数据第一行是两个正整数n和k分别表示数字个数和操作次数。

第二行有n个数字，数字之间没有空格。

output

对于每组数据，输出一行，为操作进行完之后的结果。

样例

input

output

2243233
2334

数据范围

对于前50%的数据n <=10⁴, k <= 10⁴

对于前70%的数据k <= 10⁶

对于 100%的数据1 <= n <=10⁶ ,0 <= k <=10⁹,数据组数不超过10

思路

考虑遇到一个首位为奇数的233或者223 Tgopknight会使其在这二者之间互相转变，那么只需要考虑剩余的操作数的奇偶性即可。
时间复杂度〇(n)期望得分100分。

代码

#include <bits/stdc++.h>
using namespace std;
char s[1000005];
int n, k;
int main() {
	freopen("trans.in","r",stdin);
	freopen("trans.out","w",stdout);
	while (~scanf("%d%d%s", &n, &k, s)) {
		for (int i = 0; i < n && k; i++) {
			if (s[i]=='2'&&s[i+1]=='3'&&s[i+2]=='3'&&!(i%2)) k%=2;
			if (k&&s[i]=='2'&&s[i+1]=='3') s[i]=s[i+1]=(i%2)?'3':'2',i-=2,k--;
		}
		puts(s);
	}
	return 0;
}