Codeforces Round 933(Div.3) A~F

A.Rudolf and the Ticket（暴力）

题意：

鲁道夫要去拜访伯纳德，他决定乘坐地铁去找他。车票可以在接受两个硬币的机器上购买，这两个硬币的总和不超过 $k$ 。

鲁道夫有两个装硬币的口袋。左边口袋里有 $n$ 枚面值为 $b_1,b_2,\dots,b_n$ 的硬币。右边口袋里有 $m$ 枚面值为 $c_1,c_2,\dots,c_m$ 的硬币。他想从左边口袋和右边口袋各取出一枚硬币（共两枚）。

请帮助鲁道夫判断有多少种方法可以选择序号 $f$ 和 $s$ ，从而使 $b_f+c_s\le k$ 。

分析：

数据量较小，暴力枚举所有方案然后判断是否合法即可。

代码：

#include<bits/stdc++.h>

using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, m, k;
        cin >> n >> m >> k;
        vector<int> b(n), c(m);
        for (int i = 0; i < n; ++i)cin >> b[i];
        for (int i = 0; i < m; ++i)cin >> c[i];
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (b[i] + c[j] <= k)ans++;
            }
        }
        cout << ans << endl;
    }
    return 0;
}

B.Rudolf and 121（贪心）

题意：

Rudolf有一个由 $n$ 个整数组成的数组 $a$ ，元素的编号从 $1$ 到 $n$ 。

在一次操作中，他可以选择序号 $i$ ( $2\le i\le n-1$ )并赋值：

$a_{i-1}=a_{i-1}-1$
$a_i=a_i-2$
$a_{i+1}=a_{i+1}-1$

鲁道夫可以任意多次使用这个运算。任何索引 $i$ 都可以使用 $0$ 次或更多次。

他能用这个运算使数组中的所有元素都等于零吗？

分析：

从前往后操作使 $a_{i-1}=0$ ，若 $a_i$ 小于 $0$ 则不行。

代码：

#include<bits/stdc++.h>

using namespace std;

void solve() {
    int n;
    cin >> n;
    int a[n + 1];
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 2; i < n; i++) {
        int t = a[i - 1];
        if (t < 0) {
            cout << "NO" << endl;
            return;
        }
        a[i] -= 2 * t;
        a[i + 1] -= t;
    }
    if (a[n - 1] == 0 && a[n] == 0) {
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }
}

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

C.Rudolf and the Ugly String（贪心）

题意：

鲁道夫有一个长度为 $n$ 的字符串 $s$ 。如果字符串 $s$ 包含子串 $^\dagger$ "pie"或子串"map"，鲁道夫就会认为这个字符串 $s$ 很丑，否则字符串 $s$ 将被视为优美字符串。

例如，“ppiee”、“mmap”、“dfpiefghmap"是丑字符串，而"mathp”、"ppiiee"是优美字符串。

鲁道夫希望通过删除一些字符来缩短字符串 $s$ 使其美观。

主角不喜欢吃力，所以他要求你删除最少的字符，使字符串变得漂亮。他可以删除字符串中任何位置的字符（不仅仅是字符串的开头或结尾）。

$^\dagger$ 如果字符串 $b$ 中存在等于 $a$ 的连续字符段，则字符串 $a$ 是 $b$ 的子串。

分析：

发现"pie"和"map"都含有"p"，因此可以遇到两者就删除"p"。

代码：

#include<bits/stdc++.h>

using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        string s;
        cin >> s;
        int ans = 0;
        vector<int> mp(n + 1, 0);
        string t1 = "map";
        string t2 = "pie";
        for (int i = 0; i < n - 2; i++) {
            if (mp[i] == 1) {
                continue;
            }
            if (s.substr(i, 3) == t1) {
                ans++;
                mp[i + 2] = 1;
            } else if (s.substr(i, 3) == t2) {
                ans++;
                mp[i] = 1;
            }
        }
        cout << ans << endl;
    }
    return 0;
}

D.Rudolf and the Ball Game（模拟）

题意：

鲁道夫和伯纳德决定和朋友们玩一个游戏。 $n$ 人站成一圈，开始互相扔球。他们按顺时针顺序从 $1$ 到 $n$ 依次编号。

我们把球从一个人向他的邻居移动称为一次过渡。移动可以顺时针或逆时针进行。

我们把从玩家 $y_1$ 到玩家 $y_2$ 的顺时针（逆时针）距离称为从玩家 $y_1$ 到玩家 $y_2$ 所需的顺时针（逆时针）转换次数。例如，如果 $n = 7$ ，那么从 $2$ 到 $5$ 的顺时针距离是 $3$ ，而从 $2$ 到 $5$ 的逆时针距离是 $4$ 。

最初，球在编号为 $x$ 的玩家的手中（玩家按顺时针方向编号）。在第 $i$ 次移动中，持球者将其投掷到 $r_i$ 距离处（ $1≤r_i≤n−1$ ），方向可以是顺时针或逆时针。例如，如果有 $7$ 名玩家，并且第 $2$ 名玩家接到球后将其投出 $5$ 个距离，则球将被第 $7$ 名玩家（顺时针投掷），或者第 $4$ 名玩家抓住（逆时针投掷）。下面显示了此示例的插图。

由于下雨，比赛在 $m$ 次投掷后中断。雨停后，大家又聚在一起继续比赛。但是，没有人记得球在谁手里。但是，伯纳德记住了每次投掷的距离和一些投掷的方向（顺时针或逆时针）。

鲁道夫请您帮助他，根据伯纳德提供的信息，计算出 $m$ 次抛球后可能拿到球的队员人数。

分析：

用 $se t$ 维护下当前可能在的地方，模拟即可。

代码：

#include<bits/stdc++.h>

using namespace std;

void solve() {
    int n, m, x;
    cin >> n >> m >> x;
    set<int> se;
    se.insert(x);
    set<int> t;
    for (int i = 0; i < m; ++i) {
        int d;
        char c;
        cin >> d >> c;
        for (auto v: se) {
            if (c == '0') {
                int y = (v + d) % n;
                if (y == 0)
                    y = n;
                t.insert(y);
            } else if (c == '1') {
                int y = (v - d + n) % n;
                if (y == 0)
                    y = n;
                t.insert(y);
            } else {
                int y = (v + d) % n;
                if (y == 0)
                    y = n;
                t.insert(y);
                y = (v - d + n) % n;
                if (y == 0)
                    y = n;
                t.insert(y);
            }
        }
        se = t;
        t.clear();
    }
    cout << se.size() << endl;
    for (auto v: se)
        cout << v << " ";
    cout << endl;
}

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

E.Rudolf and k Bridges（动态规划）

题意：

伯纳德喜欢拜访鲁道夫，但他总是迟到。问题是伯纳德必须乘渡船过河。鲁道夫决定帮助他的朋友解决这个问题。

这条河是由 $n$ 行和 $m$ 列组成的网格。第 $i$ 行和第 $j$ 列的交点数字 $a_{i,j}$ 表示相应单元格的深度。第一列和最后一列的所有单元格都对应河岸，因此它们的深度为 $0$ 。

河流可能是这样的。

鲁道夫可以选择 $(i,1),(i,2),\ldots,(i,m)$ 行，并在其上架桥。在该行的每个单元格中，他都可以为桥安装一个桥墩。在第 $(i, j)$ 格安装桥墩的成本为 $a_{i,j}+1$ 。安装桥墩必须满足以下条件：

必须在单元格 $(i, 1)$ 中安装一个桥墩；
单元格 $(i, m)$ 中必须安装一个桥墩；
任何一对相邻桥墩之间的距离不得大于 $d$ 。桥墩 $i,j_1)$ 和 $i,j_2)$ 之间的距离为 $j_1-j_2|-1$ 。

只建一座桥是很无聊的。因此，鲁道夫决定在河道的连续几行上建造 $k$ 座桥，即选择一些 $i$ （ $1\le i\le n-k+1$ ），独立建造 $k$ 座桥。( $1\le i\le n-k+1$ )，并在每一行 $i,i+1,\ldots,i+k-1$ 上独立建造一座桥。请帮助鲁道夫尽量减少安装桥墩的总成本。

分析：

计算在第 $i$ 行造桥的最小代价，考虑 $d p$ ，状态转移方程为 $dp_j=dp_{k}+a_{i,j}+1$ ， $k$ 为 $[j - k - 1, j - 1]$ ，枚举 $k$ 的话会超时，需要维护单调队列来直接得到 $k$ 的值，通过 $d p$ 求出每行的最小代价。最后选择连续的 $k$ 行桥，使用前缀和维护然后枚举。

代码：

#include<bits/stdc++.h>

typedef long long LL;
using namespace std;

void solve() {
    int n, m, k, d;
    cin >> n >> m >> k >> d;
    LL a[n + 1][m + 1];
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
        }
    }
    vector<LL> ans;
    for (int i = 1; i <= n; i++) {
        vector<LL> dp(m + 1, 0);
        deque<int> Q;
        while (!Q.empty()) {
            Q.pop_back();
        }
        dp[1] = a[i][1] + 1;
        Q.push_back(1);
        for (int j = 2; j <= m; j++) {
            if (!Q.empty() && j - Q.front() > d + 1)
                Q.pop_front();
            dp[j] = dp[Q.front()] + a[i][j] + 1;
            while (!Q.empty() && dp[Q.back()] > dp[j])
                Q.pop_back();
            Q.push_back(j);
        }
        ans.push_back(dp[m]);
    }
    LL pre[n + 1];
    pre[0] = ans[0];
    for (int i = 1; i < n; i++) {
        pre[i] = pre[i - 1] + ans[i];
    }
    LL cnt = pre[k - 1];
    for (int i = k; i < n; i++) {
        cnt = min(cnt, pre[i] - pre[i - k]);
    }
    cout << cnt << endl;
}

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

F.Rudolf and Imbalance（数学）

题意：

鲁道夫准备了一组复杂度为 $a_1\lt a_2\lt a_3\lt\dots\lt a_n$ 的 $n$ 个问题。他对平衡并不完全满意，因此他想最多增加一个问题来解决它。

为此，鲁道夫提出了 $m$ 个问题模型和 $k$ 个函数。第 $i$ 个模型的复杂度是 $d_i$ ，第 $j$ 个函数的复杂度是 $f_j$ 。要创建一个问题，他需要选择值 $i$ 和 $j$ （ $1\le i\le m$ ， $1\le j\le k$ ， $i$ ）。( $1\le i\le m$ , $1\le j\le k$ )，并将第 $i$ 个模型与第 $j$ 个函数相结合，得到一个复杂度为 $d_i+f_j$ 的新问题（在数组 $a$ 中插入了一个新元素）。

为了确定集合的不平衡性，鲁道夫将问题的复杂度按升序排序，并找出 $a_i-a_{i-1}$ 的最大值（ $i\gt 1$ ）。

鲁道夫根据所描述的规则最多添加一个问题所能达到的最小不平衡值是多少？

分析：

由于最多插入一个，若 $a$ 存在多个最大差值，答案即为最大差值。

若只存在一个最大差值 $r - l$ ，即在 $(l, r)$ 之间插入，插入后的差值与原第二大差值比较即可。

考虑插入的数应该趋近于中间，为 $mi d = l + r >> 1$

而后枚举 $d$ ， $f$ 应该趋近于 $mi d - d$ ，二分出趋近于 $mi d - d$ 的 $f$ ，将求出的数与 $l$ 和 $r$ 取差值，维护最小差值即可。

代码：

#include<bits/stdc++.h>

typedef long long LL;
using namespace std;

void solve() {
    int n, m, k;
    cin >> n >> m >> k;
    vector<LL> a(n + 1), d(m + 1), f(k + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= m; i++) {
        cin >> d[i];
    }
    for (int i = 1; i <= k; i++) {
        cin >> f[i];
    }
    sort(a.begin() + 1, a.end());
    sort(d.begin() + 1, d.end());
    sort(f.begin() + 1, f.end());
    LL dist = -1;
    LL sd = -1;
    int cnt = 0;
    LL l = 0;
    LL r = 0;
    for (int i = 2; i <= n; i++) {
        LL t = a[i] - a[i - 1];
        if (t > dist) {
            if (dist != -1) {
                sd = dist;
            }
            dist = t;
            cnt = 1;
            l = a[i - 1];
            r = a[i];
        } else if (t == dist) {
            cnt++;
            sd = dist;
        } else if (sd < t) {
            sd = t;
        }
    }
    if (cnt > 1) {
        cout << dist << endl;
        return;
    }
    LL ans = dist;
    LL mid = (l + r + 1) / 2;
    for (int i = 1; i <= m; i++) {
        LL x = mid - d[i];
        auto it = lower_bound(f.begin() + 1, f.end(), x);
        if (it != f.end()) {
            x = *it;
            LL t = d[i] + x;
            if (t >= l && t <= r) {
                ans = min(ans, max(r - t, t - l));
                if (sd != -1) {
                    ans = max(ans, sd);
                }
            }
        }
        if (it != f.begin() + 1) {
            it--;
            x = *it;
            LL t = d[i] + x;
            if (t >= l && t <= r) {
                ans = min(ans, max(r - t, t - l));
                if (sd != -1) {
                    ans = max(ans, sd);
                }
            }
        }
    }
    cout << ans << endl;
}

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