跳转至

ICPC Camp Day 2

排名 当场过题数 至今过题数 总题数
29/183 6 7 11

A

upsolved by

题意

题解

B

upsolved by

题意

题解

C

upsolved by

题意

题解

D

upsolved by

题意

题解

E

upsolved by

题意

题解

F

upsolved by 2sozx

题意

\(t_i = popcount(i) \bmod 2 \(，\)q\) 次询问，每次问一个区间 \((l_i, r_i)\) 构成的 \(01\) 串最早在哪个位置出现。$q\le 10^5, l\le r \le 10^{18} $

题解

令 \(T\) 为 \(t\) 构成的 \(01\) 串，首先我们证明 \(T(0 \to 01, 1 \to 10) = T\) 。

考虑位置 \(i\) ，如果 \(t_i = 1\) ，那么显然 \(t_{2i} = 1, t_{2i + 1} = 0\)，并且 \(t_i = 0\) 同理。考虑我们做 \((0\to 01, 1\to 10)\) 的变换，前 \(i - 1\) 位变换后成立，那么显然前 \(i - 1\) 位变换后占 \(0 \sim 2\times i - 1\) 位，第 \(i\) 位变换后正好在第 \((2i, 2i + 1)\) 位，因此变换成立。

将询问分成几种情况：

  • 如果询问长度 \(r - l + 1\) 比较小，我们可以暴力预处理出来出现的位置。
  • 考虑询问长度大，由于上面的变换关系，所有子串都是由某些位置进行替换后得到的，我们可以将 \((l, r)\) 逆变换到 \((\lfloor \dfrac{l}{2}\rfloor,\lfloor \dfrac{r}{2}\rfloor)\)，知道了 \((\lfloor \dfrac{l}{2}\rfloor,\lfloor \dfrac{r}{2}\rfloor)\) 的出现的最小位置后 \(\times 2\) 就是 \((l, r)\) 的最小位置，需要注意的是 \(l \bmod 2 = 1\) 时需要 \(+1\)，因为此时 \(l\) 并不是恰好 \(f(\lfloor \dfrac{l}{2}\rfloor,\lfloor \dfrac{r}{2}\rfloor)\times 2\) 得到的位置 ，即 \(f(l, r) = f(\lfloor \dfrac{l}{2}\rfloor,\lfloor \dfrac{r}{2}\rfloor) \times 2 + (l \bmod 2)\)

G

upsolved by

题意

题解

H

upsolved by

题意

题解

I

upsolved by

题意

题解

J

upsolved by

题意

题解

K

upsolved by

题意

题解

L

upsolved by

题意

题解

记录

0h：3min一堆人过A了，ZYF MJX看A，MJX YY了一个结论，给ZYF，ZYF感觉很对就写了，去看J，CSK在看D。MJX感觉把J移项可以变成很好看的式子，然后枚举就行了，ZYF用pollar rho去搞质因数了，问MJX rho返回啥，MJX忘了以为就是返回一个质因数，ZYF就直接写了。CSK给MJX说了一个D的做法，MJX感觉太对了，然后CSK想了想k=0的情况好像也对，MJX想了想也对就直接写了。

1h：DWA了，J疯狂CE！（MJX的pollar rho板子迷惑之CE，高版本C++直接寄）ZYF疯狂改，疯狂CE。

20220209Huaweiday2J.png

CSK看了看好像k=0时四元环就行，改了一发，寄了，想了想五元环也行，改了一发又寄了。ZYF对拍拍出来发现rho显然只返回其中任意的因数（MJX自裁），改了过了。MJX想了想D题n=6时也可以更优，改了过了。挂会机！。

2h：把题都过了一边，感觉还是C可做一点，ZYF想了想感觉这个题里面 \(p\) 没有用，就当作都往右走了，ZYF改了两版题意，第二版俩人都不咋会（from zzh的感觉第二版确实写起来很简单），MJX把第一版的贡献推了个逆天式子，然后还得逆天容斥，ZYF感觉可写，感觉要写麻了。

3h：ZYF写完了交了WA了，看了会发现有地方是负数没取 mod ，改了过了。剩下的感觉都不可做（，乱玩了。MJX给ZYF讲了讲B的题意，范围挺小的，ZYF感觉可以直接暴力，复杂度起飞~。MJX和CSK去YY G，MJX忘了有空间限制搞了个 \(n^2 \log{n}\) 的做法，后来想想YY了一个可以空间 \(O(n)\) 的做法，开写去了。

4h：MJX写完交了测了一年过了，ZYF B T42了，毕竟暴力状态太多了，ZYF加了个"小优化"，不用跑完所有状态，只跑到每一行都bfs过就停止，过了（，快的飞起，迷惑。

总结

  • MJX：把板子改成好用点的，太垃圾了(x

Dirt