[C++知识库]Codeforces Round #808 (Div. 2) 题解（A~D）

A题链接

题目大意：
可以无限次操作，让 $a_i=a_i?a_{i?1}$，问能否让 $a_i=0$，对于所有$2\le i\le n$。

解题思路：
只要保证后面的 $a_i$ 都是 $a_1$ 的倍数就可以了，这样的话，对于任意 $a_i$（$2\le i\le n$），都有 $a_i=a_i?a_{i?1}$ 使得 $a_i$ 依然为 $a_1$ 的倍数。
既然这样，那么任意 $a_i$ 都可以变成 $a_1$ ，所以，既然都可以变成 $a_1$ ，那么 $a_1?a_1$ 就是0，对于一个值都是 $a_1$ 的数列，从后往前执行 $a_i=a_i?a_{i?1}$ ，这样所有 $i\ge 2$ 的 $a_i$ ，都可以变成0。

代码如下：

#include <bits/stdc++.h>
#define rep(a,b,c) for(int a=b;a<=c;a++)
#define dec(a,b,c) for(int a=b;a>=c;a--)
#define x first
#define y second
#define pb push_back
#define LL long long
#define ios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define INF 0x3f3f3f3f
using namespace std;

const int N=10000;
int a[N];

void solve()
{
	int n;
	cin>>n;

	rep(i,1,n)
		cin>>a[i];
	
	rep(i,2,n)
	{
		if(a[i]%a[1]!=0)
		{
			cout<<"NO"<<endl;
			return;
		}
	}
	cout<<"YES"<<endl;
}

B题链接

题目大意：
给你 $n,l,r$，让你输出一组 $a_i$ ，使得每一个 $GCD(i,a_i)$ 都是不一样的

解题思路：
既然要让每一个都是不一样的，那么就让 $GCD(i,a_i)=i$ 即可。所以找到一个数字 $k$ 让它即在 $l$ 和 $r$ 之间，又让 $k$ 是 $i$ 的倍数就行了 （这边建议用$k=r/i\times i$来算，这样可以求出小于 $r$ 的最大的k），如果找不到就输出NO。

代码如下：

#include <bits/stdc++.h>
#define rep(a,b,c) for(int a=b;a<=c;a++)
#define dec(a,b,c) for(int a=b;a>=c;a--)
#define x first
#define y second
#define pb push_back
#define LL long long
#define ios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define INF 0x3f3f3f3f
using namespace std;

void solve()
{
	int n,l,r;
	cin>>n>>l>>r;
	
	vector<int> v;
	v.pb(l);
	rep(i,2,n)
	{
		int k=r/i*i;
		if(k<l)
		{
			cout<<"NO"<<endl;
			return;
		}
		v.pb(k);
	}
	
	cout<<"YES"<<endl;
	for(auto i:v)
		cout<<i<<" ";
	cout<<endl;
}

C题链接

题目大意：
接下来有 $n$ 个题目和 $q$ 点智商，遇到一个题值 $a_i$ ，如果智商大于等于 $a_i$ 就可以做这道题，而智商无事发生，否则智商就$?1$

解题思路：
贪心地想，首先先做小于等于智商的，再做需要让智商 $?1$ 的，这样的话，只要从后往前贪心就可以了。

C题我看到有人被干掉了，好像是因为memset的时候导致时间复杂度爆了（memset了两个2e5的数组），我开的1e5没问题。

代码如下：

#include <bits/stdc++.h>
#define rep(a,b,c) for(int a=b;a<=c;a++)
#define dec(a,b,c) for(int a=b;a>=c;a--)
#define x first
#define y second
#define pb push_back
#define LL long long
#define ios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define INF 0x3f3f3f3f
using namespace std;

const int N=1e5+10;
int a[N],ans[N];

void solve()
{
	map<int,int> mp;
	int n,q;
	cin>>n>>q;
	rep(i,1,n)
		cin>>a[i],mp[a[i]]++;
	
	int num=0;
	dec(i,n,1)
	{
		if(num<q)
		{
			if(a[i]>num)
				num++;
			ans[i]++;
		}
		else if(a[i]<=num)
			ans[i]++;
	}
	
	rep(i,1,n)
		cout<<ans[i];
	cout<<endl;
	memset(ans,0,sizeof ans);
}

D题链接

题目大意：

将数组 $a$ 排序后，另数组 $b$ 为 $b_i=a_{i+1}?a_i$ ，然后不断重复这个操作，直到最后所得一个数字。

解题思路：

用map来模拟删除的过程就可以，一开始是 $mp$ 修改后是 $mp1$ ，然后把 $mp=mp1$ ，然后继续重复这个过程就可以了

看了代码之后，最大的问题是不是就是时间复杂度问题？
实际上在 $logn$ 级别的时间就可以计算完

代码如下：

#include <bits/stdc++.h>
#define rep(a,b,c) for(int a=b;a<=c;a++)
#define dec(a,b,c) for(int a=b;a>=c;a--)
#define x first
#define y second
#define pb push_back
#define LL long long
#define ios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define INF 0x3f3f3f3f
#define PII pair<LL,LL>
#define pi 3.14159265358979323846
using namespace std;

void solve()
{
	int n;
	cin>>n;
	map<int,int> mp;
	
	rep(i,1,n)
	{
		int k;
		cin>>k;
		mp[k]++;
	}
	
	rep(i,1,n-1)//注意是n-1次
	{
		map<int,int> mp1;
		for(auto j=mp.begin();j!=mp.end();j++)
		{
			if(j->y>1)
				mp1[0]+=j->y-1;
			auto k=j;
			k++;
			if(k!=mp.end())
				mp1[k->first - j->first]++; 
		}
		mp=mp1;
	}
	
	cout<<mp.begin()->x<<endl;
}

恭喜自己蓝名啦！！！