Codeforces Round #696 (Div. 2)

A. Puzzle From the Future

题意：给你长度为n一个字符串a,由0和1构成，想要输出长度为n的字符串b，已知字符串a+b为d，已知我要使得d串最大，且相邻不相等。求字符串b。
思路：因为d串对应的每一位就是ab串对应每一位的和，列如如果a：1011 则 最优应该是1111 但是这样对应的d就是 2122了，为了避免最后两位重复，所以b只能为 1110 则d是2121是最优情况了.
一句话：从a串第一位判断，如果a串为0，则我输出1，如果前一位也是1，那我输出0，如果a串为1，那我输出1，如果前一位是1，则输出0。

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n,i,j,t;
	cin>>t;
	while(t--){
		int d=111;
		string s1,ans;
		cin>>n>>s1;
		for(i=0;i<s1.length();i++){
			if(s1[i]=='0'){
				if(d!=1)
					d=1,ans+='1';
				else 
					d=0,ans+='0';
			}
			else if(s1[i]=='1'){
				if(d!=2)
					d=2,ans+='1';
				else 
					d=1,ans+='0';
			}
		}
		cout<<ans<<endl;
	}
}	

B. Different Divisors

题意：找到一个除数至少为4，且除数相邻的差至少为d。
思路：打表找规律，发现符合条件的最优解是除开1和它本身外，还有两个素数为质数。所以找两个质数且他们的差大于d就好。

#include<bits/stdc++.h>
using namespace std;
bool jg(int i){
	int cnt=0;
	for(int d1=2;d1<=sqrt(i);d1++){
		if(i%d1==0)
			return 0;
	}
	return 1;
}
int main()
{
	int t,n,i,j,d,ans;
	cin>>t;
	while(t--){
		cin>>d;
		if(d==1){
			cout<<6<<endl;
		}
		else {
			int ans1,ans2;
			for(i=d+1;;i++){
				if(jg(i)==1){
					ans1=i;break;
				}
			}
			for(i=d+ans1;;i++){
				if(jg(i)){
					ans2=i;break;
				}
			}
			cout<<ans1*ans2<<endl;
		}
	}
}

本文地址：https://blog.csdn.net/RIPKEY/article/details/112856201