Codeforces Round #784 (Div. 4)

A:Division?

略。。。

B:Triple Code:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

int main() {
	int t;
	scanf("%d", &t);
	while(t--) {
		map<int, int> cnt;
		int n;
		scanf("%d", &n);
		int ans = -1;
		for(int i = 0; i < n; i++) {
			int x;
			scanf("%d", &x);
			cnt[x]++;
			if(cnt[x] >= 3) {
				ans = x;
			}
		}
		printf("%d\n", ans);
	}
    return 0;
}

C:Odd/Even Increments

• 思路：

我们只需判断奇数位和偶数位上的数是否相等就可以了

Code:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

const int N = 65;

int a[N];

int main() {
	int t;
	scanf("%d", &t);
	while(t--) {
		int n;
		scanf("%d", &n);
		for(int i = 1; i <= n; i++) {
			scanf("%d", &a[i]);
		}
		if(n == 2) {
			puts("YES");
			continue;
		}
		bool flag = true;
		for(int i = 3; i <= n; i += 2) {
			if(a[i - 2] % 2 != a[i] % 2) {
				flag = false;
				break;
			}
		}
		for(int i = 4; i <= n; i += 2) {
			if(a[i - 2] % 2 != a[i] % 2) {
				flag = false;
				break;
			}
		}
		if(flag) puts("YES");
		else puts("NO");
	}
    return 0;
}

D:Colorful Stamp

• 思路：

我们只关心两个\(W\)（可以认为字符串之前和之后都存在一个\(W\)）之间的字符串，所以根据\(W\)拆分字符串。容易看出，除了全为\(P\)或\(R\)，我们可以将两个\(W\)之间的字符串染成任何情况。也就是说，我们需要判断两个\(W\)之间是否同时存在\(P\)和\(R\)。如果是，则\(YES\)，反之\(NO\)。
比赛的时候光想着模拟了，其实有更简单的方法。。

Code1(Contest Submission):

#include<bits/stdc++.h>//仅供参考。。。
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

int main() {
	int t;
	scanf("%d", &t);
	while(t--) {
		int n;
		string s;
		cin >> n >> s;
		if(n == 1) {
			if(s[0] == 'W') puts("YES");
			else puts("NO");
			continue;
		}
		if(n == 2) {
			if(s[0] == s[1]) {
				if(s[0] == 'W') puts("YES");
				else puts("NO");
			}
			else {
				if(s[0] == 'W' || s[1] == 'W') puts("NO");
				else puts("YES");
			}
			continue;
		}
		vector<int> v;
		v.push_back(-1);
		for(int i = 0; i < n; i++) {
			if(s[i] == 'W') v.push_back(i);
		}
		v.push_back(n);
		int len = int(v.size());
		bool flag = false;
		for(int i = 1; i < len; i++) {
			flag = false;
			if(v[i] - v[i - 1] == 1 && v[i] == n) {
				flag = true;
				break;
			}
			if(v[i] - v[i - 1] == 2) {
				break;
			}
			flag = true;
			for(int j = v[i - 1] + 2; j <= v[i] - 1; j++) {
				flag =  false;
				if(s[j - 1] != s[j]) {
					flag = true;
					break;
				}
			}
			if(!flag) {
				break;
			}
		}
		if(flag) puts("YES");
		else puts("NO");
	}
    return 0;
}

Code2(Normal)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

int main() {
	int t;
	scanf("%d", &t);
	while(t--) {
		int n;
		string s;
		cin >> n >> s;
		s = s + 'W';
		bool cntb = false, cntr = false;
		bool flag = false;
		for(int i = 0; i < n + 1; i++) {
			if(s[i] == 'W') {
				flag |= cntb ^ cntr;
				cntb = cntr = false;
			} else if(s[i] == 'B') {
				cntb = true;
			} else if(s[i] == 'R') {
				cntr = true;
			}
		}
		if(!flag) puts("YES");
		else puts("NO");
	}
    return 0;
}

E:2-Letter Strings

一会补。。。

F:Eating Candies

• Tag：Two pointers
• 思路：

看代码应该不难理解。。

Code:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

const int N = 2e5 + 5;

int a[N];

int main() {
	int t;
	scanf("%d", &t);
	while(t--) {
		int n;
		scanf("%d", &n);
		for(int i = 0; i < n; i++) {
			scanf("%d", &a[i]);
		}
		if(n == 1) {
			puts("0");
			continue;
		}
		int l = 0, r = n - 1;
		int suml = a[l], sumr = a[r];
		int ans = 0;
		while(l < r) {
			if(suml == sumr) {
				ans = l + 1 + n - r;
				if(l < n) {
					l++;
					suml += a[l];
				} else {
					r--;
					sumr += a[r];
				}
			}
			if(suml > sumr) {
				while(suml > sumr) {
					r--;
					sumr += a[r];
				}
			}
			else if(suml < sumr) {
				while(suml < sumr) {
					l++;
					suml += a[l];
				}
			}
		}
		printf("%d\n", ans);
	}
    return 0;
}

G:Fall Down

• 思路：

由于石头是竖直降落的，所以我们可以遍历每列。因为我们求的是石头最后降落的位置，所以从最后一行开始往上找。如果遇到了阻碍，那么说明离该阻碍最近的石头最低会落在阻碍的上面。同时我们要注意，如果阻碍的上面存在石头，我们要将最后降落的位置减一（原最后降落的位置存在石头）。

Code:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

const int N = 55;

char s[N][N];

int main() {
	int t;
	scanf("%d", &t);
	int n, m;
	while(t--) {
		scanf("%d%d", &n, &m);
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < m; j++) {
				cin >> s[i][j];
			}
		}
		for(int j = 0; j < m; j++) {
			int last = n - 1;
			for(int i = n - 1; i >= 0; i--) {
				if(s[i][j] == 'o') last = i - 1;
				else if(s[i][j] == '*') {
					swap(s[i][j], s[last][j]);
					last--;
				}
			}
		}
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < m; j++) {
				cout << s[i][j]; 
			}
			cout << "\n";
		}
	}
    return 0;
}

H:Maximal AND

一会补。。。