广东实验中学 省实信奥2队
https://vjudge.net/contest/594105
11.11
早上坐车打狼人杀。
下午是开幕式，孙教授的口才真的不错，很好笑。
然后是热身赛。
15:30 热身赛
只有三个题。
看到题目背景和格式还以为是什么省选模拟赛。。。
A
昨晚 pht 讲过这个题，直接不配 .vimrc 在赛前写好代码，但是 0:00:36 没有一血（草）
强化条件为没有奇环，考虑一个分治，左右两边连满二分图，内部的递归下去，分治大概十层左右，同一层用同一种颜色。
更加强大的，__buildin_ctz(u xor v)。
B
C 看上去很难，所以我写 B，但是写着写着乱了，直接不会的，本来说秒了的。最后是黄队写的。
不等式左右两边同乘 \(2\times 10^L\) 即可避免浮点运算。因为 \(\sum p_i=1\)，特判 \(p=1\) 之后因为 \(K=10^6\) 必定是一个合法答案，所以直接枚举答案。然后有一些上下界，加起来看看 \(K\) 在不在范围内。
C
看了很久，大概是什么前缀最小值右移一位，沈队想暴力数据结构维护，但是他不会。黄队没啥想法，一直假。然后我很慌。我们看到有一队 7 分钟过了 C，想是不是诈骗的。
发现我们很会询问全局：维护所有数字到 priority_queue 中，每次放一个 \(x\) 进去之后，把最小值干掉。更多的操作时，也可以这样操作，或者将所有操作的 \(x\) 全部放进 priority_queue，然后弹出同等数量的最小值，是等价的。因为后面不影响前面，所以可以将询问拆成两个前缀之差，然后离线询问，把询问的 \(x\) 插到数列最前面。
问题变成了查询区间的前 \(k\) 小值之和。任意数据结构即可（如以下标为版本，以值域为线段树信息建立可持久化线段树，查询时二分）。\(O(n\log n)\)。
黄队说这个题很妙，确实很厉害！！！
热身赛结束
AK
晚上
吃饭，狼人杀，回酒店，没看无人机表演（看了拍摄图片很厉害，遗憾了），狼人杀，黄队演唱会，睡大觉。
11.12
行李神秘寄存，不能带电子产品和水。
0:00:00（9:00）
比赛开始，.vimrc 调试好了，然后三个人随机看题。
我看了一下 I，一开始以为 \(b\) 的值域很小可以直接枚举 \(b\)，特判 \(k=2\)（实际上两个都不是），声称要写，然后就在写。写的时候发现越来越假了，发现一个 \((a-b)|n\)，需要 Pollard-Rho，我们带了板子，可能会很久。
黄队说他会 A，于是马上把电脑给他写了。
赛后题解：按照值域分治，分治到 \([L,R]\)，取 \(mid=(L+R)/2\)。假设现在的 \(a\) 全是 \(L\)，将 \(>mid\) 的数字二操作加，然后统一用一操作抬到 \(mid+1\) 上，\([L,mid]\) 和 \([mid+1, R]\) 分治下去。
0:30:06 通过 A (-1)
沈队发现榜上过了很多 F，声称是签到题，于是电脑给他写。根本没有看题。
赛后题解：直接分讨一下？
0:47:39 通过 F (+)
我想清楚了 I 题，就是因为 \((a-b)|n\)，然后考虑 \(c=a-b\) 的 \((b+c)^k-b^k\)，展开之后有一项 \(b^{k-1}\)，因为这玩意 \(\leq 10^{18}\) 所以 \(b\leq \sqrt[k-1]{10^{18}}\)，开 __int128。Pollard-Rho 枚举 \(c\)，二分找到 \(b\)。
赛后反思：太麻烦了吧。。。
然后他们在看其他题，口胡出很多能写的题，然后喊我写快点。
1:26:58 通过 I (+)
L 题是一个期望 DP，一开始看了没啥思路，开了 IJKLM 然后只会 I 题（？？？），看了 BCD 又不会（？？？），非常伤心了。
沈队说了一遍他的 DP。我觉得很对，然后他就过掉了。期间写错一个模数和若干 \(m, k\) 互换。
2:06:35 通过 L (+)
这时候的排名有点不好看，需要加快进度。
标签：10,CCPC2023,深圳,分治,mid,然后,黄队,00,游记 From： https://www.cnblogs.com/caijianhong/p/travel-in-ccpc2023-shenzhen.html