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;
}