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