先来个小问题?
MysteryMan 是谁呢?
关于这点,我只能告诉你无可奉告,你们不高兴也不行。
好吧其实是一个2009年左右的不愿透露姓名的OI选手……
Day1
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)$了。
可以参考某篇论文。
(为了减小数据包的大小,删了一些点,这个点出锅了,被乱搞搞过去了啊)