Codeforces Round #696 (Div. 2)

A. Puzzle From the Future (构造+贪心)

  题目链接:传送门

&nsbp; 题意:给你一个二进制的数b，问你怎么凑出一个a使得c=a+b的二进制数最大，注意此处的加和并不会产生进位，换句话说， 每一位上加和的结果可能是0，1，2三种情况，并且这里连续相同的数字会缩减成一位eg:122221 => 121 解题思路:很明显不管b是什么，a的第一位肯定是1，这样才能凑出最大的c，又因为连续相同的数字会缩减成一位，所以我们可以根据前面一位的数字得出当前数字的选取，比如第一位是2，当前b的这一位是0，那我们可以选1，否则选0，其他情况亦是如此，更具前一位推后一位 Code:

#include
using namespace std;
int main()
{
	int t,n;
	string ch;
	scanf("%d",&t);
	while(t--) {
		scanf("%d",&n);
		cin>>ch;
		putchar('1');
		int last = 1 + (ch[0] -'0');//表示的是前一种状态的值
		for(int i = 1;i < n; ++i) {
			if(last == 2) {//分为三种情况讨论
				if(ch[i] == '1')
					putchar('0');
				else
					putchar('1');
				ch[i] = '0';
				last = 1;
			}
			else if(last == 1) {
				if(ch[i] == '1') {
					putchar('1');
					ch[i] = '2';
					last = 2;
				}
				else {
					putchar('0');
					last = 0;
				}
				
			}
			else if(last == 0) {
				putchar('1');
				if(ch[i] == '0')
					last = 1;
				else if(ch[i] == '1')
					last = 2;
				ch[i] = '1';
			}
		}
		putchar('\n');
	}
	
	return 0;
}

B. Different Divisors (欧拉筛 + 思维)

  题目链接:传送门

解题思路:题目比较简短，我就不描述了,我们要找到满足这样的数a，很明显我们发现其实就是找到满足这两条规定的素数，因为他这里把1个本身也算进去了，所以我们只需要找到满足条件的两个素数即可，我们通过欧拉筛，筛出一定范围内的素数，然后找到满足素数x，y,使得 \(x-1>=d且y-x>=d且x*y-y>=d\) Code:

#include
using namespace std;
#define ll long long

queue que;

const int N = 1000005;
int prime[N];
bool vis[N];

void get_prime() {
    memset(vis,true,sizeof vis);
    memset(prime,0,sizeof prime);
    vis[0] = vis[1] = false;
    for(int i = 2; i