MENU

Solution. Codeforces Round #781

现在是 12:35,只做了 ABC,简单记一下关于 DE 的想法。

D,给了 30 次询问,从信息论的角度看,$\left\lceil\log_2 10^9\right\rceil$ 恰好等于 30,那是否要求了每一次询问都将可能的答案减半,或者每次询问确定一个二进制位这样。

能够想到的就是可以通过 $\gcd(x,x+prime)$ 来判断 $x$ 是否拥有 $prime$ 这个质因子。

E,不知道或运算怎样会比较好维护,$10^5$ 3s 的话莫队然后 $O(\log n)$ 的拓展区间,总复杂度 $O(n\sqrt n\log n)$ 也问题不大,总之还是在于不会描述按位或。


这次 Editorial 居然这么快 /jy

看到 E 的 Other Solutions 里给了一种莫队 + van Emde Boas tree 的做法 /fad。

C fst 了,写的二分弄巧成拙,明天写一下 CDE。

specialist -> pupil

这个 cf 打的只能说是心态爆炸

C. Tree Infection

可以轻易的被转化为序列问题,因为每个点的儿子都是相互独立的。

整个传染的过程可以被分为两部分,一是对于每个非叶子结点的儿子而言(另外特殊考虑根结点),我们都需要至少对其中一个儿子进行「注射」,否则它们也不可能通过「传播」被感染;二是在所有非叶子结点的儿子中都存在被感染的结点后,现在「注射」操作被闲置下来,可以帮助加速「传播」的过程。

对于前者,我们知道「注射」过程一定是从儿子数量多的开始,这部分由于排序是 $O(n\log n)$ 的,当然如果精细实现似乎也可以省去排序做到线性;后者我们实际上每次也会选择未被感染儿子数量多的进行「注射」,我当时这里选择了二分一个时间,但是你就暴力的模拟这个过程也是可行的,因为考虑到总点数为 $n$,每次我们花费 $O(1)$ 的代价去扫一个结点的时候,也就必然对应着未被感染结点数量 $O(1)$ 的减少,故总复杂度为 $O(n)$,二分反倒是 $O(n\log n)$ 的。

我的二分:

for(int x: opt) tmp += x - mid; // fst, wrong answer on testcase 20
for(int x: opt) tmp += max(0, x - mid); // accepted

这玩意居然能过 pretests 而且在 20 才 wa /dk

D. GCD Guess

确实可以做到一次询问确定一个二进制位。

首先我们知道 $x\bmod 2^0=0$,接下来考虑如果知道 $x\bmod 2^k=r$,如何求 $x\bmod 2^{k+1}$。

$x\bmod 2^k=r$ 意味着 $x$ 可以被表示为 $t\cdot 2^k+r$,那么:
$$
x\bmod2^{k+1}=\begin{cases}
r,&2\mid t,\\
2^k+r,&\mathrm{otherwise}.
\end{cases}
$$
我们实际上可以通过 $\gcd(t\cdot 2^k,2^{k+1})=\gcd(x-r,x-r+2^{k+1})$ 来判断 $t$ 的奇偶性,当结果为 $2^{k+1}$ 时 $t$ 为偶数。

由于询问的 $\gcd(x+a, x+b)$ 要求 $a,b>0$,所以给询问的数加上 $2^k$,$\gcd((t+1)2^k,2^{k+1})=\gcd(x+2^k-r,x+2^k-r+2^{k+1})$,对应的,结果为 $2^{k+1}$ 时 $t$ 为奇数。

E. MinimizOR

Lemma. 答案必然在最小的 31 个数中产生。

这个 31 是基于二进制串长度的,本题中 $a_i\le 2^{30}$。

在有了这一结论之后,就可以暴力的用线段树维护最小的 31 个数,暴力的枚举任意两个数或起来然后计算答案,假设 $n,q$ 同阶,总复杂度为 $O(n\log n\log a_i+n\log^2 a_i)$。

然后我们希望来证明这个结论。

我们知道 $a_i$ 共有 30 位,从高位向低位依次考虑,对于每一位,我们有这么三种情况:

  1. 当前位全为 1,此时无论如何选择,最终答案的当前位必然为 1。当前位不会对答案的选择造成任何影响,我们可以直接忽略当前位。
  2. 当前位有不少于两个 0,那么答案必然从当前位为 0 的数中产生,同时这样选也满足使得选出数尽量小的原则。
  3. 当前位有且仅有一个 0,最终答案的当前位必然为 1,我们不一定会去选择当前位为 0 的那个数,请注意此时我们可能会违背使得选出数尽量小的原则,但尽管如此,至多也只有一个较小的数被忽略。

那么最极端的情况就是 case 3,此时每一位都可能造成至多一个较小的数被忽略,但是最后一位是特殊的,此时已经是我们的最后一次决策,我们完全可以选择那个 0,答案必然不劣。至此,我们就证明了会被忽略的较小的数至多是 29 个, 那么在最坏情况下,答案会来自于从小到大的第 30 个数以及第 31 个数。

于是,答案必然在最小的 31 个数中产生。$\blacksquare$

Last Modified: April 12, 2022
Archives Tip
QR Code for this page
Tipping QR Code