Codeforces Round #808 (Div. 2)

https://codeforces.com/contest/1708

题意： 大小为 n n n的序列 a i a_i ai​，可进行任意次操作，每次操作为选择 2 ≤ i ≤ n 2leq i leq n 2≤i≤n，使得 a i = a i − a i − 1 a_i=a_i-a_{i-1} ai​=ai​−ai−1​。判断该序列是否能除 a 1 a_1 a1​外全为 0 0 0。
题解： 若 a i a_i ai​全为 a 1 a_1 a1​的倍数，则为 Y E S YES YES；否则为 N O NO NO。
证明： 若 a 2 a_2 a2​可变为 0 0 0，那么 a 2 a_2 a2​必定为 a 1 a_1 a1​的倍数；若 a 3 a_3 a3​可变为 0 0 0，对他的操作只能是加减 a 1 a_1 a1​，则 a 3 a_3 a3​也为 a 1 a_1 a1​的倍数…以此类推，若 a i a_i ai​可变为 0 0 0，则 a i a_i ai​必定为 a 1 a_1 a1​的倍数。

#include
using namespace std;
const int N=100100;
int T,n,a[N];
int main()
{
	scanf("%d",&T);
	while(T--){
		scanf("%d",&n);
		for(int i=1;i<=n;i++) scanf("%d",&a[i]);
		bool flag=1;
		for(int i=2;i<=n;i++){
			if(a[i]%a[1]!=0){
				flag=0;
				break;
			}
		}
		if(flag) printf("YESn");
		else printf("NOn");
	}
}

题意： 给定 n , l , r n,l,r n,l,r，构造一个长度为 n n n的序列 a i a_i ai​，使得 g c d ( i , a i ) gcd(i,a_i) gcd(i,ai​)各不相同，且 l ≤ a i ≤ r l leq a_i leq r l≤ai​≤r。
题解： g c d ( i , a i ) ≤ i gcd(i,a_i) leq i gcd(i,ai​)≤i，所以各不相同只能让 g c d ( i , a i ) = = i gcd(i,a_i)==i gcd(i,ai​)==i，即判断 [ l , r ] [l,r] [l,r]中是否存在 i i i的倍数。

#include
using namespace std;
const int N=100100;
int T,n,l,r,a[N];
int main()
{
	scanf("%d",&T);
	while(T--){
		scanf("%d%d%d",&n,&l,&r);
		bool flag=1;
		for(int i=1;i<=n;i++){
			if(l/i
				flag=0;
				break;
			}
		}
		if(flag){
			printf("YESn");
			for(int i=1;i<=n;i++) printf("%d ",a[i]);
			puts("");
		}
		else printf("NOn");
	}
}

题意： 给定一个长度为 n n n的序列 a i a_i ai​和一个整数 q q q。现有 n n n场比赛，在第 i i i天，若 a i > q a_i> q ai​>q，则会导致 q − − q-- q−−，否则 q q q不变；也可选择不参加该天的比赛， q q q不会发生变化；若 q ≤ 0 q leq 0 q≤0，则不可参加接下来的比赛。求最多可参加几场比赛。
题解： 对于最优解，必定存在一个 x x x，使得 [ 1 , x ] [1,x] [1,x]天只参加 q ≥ a i q geq a_i q≥ai​的比赛， [ x + 1 , n ] [x+1,n] [x+1,n]天的比赛全部参加。证明：对一种策略，设 a a a为最后一场未参加的比赛， b b b为第一场打的 a i > q a_i> q ai​>q的比赛；若 b < a bb a b>a b>a，则使 x = = b x==b x==b即可。同时可发现随着 x x x的右移，可参加的比赛数是单调不增的，故可二分解决。

#include
using namespace std;
const int N=100100;
int T,n,q,a[N],b[N];
bool check(int x)
{
	int now=q;
	for(int i=1;i<=x;i++){
		if(now>=a[i]) b[i]=1;
		else b[i]=0;
	}
	for(int i=x+1;i<=n;i++){
		if(now
	scanf("%d",&T);
	while(T--){
		scanf("%d%d",&n,&q);
		for(int i=1;i<=n;i++) scanf("%d",&a[i]);
		int l=0,r=n,mid,ans;
		while(l<=r){
			mid=l+r>>1;
			if(check(mid)) r=mid-1,ans=mid;
			else l=mid+1;
		}
		check(ans);
		for(int i=1;i<=n;i++) printf("%d",b[i]);
		puts("");
	}
}