题解 CF379D New Year Letter

思路

提供一种比较容易想到的做法。

拿到题看数据范围发现都很小，所以放心大胆地暴力。

容易发现 \(s_i\) 中 AC 的个数等于 \(s_{i-2}\) 中 AC 的个数加 \(s_{i-1}\) 中 AC 的个数再加上两者拼接处可能有的一个 AC。

所以 \(s_1\) 和 \(s_2\) 从第二个字符到倒数第二个字符这之间的 AC 串的排布与后面拼接没有任何关系。枚举里面有几个 AC 即可。不是 AC 的地方用一个无关字母表示就没有贡献了（我的代码中用的是 X）。

然后对于 \(s_1\) 和 \(s_2\) 第一个和最后一个字符，仍然是大力枚举这个字符（分别为 X，A，C 的时候），然后直接模拟，判断最后结果是不是等于给定的 \(x\) 即可。

模拟的具体方法就是记录前两个串的第一个和最后一个字符然后判断有没有新 AC 产生即可。

Code

#include<bits/stdc++.h>
using namespace std;
int n,m,k,x;
char s1[110],s2[110],s[4]={"\0AC"};
void fun(int fir1,int las1,int fir2,int las2){
	int sum,l1,l2,q1,q2,w1,w2,qq=0,ww=0;
	memset(s1,0,sizeof(s1));
	s1[1]=s[fir1];
	s1[n]=s[las1];
	if(n<=3){
		qq=1;  //串长<=3时无法写入AC，需要特判
	}
	for(int i=fir1?2:1,sum1=0;i+1<=(las1?n-1:n)||qq;i+=2,sum1++){
		qq=0;
		if(sum1){
			s1[i]='A';
			s1[i+1]='C';
		}
		else{
			i-=2;
		}
		memset(s2,0,sizeof(s2));
		s2[1]=s[fir2];
		s2[m]=s[las2];
		if(m<=3){
			ww=1;
		}
		for(int j=fir2?2:1,sum2=0;j+1<=(las2?m-1:m)||ww;j+=2,sum2++){
			ww=0;
			if(sum2){
				s2[j]='A';
				s2[j+1]='C';
			}
			else{
				j-=2;
			}
            //模拟。
			l1=sum1;//s[i-2]的答案
			l2=sum2;//s[i-1]的答案
			q1=fir1;//s[i-2]的头
			q2=fir2;//s[i-1]的头
			w1=las1;//s[i-2]的尾
			w2=las2;//s[i-1]的尾
			if(n==1){
				q1=las1;
			}
			if(m==1){
				q2=las2;//特判覆盖了
			}
			for(int kk=3;kk<=k;kk++){
				sum=l1+l2+(w1==1&&q2==2);
				l1=l2;
				l2=sum; //模拟，更新
				swap(q1,q2);
				w1=w2;
				if(sum>x){
					break;
				}
			}
			if(sum==x){
				for(int kk=1;kk<=n;kk++){
					if(s1[kk]){
						printf("%c",s1[kk]);
					}
					else{
						printf("X");
					}
				}
				printf("\n");
				for(int kk=1;kk<=m;kk++){
					if(s2[kk]){
						printf("%c",s2[kk]);
					}
					else{
						printf("X");
					}
				}
				exit(0);
			}
		}
	}
}
int main(){
	scanf("%d%d%d%d",&k,&x,&n,&m);
	if(x==0){
		for(int i=1;i<=n;i++){
			printf("A");
		}
		printf("\n");
		for(int i=1;i<=m;i++){
			printf("A");
		}
		return 0;
	}
    //枚举头尾
	for(int i=0;i<=2;i++){
		for(int j=0;j<=2;j++){
			for(int k=0;k<=2;k++){
				for(int l=0;l<=2;l++){
					fun(i,j,k,l);
				}
			} 
		}
	}
	printf("Happy new year!");
}

完结撒花！！