[CF121B]Lucky Transformation

题目描述

Petya喜欢幸运数字。每个人都知道幸运数字是十进制下各位只包含$4$和$7$的正整数。例如数字$47$、$744$和$4$都是幸运数字,但$5$、$17$和$467$不是。

Petya有一个由$n$位数字组成的没有前导零的数。他用一个没有前导零的数组来表示这个数,我们称它为$d$。数组的下标从$1$开始顺序输入。Petya想要进行$k$次如下的变换:找到一个最小的$x(1<=x< n)$使得其满足$d_x=4$并且$d_{x+1}=7$。如果$x$是奇数,那么让$d_x=d_{x+1}=4$,否则让$d_x=d_{x+1}=7$。若没有满足条件的$x$,则数字不变。

给定初始数组和数字$k$,请你帮助Petya得出$k$次操作后的结果。

输入输出格式

输入格式

第一行包括两个整数$n$和$k(1<=n<=10^5,0<=k<=10^9)$,分别表示数字个数和操作次数。
第二行用$n$个数字表示数组$d$,数字之间没有空格,以$d_1$开始。保证数字没有前导零。

输出格式

输出一行,为操作后的结果,数字之间没有空格

说明

在第一个样例中数字变换成如下序列:$4727447\to4427447\to4427477\to4427447\to4427477$
在第二个样例中:$4478\to4778\to4478$

题解

仔细观察题面发现,$k$的取值远大于$n$,显然在操作的过程中出现了循环,否则就是无效操作
考虑何时出现循环,当出现一个满足条件的$x$时

  • 当$x\mod2==1$时,使$d_{x+1}=4$,显然,若此时存在$d_{x+2}==7$,由于$x\mod2==1$,所以$x+1\mod2==0$,所以使$d_{x+1}=7$,然而此时$d_x=4$,所以$x$又可以对答案造成一次贡献

  • 当$x\mod2==0$时,使$d_{x}=7$,若存在$d_{x-1}==4$,由于$x\mod2==0$,所以$x-1\mod==1$,所以又可以转变成上面那种情况

当存在上下两种情况互相转换时,就出现循环,此时我们只需考虑$k$的奇偶性$O(1)$变换即可

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <cstdio>
#include <algorithm>

const int N = 100009;

int n, k, flag;
int d[N];

int main() {
scanf("%d%d", &n, &k);
flag = 0;
char c = getchar();
while (c < '0' || c > '9') c = getchar();
for (int i = 1; i <= n; i++) d[i] = c - '0', c = getchar();
for (int i = 1; i <= n && k; i++) {
if (d[i] == 4 && d[i + 1] == 7 && d[i + 2] == 7 && (i & 1)) k %= 2;
if (d[i] == 4 && d[i + 1] == 7 && k) {
if (i & 1) d[i + 1] = 4;
else d[i] = 7;
i -= 2, k--;
}
}
for (int i = 1; i <= n; i++) putchar(d[i] + '0');
return 0;
}

题目这么简单不要问我为什么是黑的