Codeforces Round #483(Div.2)题解

Author Avatar
ZigZagK 2018年5月16日 01:38
remove_red_eye 20

神tm结论大赛日神仙。

A

求中位数。

B

验证一张图是不是合法的扫雷游戏图。

C

给出 \(p,q,b\) ,求 \(p\over q\)\(b\) 进制下是否除尽。

结论:如果 \(q\) 中只含有 \(b\) 的素因子,那么可以除尽。所以不停令 \(q={q\over gcd(q,b)}\) ,最后验证 \(b\ mod\ q=0\) ,如果成立那么可以除尽。然而这么写你会成功TLE,估计数据故意设计过……

实际上因为你已经令 \(q={q\over gcd(q,b)}\) ,所以下一次令 \(q={q\over gcd(q,lastgcd)}\) 就行了( \(gcd(q,b)\) 只会越来越小,所以并不需要每次和 \(b\)\(gcd\) ),这样就可以跑得飞快。

D

\[
f(b) = \begin{cases} b[1] & \quad \text{if } m = 1 \\ f(b[1] \oplus b[2],b[2] \oplus b[3],\dots,b[m-1] \oplus b[m]) & \quad \text{otherwise,} \end{cases}
\]

\(q\) 个询问,求 \(max\{f(b[i,j])|L\le i\le j\le R\}\)

画个图就会发现显然有结论 \(f(b[i,j])=f(b[i+1,j])\ xor\ f(b[i,j-1])\)

然后再开个数组存一下所有答案,询问直接输出。

本文链接:https://zigzagk.top/2018/05/16/cfr483d2
本博客所有文章除特别声明外,均采用CC BY-NC-SA 4.0 CN 许可协议。转载请注明作者和出处QwQ。