CH Round #17 #17

OI - Official

From lydrainbowcat


小时

尚未报名

贝尔数 16/63 From
穿越广场 13/54 From
舞动的夜晚 86/306 From

这轮比赛按照【真·NOIP模拟赛Day2】标准举办,题目非原创。

题解:

第一题:矩阵乘法+中国剩余定理。

这道题目延续noip day2第一题纯数学的一贯风格。

对于50%的数据,我们只需要写一个O(n^2)的递推(递推公式已经给出了)。这是送的……所以本次比赛拿不到50分就真的说不过去了……

对于100%的数据,我们发现mod的那个数恰好是31*37*41*43*47,于是可以分别对这五个小质数取模求出答案,最后使用中国剩余定理合并。mod小质数的做法也给出了同余公式,这显然是建立一个1行p列的矩阵然后用矩阵乘法加速递推就好了……

第二题:AC自动机+DP。

这道题目50%的数据可以这么考虑:F[i,j,k,l]表示有了i个R,j个D,与第一个串匹配到了第k个位置,与第二个串匹配到了第l个位置的方案数。转移就是枚举下一位是什么,如果匹配成功,第三维(或第四维)+1;如果匹配失败,那么就按照KMP算法的p数组来回到上一个匹配的位置看能否匹配……(提前对读入的两个串用KMP自匹配求出p数组)。

对于100%的数据,我们首先考虑把上面的方法优化为:F[i,j,k,l]表示有了i个R,j个D,与第k (k=1,2) 个串匹配长度较长,匹配到了第l个位置。这样对于另一个串的匹配长度是可以算出来的。但是转移会变得非常繁琐…… 至少我觉得这个方法是不太可做的。。。

正解是我们对两个串建一个AC自动机,F[i][j][k][l]表示长度为i,有j个R(i-j个D),走到了AC自动机上的k节点,包含的字符串状态为l (l=0 1 2 3为二进制状态,表示两个串是否被包含)。

边界:F[0][0][1][0]=1;

转移:F[i][j][k][l]-->F[i+1][j+1][trie[k]['R']][l']
                               F[i+1][j][trie[k]['D']][l']

trie[k]['R']是第i个单词的结尾,那么l'=l | 1<<i-1; 不是结尾   l'=l

目标:F[N+M][M][?][3]。

第三题:二分图的不可行边——最大流+Tarjan

对于50%的数据,先求出最大匹配的值,然后枚举每一条边,连上之后重求最大匹配,看答案是否为原最大匹配-1。求最大匹配用匈牙利算法。

对于100%的数据,先用Dinic求任意一组最大匹配,然后建一张新图:

匹配边(i,j) j到i连边
非匹配边 (i,j)  i到j连边
匹配的左点i (i,S)
不匹配的左点i  (S,i)
匹配的右点j (T,j)
不匹配的右点j (j,T)

然后用Tarjan求强连通分量
(i,j)是可行边的条件:
(i,j)是匹配边 或者 i,j在同一个scc里

那么总边数减去可行边数就是不可行边数,即答案。

注意这个新图要包含源和汇,不能只在二分图两部之间连边,除非原最大匹配是一个完备匹配。