[数据结构与算法]Codeforces Round #808 (Div. 2)ABCD

A. Difference Operations

题意：选择一个$i,2<=i<=n$,使得$a[i]=a[i]?a[i?1]$,判断最后是否可以将$a$中除第一个所有元素清零
思路：当且仅当这个数组所有元素都能被第一个元素整除。
3 6 12 3 9
3 6 6 3 6
3 3 3 3 3
3 0 0 0 0

const int N=110;
int a[N];
void solve()
{
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=2;i<=n;i++)
		if(a[i]%a[1])
		{
			cout<<"NO"<<endl;
			return;
		}
	cout<<"YES"<<endl;
}

B. Difference of GCDs

题意：给一个$n,l,r$，使得$a_1,a_2...a_n,(l<=a_i<=r),gcd(a[i],i)互不相同$，
构造出数组$a$
容易分析出：$gcd(a_1,1)=q_1,gcd(a_2,2)=q_2......$，$q_1<=1,q_2<=2$，这样题目就变成：在$[l,r]$内找是否存在$i$倍数

void solve()
{
	cin>>n>>l>>r;
	vector<int>v;
	for(int i=1;i<=n;i++)
	{
		int s=ceil((double)l/i)*i;
		if(s>r)
		{
			cout<<"NO"<<endl;
			return;
		}
		v.pb(s);
	}
	cout<<"YES"<<endl;
	for(auto x:v)cout<<x<<' ';
	cout<<endl;
}

C. Doremy’s IQ

题意：如果孩子当前$IQ$小于补习班的权值，如果坚持上这个补习班，那么孩子的$IQ?1$，问最后孩子最多可以上几门课
思路：如果有两门课程都需要$IQ?1$，那么尽可能选择后边的课，此时孩子有更多的$IQ$可以白嫖其他课，所以我们可以倒着扫，保证在前边的课程中孩子的$IQ$尽可能地高。

#include <bits/stdc++.h>
using namespace std;
const double pi = acos(-1);
const double eps=1e-5;
#define x first
#define y second
#define LL long long 
#define int LL
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define PII pair<int,int>
#define ll_INF 0x7f7f7f7f7f7f7f7f
#define INF 0x3f3f3f3f
#define debug(x) cerr << #x << ": " << x << endl
#define io ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
int Mod(LL a,LL mod){return (a%mod+mod)%mod;}
int lowbit(LL x){return x&-x;}//最低位1及其后面的0构成的数值
//void read(__int128 &x){char c = getchar();while (c != '-' & (c < '0' | c > '9'))c = getchar();if (c == '-') {c = getchar();while (c >= '0' & c <= '9') {x = x * 10 + c - '0';c = getchar();}x = 0 - x;} else {while (c >= '0' & c <= '9') {x = x * 10 + c - '0';c = getchar();}}}
//void out(__int128 x) {string c = "";while (x) {c += x % 10 + '0';x /= 10;}reverse(c.begin(), c.end());cout << c << endl;}
int qmi(int a, int k, int p){int res = 1 % p;while (k){if (k & 1) res = Mod(res * a , p);a = Mod(a * a , p);k >>= 1;}return res;}
int _;
int n,q;
const int N=1e5+10;
int a[N];
void solve()
{
	cin>>n>>q;
	for(int i=1;i<=n;i++)cin>>a[i];
	vector<int>v(n+10);
	int k=0;
	for(int i=n;i;i--)
	{
		if(k<q)
		{
			if(a[i]>k)
			{
				k++;
				v[i]=1;
			}
			else v[i]=1;
		}
		else
		{
			if(a[i]<=k)v[i]=1;
		}
	}
	for(int i=1;i<=n;i++)cout<<v[i];
	cout<<endl;
}
signed main()
{
    io;
 	cin>>_; 
 	while(_--)
    solve();
    return 0;
}

D. Difference Array

题意：给一个数组$a$，每次求他的差分数组，问最后一次所剩的那个元素。

根据这句话可知$sum(a_i)<=2?10^5$实则每个$a_i$的范围很小，所以首先想到能不能暴力解决这个问题。
由于一直进行差分操作，最后会使数组出现许多的0，当一个数组元素全部相同时，答案为0，否则，最后结果一定不为0。0的多少对于差分来说是不造成影响的，所以如果有0产生，我们只需要给数组中加1个零即可，最后就是暴力解决。

void solve()
{
	cin>>n;
	vector<int>v1;
	res=0;
	for(int i=1;i<=n;i++)
	{
		int x;
		cin>>x;
		v1.pb(x);
	}
	while(v1.size()>=2)
	{
		vector<int>v2;
		for(int i=1;i<v1.size();i++)
			if(v1[i]==v1[i-1])res++;//0只加一次
			else v2.pb(v1[i]-v1[i-1]);
		if(res)v2.pb(0),res--;
		v1=v2;
		sort(all(v1));
		//替换/// 
	
	} 
	cout<<v1[0]<<endl;
}