算法练习题41---蓝桥杯2021国赛B组-异或变换

• 前言
• 一、题目描述
• • • 输入输出样例
    • • 示例
    • 样例说明
    • 评测用例规模与约定
    • 运行限制
• 二、思路
• 三、具体代码

蓝桥杯2021年国赛B组，编程题（C++）

赛题链接：异或变换 - 蓝桥云课 (lanqiao.cn)

输入

5 3
10110

输出

11010

初始时为 10110，变换 1 次后变为 11101，变换 2 次后变为 10011，变换 3 次后变为 11010。

对于 40% 的评测用例，1 ≤ n ≤ 100, 1 ≤ t ≤ 1000。

对于 80% 的评测用例，1 ≤ n ≤ 1000, 1 ≤ t ≤ 10^9。

对于所有评测用例，1 ≤ n ≤ 10000, 1 ≤ t ≤ 10^{18}。

• 最大运行时间：3s
• 最大运行内存: 256M

这个题目如果单纯模拟去做的话，大概40%的样例可以通过，但剩下的就会超时。这种情况往往是有规律可循的，我们拿几个较短的字符串去模拟这个过程：

输入n=5，t=8，不难发现，在第4次就开始循环往复了。

（0）01101

（1）01011

（2）01110

（3）01001

（4）01101 ←

（5）01011

（6）01110

（7）01001

（8）01101 ←

那么，最终的规律是当大于等于n的一个2的整数次幂情况下，必定存在循环。

也就是满足 max_per=2^x，max_per>=n，在这个max_per范围内，必定存在一个循环

#include
using namespace std;
int main()
{
	long long n,t;
	cin>>n>>t;
	string s;
	cin>>s;
	int max_per=1;
	while(max_per
		max_per*=2;
	}
	t=t%max_per;
	for(int i=0;i
		for(int j=n-1;j>=1;j--)
		{
			s[j]=(s[j]-'0')^(s[j-1]-'0')+'0';
		}
	}
	cout< 
感谢Mr_渣渣辉 博主提供的题目集，图片出自2021第十二届蓝桥杯国赛C/C++大学B组题解_Mr_渣渣辉的博客-CSDN博客_2021蓝桥杯c语言b组答案