【CF补题】Codeforces Round #784 (Div. 4)C++代码

A.

#include<bits/stdc++.h>
using namespace std;
int a, b;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int k;
	cin >> k;
	while (k--)
	{
		int t;
		cin >> t;
		if (t <= 1399) cout << "Division 4\n";
		else if (t <= 1599) cout << "Division 3\n";
		else if (t <= 1899) cout << "Division 2\n";
		else  cout << "Division 1\n";
	}
	return 0;
}

B.

#include<bits/stdc++.h>
using namespace std;
int a[200001];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int t;
	cin >> t;
	while (t--)
	{
		int n;
		int x;
		bool flg = 0;
		memset(a, 0, sizeof(a));
		cin >> n;
		for (int i = 1; i <= n; i++)
		{
			cin >> x;
			a[x]++;
		}
		for (int i = 1; i <= n; i++)
		{
			if (a[i] >= 3)
			{
				cout << i << '\n';
				flg = 1;
				break;
			}
		}
		if (flg == 0)cout << "-1\n";
	}
	return 0;
}

C.

#include<bits/stdc++.h>
using namespace std;
int a[2], b[2];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int t;
	cin >> t;
	while (t--)
	{
		int n;
		int x;
		bool flg = 0;
		memset(a, 0, sizeof(a));
		memset(b, 0, sizeof(b));
		cin >> n;
		for (int i = 1; i <= n; i++)
		{
			cin >> x;
			if (i % 2 == 0)a[x % 2]++;
			else b[x % 2]++;
		}
		if (a[0] == 0 || a[1] == 0)
		{
			if (b[0] == 0 || b[1] == 0)
			{
				cout << "YES\n";
				flg = 1;
			}
		}
		if (flg == 0)cout << "NO\n";
	}
	return 0;
}

D.

#include<bits/stdc++.h>
using namespace std;
int a[2], b[2];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int t;
	cin >> t;
	while (t--)
	{
		int n;
		char c;
		int cnt1 = 0;
		int cnt2 = 0;
		bool flg = 0;
		memset(a, 0, sizeof(a));
		memset(b, 0, sizeof(b));
		cin >> n;
		for (int i = 1; i <= n; i++)
		{
			cin >> c;
			if (c == 'B')cnt1++;
			if (c == 'R')cnt2++;
			if (c == 'W')
			{
				if (cnt1 == 0 && cnt2 != 0 || cnt2 == 0 && cnt1 != 0)
				{
					flg = 1;
				}
				cnt1 = 0;
				cnt2 = 0;
			}
		}
		if (cnt1 == 0 && cnt2 != 0 || cnt2 == 0 && cnt1 != 0)
		{
			flg = 1;
		}
		if (flg == 1)cout << "NO\n";
		else cout << "YES\n";
	}
	return 0;
}

以上是比赛的时候做出来的呜呜呜，卡在E题了。

E。

（组合数学，容斥）有多少字符串对满足有一个位置的字符相同

通过一个矩阵数组来记录该字符串情况，然后枚举第一个字符的情况和第二个字符的情况

ps大佬的写法：ans=一对字符串中第一个字母相同的对数＋一对字符串中第二个字母相同的对数-两个字符串中两个字母都相同的个数。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll sum[200010];
int n, m;
int a[200][200];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int t;
	cin >> t;
	while (t--)
	{
		cin >> n;
		memset(a, 0, sizeof(a));
		char c1, c2;
		for (int i = 1; i <= n; i++)
		{
			cin >> c1 >> c2;
			a[c1 - 'a'][c2 - 'a']++;
		}
		ll ans=0;
		for (int i = 0; i <= 26; i++) 
		{
			ll now = 0;
			ll dq = 0;
			for (int j = 0; j <= 26; j++) 
			{
				dq += (now * a[i][j]);
				now += a[i][j];
			}
			ans += dq;
		}
		for (int j = 0; j <= 26; j++)
		{
			ll now = 0;
			ll dq = 0;
			for (int i = 0; i <= 26; i++)
			{
				dq += (now * a[i][j]);
				now += a[i][j];
			}
			ans += dq;
		}
		cout << ans << '\n';
	}
}

F.

关于为什么暴力能做，而我打cf的时候二分过不了这件事（我居然到比赛结束才意识到这题用二分有个鬼用啊喂！！）

用前缀和和后缀和处理后，查询那个相同的位置即可，判断是不是该位置A和B的吃的糖果数目要<=n 。

不要直接双重循环会tle

#include<bits/stdc++.h>
using namespace std;
long long now;
long long ans;
int sum[200010], sum2[200010], a[200010];
int n;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int t;
	cin >> t;
	int x;
	while (t--)
	{
		cin >> n;
		ans = 0;
		sum[0] = 0;
		for (int i = 1; i <= n; i++)
		{
			cin >> a[i];
			sum[i] = sum[i - 1] + a[i];
		}
		sum2[n + 1] = 0;
		for (int i = n; i >= 1; i--) {
			sum2[i] = sum2[i + 1] + a[i];
		}
		sort(sum2 + 1, sum2 + n + 1);//倒序，好直接i-i
		for (int i = 1; i <= n; i++)
		{
			int j = lower_bound(sum2 + 1, sum2 + n + 1, sum[i]) - sum2;
			if (sum[i] == sum2[j] && i + j <= n)
			{
				ans = i + j;
			}
		}
		cout << ans << '\n';
	}
	return 0;
}

G.