Codeforces Round 933 (Div. 3)

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\le i \le 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

一个串如果包含 \(pie\)，\(map\) 就认为这个串是不美丽的

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

Solution

显然，一个串如果出现 \(pie\) 只需要删除中间的 \(i\) 就可以打破 \(pie\)

同理 \(map\) 需要删去中间的 \(a\)

特殊地， \(mapie\) 需要删除中间的 \(p\)，而不是删除 \(a\) 和 \(i\)

所以总次数就是 \(map\) 的个数 \(+\) \(pie\) 的个数 \(-\) \(mapie\) 的个数

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 的思想，定义 \(dp[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

每一行单独看，定义 \(dp[i]\) 表示建桥建到 \(i\) 且必须在 \(i\) 建一个桥墩的最小代价，转移方程为 \(dp[i]=\min_{j=i-k-1}^{i-1}\{dp[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

定义 \(mx1,mx2\) 分别表示差值的最大值和次大值

如果 \(mx1=mx2\) ，则无论怎么样都无法减小差值，直接输出 \(mx1\)

如果 \(mx1>mx2\) ，那么我们尝试在 \(mx1\) 之中插入一个数

假设 \(mx1\) 对应的位置是 \(pos\)，那么我们就需要从 \(d,f\) 中找出一个组合，使得 \(d_i+f_j\) 距离 \((a[pos]+a[pos+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\) 对应的虚点为 \(mp[w]\)

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

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

从 \(u\rightarrow mp[w]\)，边权为 \(1\)，从 \(v\rightarrow mp[w]\) ，边权为 \(1\)

从 \(mp[w]\rightarrow u\)，边权为 \(0\)，从 \(mp[w]\rightarrow v\)，边权为 \(0\)

由于边权只有 \(01\) ，直接刷 \(01BFS\) 即可

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