Codeforces Round 660

Posted on | In , |

官方题解链接： Codeforces Round #660 Editorial

A. Captain Flint and Crew Recruitment

Codeforces 1388 A

如果一个正整数是两个 不同 质数的积，那么定义其为 类质数 。

给定一个正整数 $n$，询问是否能将 $n$ 分解成四个 互不相同 的正整数，并满足这四个正整数中至少有三个是类质数。

若能，则要求给出任意一种分解方案。

多组数据 $t\le 10^3$ ， $n\le 2\times 10^5$

Solution

四个互不相同的正整数，至少三个类质数。

最小的三个类质数 $6,10,14$ ，和为 $30$ ，则 $n\le 30$ 无解。

防止重复，$n=36,40,44$ 时用 $6,10,15,n-31$ 分解，其余情况用 $6,10,14,n-30$ 分解。

1
2
3
if (n <= 30) printf("NO\n");
else if (n == 36 || n == 40 || n == 44) printf("YES\n6 10 15 %d\n", n - 31);
else printf("YES\n6 10 14 %d\n", n - 30);

B. Captain Flint and a Long Voyage

Codeforces 1388 B

定义一个数的 二进制连缀表达式 为，将该数按位转换成二进制，再按原数位依次链接。

例如 $729$ 的二进制连缀表达式为 $111101001$ ，因为二进制下 $7 = 111, 2= 10 , 9 = 1001$ 。

现在要求构造一个 $n$ 位正整数 $x$，满足：

  • 将 $x$ 的二进制连缀表达式，删掉后 $n$ 位后最大（将二进制连缀表达式视作十进制数）

  • 有多个删掉后相同的 $x$ ，输出其中最小的一个

多组数据 $t\le 10^3$ ， $n\le 2\times 10^5$ ，$\sum n\le 2\times 10^5$

Solution

二进制下只有 $8(1000)$ 和 $9(1001)$ 是四位，想要最后的结果最大，位数不能少。

因此 $x$ 只能由 $8$ 和 $9$ 构成，同时前缀应为 $9$ ，最后若干位受删除影响的可以放 $8$ 。

注意到 $9(1001)$ 只要删掉最后一位就和 $8$ 相同，因此尾部需要放 $\lfloor\frac{n+3}{4}\rfloor$ 个 $8$ ，前缀都是 $9$ 。

1
2
3
4
int n8 = (n + 3) / 4;
int n9 = n - n8;
while (n9--) putchar('9');
while (n8--) putchar('8');

C. Uncle Bogdan and Country Happiness

Codeforces 1388 C

一个国家，$n$ 个城市和 $n-1$ 条道路构成树形结构，$1$ 号城市是首都。

国家总人口数为 $m$ ，第 $i$ 号城市居住人口为 $p_i$ ，保证 $\sum p_i=m$ 。

每天早上所有人从所居住的城市前往首都上班，晚上下班回到所居住的城市，走最短路。

每个人下班时都会高兴或不高兴，人们在 道路上 情绪 只可能 会从高兴变成不高兴，或保持不变。

每个城市都安装了幸福指数检测器，能够统计下班路上高兴的人数 $h_i$ 和不高兴的人数 $s_i$ 。

具体的说，若下班路上经过城市 $i$ 的有 $h_i$ 个高兴的人，有 $s_i$ 个不高兴的人，则显示器显示 $a_i=h_i-s_i$ 。

现给定一组 $a_1…a_n$ ，询问是否存在一种可能的情况满足 $a_1…a_n$ 都成立。

多组数据 $t\le 10^4$ ， $n\le 10^5$ ，$\sum n\le 2\times 10^5$ ， $m\le 10^9$

Solution

可行性验证，设 $1$ 号首都为根，树上后缀和就是对应到该点的总人数 $totp_i$。

对于 $a_i$ 和 $totp_i$ 固定， $h_i$ 和 $s_i$ 也就固定了：$h_i-s_i=a_i,\ h_i+s_i=totp_i$ 。

因此只需找出不合法情况：

  • $a_i$ 和 $totp_i$ 奇偶性不同

  • 求出 $h_i<0$ 或 $s_i<0$

  • 对于所有子节点，$\sum h_{son}>h_i$ （心情可以由好变坏，$s$ 无需验证）

代码中 $0$ 代表合法，$1$ 代表不合法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
bool dfs(int x, int fa) {
  totp[x] = p[x];
  int toth = 0;
  for (int i = hd[x]; i; i = nxt[i])
    if (ver[i] != fa) {
      if (dfs(ver[i], x)) return 1;
      totp[x] += totp[ver[i]];
      toth += h[ver[i]];
    }
  if ((totp[x] & 1) != (abs(a[x]) & 1)) return 1;
  h[x] = (totp[x] + a[x]) / 2;
  s[x] = totp[x] - h[x];
  if (h[x] < 0 || s[x] < 0) return 1;
  if (toth > h[x]) return 1;
  return 0;
}

D. Captain Flint and Treasure

Codeforces 1388 D

有两个长度为 $n$ 的数组 $a$ 和 $b$ 。

一开始，答案 $ans$ 为 $0$，进行如下操作：

  • 选择一个位置 $i(1\le i\le n)$， 将 $a_i$ 加到 $ans$ 中。

  • 如果 $b_i \neq -1$ ，将 $a_i$ 加到 $a_{b_i}$ 上。

现确定一个操作序列 $s$ ，为 $1,..,n$ 的全排列，使得依次操作后， $ans$ 的值最大。

数据保证：$b_i$，$b_{b_i}$ , $b_{b_{b_i}}$，… 不会出现循环（总以 $-1$ 结束）

$n\le 2\times 10^5$ ，$-10^6\le a_i\le 10^6$ ， $1\le b_i\le n$ 或 $b_i = -1$

Solution

每个点最多只有一个指向，无环，森林结构。

假设 $i$ 号点在最终累计答案时的取值为 $mx_i$ 。

枚举子节点，若最终 $mx_{son} > 0$ ，则该值可在父节点继续贡献，将其值加到当前点上，反之不加。

第一遍 dfs 求最优解，第二遍 dfs2 输出方案。

对于当前点 $x$，先搜 $mx_{son} > 0$ 的子节点，先输出他们的编号，再输出 $x$ 的编号，再搜其他子节点即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void dfs(int x) {
  mx[x] = a[x];
  for (int i = hd[x]; i; i = nxt[i]) {
    dfs(ver[i]);
    mx[x] += max(mx[ver[i]], 0ll);
  }
  ans += mx[x];
}

void dfs2(int x) {
  for (int i = hd[x]; i; i = nxt[i])
    if (mx[ver[i]] > 0) dfs2(ver[i]);
  printf("%d ", x);
  for (int i = hd[x]; i; i = nxt[i])
    if (mx[ver[i]] <= 0) dfs2(ver[i]);
}

（E 留坑）