Codeforces Round #698 (Div. 2)

A、Nezzar and Colorful Balls

根据题意相同的标号的小球不可能标记为同一个颜色，只需要输出同一标号小球数量最多为多少就可以了

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
const int maxn = 1e6+10;
const int INF = 1e8;
const int mod = 1e9+7;
int a[maxn],cnt[maxn];
int main()
{
	int t;
	cin>>t;
	while(t--) {
		int n;
		cin>>n;
		int maxx = 0;
		memset(cnt,0,sizeof(cnt));
		for(int i=1;i<=n;i++) {
			cin>>a[i];
			cnt[a[i]]++;
		}
		for(int i=1;i<=110;i++) {
			maxx = max(maxx,cnt[i]);
		}
		cout<<maxx<<endl;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

B、Nezzar and Lucky Number

大于10d的数字肯定能由两个十进制数位上包含d的数组成一个是10d+10-d,一个是n-10(d-1)+d.所以大于10d的时候就可以直接YES小于的直接暴力每次减一个d判断剩下的满不满足条件就可以了

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
const int maxn = 1e6+10;
const int INF = 1e8;
const int mod = 1e9+7;
bool check(int n,int d) {
	while(n) {
		int res = n%10;
		if(res == d) return true;
		n/=10;
	}
	return false;
}
int main()
{
	int t;
	cin>>t;
	while(t--) {
		int t1,d;
		cin>>t1>>d;
		while(t1--) {
			int n;
			cin>>n;
			if(n>10*d || check(n,d)) cout<<"YES"<<endl;
			else {
				int flag = 0;
				while(n>0) {
					n-=d;
					if(check(n,d)) {
						flag = 1;
						cout<<"YES"<<endl;
						break;
					}
				}
				if(!flag) {
					cout<<"NO"<<endl;
				}
			}
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

C、Nezzar and Symmetric Array

动手模拟一下样例可以发现一个数与比他小的一对对称数的距离等于两倍的自己的大小比如4(-4)和3,-3或1,-1的差的绝对值之和都是8，那么这就是小于的情况，再看大于的时候1,-1或2,-2或3,-3与4(-4)的差的绝对值之和也都是8。通过分类讨论也就可以得出无论是大于还是小于每个ai和其余的2n-1个数的差的绝对值之和就是两方较大的那个的和的两倍，所以在已知di的情况下ai就等于（di/2-sum(比它大的所有|ai|之和))/n,所以从大到小由di算出ai再判断合法性就可以了。

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
const int maxn = 1e6+10;
const int INF = 1e8;
const int mod = 1e9+7;
ll d[maxn];
int main()
{
	int t;
	cin>>t;
	while(t--) {
		ll n;
		cin>>n;
		map<ll,ll,greater<ll> >mp;
		for(int i=1;i<=2*n;i++) {
			cin>>d[i];
			mp[d[i]]++;
		}
		int flag = 0;
		for(auto i:mp) {
			if(i.first%2 || i.second!=2) {
				flag = 1;
				break;
			}
		}
		if(flag) cout<<"NO"<<endl;
		else {
			ll sum = 0;
			for(auto i:mp) {
				ll res = i.first/2-sum;
				if(res<=0 || res%n ) {
					flag = 1;
					break;
				}
				sum+=res/n;
				n--;
			}
			if(flag) cout<<"NO"<<endl;
			else cout<<"YES"<<endl;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

B、Nezzar and Board

我们任意挑选4个数：x，y，p，q并将2·x-y和2·p-q加入到序列中，挑选出新增的两个数：2·x-y、2`·p-q得到2·(2·x-y)-(2·p-q)，化简即：x+(x-p)+2(x-y)-(p-q)。由此我们可以得到的值的范围是(ai-aj)经过线性组合后与ai的和能取到的所有数，判断k是否在这个范围内就可以了。

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
const int maxn = 1e6+10;
const int INF = 1e8;
const int mod = 1e9+7;
ll a[maxn];
int main()
{
	int t;
	cin>>t;
	while(t--) {
		ll n,k;
		cin>>n>>k;
		ll g;
		for(int i=1;i<=n;i++) {
			cin>>a[i];
			if(i == 2) g = a[i]-a[i-1];
			else g = __gcd(g,a[i]-a[i-1]);
		}
		int flag = 0;
		for(int i=1;i<=n;i++) {
			if(abs(k-a[i])%g == 0) {
				flag = 1;
				break;
			}
		}
		if(flag) cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
	} 
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32