Educational Codeforces Round 167 (Rated for Div. 2)(A~C)题解

A. Catch the Coin

 解题思路:

最终𝑥一定会相等，我们考虑直接到下面接住他。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define N 1000005
ll dp[N], w[N], v[N], h[N];
ll dis[1005][1005];
ll a, b, c, n, m, t;
ll ans, sum, num, minn = 1e9 + 7, maxx = 0;
struct node {
	ll a, b, c;
}f[N];
int main()
{
	cin >> t;
	while (t--)
	{
		cin >> a >> b;
		if (b>=-1) {
			cout << "YES" << endl;
		}
		else {
			cout << "NO" << endl;
		}
	}
	return 0;
}

B. Substring and Subsequence

解题思路:

由于 a 是肯定全部要出现的，因此只要找出在 a 中最多能匹配上 b 中的多少个字符

不难发现 b 中匹配的一定是连续的一段，因此可以暴力枚举区间然后暴力检验

代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define N 1000005
ll dp[N], w[N], v[N], h[N];
ll dis[1005][1005];
ll a, b, c, n, m, t;
ll ans, sum, num, minn = 1e9 + 7, maxx = 0;
struct node {
	ll a, b, c;
}f[N];
string s1, s2;
int main()
{
	cin >> t;
	while (t--)
	{
		cin >> s1 >> s2;
	    ans = 0;
		for (int i = 0; i < s2.size(); i++) {
			ll num1 = i, num2 = 0;
			for (int j = 0; j < s1.size(); j++) {
				if (s1[j] == s2[num1]) {
					num1++;
					num2++;
				}
			}
			ans = max(ans, num2);
		}
		
		cout << s1.size() + s2.size() - ans << endl;
	}
	return 0;
}

C. Two Movies

解题思路:

首先如果 ai,bi不同，则直接把评分加到较大的那个数上去一定是最优的，这个分析一下会发现对于所有情形成立

在此基础上可以先得到两部电影的评分，分别记为 x, y，然后考虑将剩下的1 1数量记为 X，-1 -1数量记为 Y

分类讨论一下加入 X 个 1 和 Y 个 −1 的影响即可，每次先把两个数做到平均一定是最优的

代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define N 1000005
ll dp[N], w[N], v[N], h[N];
ll dis[1005][1005];
ll a, b, c, n, m, t;
ll ans, sum, num, minn = 1e9 + 7, maxx = 0;
struct node {
	ll a, b, c;
}f[N];
string s1, s2;
int main()
{
	cin >> t;
	while (t--)
	{
		cin >> n;
		int x=0, y=0, X=0, Y=0;
		for (int i = 1; i <= n; i++)
			cin >> w[i];
		for (int j = 1; j <= n; j++)
			cin >> v[j];
		for (int i = 1; i <= n; i++) {
			if (w[i] != v[i]) {
				if (w[i] > v[i]) x+=w[i];
				else y+=v[i];
			}
			else {
				if (w[i] == 1) {
					X++;
				}
				else if (w[i]==-1) {
					Y++;
				}
			}
		}
		if (X <= abs(x - y)) {
			if (x <= y) x += X;
			else y += X;
		}
		else {
			int k = X - abs(x - y);
			maxx = max(x, y);
			x = y = maxx;
			x += k / 2, y += (k + 1) / 2;
		}
		if (Y <= abs(x - y)) {
			if (x <= y) y -= Y;
			else x -= Y;
		}
		else {
			int k = Y - abs(x - y);
			minn = min(x, y);
			x = y = minn;
			x -= k / 2, y -= (k + 1) / 2;
		}
		cout << min(x, y) << endl;
	}
	return 0;
}