- 搬题人
- 青鱼和序列:p_b_p_b
- 青鱼和怪兽:Qingyu
- 青鱼和区间:alpha1022
- 青鱼和游戏:ShanLunjiaJian
- 组题人:Qingyu
- 题解:alpha1022, Qingyu, ShanLunjiaJian, p_b_p_b
青鱼和序列
来源:
- 2022 China Collegiate Programming Contest (CCPC) Guilin Site, Problem C
- https://codeforces.com/gym/104008/problem/C
Tutorial by p_b_p_b.
注意到使用操作二会使得序列变成回文串,于是接下来使用操作一和操作二就没有任何区别了。
因此直接枚举第一次使用操作二是在第几轮,以及特判每次都用操作一的情况,即可得到答案。
事实上还可以注意到,只要用过操作二,无论操作序列如何,最终答案都相等,所以枚举也可以省去。
复杂度 O(n+logm) 。
青鱼和怪兽
来源:
- Petrozavodsk Summer 2014. Day 4. Moscow SU SG Contest, Problem J
TBD
青鱼还在咕,来帮青鱼补一下。
本题难点显然在于打不动了可以重开,因此无脑 dp 会成环。
有环的 dp 的一般解决方案是用未知数把环上的一个点替代掉,然后用未知数把其他所有状态的 dp 值表示出来。
如果设 dpn,m=x ,根据转移方程不难发现,每个状态的 dp 值都可以写成一大堆关于 x 的一次函数取 min ,且 x 的系数应当都 \le 1 。
一次函数取 \min 会得到一个凸壳,第一条边的斜率 =1 ,后续的斜率都 \le 1 。只要暴力维护分段函数,得到 dp_{n,m} 的分段函数 f(x) ,那么答案就是 x=f(x) 的最大的解。之所以要最大是因为 (n,m)\to (n,m) 的转移是不存在的。
直接维护这个分段函数大概是过不去的。但是通过以上的分析不难发现可以二分答案 x ,做一遍 dp ,判断是否有 dp_{n,m}\le x ,如果有就 ans\le x ,否则 ans>x 。这样就做完了。
青鱼和区间
来源:
- CSAcademy Round #35, Counting Quests
- https://csacademy.com/contest/round-35/task/counting-quests/
Tutorial by alpha1022.
题意就是要求用询问区间区分出每道题目。
记覆盖 i 的区间集合为 S_i,则所求即 S_i 互不相同,但这并不好直接计算。
接下来我们注意到一个重要性质:对于任意方案,不会存在 i_1 < i_2 < j_1 < j_2 使得 S_{i_1} = S_{j_1} \ne S_{i_2} = S_{j_2}。
这个性质使我们联想到括号序列。因此,考虑如下的构造:维护指针 i,初始时 i=1,每次取 \max \{ j \mid S_i = S_j \},并令 i=j+1。注意到,所有区间要么是在某个 [i+1, j-1] 内部,要么是以某个 i 为左端点,某个 j 为右端点。并且,我们至少可以保证可以将每个数区分到某个区间中。
注意到,若确定了分段方案 [i_1, j_1], [i_2, j_2], \dots, [i_k, j_k],则段内的区间可以任意选取,而跨过段的区间选择的方案数就是我们所要求的答案:选择若干 [1, k] 的子区间区分出所有 k 道题的方案数。
因此我们考虑一个容斥:用 2^{\binom{k+1}2} 减去不能区分出所有题目的方案数,同时维护一个背包数组用来计量分段的方案数,由此即可递推得到答案。时间复杂度 O(n^3)。
这还是一个生成函数的复合方程,借助拉格朗日反演可以做到 O(n \log n)。
青鱼和游戏
来源:
- Polish Olympiad in Informatics 2016, Not Nim
- https://szkopul.edu.pl/problemset/problem/M5CruI5eCu8elnNFHuiXBrvV/site/
Tutorial by ShanLunjiaJian.
算法0
显然青鱼的每一步都会清空一堆。
我们计算青鱼的步数x,那么答案就是2x-1。
首先考虑一下这个游戏会如何进行。青鱼一旦操作一堆(x,y)\rightarrow (x,0),缺头鱼必然跟着把这一对摊平成(\lfloor\frac{x}{2}\rfloor,\lceil\frac{x}{2}\rceil)。如果一对堆都空了,缺头鱼不得不把一步用到别的某对堆x^\prime,y^\prime,那么假设x^\prime\leq y^\prime,他必然会把这对堆变成x^\prime+1,y^\prime-1。
我们将青鱼把一对中大的拿走这个操作称为拿,缺头鱼把一对中有一个0的摊平称为摊,缺头鱼把两堆大小相同的一对搞的不同称为炸。如果只有拿和摊,可以发现答案就是2\sum\limits_i(\lg a_i+1)-1。炸可能减少步数,并且可以发现如果减少了只可能是减少一步。
看看二进制,设一对是a,a,如果a的二进制表示全1,那么一轮炸-拿-摊可以把a的长度减少1,如此一直进行a的长度次就能在这一对上减少一步,但一旦中断就不可能再减少一步了。如果a中有0,那么先使用若干轮拿-摊直到全1,此时仍然可能减少一步,因此这样做必然不劣。
于是青鱼在一开始会把每一对都搞成全1的形状,然后两鱼每次都会选择最长的那一对操作,缺头鱼如此选择是因为最长的最不容易产生作用,青鱼则要逼缺头鱼往短的上走,这个还是比较自然的。青鱼一旦先手操作一堆就会操作干净,因为它上面不可能再省下步数了,而缺头鱼先手操作一堆会让这一堆长度减少1。最后每一堆长1的都能贡献,不过如果青鱼先手则有一堆不行。
此时我们可以对于每个前缀连续1个数求出它的出现次数,然后对着这个数组模拟,复杂度O(q(n+\log v))。结合两个答案只跟区间长度相关的特殊性质,可以通过前6个测试点。
算法1
当然可以用数据结构维护这个出现次数!前缀和可以通过测试点7,8,BiT简单卡卡常可以通过测试点9,10,11。
这个做法空间是O(n\log v)的,为了砍掉这个\log v,我们对底层按\log v大小分块,维护块间的BiT,时间复杂度不变而空间变为线性,可以通过12,13,14,提交记录,卡卡常大概能过15,16。使用avx可能可以直接草过去。
算法2
观察模拟的代码。这是搬题人写的一份代码 :
const int B=40;
inline int query(int l,int r)
{
int c[B+1]={0},p[B+1]=0,g=0;
for(int i=l;i<=r;i++) c[__builtin_clzll(~(a[i]<<__builtin_clzll(a[i])))-1]++,g+=(65-__builtin_clzll(a[i]));
for(int i=B;i>0;i--) c[i-1]+=(c[i]+p[i])/2,p[i-1]=p[i]^(c[i]&1);
return 2*(g-(c[0]-!p[0]))-1;
}
其中c_i表示前缀连续1个数为i-1的数的个数;p_i=0/1表示进行到c_i中的对时的青鱼是先/后手,g是不考虑炸的答案。可以发现这里如果把循环各轮的c,p分别倒过来组成一个二进制数,我们就是计算了c和p的和,不过c的每一位可以>1,并且进到B位就停止。接下来使用这个定义的c,p(也就是说它们都是倒过来的)。
继续考虑p是什么,可以发现它就是c+p上"经过"每一位的值的奇偶性的前缀和,也就是说如果向第i位发生了一次进位,对p_{j\geq i}的贡献就是\operatorname{xor}上一个1。注意到如果c的某位值\geq 2则必然向下一位进位,考虑一下发现我们在c上做完这些进位,做法就是直接加起来,最后再跑一遍上面的模拟即可。用BiT支持单点修改区间求和,复杂度O(q(\log n+\log v))。提交记录。
算法2.5
怎么砍\log v?下面这个做法由 hehezhou 发现。喝喝粥好闪,拜谢喝喝粥!
考虑扫过某个c_i=1的i时会发生什么,发生进位当且仅当p_i=1,否则这一位保留1,p_{i+1}变成1。如果p_i=1,那么p_{i+1}=0,于是c_{i+1}=1的话它得到i的进位而继续进位,否则它必然不会进位。于是我们知道经过连续的一段1之后p又变回1,而类似1111这样的东西它的c+p是00001。也就是说它不会改变第一个1,而在经过第一个1之后它的效果就是把每个1连续段清空并把连续段后一位赋为1。
我们只关心c_B-\operatorname{not}p_B(不考虑B及以上位的初值)。讨论一下 :
如果c全0,那么c_B=p_B=0。
如果c_{B-1}=0,那么c_B=0,p_B=1。
如果c_{B-1}=1,p_{B-1}=0,那么c_B=0,p_B=1。
如果c_{B-1}=1,p_{B-1}=1,那么c_B=1,p_B=0。
只有第一个case的结果是1,所以我们知道c_B-\operatorname{not}p_B=1当且仅当c全0。这样就O(1)了。提交记录。