比赛链接：https://codeforces.com/contest/1409

A. Yet Another Two Integers Problem

题意

给出两个数 $a$ 和 $b$，有以下两种操作：

$a+=k$
$a-=k$
$k \in [1, 10]$

问将 $a$ 变为 $b$ 最少需要操作多少次。

题解

$a,b$ 之差的绝对值对 $10$ 取上整。

代码

#include <bits/stdc++.h>

using namespace std;

void solve() {

    int a, b;

    cin >> a >> b;

    cout << (abs(b - a) + 9) / 10 << "\n";

}

int main() {

    int t;

    cin >> t;

    while (t--) solve();

}

B. Minimum Product

题意

给出两个数 $a$ 和 $b$，每次可以选择一个数减一，该操作最多执行 $k$ 次，同时要求 $a$ 不能小于 $x$，$b$ 不能小于 $y$，问 $a \cdot b$ 的最小值。

题解

如果给一个数减一，最佳方案就是一直给它减一，减到底后再减另一个数。

然后枚举先减 $a$ 还是先减 $b$ 即可。

代码一

#include <bits/stdc++.h>

using namespace std;

void solve() {

    int a, b, x, y, n;

    cin >> a >> b >> x >> y >> n;

    auto cal = [](int a, int b, int x, int y, int n) {

        int mi = min(n, a - x);

        n -= mi;

        a -= mi;

        mi = min(n, b - y);

        n -= mi;

        b -= mi;

        return 1ll * a * b;

    };

    cout << min(cal(a, b, x, y, n), cal(b, a, y, x, n)) << "\n";

}

int main() {

    int t;

    cin >> t;

    while (t--) solve();

}

代码二

#include <bits/stdc++.h>

using namespace std;

void solve() {

    int a, b, x, y, n;

    cin >> a >> b >> x >> y >> n;

    auto cal = [&](int a, int b, int x, int y) {

        int da = min(n, a - x);

        int db = min(n - da, b - y);

        return 1ll * (a - da) * (b - db);

    };

    cout << min(cal(a, b, x, y), cal(b, a, y, x)) << "\n";

}

int main() {

    int t;

    cin >> t;

    while (t--) solve();

}

C. Yet Another Array Restoration

题意

给出一个数组的大小 $n$ 和其中的两个元素 $x,y(x<y)$，试还原这个数组，要求：

数组中有 $n$ 个不同的正整数
数组排序后相邻元素之差相等
数组中的最大值尽可能地小

题解

数组相邻元素之差一定是 $y-x$ 的因子，据此分为以下三种情况：

因子过小，$x$ 到 $y$ 间可以容纳的元素个数大于 $n-2$，继续寻找更大的因子
因子适中，$x$ 到 $y$ 间可以容纳的元素个数等于 $n-2$，此时以 $x$ 为起点，因子大小为步长输出 $n$ 次即可
因子过大，$x$ 到 $y$ 间可以容纳的元素个数小于 $n-2$，因为最大值要尽量小，所以应尽可能地向 $x$ 的左端拓展正起点

代码

#include <bits/stdc++.h>

using namespace std;

void solve() {

    int n, x, y;

    cin >> n >> x >> y;

    int len = y - x;

    for (int p = 1; p <= len; p++) {

        if (len % p == 0) {

            int can_hold = len / p - 1;

            if (can_hold > n - 2) {

                continue;

            } else if (can_hold == n - 2) {

                for (int i = x; i <= y; i += p)

                    cout << i << " \n"[i == y];

                return;

            } else {

                int extra = n - 2 - can_hold;

                int cnt = 0;

                for (int i = x - p * min(extra, x / p - (x % p == 0)); cnt < n; i += p)

                    cout << i << " \n"[++cnt == n];

                return;

            }

        }

    }

}

int main() {

    int t;

    cin >> t;

    while (t--) solve();

}

D. Decrease the Sum of Digits

题意

给出一个数 $n$，每次可以给 $n$ 加上 $1$，找出使得 $n$ 的数位之和 $\le s$ 的最少操作数。

题解

给一个数位操作最终一定会使该数位的值变为 $0$（否则会一直增加数位之和），从低位到高位模拟即可。

代码

#include <bits/stdc++.h>

using namespace std;

int sum(string s) {

    int res = 0;

    for (char c : s) res += c - '0';

    return res;

}

void solve() {

    string n;

    int s;

    cin >> n >> s;

    long long ans = 0, p = 1;

    n = "0" + n;

    for (int i = n.size() - 1; sum(n) > s; i--) {

        ans += ('9' + 1 - n[i]) * p;

        n[i] = '0';

        ++n[i - 1];

        p *= 10;

    }

    cout << ans << "\n";

}

int main() {

    int t;

    cin >> t;

    while (t--) solve();

}

E. Two Platforms

题意

给出一个平面 $n$ 个点的坐标，有两个长为 $k$ 的平台，每个平台可以选择一个位置固定放置，问当所有点同时开始下落后，两个平台加起来最多可以接到多少个点。

题解

因为平台的纵坐标可以无限低所以只考虑横坐标即可。

将点的横坐标排序并计算两个 $dp$ 数组：

$dp1$ 以该点为起点放置平台可以接到多少个点
$dp2$ 以该点或之后的点为起点放置平台最多可以接到多少个点

枚举第一个平台的起点 $i$，然后找到第一个坐标大于 $x+k$ 的点 $j$，答案即 $max(dp1[i] + dp2[j])$ 。

代码一

二分查找点 $j$

#include <bits/stdc++.h>

using namespace std;

void solve() {

    int n, k;

    cin >> n >> k;

    vector<int> x(n), y(n);

    for (int i = 0; i < n; i++)

        cin >> x[i];

    for (int i = 0; i < n; i++)

        cin >> y[i];

    sort(x.begin(), x.end());

    vector<int> dp1(n);

    for (int i = 0; i < n; i++) {

        int j = upper_bound(x.begin(), x.end(), x[i] + k) - x.begin();

        dp1[i] = j - i;

    }

    vector<int> dp2(dp1);

    for (int i = n - 2; i >= 0; i--)

        dp2[i] = max(dp2[i], dp2[i + 1]);

    int ans = 0;

    for (int i = 0; i < n; i++) {

        int j = upper_bound(x.begin(), x.end(), x[i] + k) - x.begin();

        ans = max(ans, dp1[i] + (j < n ? dp2[j] : 0));

    }

    cout << ans << "\n";

}

int main() {

    int t;

    cin >> t;

    while (t--) solve();

}

代码二

双指针查找点 $j$

#include <bits/stdc++.h>

using namespace std;

void solve() {

    int n, k;

    cin >> n >> k;

    vector<int> x(n), y(n);

    for (int i = 0; i < n; i++)

        cin >> x[i];

    for (int i = 0; i < n; i++)

        cin >> y[i];

    sort(x.begin(), x.end());

    vector<int> dp1(n);

    for (int i = 0, j = 0; i < n; i++) {

        while (j < n and x[j] <= x[i] + k)

            ++j;

        dp1[i] = j - i;

    }

    vector<int> dp2(dp1);

    for (int i = n - 2; i >= 0; i--)

        dp2[i] = max(dp2[i], dp2[i + 1]);

    int ans = 0;

    for (int i = 0, j = 0; i < n; i++) {

        while (j < n and x[j] <= x[i] + k)

            ++j;

        ans = max(ans, dp1[i] + (j < n ? dp2[j] : 0));

    }

    cout << ans << "\n";

}

int main() {

    int t;

    cin >> t;

    while (t--) solve();

}

F. Subsequences of Length Two

题意

给出两个小写字母串 $s$ 和 $t$，$t$ 长为 $2$。每次可以替换 $s$ 中的一个字母，该操作最多执行 $k$ 次，问 $t$ 作为 $s$ 的子序列最多可以出现多少次。

题解

$dp[i][j][k]$ 为前 $i$ 位操作 $j$ 次后有 $k$ 个 $t_0$ 时的子序列个数。

代码

#include <bits/stdc++.h>

using namespace std;

constexpr int INF = 1e9;

void chmax(int &x, int y) {

    x = max(x, y);

}

int main() {

    int n, k;

    cin >> n >> k;

    string s, t;

    cin >> s >> t;

    vector<vector<vector<int>>> dp(n + 1, vector<vector<int>>(n + 1, vector<int>(n + 1, -INF)));

    dp[0][0][0] = 0;

    for (int i = 0; i < n; i++) {

        for (int ck = 0; ck <= k; ck++) {

            for (int cnt0 = 0; cnt0 <= n; cnt0++) {

                if (dp[i][ck][cnt0] == -INF) continue;

                int e0 = s[i] == t[0];

                int e1 = s[i] == t[1];

                int e01 = t[0] == t[1];

                //不操作

                chmax(dp[i + 1][ck][cnt0 + e0], dp[i][ck][cnt0] + (e1 ? cnt0 : 0));

                if (ck < k) {

                    //s[i]变为t[0]

                    chmax(dp[i + 1][ck + 1][cnt0 + 1], dp[i][ck][cnt0] + (e01 ? cnt0 : 0));

                    //s[i]变为t[1]

                    chmax(dp[i + 1][ck + 1][cnt0 + e01], dp[i][ck][cnt0] + cnt0);

                }

            }

        }

    }

    cout << *max_element(dp[n][k].begin(), dp[n][k].end()) << "\n";

}

巴特西

Codeforces Round #667 (Div. 3)