p_b_p_b的博客

博客

Public NOIP Round #5 题解

2023-02-25 16:00:21 By p_b_p_b
  • 搬题人
    • 青鱼和序列:p_b_p_b
    • 青鱼和怪兽:Qingyu
    • 青鱼和区间:alpha1022
    • 青鱼和游戏:ShanLunjiaJian
  • 组题人:Qingyu
  • 题解:alpha1022, Qingyu, ShanLunjiaJian, p_b_p_b

青鱼和序列

来源:

Tutorial by p_b_p_b.

注意到使用操作二会使得序列变成回文串,于是接下来使用操作一和操作二就没有任何区别了。

因此直接枚举第一次使用操作二是在第几轮,以及特判每次都用操作一的情况,即可得到答案。

事实上还可以注意到,只要用过操作二,无论操作序列如何,最终答案都相等,所以枚举也可以省去。

复杂度 $O(n+\log m)$ 。

青鱼和怪兽

来源:

  • Petrozavodsk Summer 2014. Day 4. Moscow SU SG Contest, Problem J

TBD

青鱼还在咕,来帮青鱼补一下。

本题难点显然在于打不动了可以重开,因此无脑 dp 会成环。

有环的 dp 的一般解决方案是用未知数把环上的一个点替代掉,然后用未知数把其他所有状态的 dp 值表示出来。

如果设 $dp_{n,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$ 。这样就做完了。

青鱼和区间

来源:

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)$。

青鱼和游戏

来源:

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)$了。提交记录

评论

Alphaban
有没有C详细一点的做法?QAQ
  • 2023-02-25 20:47:23
  • Reply
jinhaoxian
其中 $c_i$ 表示前缀连续 $1$ 个数为 $i−1$ 的数的个数
  • 2023-11-16 11:03:03
  • Reply
tzl_Dedicatus545
TBD是啥玩意p_b_p_b
  • 2023-02-25 16:38:33
  • Reply
tzl_Dedicatus545
TBD是啥玩意p_b_p_b
  • 2023-02-25 16:38:34
  • Reply

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。