Educational Codeforces Round 167 (Rated for Div. 2)
A.Catch the Coin
题面翻译
题目描述
Monocarp参观了一家带有街机柜的复古街机俱乐部。人们对“接硬币”的柜子很好奇。
这个游戏非常简单。屏幕表示这样一个坐标网格:
- x轴从左向右;
- y轴从下向上;
-屏幕中心的坐标为(0,0)。
在游戏开始时，角色位于中间，屏幕上出现 n 硬币- 第i枚硬币的坐标为 (x_i, y_i) 。所有硬币的坐标是不同的，且不等于(0,0)。
在一秒钟内，Monocarp可以将角色移动到八个方向之一。如果字符是坐标(x, y),那么它可以在任何的最终坐标(x, y + 1),(x + 1, + 1),(x + 1, y),(x + 1, - 1),(x, y - 1),(x - 1, - 1),(x - 1, y),(x - 1, + 1)。
如果角色最终在坐标处获得一枚硬币，那么Monocarp就会收集这枚硬币。
在Monocarp移动之后，所有的硬币下降 1 ，也就是说，它们从 (x, y) 移动到 (x, y - 1) 。你可以假设游戏场在所有方向上都是无限的。
Monocarp想要收集至少一枚硬币，但无法决定去拿哪枚硬币。帮助他决定，对于每一枚硬币，他是否能收集到。
输入格式
第一行包含一个整数 n ( 1 \le n \le 500 )——硬币的数量。
在接下来 n 行的 i -第一行中，写了两个整数 x_i 和 y_i ( -50 \le x_i, y_i \le 50 ) - i -硬币的坐标。所有硬币的坐标都不一样。没有硬币位于(0,0)。
输出格式
对于每个硬币，如果Monocarp可以收集到，则打印“YES”。否则打印“NO”。
提示
注意例子中的第二枚硬币。Monocarp可以先从(0,0)移动到(-1，-1)。然后硬币下降了1美元，最终是(- 2,2)美元。最后，Monocarp移动到(- 2,2)并收集硬币。
模拟一下就知道，y 轴上去捡硬币的速度和硬币下降的速度是一样的，因此只要 y 轴上的坐标比 0 低了超过 1 的距离就不可以。
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6 + 9;
#define int long long
const int MOD = 998244353;
int qmi(int a, int b, int p) {
int res = 1;
while (b) {
if (b & 1) res = res * a % p;
a = a * a % p;
b >>= 1;
}
return res;
}
int inv(int x) {return qmi(x, MOD - 2, MOD);}
int gcd(int a, int b) {return b > 0 ? gcd(b, a % b) : a;}
int lcm(int a, int b) {return a / gcd(a, b) * b;}
int n;
int x[N], y[N];
void solve() {
cin >> n;
for (int i = 1; i <= n; ++ i) cin >> x[i] >> y[i];
for (int i = 1; i <= n; ++ i) {
if (y[i] <= -2) cout << "NO\n";
else cout << "YES\n";
}
}
signed main() {
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int _ = 1;
//cin >> _;
while (_--) solve();
return 0;
}
B.Substring and Subsequence
题目描述
给您两个字符串 a和b ，这两个字符串都由小写拉丁字母组成。
字符串的子串是从原始字符串中删除几个(可能是零)字符后得到的字符串。字符串的子串是该字符串的连续子串。
例如，考虑字符串 abac：
- a、b、c、ab、aa、ac、ba、bc、aba、abc、aac、bac 和 abac 是其子序列；
- a、b、c、ab、ba、ac、aba、bac 和 abac 是它的子串。
你的任务是计算包含a 作为子串和b 作为子序列的字符串的最小可能长度。
输入格式
输入
第一行包含一个整数 t(1 \le t \le 10^3 ) - 测试用例数。
每个测试用例的第一行包含一个由小写拉丁字母组成的字符串 a (1 \le |a| \le 100 )。
每个测试用例的第二行包含一个由小写拉丁字母组成的字符串 b(1 \le |b| \le 100 )。
输出格式
输出
对于每个测试用例，打印一个整数 - 包含 a 作为子串和 b作为子串的字符串的最小可能长度。
提示
在下面的示例中，与等于 b 的子序列相对应的字符用粗体标出。
在第一个例子中，可能的答案之一是 caba。
在第二个例子中，可能的答案之一是 ercf。
在第三个例子中，可能的答案之一是mmm。
在第四个例子中，其中一个可能的答案是 contest。
在第五个例子中，可能的答案之一是abcdefg。
思路
收获到了，贪心匹配，是这样用的。只需要看看b中的字符有几个能和a匹配的，最后二者长度相加再减去匹配的长度即可。判断匹配的方法很重要。
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6 + 9;
#define int long long
const int MOD = 998244353;
int qmi(int a, int b, int p) {
int res = 1;
while (b) {
if (b & 1) res = res * a % p;
a = a * a % p;
b >>= 1;
}
return res;
}
int inv(int x) {return qmi(x, MOD - 2, MOD);}
int gcd(int a, int b) {return b > 0 ? gcd(b, a % b) : a;}
int lcm(int a, int b) {return a / gcd(a, b) * b;}
int n;
void solve() {
string a, b;
cin >> a >> b;
int ans = 0;
for (int i = 0; i < b.size(); ++ i) {
int match = 0;
for (auto c : a) {
if (c == b[i + match]) match ++;
}
ans = max(ans, match);
}
cout << b.size() - ans + a.size() << "\n";
}
signed main() {
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int _ = 1;
cin >> _;
while (_--) solve();
return 0;
}
C.Two Movies
题面翻译
题目描述
一个公司发行了两部电影。现在有 n 位观众，每个人都会看一部这个公司的电影。
每位观众都会对其看的电影进行评分，分数 a_i,b_i\in\{-1，0，1\}。电影的总评分是看了此电影的观众对此电影的评分总和。公司的最终得分是这两部电影的总评分的较小值。
已知这些观众对两部电影的评价，你需要给每个人推荐一部电影，使公司的最终得分最大。求这个最大值。
输入格式
第一行一个整数 t（1\leqslant t \leqslant 10^4），代表输入数据组数。
接下来，对于每组数据，第一行一个整数 n （1 \leqslant n \leqslant 2 \times 10 ^ 5,\sum n \leqslant2\times10^5），表示观众数。
第二行 n 个整数 a_i，代表每位观众对第一部电影的评价（ -1 \leqslant a_i \leqslant 1 ）。
第三行 n 个整数 b_i，代表每位观众对第二部电影的评价（ -1 \leqslant b_i \leqslant 1 ）。
输出格式
一行一个整数，代表公司最终得分的最大值。
样例 #1
样例输入 #1
4
2
-1 1
-1 -1
1
-1
-1
5
0 -1 1 0 1
-1 1 0 0 1
4
-1 -1 -1 1
-1 1 1 1
样例输出 #1
0
-1
1
1
思路
这道题看起来就很简单，这场像是贪心专场，要最大化两者的最小值，那我就一定会评分时尽量让小的多评分，如果两个评分不相同，那只用评价大的就行，如果相同，确认这个是 -1 还是 1，让大的 -1， 小的 + 1，如此最大化二者的最小值。
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6 + 9;
#define int long long
const int MOD = 998244353;
int qmi(int a, int b, int p) {
int res = 1;
while (b) {
if (b & 1) res = res * a % p;
a = a * a % p;
b >>= 1;
}
return res;
}
int inv(int x) {return qmi(x, MOD - 2, MOD);}
int gcd(int a, int b) {return b > 0 ? gcd(b, a % b) : a;}
int lcm(int a, int b) {return a / gcd(a, b) * b;}
int n, a[N], b[N];
void solve() {
cin >> n ;
int cnt1 = 0, cnt2 = 0;
for (int i = 1; i <= n; ++ i) cin >> a[i];
for (int i = 1; i <= n; ++ i) cin >> b[i];
int ans = 0;
int pre = 0, las = 0;
for (int i = 1; i <= n; ++ i) {
if (a[i] > b[i]) cnt1 += a[i];
else if (a[i] < b[i]) cnt2 += b[i];
else {
pre += a[i] > 0;
las += a[i] < 0;
}
}
while (pre --) {
if (cnt1 < cnt2) cnt1 ++;
else cnt2 ++;
}
while (las --) {
if (cnt1 < cnt2) cnt2 --;
else cnt1 --;
}
cout << min(cnt1, cnt2) << "\n";
}
signed main() {
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int _ = 1;
cin >> _;
while (_--) solve();
return 0;
}
