Educational Codeforces Round 167(Div.2) A~D

A.Catch the Coin（思维）

题意：

Monocarp 参观了一家有街机柜的复古街机俱乐部。在那里，他对"抓硬币"游戏机产生了好奇。

游戏非常简单。屏幕上的坐标网格是这样的

$X$ 轴从左到右；
$Y$ 轴从下往上；
屏幕中心的坐标为 $(0, 0)$ 。

游戏开始时，角色位于中心位置，屏幕上出现了 $n$ 枚硬币，其中第 $i$ 枚硬币的坐标为 $x_i,y_i)$ 。所有硬币的坐标都不相同，也不等于 $(0, 0)$ 。

在一秒钟内，可以向八个方向之一移动角色。如果字符位于坐标 $(x, y)$ ，那么它可能最终到达坐标 $(x, y + 1)$ 、 $(x + 1, y + 1)$ 、 $(x + 1, y)$ 、 $(x + 1, y - 1)$ 、 $(x, y - 1)$ 、 $(x - 1, y - 1)$ 、 $(x - 1, y)$ 、 $(x - 1, y + 1)$ 中的任意一个。

如果角色最终在坐标处获得了一枚硬币，那么Monocarp就会收集这枚硬币。

在Monocarp移动之后，所有硬币都会下降 $1$ ，即从 $(x, y)$ 移动到 $(x, y - 1)$ 。我们可以假设游戏场地在所有方向上都是无限的。

Monocarp想要收集至少一枚硬币，但却无法决定收集哪枚硬币。请帮助他确定能否收集到每一枚硬币。

分析：

设一个硬币与原点的 $x$ 轴方向距离为 $d$ 。最优思路肯定是在开局的 $d$ 秒内走到与硬币 $x$ 坐标相同、 $y$ 坐标为 $- d$ 的位置。如果此时硬币已经掉到这个位置下方那就收集不到了，否则就肯定可以接到。

代码：

#include<bits/stdc++.h>

using namespace std;

int main() {
    int n, x, y;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> x >> y;
        int dist = (x == 0 ? 0 : abs(x));
        int yy = -dist;
        if (y - dist >= yy - 1)
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
    }
    return 0;
}

B.Substring and Subsequence（贪心）

题意：

给你两个字符串 $a$ 和 $b$ ，这两个字符串都由小写拉丁字母组成。

字符串的子串是从原始字符串中删除几个（可能是零）字符后得到的字符串。字符串的子串是该字符串的连续子串。

例如，考虑字符串 $aba c$ ：

$a 、 b 、 c 、 ab 、 aa 、 a c 、 ba 、 b c 、 aba 、 ab c 、 aa c 、 ba c$ 和 $aba c$ 是其子序列；
$a 、 b 、 c 、 ab 、 ba 、 a c 、 aba 、 ba c$ 和 $aba c$ 是它的子串。

你的任务是计算包含 $a$ 作为子串和 $b$ 作为子序列的字符串的最小可能长度。

分析：

考虑贪心，答案一定包含这两个字符串并加上一些字符，为使答案最短，要让添加的字符最少，即让 $a$ 和 $b$ 的公共子序列尽可能长，所以答案即为两个字符串长度之和减去最长公共子序列的长度。

观察数据范围较小，暴力寻找最长公共子序列，每次从 $b$ 的的一个字符开始向后与 $a$ 匹配， $s u m$ 记录当前区间的最长公共子序列， $s$ 记录 $a$ 和 $b$ 的最长公共子序列。

代码：

#include<bits/stdc++.h>

using namespace std;

void solve() {
    string a, b;
    cin >> a >> b;
    int n = a.size();
    int m = b.size();
    int s = 0;
    for (int i = 0, sum = 0; i < m; i++, s = max(s, sum), sum = 0)
        for (int j = 0, t = i; j < n; j++)
            if (a[j] == b[t]) {
                t++;
                sum++;
            }
    cout << n + m - s << endl;
}

int main() {
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

C.Two Movies（贪心）

题意：

某电影公司发行了 $2$ 部电影。有 $n$ 人观看了这 $2$ 部电影。我们知道每个人对第一部电影的态度（喜欢、中立或不喜欢）以及对第二部电影的态度。

如果要求某人为电影留下评论，那么

如果这个人喜欢这部电影，他就会留下好评，这部电影的评分就会增加 $1$ ；
如果此人不喜欢这部电影，则会留下差评，电影评分将降低 $1$ ；
否则，他们会留下中评，电影评分不会改变。

每个人都会评论一部电影，您可以为每个人选择评论哪部电影。

公司的评分是两部电影评分的最小值。您的任务是计算公司可能获得的最高评分。

分析：

本题我们采用贪心的思路，如果某人对两部电影评分不一样，显然取评分高的那一个。即如果是 $1$ 和 $0$ 或 $1$ 和 $- 1$ ，那么显然取 $1$ 。如果是 $0$ 和 $- 1$ ，显然取 $0$ 。

下面讨论评分一样的情况。对于 $0$ 和 $0$ ，取哪一个都没有影响，直接忽略。对于 $1$ 和 $1$ ，我们记录这种人的个数，在处理完评分不一样的人之后统一处理。由于我们要使最小值最大，所以优先将这种人的增加评分给较小的一部电影。否则不会影响最小值，显然不是最优方法。对于 $- 1$ 和 $- 1$ ，同理，我们记录这种人的个数，在处理完评分不一样的人之后统一处理。由于我们要使最小值最大，所以优先将这种人的减少评分给较大的一部电影。否则会减小最小值，不是最优情况。

代码：

#include<bits/stdc++.h>

typedef long long LL;
using namespace std;
const int MOD = 998244353;
LL n, a[300000], b[300000];

void solve() {
    LL x = 0, y = 0, cnt1 = 0, cnt2 = 0;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++)
        cin >> b[i];
    for (int i = 1; i <= n; i++) {
        if (a[i] > b[i])
            x += a[i];
        else if (a[i] < b[i])
            y += b[i];
        else if (a[i] == 1 && b[i] == 1)
            cnt1++;
        else if (a[i] == -1 && b[i] == -1)
            cnt2++;
    }
    while (cnt1) {
        if (x <= y)
            x++;
        else
            y++;
        cnt1--;
    }
    while (cnt2) {
        if (x >= y)
            x--;
        else
            y--;
        cnt2--;
    }
    cout << min(x, y) << endl;
}

int main() {
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

D.Smithing Skil（贪心、动态规划）

题意：

您正在玩一款著名的电脑游戏，在这款游戏中，您可以提升各种技能的等级。今天，你的重点是 "铸造"技能。你的战术显而易见：用金属锭锻造武器，然后将其熔化，部分返回材料。简单来说，每制造一件物品，你就能获得 $1$ 点经验值，而每熔化一件物品，你也能获得 $1$ 点经验值。

可以锻造的武器有 $n$ 种，金属锭有 $m$ 种。

花费 $a_i$ 个同类金属锭，你就可以打造一把 $i$ 类的武器。熔化一件（你之前制作过的） $i$ 阶级的武器会为你带来 $b_i$ 块与之相同类型的金属锭。

你有 $c_j$ 块 $j$ 类型的金属锭，而且你知道你可以用任何金属类型制作任何类型的武器。武器等级和金属类型的每种组合都可以使用任意次数。

制作和熔炼武器最多可以获得多少经验值？

分析：

观察题目发现要对每种金属求出最多能获得的经验数，然后相加。此外，一种装备锻造了之后一定会将其融化掉，因为熔掉获得材料和经验。我们注意到 $a_i−b_i$ 最小的装备是贡献最高的，因为消耗材料最少。在所有贡献最高的装备里面我们可以随便选取一种出来针对同一种金属不停地锻造再熔掉，直到因为剩余金属量 $a_i$ 而不能锻造为止。

观察数据范围发现 $a_i≤10^6$ ，当某种金属剩余量为 $x$ 时，我们的最优方案是在所有 $a_i≤x$ 的装备中选贡献最高的锻造。因此我们可以对所有 $10^6$ 的金属剩余量用一个简单的 $d p$ 预处理出这个剩余量所能挣到的经验。对于较大的剩余量 $c_k(k∈[1,m])$ ，先用贡献最高的装备把剩余量消耗到 $10^6$ 以下，然后调用预处理的值即可。

代码：

#include<bits/stdc++.h>

typedef long long LL;
using namespace std;
const int N = 1000010;
const int MOD = 998244353;

void sol(LL &a, LL b) {
    if (a > b)
        a = b;
}

LL n, m, a[N], b[N], c[N], add[N], dp[N];

int main() {
    ios::sync_with_stdio(false);
    for (int i = 0; i < N; i++) add[i] = 1e18;
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < n; i++) {
        cin >> b[i];
        b[i] = a[i] - b[i];
        sol(add[a[i]], b[i]);
    }
    for (int i = 0; i < m; i++) cin >> c[i];
    LL mn = 1e18;
    for (LL i = 1; i <= 1000003; ++i) {
        sol(mn, add[i]);
        if (mn <= i) dp[i] = dp[i - mn] + 1;
    }
    pair<LL, LL> opt = make_pair(1e18, 1e18);
    for (int i = 0; i < n; i++) opt = min(opt, make_pair(b[i], a[i]));
    LL ans = 0;
    for (int i = 0; i < m; i++) {
        if (c[i] >= opt.second) {
            ans += (c[i] - opt.second + opt.first - 1) / opt.first;
            c[i] -= (c[i] - opt.second + opt.first - 1) / opt.first * opt.first;
        }
        ans += dp[c[i]];
    }
    cout << ans * 2 << endl;
    return 0;
}