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

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

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

Codeforces Round 843
https://chenz01.github.io/2023/01/14/Codeforces-Round-843/
作者
ChenZ01
发布于
2023年1月14日
许可协议