Codeforces Round #579 (Div. 3)

A-Circle of Students【暴力】

思路：

简单水题目，把数组多复制一串在后头，然后遇到1先向右搜索，然后向左搜索，解决了。

代码：

#include<bits/stdc++.h>
using namespace std;
 
int main() {
    
	int t;
	cin >> t;
	while(t--) {
    
		int n;
		int data[2000];
		cin >> n;
		for(int i = 0; i < n; i++) {
    
			cin >> data[i];
		}
		//向后复制一串
		for(int i = n; i < 2*n; i++) {
    
			data[i] = data[i-n];
		}
		
		int count = 1;
		int ans = 0;
		int flag = 0;
		//向右搜索
		for(int i = 0; i < 2*n; i++) {
    
			if(data[i] == 1) {
    
				count = 1;
				for(int j = i; j < 2*n; j++) {
    
					if(count == data[j]) {
    
						if(count == n) {
    
							flag = 1;
							break;
						}
						count++;
						continue;
					}
					else
						break;
				}
				if(flag == 1) {
    
					break;
				}
			}
		}
		if(flag == 1) {
    
			printf("YES\n");
			continue;
		}
		//向左搜索
		count = 1;
		for(int i = 2*n-1; i >= 0; i--) {
    
			if(data[i] == 1) {
    
				count = 1;
				for(int j = i; j >= 0; j--) {
    
					if(count == data[j]) {
    
						if(count == n) {
    
							flag = 1;
							break;
						}
						count++;
						continue;
					}
					else
						break;
				}
				if(flag == 1) {
    
					break;
				}
			}
		}
		if(flag == 1)
			printf("YES\n");
		else if(flag == 0)
			printf("NO\n");
	}
	return 0;
} 

B-Equal Rectangles

思路：

由于因数的性质，只有让最小的和最大的匹配，第二小的和第二大的匹配才能构造出相等的面积。并且还要判断一下边数是否能匹配。

代码：

#include<bits/stdc++.h>
using namespace std;
 
int main() {
    
	int t;
	cin >> t;
	while(t--) {
    
		int n;
		cin >> n;
		int a[4000];
		for(int i = 0; i < 4*n; i++) {
    
			cin >> a[i];
		}
		sort(a,a+4*n);
		//由于因数的性质，一定是最小的和最大的，第二小和第二大的组合，以此类推
		int p = 4*n-1;
		int temp = a[0] * a[p];
		int ans = 0;
		for(int i = 0; i < 2*n; i+=2) {
    
			if(a[i] * a[p] != temp) {
    
				ans = 1;
				break;
			}
			else
				p -= 2;
		}
		//保证所有边都是成对出现的
		for(int i = 0; i < 4*n; i+=2) {
    
			if(a[i] != a[i+1]) {
    
				ans = 1;
				break;
			}
		}
		if(ans == 1)
			printf("NO\n");
		else
			printf("YES\n");
	}
	return 0;
}

E-Boxers【桶排+贪心】

思路：

桶排计算出每个体重的选手的数量，接着让每个选手都先尽可能的降低体重，然后保持体重，最后才增加体重。不过，要特判一下体重为 1 的选手，因为体重不能为 0。

代码：

#include<string.h>
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
using namespace std;
#define ll long long
 
ll a[200000];
ll tp[150005];
ll tp2[150005];
 
int main() {
    
	ll n;
	scanf("%lld",&n);
	//这里是两个桶排，tp 记录的是不同体重选手的数量
	//tp2 记录的是某个体重是否被加入队伍中。
	memset(tp, 0, sizeof(tp));
	memset(tp2, 0, sizeof(tp2));
	
	for(int i = 0; i < n; i++) {
    
		scanf("%lld",&a[i]);
		tp[a[i]]++;
	}
	for(int i = 1; i < 150001; i++) {
    
		if(i == 1) {
    
		//这里特判体重为1的选手
			if(tp[i] != 0) {
    
				tp2[i]++;
				tp[i]--;
			}
			if(tp[i] != 0) {
    
				tp2[i+1]++;
				tp[i]--;
			}
		}
		else {
    
			if(tp[i] != 0) {
    
				//优先降低体重
				if(tp2[i-1] == 0) {
    
					tp2[i-1]++;
					tp[i]--;
				}
				//然后保持体重
				if(tp[i] != 0 && tp2[i] == 0) {
    
					tp[i]--;
					tp2[i]++;
				}
				//最后才是提升体重。
				if(tp[i] != 0 && tp2[i+1] == 0) {
    
					tp[i]--;
					tp2[i+1]++;
				}
			}
		}
	}
	ll ans = 0;
	for(int i = 0; i < 150005; i++) {
    
		if(tp2[i] != 0)
			ans++;
	}
	cout << ans << endl;
	
	return 0;
}