Codeforces Round 843

这几天忙于通核 & 宣讲事宜没能更新，明天就是 tourist 出的一场 Div. 1 + Div. 2 了，但是由于社会实践估计还是打不了

Source

Codeforces Round 843

A - Gardener and the Capybaras

Code

A1 直接暴力

A2 我的做法是大讨论，WA 了两发之后发现许多情况都能合并

1775 A2

B - Gardener and the Array

「位」指二进制位

问题即寻找这样的 $c_k$：对于$c_k$ 的每一个为 1 的位，其它的数中至少有一个该位也为 1

模拟即可。我的做法是记录每个位为 1 的次数

Code

1775 B

C - Interesting Sequence

「位」指二进制位

能对拍就对拍，中小范围数据基本上算全面了

首先，显然要有 $n \And x = x$。再把 $n = x, x = 0, x = 1$ 以及 $n, x$ 最高位不同的情况都特判了

接下来，找到首个 $n, x$ 不同的位，其实也就是首个 $n$ 为 1，$x$ 为 0 的位

• 若其高于 $x$ 的最低的为 1 的位，则一定无解。因为该位变成 0 一定会使 $n\And (n + 1)\And\cdots\And m$ 中比其低的位全部变成 0
• 若更高一位上仍是 1，则一定无解。因为该位变成 0 一定会使 $n\And (n + 1)\And\cdots\And m$ 中的更高一位变成 0，而由约定，$x$ 的更高一位为 1
• 否则有解。将该位及更低位变成 0，更高一位变成 1 即可。实现可以用先右移后左移来完成

Code

1775 C

D - Friendly Spiders

OI 的一些做法还是得通过打比赛来回忆，本题难点在于建图。

考虑以质因子作为虚点。对于 $a_i$，建 $i\to d, \forall d$ 且边权为 0，建 $d\to i, \forall d$ 且边权为 1，其中 $d$ 为 $a_i$ 的质因子。跑 Dijkstra 即可

被连边坑惨了。先筛出 $3\times10^5$ 内的所有质数。对于 $a_i$，先用 $[2, \sqrt{a_i}]$ 的判一遍，这样可以获得 $a_i$ 大于 $\sqrt{a_i}$ 的质因子。接下来二分查找其编号即可（也可以开个 map）

当然，对于边权为 $0/1$ 的图跑最短路，有一种叫做 01BFS 的东西，在此不表（STL 的堆优 Dijkstra 都能过）

Code

1775 D

E - The Human Equation

又是这种奇妙的观察题

观察前缀和。每一次操作选出了 $i, j, \cdots$，相当于在 $[s_i, \cdots, s_{j - 1}], \cdots$ 上同时进行 $+1, 0, -1$ 其一的操作。由题，要么是 $+1, 0, +1, 0, \cdots$，要么是 $-1, 0, -1, 0, \cdots$，因此答案即为 $\max s_i - \min s_i$

Code

1775 E

Warnings

这场开头打的稀烂，好在情绪稳定下来了

• 打比赛不能总是怀着「要上分」的想法，而应该专注于比赛
• 不放心的，可以对拍，别担心费时