人生第一次 AK!

这次的题目似乎比以前要简单一些

A. Book Reading

这题是说，有 $N\le 1e5$ 页书，有 $M$ 页是坏的，有 $Q$ 个人分别从 $q_i\le N$ 开始读，只读 $q_i$ 的倍数，坏的不读， 求共读了多少页

题解

直接暴力就行了，类似埃筛(complexity $O(n\log n)$))注意将相同 $q_i$ 存一下

code

code

B.The Equation

这题的意思是，找一个最大的 $k\ge0\ s.t.\ \sum k\land A_i \le M, M\le 10^{15},A_i\le 10^{15}$

分析

从最高位开始，如果那一位能够置为 $1$， 那就置为 $1$, 否则放 $0$

最高位能置为 $1$ 的条件是，后续和的最小值 $\le M-val(highest\ bit =1)$

complexity $O(\log M)$

code

code

C.Shifts

这题就更简单了，直接暴力枚举 $3^{20}$ 种状态就行了

code

更新了一个 $O(3^{N/2})$ 的做法

见:pbds

版权声明

本作品为作者原创文章，采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议

作者: taotao

仅允许非商业转载，转载请保留此版权声明，并注明出处