Martian148's blog
martian148
2024-08-02
目录

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

Codeforces Round 933 (Div. 3) (opens new window)

# A - Rudolf and the Ticket

# Solution

因为 nn 很小，直接枚举 bi+cjb_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();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# B - Rudolf and 121

# Question

给出 nn 个数，可以进行这样一个操作，选中一个 (1≤i≤n−1)(1\le i \le n-1)

  • ai−1=ai−1−1a_{i-1}=a_{i-1}-1
  • ai=ai−2a_i=a_i-2
  • ai+1=ai+1−1a_{i+1}=a_{i+1}-1

问能否把这 nn 个数都变成 00

# Solution

显然，a1a_1 只能每次 −1-1 ，那么 a2a_2 就需要减 a1×2a_1\times 2，a3a_3 需要减 a1a_1

从 11 开始往后枚举 ii，如果 aia_i 还有剩余，就把 aia_i 每次 −1-1，然后计算 ai+1,ai+2a_{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();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

# C - Rudolf and the Ugly String

# Question

一个串如果包含 piepie，mapmap 就认为这个串是不美丽的

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

# Solution

显然，一个串如果出现 piepie 只需要删除中间的 ii 就可以打破 piepie

同理 mapmap 需要删去中间的 aa

特殊地， mapiemapie 需要删除中间的 pp，而不是删除 aa 和 ii

所以总次数就是 mapmap 的个数 ++ piepie 的个数 −- mapiemapie 的个数

# 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();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# D - Rudolf and the Ball Game

# Solution

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

顺时针传球认为是 j⇒j+xj\Rightarrow j+x ，逆时针传球被认为是 j⇒j+n−xj\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();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

# E - Rudolf and Imbalance

# Solution

每一行单独看，定义 dp[i]dp[i] 表示建桥建到 ii 且必须在 ii 建一个桥墩的最小代价，转移方程为 dp[i]=min⁡j=i−k−1i−1{dp[j]+a[i]+1}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();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

# F - Rudolf and Imbalance

# Solution

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

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

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

假设 mx1mx1 对应的位置是 pospos，那么我们就需要从 d,fd,f 中找出一个组合，使得 di+fjd_i+f_j 距离 (a[pos]+a[pos+1])/2(a[pos]+a[pos+1])/2 最近

这个暴力枚举 did_i ，二分查找 fjf_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();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

# G - Rudolf and Subway

# Solution

把每个颜色分别建一个虚点，ww 对应的虚点为 mp[w]mp[w]

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

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

从 u→mp[w]u\rightarrow mp[w]，边权为 11，从 v→mp[w]v\rightarrow mp[w] ，边权为 11

从 mp[w]→ump[w]\rightarrow u，边权为 00，从 mp[w]→vmp[w]\rightarrow v，边权为 00

由于边权只有 0101 ，直接刷 01BFS01BFS 即可

# 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();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
上次更新: 2025/04/08, 18:03:31
Educational Codeforces Round 168 (Rated for Div. 2) A-E 题解

Educational Codeforces Round 168 (Rated for Div. 2) A-E 题解→

最近更新
01
在 ACM 集训队年会上的讲话
07-01
02
计算机网络笔记
06-13
03
LLM101 NLP学习笔记
06-02
更多文章>
Theme by Vdoing | Copyright © 2024-2025 Martian148 | MIT License