比赛 NOIP水题赛2 评测结果 AAATTTTTTT
题目名称 AACC(无题面) 最终得分 30
用户昵称 胡嘉兴 运行时间 7.687 s
代码语言 C++ 内存使用 3.56 MiB
提交时间 2018-11-02 18:37:52
显示代码纯文本
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5+7, p1 = 1e9+7, p2 = 1e9+9;
char s[N], ch[N], tmp[N];
void add1(int & a, int b)
{
	a += b;
	if(a>=p1)
	{
		a -= p1;
	}
	return;
}
void add2(int & a, int b)
{
	a += b;
	if(a>=p2)
	{
		a -= p2;
	}
	return;
}
int hash1(int n)
{
	int res = 0;
	for(int i = 1; i <= n; i++)
	{
		add1(res, res);
		add1(res, tmp[i]-'0');
	}
	return res;
}
int hash2(int n)
{
	int res = 0;
	for(int i = 1; i <= n; i++)
	{
		add2(res, res);
		add2(res, tmp[i]-'0');
	}
	return res;
}
int main()
{
	ll t;
	int n, beg1, beg2, c = 0;
	beg1 = beg2 = 0;
	freopen("AACC.in", "r", stdin);
    freopen("AACC.out", "w", stdout);
	scanf("%d%lld%s", &n, &t, s+1);
	memcpy(ch, s, (n+2)*sizeof(s[0]));
	for(int i = 1; i <= t; i++)
	{
		tmp[1] = s[2];
		tmp[n] = s[n-1];
		for(int j = 2; j < n; j++)
		{
			tmp[j] = s[j-1]==s[j+1]?'0':'1';
		}
		int val1 = hash1(n);
		int val2 = hash2(n);
		if(i==1)
		{
			beg1 = val1;
			beg2 = val2;
		}
		else if(beg1==val1&&beg2==val2)
		{
			c = i-1;
			break;
		}
		memcpy(s, tmp, (n+2)*sizeof(s[0]));
	}
	if(!c)
	{
		for(int i = 1; i <= n; i++)
		{
			printf("%c", s[i]);
		}
		puts("");
		return 0;
	}
	t = t%c+c;
	for(int i = 1; i <= t; i++)
	{
		tmp[1] = ch[2];
		tmp[n] = ch[n-1];
		for(int j = 2; j < n; j++)
		{
			tmp[j] = ch[j-1]==ch[j+1]?'0':'1';
		}
		memcpy(ch, tmp, (n+2)*sizeof(s[0]));
	}
	for(int i = 1; i <= n; i++)
	{
		printf("%c", ch[i]);
	}
	puts("");
	return 0;
}