Contest Info

date: 2018.10.22 14:15-16:15

practice link

Solutions

A. Bear and Three Balls

签到题。

B. Bear and Compressing

签到题。

C. Bear and Up-Down

签到题。

D. Delivery Bears

题目大意：给出一个有向图，每条边有一个权。现在有 \(x\) 只熊要从 \(1\) 走到 \(n\)，每只熊都要搬运等重量的货物，且每条边的总承重量不能超过它的边权。问最多搬运多少货物。

题解：二分以后就是一个裸的最大流。嘴了一下没写。

E. Bear and Forgotten Tree 2

题目大意：有 \(n\) 个点，要求你构造一棵 \(n\) 个点的，且点 \(1\) 的度恰为 \(k\) 的树，另外告诉你某些边不能连。问能否构造出来。

题解：显然一个必要条件是补图连通。考虑在补图上 bfs，用一个 set 维护当前未访问过的点，那么访问完一个点之后，这个 set 的大小至多为该点在原图中的度。因此这样总复杂度为 \(\mathcal{O}((n+m)\log n)\)。

然后再考虑度数能否为 \(k\)。显然度数最小值为补图中删除 \(1\) 后的连通块数量，最大值为 \(n-1-\deg_{1}\)，而这之间的值都能取到。那么再类似地 bfs 一下求连通块数量即可。

F. Paper task

字符串题。pass

G. Move by Prime

题目大意：定义一个序列的代价为使用如下两种操作使得序列中所有数一样的最小操作次数：

• 将序列中的某个数乘上某个质数

• 将序列中的某个数除以某个质数（要求能够整除）

给你 \(n\) 个数，求所有 \(2^{n}\) 个子序列的代价和。

题解：显然可以对每个质数分别计算。一个序列的代价即为所有数和中位数的差的绝对值。枚举这个中位数，然后用组合数计算一下即可。\(0\) 的数量有很多，需要注意处理。