Codeforces Global Round 2

07 April 2019 | Duanyll | Tags: OI 题解

人生第一次rated的CF比赛，难度Div2到Div1都有，题比较多，像我这种蒟蒻就只能做前五道题了……

感觉做前面的题的时候要相信直觉，不要想太多（时间只有两小时）

A. Ilya and a Colorful Walk

签到题，直接两边各自往中间走就对了

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;

const int MAXN = 3e5+10;

int c[MAXN];

int main(){
	int n;
	cin >> n;
	for(int i = 1;i <= n;i++){
		cin >> c[i];
	}
	int l = 1,r = n;
	while(c[l] == c[r]){
		l++;
	}
	int ans1 = r-l;
	l = 1,r = n;
	while(c[l] == c[r]){
		r--;
	}
	cout << max(r-l,ans1) << endl;
}

B. Alyona and a Narrow Fridge

明显二分，判断时先排序然后两两配对，奇数个让最小的一个单出来更优。

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;

const int MAXN = 1e3+10;

typedef long long int64;

int64 a[MAXN];
int64 tmp[MAXN];

int64 n,h;

bool check(int64 x){
	if(x == 0 || x > n){
		return false;
	}
	memcpy(tmp,a,sizeof a);
	sort(tmp+1,tmp+x+1);
	int64 ans = 0;
	for(int i = x;i>=2;i-=2){
		ans += max(tmp[i],tmp[i-1]);
	}
	if(x & 1){
		ans += tmp[1];
	}
	return ans <= h;
}

int main(){
	cin >> n >> h;
	for(int i = 1;i<=n;i++){
		cin >> a[i];
	}
	int64 l = 0,r = n+1;
	while(l < r){
		int64 mid = (l+r+1) >> 1;
		if(check(mid)){
			l = mid;
		}else{
			r = mid-1;
		}
	}
	cout << l << endl;
}

注意开int64。

C. Ramesses and Corner Inversion

容易想到两个矩阵先取一个异或，再怎么判断奇偶性。

观察发现异或后每行上一定有偶数个，每列上也有偶数个，并且似乎这就是充要条件了，赛场上没有找到反例。

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;

const int MAXN = 510;

int a[MAXN][MAXN];
int b[MAXN][MAXN];
int d[MAXN][MAXN];

int n,m;

int main(){
	cin >> n >> m;
	for(int i = 1;i<=n;i++){
		for(int j = 1;j<=m;j++){
			cin >> a[i][j];
		}
	}
	int cnt1 = 0;
	for(int i = 1;i<=n;i++){
		for(int j = 1;j<=m;j++){
			cin >> b[i][j];
			d[i][j] = a[i][j]^b[i][j];
			cnt1 += d[i][j];
		}
	}
//	if(cnt1 % 4 != 0){
//		cout << "No" << endl;
//		return 0;
//	}else{
		for(int i = 1;i<=n;i++){
			int cntnow = 0;
			for(int j = 1;j<=m;j++){
				cntnow += d[i][j];
			}
			if(cntnow & 1){
				cout << "No" << endl;
				return 0;
			}
		}
		for(int j = 1;j<=m;j++){
			int cntnow = 0;
			for(int i = 1;i<=n;i++){
				cntnow += d[i][j];
			}
			if(cntnow & 1){
				cout << "No" << endl;
				return 0;
			}
		}
		cout << "Yes" << endl;
//	}
}

D. Frets On Fire

生词太多，花了好久才读懂题意……

复杂度明显qlogn

详细解释：咕咕咕，看代码吧。

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;

typedef long long int64;

const int64 MAXN = 1e5+10;
const int64 INF = 0x3f3f3f3f3f3f3f3fll;

int64 s[MAXN],d[MAXN],sum[MAXN];

int main(){
	int n;
	cin >> n;
	for(int i = 1;i<=n;i++){
		cin >> s[i];
	}
	sort(s+1,s+n+1);
	for(int i = 2;i<=n;i++){
		d[i-1] = s[i] - s[i-1];
	}
	sort(d+1,d+n);
	for(int i = 1;i<n;i++){
		sum[i] = sum[i-1] + d[i];
	}
	d[0] = INF;
	int q;
	cin >> q;
	for(int i = 1;i<=q;i++){
		int64 L,R;
		cin >> L >> R;
		int64 x = R-L+1;
		int l = 0,r = n-1;
		while(l < r){
			int mid = (l+r+1) >> 1;
			if(d[mid] < x){
				l = mid;
			}else{
				r = mid-1;
			}
		}
		cout << n*x - l*x + sum[l] << ' ';
	}
	cout << endl;
}

E. Pavel and Triangles

显然，成立的情况要么一短两长，要么等边三角形。于是考虑贪心，应该先保证一短两长的情况再剩下的里面找等边，才能保证剩下的1,2最少；如果像我一开始的做法就可能剩下大量未匹配到2的1，不够优秀。

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;

typedef long long int64;

const int MAXN = 3e5+10;

int64 a[MAXN];

int main(){
	int n;
	cin >> n;
	for(int i = 1;i<=n;i++){
		cin >> a[i];
	}
	int64 ans = a[1]/3,res = a[1]%3;
	for(int i = 2;i<=n;i++){
		if(res <= a[i]/2){
			ans += res;
			a[i] -= res*2;
			ans += a[i] / 3;
			res = a[i] % 3;
		}else{
			ans += a[i]/2;
			res -= a[i]/2;
			res += a[i]%2;
		}
	}
//	for(int i = 1;i<=n;i++){
//		ans += a[i]/3;
//		a[i] %= 3;
//	}
//	int64 cnt1 = 0,cnt2 = 0;
//	for(int i = 1;i<=n;i++){
//		if(a[i] == 1){
//			cnt1++;
//		}else if(a[i] == 2){
//			if(cnt1 >= 1){
//				cnt1--;
//				ans++;
//			}else{
//				cnt2++;
//			}
//		}
//	}
//	ans += (cnt2 / 3) * 2;
//	if(cnt2 % 3 == 2){
//		ans++;
//	}
	cout << ans << endl;
}

后面的图论和DP就不在我的能力范围之内了，看来我还是只会二分贪心……