竞赛讨论区 > 牛客挑战赛67-题解
头像
_Sugar_
发布于 2023-03-17 22:09 浙江
+ 关注

牛客挑战赛67-题解

A.首先我们注意到,条件等价于1in\forall 1\le i \le n,有preisufipre_{i} \neq suf_{i}。因为当i>ni > n时,prei=suf2nipre_{i} = suf_{2n - i},即preisufipre_{i} \neq suf_{i}pre2nisuf2nipre_{2n-i} \neq suf_{2n-i}是等价的。然后,不妨直接把条件增强,令1in\forall 1\le i \le n,均有prei<sufipre_{i} < suf_{i},不难看出,将11nn填入前半部分,n+1n+12n2n填入后半部分即可,顺序任意。

然后考虑Pa=bP_{a} = b的限制,如果有ana \le nbnb \le n同时满足(或者同时不满足),上面的构造已经符合要求。如果两者一个满足一个不满足,则将n+1n+12n2n填入前半部分,11nn填入后半部分即可。

不断随机几个满足Pa=bP_{a} = b的排列,并检查是否符合条件也是可以通过的。

 \space

B.将字符00视为10610^6,字符11视为106+110^6 + 1,字符22视为(2106+1)-(2\cdot 10^6 + 1)。则一个子串含有相同数量的0,1,20,1,2,当且仅当子串和为00。跑一个前缀和+map检查即可。

 \space

C.在下文中,对于路径SS,我们约定用S|S|表示路径的长度。

假设我们枚举最终的路径S=(u,v)S = (u,v)S>1|S| > 1),考虑如何计算至多有多少条不同的路径的交为该路径。其答案是sizu×sizvsiz_{u}\times siz_{v},其中sizusiz_{u}代表以对方(点vv)为根时,uu的子树大小。如果统一令11号点为根,则当uuvv的祖先的时候,答案是(nsizu+1)×sizv(n - siz_{u} + 1) \times siz_{v},否则是sizu×sizvsiz_{u} \times siz_{v}

此时可以考虑dsu on the tree。对于每个点uu,维护集合{(d,sd)}\{(d , s_{d})\},代表uu的子树中,深度大于等于dd的点中,子树大小的最大值sds_{d}。则当合并两个集合时,子树大小为sds_{d}的节点,至少需要匹配一个子树大小为ksd\lceil \frac{k}{s_{d}} \rceil的节点。这一步可以通过在另一个集合中lower_bound来实现。而更新对应的(d,sd)(d,s_{d})只需要对后缀取max即可。

特殊判断祖先-子孙节点的情况,和答案等于11的情况。

 \space

D.首先可以对每个连通块单独处理。假设一个连通块具有nn个点,mm条边。若n20n \le 20,则我们可以暴力枚举哪些点被删除,然后统计答案,时间复杂度O(2n×m)O(2^n\times m)

n>20n > 20,则必有mn20m - n \le 20。我们找出一棵生成树,并先考虑没有非树边的情况应该怎么计算。一个简单的办法是令fi,0/1f_{i,0/1}代表ii的子树,点ii删或者不删的最小代价,直接dp即可。而对于每条非树边,其有三种可能性:用aa的代价直接删掉,被其中一个端点删掉,被另一个端点删掉。假设我们枚举这三种可能性的一种,相当于钦定了某若干个点必须删掉,仍可以套用上述的树dp。时间复杂度O(3mn×n)O(3^{m-n} \times n),显然是过不了的。

现在我们假设,对于每条边,强制枚举它被某一个端点删掉,这样复杂度就可以退化到O(2mn×n)O(2^{m-n}\times n)。但是这样子会遗漏被直接使用aa的代价删掉的情况,怎么办呢?我们可以弱化对点的限制:本来情况下,枚举每条边被哪个点删掉,那个点被要求无法保留,而现在我们增加一个决策:可以保留这个点,但是需要额外支付aa的代价(相当于删去这条边,放弃对强制删除点的限制)。仍可以套用上述树dp,复杂度为O(2mn×n)O(2^{m-n}\times n)

赛时有选手写了类似于O(2n/2)O(2^{n/2})的的独立集做法,没有特别看懂,应该也是对的。

退火是过不了的,不知道有没有其他技巧高超的乱搞可以过。(赛时大家都是怎么过的呢)

 \space

E.一眼:妈妈我会容斥!考虑假定选取的点具有顺序,并枚举所有的可重联通块。不妨令集合Si,jS_{i,j}代表,第ii号点和第jj号点直接相邻的方案数,则对所有k(k1)2\frac{k(k-1)}{2}个集合容斥即可得到答案。具体地,令fi,jf_{i,j}表示ii个点,违反jj条限制(每条限制形如上述的(i,j)(i,j)相邻)的方案数。对每个形状的连通快插头dp,算出恰有xx条边的连通子图的方案数,然后大力dp转移……

上面这个做法不仅难写而且时间还大。但是它启发我们一件事情:假设一个连通块长为dxdx,宽为dydy,则它在图中出现的方案数为(ndx)(mdy)(n - dx)(m - dy)。换句话说,纵使我们不清楚它具体的容斥系数,我们也能推断出,当n,mkn,m \ge k的时候,答案是关于n,mn,m的,不超过kk次的二元多项式(只有当n,mkn,m \ge k时,所有的连通块贡献才均不为00)。当n,mkn,m \le k时,答案是关于mm的多项式,其中对于每个nn均有不同的多项式。

接下来只需要计算出所有n,m2kn,m \le 2k的值,便可以插值多项式了。一种做法是轮廓线dp,注意到轮廓线上的点,至多只有一对连续的11,故每条长为nn的轮廓线状态数是O(ϕn)O( \phi^{n})级别的,共有n2n^2个轮廓线要考虑。故令Fi,j,k,SF_{i,j,k,S}代表在点(i,j)(i,j)处,选了kk个点,轮廓线状态为SS的方案数。单个nn复杂度是O(n2kϕn)O(n^2k\phi^n),总的复杂度是O(k3ϕ2k)O(k^3 \phi^{2k})

赛时有一票子选手打表多项式,我应该手动输入模数pp的(悲

 \space

F.本来发现了插值做法之后想加强成算Sk(k1000)S^k(k \le 1000),后来因为种种原因就没有加……谢罪.jpg。

这里直接介绍原做法:令Fi,k,pF_{i,k,p}表示ii个变量,每个变量从11取到mm,答案不超过pp的方案数。我们递归地证明,Fi,k,pF_{i,k,p}是关于k,pk,p的,总次数不超过ii的二维多项式(k<p2kk < p \le 2k)。

考虑枚举最左边的最大值位置xx,令其值为k1k_{1},则若2k1p2k_{1} \le p,方案数为k1ik_{1}^i,若2k1>p2k_{1} > p则方案数为Fx2,k11,p×Fix1,k1,p×(kk1)2F_{x - 2 , k_{1} - 1,p} \times F_{i - x - 1 , k_{1} , p} \times (k - k_{1})^2。式子的含义是,最大值两端的值必须取kk1\le k-k_{1}的值,并且取完之后对剩下部分没有影响。(当x2x \le 2xi1x \ge i - 1)时式子会有所区别,不再赘述。

故对于这个xx,有Fi,k,p=(p2)i+k1=p2+1kFx2,k11,p×Fix1,k1,p×(kk1)2F_{i,k,p} = (\lfloor \frac{p}{2} \rfloor)^i + \sum_{k_{1} = \lfloor \frac{p}{2} \rfloor + 1}^{k}{F_{x - 2 , k_{1} - 1,p} \times F_{i - x - 1 , k_{1} , p} \times (k - k_{1})^2}

如果把Fi,k,pF_{i,k,p}写成ai,jkipj\sum{a_{i,j} k^ip^j}的形式,可以发现我们需要的仅仅是卷积后求一次若干次幂前缀和,这是完全可以预处理的部分。

但是有另一个问题,p2\frac{p}{2}是没法写进多项式里的(这个12\frac{1}{2}不能简单地作为系数)。解决方案是分p=2x+1p = 2x + 1p=2xp=2x讨论,分别建立两部分的多项式。细节会有点多。得到了最终的多项式,可以轻松求得期望。

一个事实是最终对pp求和会让答案退化成关于mm的一元多项式,于是可以暴力插值。如果题意改为询问SkS^k的值,答案会进化成n+kn+k次多项式,就无法暴力dp求得点值了。

全部评论

(11) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐