ZigZagK

Never give up fighting!

Codeforces Round #483(Div.2)题解

神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])\)

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

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注