Codeforces Round 933 (Div. 3) A-G 题解

A - Rudolf and the Ticket

Solution

因为 $n$ 很小，直接枚举 $b_{i} + c_{j}$ 所产生的所有数字。

Code

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int n, m, k;
    cin >> n >> m >> k;
    int ans = 0;
    vector<int> a(n), b(m);
    for (auto &x : a) cin >> x;
    for (auto &x : b) cin >> x;
    for (int i = 0; i < n; i++) 
        for (int j = 0; j < m; j++) 
            ans += a[i] + b[j] <= k;
    cout << ans << '\n';
}

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

B - Rudolf and 121

Question

给出 $n$ 个数，可以进行这样一个操作，选中一个 $(1 \leq i \leq n - 1)$

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

问能否把这 $n$ 个数都变成 $0$

Solution

显然， $a_{1}$ 只能每次 $- 1$ ，那么 $a_{2}$ 就需要减 $a_{1} \times 2$ ， $a_{3}$ 需要减 $a_{1}$

从 $1$ 开始往后枚举 $i$ ，如果 $a_{i}$ 还有剩余，就把 $a_{i}$ 每次 $- 1$ ，然后计算 $a_{i + 1}, a_{i + 2}$ 当某个数出现负数的情况就是不合法的

Code

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int n; cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n - 2; i++) {
        if (a[i] > a[i + 1]) {
            puts("NO"); return ;
        }
        int x = a[i];
        if (a[i + 1] < x * 2) {
            puts("NO"); return ;
        }
        if (a[i + 2] < x) {
            puts("NO"); return ;
        }
        a[i] -= x; a[i + 1] -= x * 2; a[i + 2] -= x;
    }
    if (a[n - 1] != 0 || a[n] != 0) {
        puts("NO"); return ;
    }
    puts("YES");
}

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

C - Rudolf and the Ugly String

Question

一个串如果包含 $p i e$ ， $m a p$ 就认为这个串是不美丽的

给出一个串，问最少删除几个字母使得串变美丽

Solution

显然，一个串如果出现 $p i e$ 只需要删除中间的 $i$ 就可以打破 $p i e$

同理 $m a p$ 需要删去中间的 $a$

特殊地， $m a p i e$ 需要删除中间的 $p$ ，而不是删除 $a$ 和 $i$

所以总次数就是 $m a p$ 的个数 $+$ $p i e$ 的个数 $-$ $m a p i e$ 的个数

Code

#include <bits/stdc++.h>
using namespace std;
void solve() {
    int n; cin >> n;
    string s; cin >> s;
    vector<string> p = {"pie", "map","mapie"};
    vector<int> num(3,0);
    for (int i = 0; i < 3; i++) {
        string now = p[i];
        for (int j = 0; j + now.size() - 1 < s.size(); j++) {
            if (s.substr(j, now.size()) == now)
                num[i] ++;
        }
    }
    cout << num[0] + num[1] - num[2] << '\n';
}
int main() {
    int t; cin >> t;
    while (t--) solve();
}

D - Rudolf and the Ball Game

Solution

DP 的思想，定义 $d p [i] [j]$ 表示前 $i$ 次传球， $j$ 位置是否有可能接球

顺时针传球认为是 $j \Rightarrow j + x$ ，逆时针传球被认为是 $j \Rightarrow j + n - x$

Code

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e3 + 5;

int f[maxn][maxn];

void solve(){
    int n, m, k; cin >> n >> m >> k;
    for (int i = 0; i < n; i++) {
        f[0][i] = i == k - 1;
    }
    for (int i = 1; i <= m; i++) {
        int x; char ch;
        cin >> x >> ch;
        for (int j = 0; j < n; j++) f[i][j] = 0;
        for (int j = 0; j < n; j++) {
            if (ch != '1') 
                f[i][(j + x) % n] |= f[i - 1][j];
            if (ch != '0') 
                f[i][(j + n - x) % n] |= f[i - 1][j];
        }
    }
    int ans = 0;
    for (int j = 0; j < n; j++) 
        if (f[m][j]) ans++;
    cout << ans << '\n';
    for (int j = 0; j < n; j++) 
        if (f[m][j]) cout << j + 1 << ' ';
    cout << '\n';
}

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

E - Rudolf and Imbalance

Solution

每一行单独看，定义 $d p [i]$ 表示建桥建到 $i$ 且必须在 $i$ 建一个桥墩的最小代价，转移方程为 $d p [i] = {min}_{j = i - k - 1}^{i - 1} {d p [j] + a [i] + 1}$

单调队列优化转移过程即可

Code

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> pii;

int calc (vector<int> a, int d) {
    int n = a.size() - 1;
    vector<int> f(n + 1, 0);
    deque<pii> q;
    q.push_back({1, a[1] + 1}); f[1] = a[1] + 1;
    for (int i = 2; i <= n; i++) {
        while (q.size() > 0 && q.front().first < i - d) q.pop_front();
        f[i] = q.front().second + a[i] + 1;
        while (q.size() > 0 && q.back().second >= f[i]) q.pop_back();
        q.push_back({i, f[i]});
    }
    return f[n];
}

void solve() {
    int n, m, k, d; cin >> n >> m >> k >> d;
    d = d + 1;
    vector<vector<int> > a(n + 1, vector<int>(m + 1, 0));
    for (int i = 1; i <= n; i++) 
        for (int j = 1; j <= m; j++) 
            cin >> a[i][j];
    vector<int> p(n + 1);
    for (int i = 1; i <= n; i++) 
        p[i] = calc(a[i], d);
    vector<int> s(n + 1, 0);
    for (int i = 1; i <= n; i++) 
        s[i] = s[i - 1] + p[i];
    int ans = 1e18;
    for (int i = k; i <= n; i++) {
        ans = min(ans, s[i] - s[i - k]);
    }
    cout << ans << '\n';
    
}

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

F - Rudolf and Imbalance

Solution

定义 $m x 1, m x 2$ 分别表示差值的最大值和次大值

如果 $m x 1 = m x 2$ ，则无论怎么样都无法减小差值，直接输出 $m x 1$

如果 $m x 1 > m x 2$ ，那么我们尝试在 $m x 1$ 之中插入一个数

假设 $m x 1$ 对应的位置是 $p o s$ ，那么我们就需要从 $d, f$ 中找出一个组合，使得 $d_{i} + f_{j}$ 距离 $(a [p o s] + a [p o s + 1]) / 2$ 最近

这个暴力枚举 $d_{i}$ ，二分查找 $f_{j}$ 的值，统计答案即可

Code

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> pii;
const int INF = 1e18;
void solve() {
    int n, m, k; cin >> n >> m >> k;
    vector<int> a(n + 1), d(m + 1), f(k + 1, 0);
    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];
    pii mx1 = {-1,0}, mx2 = {-1,0};
    for (int i = 1; i < n; i++) {
        int x = a[i + 1] - a[i];
        if (x > mx1.first) { mx2 = mx1; mx1 = {x, i}; }
        else if (x > mx2.first) { mx2 = {x, i}; }
    }
    if (mx1.first == mx2.first) {
        cout << mx1.first << '\n';
        return ;
    }
    // 把 pos1 的位置拆开
    int mid = (a[mx1.second] + a[mx1.second + 1]) / 2;
    sort (d.begin() + 1, d.end());
    sort (f.begin() + 1, f.end());
    int ret = mx1.first;
    for (int i = 1; i <= m; i++) {

        auto check = [&](int pos) {
            if (pos < 1 || pos > k) return INF;
            int x = d[i] + f[pos];
            if (!(x > a[mx1.second] && x < a[mx1.second + 1])) return INF;
            return max (x - a[mx1.second], a[mx1.second + 1] - x);
        };

        int pos = lower_bound(f.begin() + 1, f.end(), mid - d[i]) - f.begin();
        ret = min (ret, check(pos));
        ret = min (ret, check(pos - 1));
        ret = min (ret, check(pos + 1));
    }
    cout << max (mx2.first, ret) << '\n';
}

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

G - Rudolf and Subway

Solution

把每个颜色分别建一个虚点， $w$ 对应的虚点为 $m p [w]$

我们利用虚点对节点进行转移

如果存在一条 $u, v$ 的边，颜色为 $w$ ，需要用虚点进行过度

从 $u \to m p [w]$ ，边权为 $1$ ，从 $v \to m p [w]$ ，边权为 $1$

从 $m p [w] \to u$ ，边权为 $0$ ，从 $m p [w] \to v$ ，边权为 $0$

由于边权只有 $01$ ，直接刷 $01 B F S$ 即可

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
void solve() {
    int n, m; cin >> n >> m;
    int cnt = n;
    map<int,int> mp;
    vector<vector<pair<int,int>>> g(n + m + 1);
    for (int i = 1; i <= m; i++){
        int u,v,w; cin >> u >> v >> w;
        if (mp.count(w) == 0) mp[w] = ++cnt;
        g[u].push_back({mp[w],1});
        g[v].push_back({mp[w],1});
        g[mp[w]].push_back({u,0});
        g[mp[w]].push_back({v,0});
    }
    int s, t; cin >> s >> t;
    vector<long long> dis(n + m + 1,INF);
    deque<int> q;
    dis[s] = 0; q.push_front(s);
    while (q.size()) {
        int u = q.front(); q.pop_front();
        for (auto &[v,w] : g[u]) {
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                if (w == 1) q.push_back(v);
                else q.push_front(v);
            }
        }
    }
    cout << dis[t] << '\n';
}

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