Codeforces Round #787 (Div. 3)

A. Food for Animals

\(a\) 个狗粮，\(b\) 个猫粮，\(c\) 个通用粮（都能吃），能不能保证 \(n\) 个狗 \(m\) 个猫都有的吃？

每个都先减掉专用的食物，剩下的看通用的够不够分即可。

1
2
3
4
5
inline void work() {
    int a = rd(), b = rd(), c = rd();
    int n = max(0, rd() - a), m = max(0, rd() - b);
    puts(n + m > c ? "NO" : "YES");
}

B. Make It Increasing

给一个数列，每次操作把一个位置整除 \(2\) ，最少操作多少次使得数列严格递增？

从后往前倒推，答案是固定的，一直做到符合要求即可。

1
2
3
4
5
6
7
8
9
10
11
int a[57];
inline void work() {
    int n = rd(), ans = 0;
    for (int i = 1; i <= n; ++i) a[i] = rd();
    for (int i = n - 1; i; --i) 
        if (a[i] >= a[i + 1]) {
            if (a[i + 1] == 0) {puts("-1"); return;}
            while (a[i] >= a[i + 1]) {++ans; a[i] = a[i] / 2;}
        }
    printf("%d\n", ans);
}

C. Detective Task

有一幅画， \(n\) 个人看，中间某一时刻被某一个人偷走了。

问每个人他看的时候画还在不在，答案可能是有 (1) / 无 (0) / 忘记了 (?)。

好人会说实话/忘记了，偷走的人会随机选一个答案，求有多少个嫌疑人。

  • 最后一个说有（1）的人，前面的人都不会是嫌疑人：如果前面的人是嫌疑人，那么他进去的时候应该已经被偷了，他就说谎了。
  • 第一个说无（0）的人，后面的人都不会是嫌疑人：如果后面的人是嫌疑人，那么他进去的时候还没被偷，他就说谎了

因此答案是从最后一个说有的人到第一个说无的人这一段的人数。

1
2
3
4
5
6
7
8
9
10
11
string s;
inline void work() {
    cin >> s;
    int n = s.length();
    int l = 0, r = n - 1;
    for (int i = 0; i < n; ++i) 
        if (s[i] == '1') l = i;
    for (int i = l; i < n; ++i) 
        if (s[i] == '0') {r = i; break;}
    printf("%d\n", r - l + 1);
}

D. Vertical Paths

给一棵树，问最少分成多少个从上到下的链，并输出方案。

显然每个叶子都需要一个链，每个非叶子挑一个叶子挂上就行了，纯考实现。

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
48
#include <bits/stdc++.h>
using namespace std;

inline int rd() {
    int x = 0;
    bool f = 0;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) f |= (c == '-');
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    return f ? -x : x;
}

#define N 200007

bool vis[N];

int n, rt, f[N], cnt;

vector<int> res[N], son[N];

void dfs(int u, int bel) {
    res[bel].push_back(u);
    if (son[u].empty()) {++cnt; return;}
    dfs(son[u][0], bel);
    for (int i = 1; i < son[u].size(); ++i) dfs(son[u][i], son[u][i]);
}

inline void work() {
    n = rd(); cnt = 0;
    for (int i = 1; i <= n; ++i) {res[i].clear(); son[i].clear();}
    for (int i = 1; i <= n; ++i) {
        f[i] = rd(); 
        if (f[i] == i) rt = i;
        else son[f[i]].push_back(i);
    }
    dfs(rt, rt); 
    printf("%d\n", cnt);
    for (int i = 1; i <= n; ++i)
        if (!res[i].empty()) {
            printf("%d\n", (int)res[i].size());
            for (auto j : res[i]) printf("%d ", j); puts("");
        }  
}

int main() {
    for (int t = rd(); t; --t) work();
    return 0;
}

E. Replace With the Previous, Minimize

给一个字符串，每次操作你可以选定一个字符，并把串中的所有这个字符换成字典序前一个（a 变成 z ）

问 \(k\) 次操作内，字符串可能的字典序最小的结果是什么？

首先如果 \(k>25\) ，那么我从 z 到 b 都操作一遍就都变成 aaaaaaa 这样子了。

否则也一定不会对 a 操作，因为次数不够变回来了，因此操作是单向的，没有循环的。

因此按照字典序贪心就完事了，维护一个 \(\Sigma\to \Sigma\) 的转移表，每次可以的话往前移动一下。

需要注意的是利用此前的结果，也就是每次做完之后记得把前缀覆盖一下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
string s;
unordered_map<char, char> tr;
inline void work() {
    int n = rd(), k = rd();
    cin >> s;
    for (char i = 'a'; i <= 'z'; ++i) tr[i] = i;
    for (auto i : s) {
        while (k && tr[i] > 'a') {
            --tr[i]; --k;
            tr[i] = tr[tr[i]];
        }
        for (char j = i; j >= tr[i]; --j) tr[j] = min(tr[j], tr[i]);
        if (k == 0) break;
    }
    for (auto i : s) putchar(tr[i]); puts("");
}

F. Vlad and Unfinished Business

给一棵树，树上的两个点 \(x, y\) ，以及一系列点 \(a_1, a_2, \dots,a_k\)

求一个最短路径，从 \(x\) 出发，以任意顺序遍历完 \(a_1, a_2, \dots,a_k\) ，最后走到 \(y\)

首先一个常见的套路（虚树）是，树上遍历一个点集的最短回路，就是所有点按照dfs序一次性访问。

现在考虑让树以 \(x\) 为根，现在需要遍历 \(a_1,a_2,\dots,a_k\) 这些点，最后再走到 \(y\) 。

其实可以看成回路遍历点集 \(x, a_1, a_2,\dots, a_k,y\) ，最后再把 \(x\) 到 \(y\) 的距离（也就是 \(y\) 的深度）扣掉。

所以按照 dfs 序依次访问即可，可能比较难写。

另外一种简单的写法是暴力往根跳，跳到第一个访问到的点即可，往答案里累加新增的点数 * 2 。

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
48
49
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

inline int rd() {
    int x = 0;
    bool f = 0;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) f |= (c == '-');
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    return f ? -x : x;
}

#define N 200007

vector<int> e[N], seq;

bool vis[N];

int n, k, x, y, f[N], ans;

void dfs(int u, int fa, int dep) {
    f[u] = fa;
    if (u == y) ans = -dep;
    for (auto v : e[u])
        if (v != fa) dfs(v, u, dep + 1);
}

inline void work() {
    seq.clear();
    n = rd(); k = rd(); x = rd(); y = rd();
    for (int i = 1; i <= n; ++i) vis[i] = 0, e[i].clear();
    for (int i = 1; i <= k; ++i) seq.push_back(rd());
    seq.push_back(y);
    for (int i = 1; i < n; ++i) {
        int u = rd(), v = rd();
        e[u].push_back(v); e[v].push_back(u);
    }
    dfs(x, x, 0);
    vis[x] = 1;
    for (auto i : seq)
        for (int u = i; !vis[u]; u = f[u]) vis[u] = 1, ans += 2;
    printf("%d\n", ans);
}

int main() {
    for (int t = rd(); t; --t) work();
    return 0;
}

G. Sorting Pancakes

给你一个序列，每次操作可以选两个相邻的两个位置一个 \(-1\) 一个 \(+1\) ，问最小操作多少次是的序列单减。

看到这种问题一般都是 dp ，就是状态设计需要好好考虑一下。

设 \(f_{i,j}\) 表示考虑了前 \(i\) 位，前缀和是 \(j\) 的最小操作数，那么转移就是枚举序列最终下一个位置的数字 \(k\) 。

即 \(f_{i+1,j+k}=\min\{f_{i+1,j+k}, f_{i,j} + cost (i + 1, j+k)\}\) 其中 \(cost(x, w)\) 表示前缀 \(x\) 在此前基础上变成总和 \(w\) 的最小代价。

考虑 \(f_{i,j}\) 里已经包含了让前缀 \(i\) 合法的代价，现在其实只需要考虑新一位是 \(k\) 的代价。

本质上我们只需要考虑第 \(i+1\) 位和后面的后缀交流的多少次，即 \(cost(i+1,j+k)=|\sum_{p=1}^{i+1}a_p-(j+k)|\)

那么怎么保证序列单减呢？把枚举 \(k\) 的循环放到最外面，从大到小，这样转移是从大到小的，比较妙。

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
#include <bits/stdc++.h>
using namespace std;

inline int rd() {
    int x = 0;
    bool f = 0;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) f |= (c == '-');
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    return f ? -x : x;
}

#define N 257

int a[N], s[N], f[N][N];

int main() {
    int n = rd(), m = rd();
    for (int i = 1; i <= n; ++i) 
        s[i] = s[i - 1] + (a[i] = rd());
    memset(f, 0x3f, sizeof(f));
    f[0][0] = 0;
    for (int k = m; ~k; --k)
        for (int i = 0; i < n; ++i)
            for (int j = 0; j <= m - k; ++j) 
                f[i + 1][j + k] = min(f[i + 1][j + k], f[i][j] + abs(j + k - s[i + 1]));
    printf("%d\n", f[n][m]);
    return 0;
}