P8763 [蓝桥杯 2021 国 ABC] 异或变换 题解

· · 题解

题目传送门

P8763 题解

(话说这道题我也是拿了一血的，求过)

题意概括

一个字符串，经过 t 次变化之后会变成什么样。

分析

首先看数据范围：对于所有评测用例， 1 \le N \le 10000 ， 1 \le t \le 10^{18} 。
看看这 t 的范围！暴力肯定是过不了的。
暴力 WA 掉的记录
但是，暴力如果过不了题，我们就要让暴力为我们服务！
我测试了很多样例，用暴力代码输出它的变化过程：
比如样例： 

(begin) 10110 -> 11101 -> 10011 -> 11010 -> 10111 -> 11100 -> 10010 -> 11011 -> 10110 (end)

然后自创一个样例：

(begin) 100010 -> 110011 -> 101010 -> 111111 -> 100000 -> 110000 -> 101000 -> 111100 -> 100010(end)

这两个例子整个的过程都经历了 8 次变化找到了循环节， 8 = 2^3 。

接着再测一组：

(begin)1010 -> 1111 -> 1000 -> 1100 -> 1010(end)

这一组样例只用了 4 次变化就找到了循环节， 4 = 2^2 。

再比如：

(begin)11111000 -> 10000100 -> 11000110 -> 10100101 -> 11110111 -> 10001100 -> 11001010 -> 10101111 -> 11111000(end)

这一组也是用了 8 次回到原来的数， 8 = 2^3 。
建议大家也多尝试一下。

在许多次的探究中，我得出了一个结论：
循环节的长度与 t 无关，因为不管怎样一定会出现循环节，循环节的长度只与字符串的长度 n 有关。

结论

最终满足 x = 2^k（k 为使 x \ge n 的最小整数）时，必定存在一个循环节出现。
也就是说： 我们需要遍历出 k 的值，来压缩 t 的值。

怎样求出 x

从以上推论中可以得知：满足 x = 2^k（k 为使 x \ge n 的最小整数）时，必定存在一个循环。
那么应该如何求 x 的值呢？
枚举，从 1 枚举到直到 x \ge n 的时候，就能得到最大的 x 值。
接下来用 t 取余循环节的长度，就可以大大优化时间复杂度。

代码

#include<bits/stdc++.h>
using namespace std;
int n,x=1;
long long t;
char s[10005];
char XOR(char x1,char x2){
    if(x1!=x2) return '1';
    else return '0';
}//异或函数
int main(){
    scanf("%d %lld",&n,&t);
    scanf("%s",s+1);
    while(x<n) x<<=1;//循环节长度
    t%=x;//压缩 t
    while(t--) for(int i=n;i>=2;i--) s[i]=XOR(s[i],s[i-1]);
    printf("%s",s+1);
    return 0;
}

感谢观看，点个赞再走吧！
本蒟蒻第一篇题解，跪求管理员大大通过！