UOJ Logo C_SUNSHINE的博客

博客

UOJ NOI Round #2 题解

2017-07-13 13:39:31 By C_SUNSHINE

先来个小问题?

MysteryMan 是谁呢?

关于这点,我只能告诉你无可奉告,你们不高兴也不行。

好吧其实是一个2009年左右的不愿透露姓名的OI选手……

Day1

UOJ拯救计划

from MysteryMan, 题解 by ydc

大家好,这是 MysteryMan 出的题,题解由失踪多年的ydc来写。

这题说白了就是求解图染色方案数,由于图染色问题是NPC的,因此只要你输出答案模6的值。

对于前$30\%$的数据,我们直接爆搜即可,$O(k^n)$。

对于$4,5$两个测试点,由于$k=1$,我们发现只有当$m=0$时有解(且解为$1$)。当然爆搜也是可以的。

对于$6$号测试点,由于是一棵树,我们可以用组合计数的方法得知答案为$k*(k-1)^{n-1}$

对于满分做法,我们首先可以推导得知答案为$\sum\limits_{i=1}^k A(k,i) \times $恰好用$i$个颜色染色的方案数,A为排列数,然后由于答案要模$6$,因此当$i \ge 3$时,对答案贡献为$6|A(k,i)$。

所以我们唯一要做的就是考虑$i=1,i=2$,当$i=1$的话,只有当$m=0$的时候才有解,所以问题就是只考虑$i=2$了。

我们知道,对于一个联通的二分图,确定了一个点后,其余点的颜色就都确定了。因此,我们判断整张图是否是二分图。如果不是二分图,直接输出$0$,否则统计联通块个数,输出2的联通块个数次方即可。

最后有一个小细节即$m=0$,因为当$m=0$的时候,恰好用两个颜色染色的方案数就不是2的联通块个数次方,而要减去全黑和全白。

这题还有另一个思考的思路,即色数多项式——一张$n$个点图的染色方案是关于$k$的$n$次多项式,记作$f(k)$。我们要想知道$f(k)$模6的值,只要知道$f(k)$模$2,3$的值即可。要想知道$f(k)$模$2,3$的值,只要知道$f(0),f(1),f(2)$模$2,3$的值即可。然后就能得到一个殊途同归的算法。

排兵布阵

from MysteryMan, 题解 by jiry_2

收题的时候我感觉这题应该是 T3 的,但是当了几个月甩手掌柜之后发现这题被放到了 T2..感觉组题的人有点石乐志。

C_SUNSHINE:“行吧我石乐志……”

算法一

直接 $O(n^2)$ 暴力,可以通过第一个数据集。

算法二

没有移动操作,那么可以用处理矩形加,询问矩形信息的数据结构 kd-tree 来做。

时间复杂度 $O(n \sqrt n)$,可以通过第二个数据集。

当然肯定有其他复杂度更低的方法。

算法三

因为这是一道对着 idea 出的题,所以不排除有简单的算法或者复杂度更低的算法,但是这题的 idea 本身还是很妙的。

考虑这么一个数据结构:我们对平面里的每一行统计这一行的点数 $nx_i$,每一列统计这一列的点数 $ny_i$。对于一个点 $(x,y)$,如果 $nx_x \geq ny_y$,那么它就作为 $y$ 列的关键点,否则就作为 $x$ 行的关键点。

不难发现每一行每一列的关键点个数都是严格 $O(\sqrt n)$ 的。

于是思路就是每一个操作,都是关键点上暴力,非关键点打标记,同时对每一行每一列维护非关键点的权值最大值。这样每一次操作都是严格 $O(\sqrt n)$ 的。

只要利用好每一个点要么是行关键点,要么是列关键点,那么每一个操作都可以顺其自然的暴力了。

思路虽然简单但是细节还是比较多的:

维护权值

这个问题的核心在于把横纵的修改和询问联系起来。在刚才那个结构中,可以定义一个行关键点 $(x,y)$ 的权值为它的点权加上列 $y$ 上的非关键点加标记。

这样在行操作的时候,我们把每一个行关键点的点权修改一下,同时更新这个关键点所在列的非关键点最大值。列操作类似。

关于合并

关于合并一个简单的想法是,直接把关键点集合并起来,然后把非关键点最大值取个 $\max$,但是实际上没有那么简单。

首先是标记,在合并两个有标记的行的时候,因为标记是不能下传的(下传要遍历每一个非关键点并修改,复杂度爆炸了)。所以标程的做法是对行和列分别维护一个并查集,同时用类似同态加边判断是否是二分图的方法,在并查集的每一条边上维护儿子和父亲的标记差。

这样对于一个原来坐标是 $(x,y)$ 的点,我们要看它列上的标记,只要在列并查集里求它到根的边权和就可以了。

接着,因为在合并了两行之后,行的点数变多了,所以一些行关键点会变成列关键点。这个时候我们要遍历所有行关键点,然后看关键点是否会跑到另一边去。因为一次合并之后关键点也是 $O(\sqrt n)$ 的,所以这一步也可以暴力。但是要注意的是行关键点变成列关键点后,这个点的点权要根据行列的标记修改一下以满足我们刚才的定义。

关于去重

行列的关键点个数是 $O(\sqrt n)$ 的分析建立在没有重点的基础上,但是合并的过程中会出现重点,这个时候我们需要对关键点去重。

去重的过程相当于把所有相同位置的关键点变成一个点,且权值为这个位置所有关键点的最大值。

如果每一次合并都去重的话,去重的复杂度在瓶颈上,必须要写 hash 之类的方法,常数较大。

实际上可以设一个阈值 $S$,例如 $\frac{3}{2}\sqrt n$,然后在每一次我们要暴力扫关键点集合的时候,如果我们发现关键点数量超过了 $S$,那么就进行一次去重。

因为每一次去重都至少删掉了 $O(\sqrt n)$ 个点,而总点数只有 $n$,所以去重的复杂度不在瓶颈上,可以用 map 暴力。

综上,这个算法的时间复杂度是 $O(n \sqrt n)$ 的,并查集、去重的时间复杂度都不是瓶颈。可以通过后两个数据集。

第三个数据集的用意是避免掉合并操作时标记合并的一些细节。当然可能存在着一些针对性的算法。

个人感觉这题的 idea 还是挺不错的,但是好的 idea 到好的题目的过程还是有点难.. 之前思考熊那题就是这么翻车的。这题虽然有 $6$ 个操作但是因为横竖是对应的如果写的好的话应该可以只写 $3$ 个操作,或者竖的部分可以从横的部分贴过来改一下。因此代码量虽然略大但是应该还是在 OI 比赛可接受范围内,当个 T3 挺合适的。

(不过 UNR 传统是 T2 最难?)

C_SUNSHINE:“Exactly!”

黎明前的巧克力

from sevenkplus, 题解 by C_SUNSHINE

题解很啰嗦,觉得想的差不多的可以直接看算法七。

算法一

我们可以 $3^n$ 直接枚举每个巧克力是在 Evan 的集合 $A$ 里还是 Lyra 的集合 $B$ 里,并判断异或值是否相等,时间复杂度$O(3^n)$,期望得分 5 分。

算法二

我们重新考虑算法一,我们可以先枚举一个巧克力是否在 $A + B$ 里,再考虑是再谁的集合里,由于两个集合的异或值相等,$A + B$ 的异或值一定为 $0$,接着观察可以发现, Evan 可以选择 $A + B$的任何一个子集作为 $A$,Lyra 只要选择其补集即可,所以我们只要对于所有异或和为 $0$ 的集合 $S$,把 $2^{|S|}$ 加到答案里去就好了,最后别忘了 $-1$ 去掉 $S$ 为空集的情况。

如果我们枚举所有可能的 $S$ 集合,我们的算法复杂度就是$O(2^n)$,期望得分 15 分。

算法三

当$a_i$的值域不大的时候,显然这个东西我们是可以DP的,定义一个集合 $S$ 的权值为 $2^{|S|}$。我们可以用 $f_{i,j}$ 表示,前 $i$ 个数,异或和为 $j$ 集合的权值和。那么转移时枚举当前数选不选:

$f_{i-1,j} \rightarrow f_{i,j}$

$f_{i-1,j}\times 2 \rightarrow f_{i,j~xor~a_i}$

用 $m$ 表示最小的 $k$ 满足所有 $a_i$ 都小于 $2^k$,这个做法的时间复杂度是$O(n2^m)$的,结合前面的算法,期望得分 30 分。

算法四

注意到有部分数据不同的数字种类数不算多,我们可以发现一个数字选奇数个对异或和的贡献都是一样的,于是我们用组合数预处理每个数选奇数个/偶数个的权值和,再按数字DP,每次枚举当前数字是选择奇数个还是偶数个进行转移即可,转移方法类似算法三。

假设有 $D$ 个不同的数字,时间复杂度是 $O(D2^m)$,期望得分 40 分。

算法五

继续观察算法三,可以发现每次转移相当于是原数组和当前数组 $F_{a_i}$ 做了一个 $XOR$ 卷积,当前数组 $F_{a_i}$ 满足 $F_{a_i}(0)=1$,$F_{a_i}(a_i)=2$,其他位置上都是 $0$,那我们考虑使用快速沃尔什变换(FWT)来优化这个位运算卷积。

对每一个数 $a_i$ ,都求出 $FWT(F_{a_i})$,然后把这些变换之后的数组乘起来,在逆变换回去得到 $G$,最后输出 $G(0)$ 即可。

这样,你就可以获得…… 0 分了,可以发现这算法的复杂度是 $O(nm2^m)$ 的,会全部TLE。

算法六

作为新时代的OI少年,我们一定要把这个FWT优化到极致,继续观察这个FWT的性质,可以发现 $F_{a_i}$ 只有两个位置上有值,那不妨把 FWT 的结果打印出来观察一下——

可以发现每个位置都是 $-1$ 或者 $3$。

由于FWT是线性变换,即$FWT(F_1+F_2) = FWT(F_1)+FWT(F_2)$,所以若第 $a_i$ 位上的 $2$ 对 $x$ 位置贡献了一个 $+2$ 则第 $x$ 位上是 $3$,反之贡献了 $-2$ 导致 $x$ 位置上是 $-1$。

接着观察可以发现,当 $x~and~a_i$ 的二进制中有偶数个 $1$ 时,贡献为 $+2$,否则贡献为 $-2$。

为什么呢?

不妨采用高维FFT理解FWT来证明一下,我们把数字 $x$ 二进制下的第 $k$ 位用 $x_k$ 表示,则FWT可以写成:

$$FWT(F)(n) = \sum_{k=0}^{2^m-1} \left(F(k) \prod_{j=0}^{m-1}(-1)^{n_jk_j}\right)$$

由于 $01$ 变量的乘法可以看成 $and$,令 $bitcount(x)$ 表示 $x$ 二进制中 $1$ 的数目,则:

$$FWT(F)(n) = \sum_{k=0}^{2^m-1} F(k) (-1)^{bitcount(n_j~and~k_j)}$$

那么这个式子怎么算呢?

不妨考虑枚举 $t=n_j~and~k_j$,在枚举 $s$ 是 $t$ 的超集即$s~and~t = t$,则能收到 $s$ 的贡献的位置 $x$ 满足的条件是,$t$ 的超集集合中,除了 $t$ 为 $1$ 的那几位之外,与 $s$ 没有交集的 $x$。只考虑 $t$ 之外的位,可以发现 $s$ 的贡献其实是针对一个子集的,所以我们只要对子集打上标记,最后补集转化后做子集和变换就可求得贡献和了。

现在我们会求所有元素的贡献和了,可我们要的不是贡献和啊,我们要的是贡献积,这怎么办呢?

假设对于某一个贡献和为 $s$ 位置,$x$ 个数贡献了 $-1$,那么就有 $n-x$ 个数贡献了 $3$,于是列出方程 $3(n-x)-x=s$,可以解得 $x=\frac{3n-s}{4}$。

解出 $x$ 之后,贡献积就是 $(-1)^x \times 3^{n-x}$了,用快速幂计算即可,之后逆FWT回来输出 $G(0)$ 就可以了。

由于要枚举集合和超集,还要做子集和变换,时间复杂度是 $O(n+m3^m)$,结合前面算法期望得分 65 分。

算法七

之前提到过,对于贡献和为 $s$ 位置,设$x$ 个数贡献了 $-1$,列出方程 $3(n-x)-x=s$,可以解得 $x=\frac{3n-s}{4}$,接着贡献积是 $(-1)^x \times 3^{n-x}$了,用快速幂计算即可。

那么观察算法六我们的推导过程,可以发现我们对FWT做了细致的解析,然而既然我们知道他是FWT,其实完全可以不做这个解析,直接用FWT计算贡献和即可。

简单来说我们直接把每一个数的数组 $F_{a_i}$ 加起来,然后做FWT,通过贡献和求出贡献积,在逆FWT回去就能求出答案数组了。

只需要使用 $FWT$ 和快速幂,时间复杂度 $O(n +m2^m)$,期望得分 100 分。

算法八

$$FWT(F)(n) = \sum_{k=0}^{2^m-1} \left(F(k) \prod_{j=0}^{m-1}(-1)^{n_jk_j}\right)$$

这个式子,其实是可以DP计算的,令 $dp_{i,j}$ 表示前 $i$ 位任意,后 $m-i$ 位和 $j$ 相等的数,乘以 $(-1)^{|t|}$ ($t$ 是前 $i$ 位与 $j$ 的交集)的总和。

转移时只用枚举当前位变为前 $i$ 位是,是变成 $1$ 还是变成 $0$,如果第 $i$ 位变成 $1$ 还要考虑当前数字在第 $i$ 位是否为 $1$ 以决定是否要乘以 $-1$.

这个 $DP$ 的复杂度是 $O(m2^m)$的……

不过,明眼人一下子就看出来了,这个DP其实就是一个按位分层求FWT的东西……

除此之外还有一个优化,在做逆FWT的时候,由于我们只要求 $G(0)$,可以发现 $G(0)$ 就是逆变换前数组中所有的元素之和,再乘以 $2^m$ 的逆元,所以直接扫一遍求和即可,不用逆FWT,这样常数可以减小很多。

这样FWT就完全被(或者假装被)省略了……

一个用FWT推完的题代码里没有FWT也是一件有趣的事呢?

时间复杂度$O(n+m2^m)$,期望得分 100 分。

Day2

积劳成疾

from MysteryMan, 题解 by C_SUNSHINE

算法

介于除了最基本的 20 分部分分,其他部分分似乎都比std难写……

于是我们直接说std做法吧!

令 $f_{m,n}$ 表示最大值不超过 $m$,长度为 $n$ 的序列的劳累度之和。

那么首先对最大值是否等于 $m$ 分类,若最大值不为 $m$ 则可以直接加上$f_{m-1,n}$。

接着考虑最大值为 $m$ 的情况,我们不妨枚举最大值第一次出现的位置 $p$,即 $a_p = m; a_{i} < m (1 \leq i \leq p-1); a_{j} \leq m (p+1 \leq j \leq n)$

可以发现,所有包含位置 $p$ 的若干个区间的劳累度都确定了(不妨即为 $c$ 个),为 $w_k$,除了这些区间,$p$ 把整个序列分成了互相独立的两个部分,根据期望线性性,这个序列的劳累度期望为左侧序列劳累度期望乘以 $m^c$ 再乘以右侧序列劳累度的期望,于是就可以 $O(n)$ 转移了。

即 $f_{m,n} \leftarrow \sum_{p=1}^{n} f_{m-1,p-1} \times m^c \times f_{m,n-p}$

时间复杂度 $O(n^3)$,期望得分 100 分。

梦中的题面

La tâche est écrite par ftiasch,

et la solution est écrite par matthew99

算法一

枚举前$m - 1$个数,算出第$m$个数的可能数量,期望得分10分。

算法二

考虑容斥,枚举有哪些数超过了限制,然后使用可重组合数算出方案数,时间复杂度为$O(2 ^ m m)$,期望得分30分。

算法三:

考虑数位DP,记录当前每一个数与限制的大小关系,然后枚举下一位的值,如果使用二进制并采用逐位逐数转移的话,时间复杂度为$O(2 ^ m m ^ 2 \log {b})$,期望得分30分。

算法四:

考虑$c = 1$,如果我们在b进制下进行数位DP,那么我们发现对于从第$x$低位,恰好有$m - x + 1$个数可以取任意$0$到$b - 1$之间的值,剩下的$x - 1$个数只能是0。首先求出$a$个取$0$到$b - 1$的数和恰好为$b$的方案数$\text{ways}_{a, b}$,考虑从低位开始进行DP,维护$sum{x_i} - n$的值,通过记录当前位的进位(或者退位)数,通过前面求出的$\text{ways}$我们很容易进行转移。由于$sum{x_i} < n$,因此最后必须退一位(也可以看成进位为-1),于是我们也很容易求出答案。

时间复杂度为$O(m ^ 2b ^ 2)$,期望得分60分。

算法五:

考虑$c = 0$,那么无非就是有一些$x_k$可以取恰好$b ^ {k + 1}$,也就是,它在前$k$位都必须取0,第$k + 1$位取1,我们很容易通过给DP加一维来实现转移,也就是记录当前有多少数必须取0,那么最开始显然这个数的数量可以任意(因为可以有任意个$x_k$恰好取了$b ^ {k + 1}$),转移就是对于第$k$位枚举$x_k$是否取了$b ^ {k + 1}$,如果取了的话,它本来就必须取0,于是必须取0的数数量不变,否则取0的数个数需要加一。

时间复杂度为$O(m ^ 3b ^ 2)$,期望得分100分。

算法六:

我们考虑从高位往低位进行数位DP,那么取0的个数最开始是$n$,这一维的转移也很好转移。

这个时候我们就不能记录进位了,我们记录从第$k + 1$位开始往后,$n - sum{x_i}$的值,如果这个值大于$m$,那么就是前面所有$x_l$全取$b ^ {l + 1}$也不可能使这个值小于等于0,于是我们只要在0到$m$中枚举,同理,我们也只要考虑这一位之后$n - sum{x_i}$在0到$m$的情况,于是我们枚举这个值,这样我们可以将复杂度降到$O(m ^ 2b ^ 2)$,期望得分100分。

解开尘封的仪式

from sqc, 题解 by sqc

sqc太菜了,他的提答被A穿了,就当送分好了……

炸弹熊

这种不是NPC问题的求最优解的东西果然不适合造提答……数据太难造了QAQ (出题人尽力克制数据包不太大结果出锅了QAQ)

这次提答不良心都是我的锅QAQ

下面说一下每个点的解法吧(当然还有其他做法吧):

测试点1

哇,这是一条链!我会Manacher或回文树!时间复杂度 $O(n)$ 。

测试点2

这个点字符全是 $a$ 啊,拓扑排序找最长路就没了啊。时间复杂 $O(n+m)$。

测试点3

这个点是由 $1 \rightarrow 2,1 \rightarrow 3,2 \rightarrow 4,3 \rightarrow 4$ 这样的基本单位组成的。

枚举中点,暴力向两边拓展即可。

测试点4

一个比较小的一般的DAG。

考虑 $f[k][u][v]$ 表示是否存在长度为k的路径,起点是u,终点是v,然后存一下正图和反图,转移一下。

测试点5

这个图是由一堆链构成的,且链以随机为主。

由于分支路径不太多,所以可以每条路径搞出来然后回文树或Manacher解决。

测试点6

这个图是一个分块图,块间有连边。

观察可以发现块间连边是一个块的某个入度为 $0$ 的点连向另一个块的出度为 $0$ 的点。

所以这个块间连边不影响答案。

对每块用测试点4的方法做就好啦!

测试点7

哇,这是一颗树!数据范围还那么小!

这个点可以随便搞过去。

测试点8

这个点……似乎没什么特殊的性质?

那就……很尴尬了啊……

我们回头看下第7个点?

测试点7(解法2)

诶?这个字符序列……有点奇妙啊……

发现这是个由后缀组成的Trie?

找出最长链然后跑Manacher就好了吧。

测试点8

发现这个点是由一个后缀Trie+一条链+一个前缀Trie组成的。

然后就很好做了。

(泥萌怎么都会这个点啊捂脸熊

测试点9

这个点是性质是一个有向的有根树。

那……试试回文树?

诶?怎么跑半天跑不出来啊,怕是不对?

现在考虑回文树为什么跑不出来。

直接回文树做的话,是均摊复杂度的。如果一条全 $a$ 链后接一个全 $a$ 的菊花就会导致复杂度退化成 $O(n^2)$ ,所以跑不出来。

我们可以考虑把均摊复杂度搞成严格复杂度的。

考虑可持久化KMP的做法。

我们像可持久化KMP一样做,每个转移记录一下trans,然后就是$O(n)$了。

可以参考某篇论文。

(为了减小数据包的大小,删了一些点,这个点出锅了,被乱搞搞过去了啊

评论

C_SUNSHINE
沙发咯~
matthew99
板凳
l__ZeRo_t
前排
yanQval
前排
orzlxl
前排膜
hanyuu
前排
ddddddpppppp
哇!!!!
lethalboy
前排膜
liu_cheng_ao
我好菜啊
_Itachi
中排摸
tayloronline
中后排边蒙蔽边膜
liu_runda
话说UOJ NOI Round评测的时候会把我交的所有代码都评一遍啊.....
xumingkuan
T1出题人真良心啊,给了我们这些忘判m=0直接如果k模3不余2就输出0的可怜选手10分,有效防止了爆零,非常贴合NOI d1t1难度
zzyu5ds
原来T2最难吗,做到T2我看了下并不会正解正好就有点困了,T3没看我就去睡觉了
WAAutoMaton
居然t2最难,,,,,,我发现t2不会做之后就差不多弃疗了.....
g19zwk
蒟蒻后排吸灵气(=^=)
xuhaike
第一题为什么是A(k,i)而不是C(k,i)?
AntiLeaf
后排暴力膜
150137
后排伏地膜 话说这个T1做法不止这一个吧 机房四个人三个做法qwq
wangxiuhan
这个T3可以强行FWT的... 那个式子可以强行构造一波

发表评论

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