CF900.Div3


CF900.DIV3

A

只需判断数组中是否有 $k$ 即可。


B

有很多构造方法。

我的是

还可以直接输出奇数。


补C

卡在这题上了,太 sb 了。

有点困,交了几发二分没过后就上床准备睡觉了。

上床了突然意识到,在和的最小值 $L$ 和最大值 $R$ 之间的值都可以取到。

难绷。


补D

$k$ 个区间不相互影响,且首尾相连,所以也就是分成了 $k$ 段。

而且每个反转的区间都是在相应的段中对称的。

所以对于每次反转,直接差分,最后求前缀和得到每个位置被反转的次数,接着一段一段处理,如果该位置被反转了奇数次就将其与在段中与其中心对称的位置交换一下。

时间复杂度 $O(n)$ 。


补E

赛时读了一下题,感觉不好做,就没想。

第二天才发现读错题了,是 与 而不是 异或。

是 与 的话就好搞了,因为与操作后的值肯定越来越小,具有单调性,所以可以考虑二分。

对每一位 $i$ 统计 $1$ 的个数,如果当前 check 的区间内 $1$ 的个数等于区间长度,就把值加上 $2^i$ 。

时间复杂度 $O(32\times q\log n)$ 。


补F

由于 $d(n)$ 为积性函数,所以 $\gcd(a,n)=1$ 且 $d(n\times a)=n$ 即为

所以即判断是否有 $d(n)|n$ .

注意到 $q$ 十分小,只有 $1000$ ,所以对每次操作直接暴力分解质因数来求出新的因数个数 $d(n)$ ,再把 $d(n)$ 分解质因数判断每个质因数的指数是否都小于 $n$ 中相应的指数即可。

注意不能动态维护 $n$ 再取模判断,因为过程中 $n$ 会很大。


文章作者: HoshiuZ
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 HoshiuZ !
  目录