10月做题记录

10月做题记录
最后一个10月份了,年份都不用写了;即使实力不强也希望这份题单能给后人一些帮助

这个月主要在做课件,整体质量不错

好题:「HNOI2016」网络、HDU6634 Salty Fish、HDU5709 Claris Loves Painting

loj2049「HNOI2016」网络

请先思考后再展开

注意到求的是不经过而不是经过,判断一堆路径中是否有不经过可以转化为x是否在路径的交上,求路径交是可以$O(1)$的

做法一(好写,在线,$O(nlog^3n)$):无脑树剖+线段树,每个节点开可删堆

做法二(难写,离线,$O(nlog^3n)$):无脑线段树分治+树剖+线段树+撤回末尾操作,因为更新max的标记是可以快速合并的

做法三(难写,离线,$O(nlog^2n)$):考虑二分,转化为判断是否所有路径都经过x,考虑路径交;依然线段树分治,预处理线段树每个节点权值顺序后缀路径交(这部分两个log),每次在上面log个节点上二分后取max;或者也可以另外写个权值线段树,区间与一个路径求并,询问在上面二分,这个需要写撤回末尾

做法四(好写,离线,$O(nlog^2n)$):整体二分,支持插入删除维护路径交就是一个差分+树状数组求子树和来判断次数是否和所有相等

做法五(好写,在线,$O(nlogn)$):其实上面都在假设删除不好搞,所以用线段树分治;或者用整体二分套数据结构辅助二分

但其实经过上面感受到路径交对二分的便利性后,其实是可以考虑直接按时间顺序在线做,每次二分回答的。考虑到二分需要求值域后缀的路径交,如果放到值域线段树上二分,其实是可以便利地处理删除的——在叶子节点修改,然后合并上去即可;可以用值互不相同的离散化实现

HDU6634 Salty Fish

请先思考后再展开

明显最小割(割苹果表示舍弃,割监控表示hack),转化为求最大流

注意到是个二分图,而且连边的形式很特殊,范围又特别大,考虑贪心i am the king

注意到每次都会优先流深度最深的可以流的节点,将入边放到树上,等于每次找深度范围内能搞的流出去

注意到对于子树内的出边,只和深度有关,考虑长链剖分,搞个map存每个深度,还没有流完的,借助upper_bound和erase可以保证复杂度即$O(nlogn)$,code

CF997E Good Subsegments

请先思考后再展开

这题似乎可以析合树,然而我并不会构造树,就不这样搞了;口胡一下另一种做法

注意到允许离线,那么把询问挂在右端点上,对于每个右端点给其合法左端点打上标记,那么回答询问就是查询这个和

连续段满足$min(mx-mi+l)=r$,所以维护好这东西的话就可以用线段树给最小值位置打标记

mx和mi可以通过单调栈找到并更新,需要支持区间加减(这样应该更好维护?),区间询问标记和,应该可以$O(nlogn)$

HDU5709 Claris Loves Painting

题意:n个有色点的树,q次询问一个点的子树中与这个点距离不超过d的点的颜色有多少种,强制在线,$\sum n,\sum q \le 5e5$

请先思考后再展开

数颜色题可能有个套路是每个颜色贡献到它第一次出现

先求出每个子树内,某个颜色第一次出现的位置,可以用启发式合并map求,$O(nlog^2n)$

但现在要计数的话,就是区间询问在这个深度出现的颜色数,直接合并肯定是不行的,但我们可以在做上面那玩意的时候,如果发现重复颜色修改对应深度颜色数,这样的修改只有颜色数即n次,然后每个深度的颜色数也用启发式合并map的话,也是$O(nlog^2n)$

复杂度不优秀而且是离线算法,将两个启发式合并都改成线段树合并,这样就是$O(nlogn)$的,code

CF1209G2 Into Blocks

题意:长度为n的序列,q次单点修改后询问序列美丽值。美丽值为通过每次修改某颜色所有位置为另一颜色,最后使得整个序列任意颜色都是连续一段,的最小修改量,$n,q\le 2e5$

请先思考后再展开

首先很明显easy就是让我们找到不带修时的做法,挖掘一些性质然后hard用一些数据结构维护,然而我还是不会

对于无修改,设值c的出现区间为$[fl_c,fr_c]$,最后$fl_c…fr_c-1$都要和下一个相同,设$f_i$为被如此统计的次数

那么$f_i=0$的位置就是一个段的结尾,将每种颜色的出现次数贡献到最左边的位置并记为$cnt_i$

$ans=n-\sum_{每个段} cnt[fl_{出现最多次的值}]$,现在就是对这玩意求和,无修改直接扫一遍即可。

考虑线段树能否维护,「最小值为0维护以0分割连续段的信息」经典转化成「区间以最小值分割的连续段的信息」

其实已经可以做了,如果你还是不会维护可以继续往下看,用一棵还是两棵线段树维护无所谓

我们只需要保证对于$mif=0$的区间算出的信息是正确的,设一个段$[kl,kr]$,记区间询问最大cnt为变量mxc,然后区间所有段的mxc和为sum,mif不为0的区间得出的sum并没有直接意义

如何合并两侧的信息?发现需要记录$mif、mif最左边的点mifl、最右边的点mifr$

对于两侧最小值不同的情况:

$sum[x]=sum[lc]+sum[rc]-mxc(mifr[lc]+1..mid)-mxc(mid+1..mifl[rc])+mxc(mifr[lc]+1..mifl[rc])$

若$mif[lc]<mif[rc]$:$sum[x]=sum[lc]-mxc(mifr[lc]+1,mid)+mxc(mifr[lc]+1,r)$

若$mif[lc]>mif[rc]$:$sum[x]=sum[rc]-mxc(mid+1,mifr[rc])+mxc(l,mifr[rc])$

最后$ans=n-sum[root]$,修改就是「单点改cnt而改mxc,更新包含这个点的区间的f和sum」、「区间加减f,sum不变,记录加法标记tag即可」

维护sum需要调用log次查询mxc,$O(qlog^2n)$,code

CF97E Leaders

题意: n个点m条边的简单无向图,q次询问两点间是否存在长度为奇数的简单路径,$n,m,q \le 1e5$

请先思考后再展开

一般图两点间路径会想到处理出一棵生成树,那肯定是选择dfs搜索树方便,因为没有横叉边

结论:对于无向图,一个点双如果有奇环,那么内部每条边都至少在一个奇环中;点双内有奇环的充要条件是在dfs搜索树上存在一个「一条非树边+若干树边」组成的奇环(这个奇环上所有边一定都在同一个点双内);

两个点间存在奇数长度简单路径的充要条件是:两点树上距离为奇数,或,两点树上路径中至少一条边在至少一个奇环中

两个点间存在偶数长度简单路径的充要条件是:两点树上距离为偶数,或,两点树上路径中至少一条边在至少一个奇环中

于是搞出搜索树,对于每个点记录回溯边,每个点双只是用回溯边找奇环确保复杂度,然后树上差分回答询问即可

$O(n)$,code

CF917D Stranger Trees

题意:给出一棵n个节点的带标号树,要求对于每个k,求出有多少棵生成树满足恰好有k条边与原树相同,$n \le 1e2$

请先思考后再展开

如果直接搞多项式,x的指数表示多少条重复的边,直接换元矩阵树定理+拉格朗日插值,$O(n^4+n^3)$

然后因为一开始做的时候并不会基尔霍夫,接下来介绍如何容斥计数(而且明显这个更有前途)

设f恰好g至少i条边被使用,$g_i=\sum_{j=i}^{n-1}C_j^i f_j,二项式反演得,f_i=\sum_{j=i}^{n-1} (-1)^{j-i} C_j^i g_j$

生成树考虑Cayley公式的推论
$$
明显可以直接树形背包,设f(x,cnt,siz_t)表示目前变成cnt个块(不包括子树根节点),子树根节点所在块大小为siz_t \\
new-f(x,cnt1+cnt2,siz1+siz2)+=f(x,cnt1,siz1)*f(son,cnt2,siz2)\\
new-f(x,cnt1+cnt2+1,siz1)+=f(x,cnt1,siz1)*f(son,cnt2,siz2)*siz2\\
g_{n-k}=\sum f(1,k,siz)*siz*n^{n-k-2},经典树形背包,O(n^4) \\
观察发现可以设ff(x,cnt)=\sum_{siz} f(x,cnt,siz),g(x,cnt)=\sum_{siz} f(x,cnt,siz)*siz \\
new-g(x,cnt1+cnt2)+=g(x,cnt1)*ff(son,cnt2)+ff(x,cnt1)*g(son,cnt2) \\
new-ff(x,cnt1+cnt2)+=ff(x,cnt1)*ff(son,cnt2) \\
new-g(x,cnt1+cnt2+1)+=g(x,cnt1)*g(son,cnt2) \\
new-ff(x,cnt1+cnt2+1)+=ff(x,cnt1)*g(son,cnt2) \\
g_{n-k}=g(1,k-1)*n^{n-k-2},复杂度降低为O(n^2)
$$

code

loj2575「TJOI2018」party

请先思考后再展开

如果给出两个串求最长公共子序列,就是经典的dp即$f(i,j)=max\ f(i-1,j-1)+[S_i=T_j],f(i-1,j)$

注意到A长B短,考虑把dp状态放到状态里面(所谓dp套dp?)计数,$f(|A|,state)=dp状态恰为state的A的数量$

考虑state怎么设计,注意到$f(a,b)最多比f(a,b-1)多1$,在state里面放差分后的$f(|A|,b)$,状态数为$2^{|B|}$

注意还要求A中不能有NOI,再多加一维0/1/2表示末尾与NOI的匹配长度

预处理好每种状态的3种转移以快速转移,dp的时候只需要枚举下一个字符$O(n2^m3*3)$,code

loj2048「HNOI2016」最小公倍数

请先思考后再展开

其实就是询问只用$「a_i \le a且b_i \le b」的边$形成连通块,x和y是否在相同连通块且连通块内$max(a_i)=a,max(b_i)=b$

首先max其实没啥用,因为并查集轻松维护这个信息

一开始以为把边做成两个序列分别按a和b排序,然后莫队,只在第二次碰到时加入,第一次去掉时删除,然而仔细想想发现这东西并不是并查集的末尾撤回,光荣假掉

但我们可以考虑一下将边按照a分块,每个块内b递增,然后询问也挂到块上,设块大小为B

那么回答每个块的时候,前面的边只需要维护一个指针将前缀的边加入,每次询问都暴力扫块内的边并加入再回撤

$O((\frac{m}{B}*m+qB)logn)=O(m \sqrt qlogn)$,code

CF76A Gift

题意:给出一个有重边有自环的n点m边无向图,每条边有两个权值$a_i,b_i$,自定义参数A和B以最小化$A*G+B*S且只用[a_i \le A,b_i \le B]$的边能使图连通,$n \le 2e2,m \le 5e4$

请先思考后再展开

枚举A,维护一个A以内按照B排序,存b的最小生成树边,重构的复杂度为n,总复杂度为$O(mn)$

CF892E Envy

题意:给出一个n个点m条边的无向图,q次询问一个边集能否同时在一个mst中。$n,m,\sum |边集| \le 5e5$

请先思考后再展开

mst的一些性质

那么把每个询问按照边的权值分若干组,离线后依次处理某个权值的所有询问组,一组询问合法当且仅当只加入权值更小的边和这组询问的边,没有成环;一种实现是写可撤回末尾操作的并查集,$O(mlogm+qlogn)$,另一种实现是对每种权值把前面的并查集缩点后建新图,dfs判环,这样就能路径压缩,$O(mlogm+q* \alpha (n))$,可以出更大的q

CF743E Vladik and cards

题意:给定值域为$[1,8]$的序列求最长子序列——满足每两种数字的出现次数相差不超过1,每种数字在子序列中连续,$n \le 2e3$

请先思考后再展开

枚举较小的出现次数a,设$f(a)$表示能否实现,二分出最大可实现的a后摆动一下即可求答案,接下来只说怎么check,设C为颜色数

考虑每种数字是a还是a+1,枚举数字的出现次数,贪心跳(记录数字i的第j个在哪里,以及自己是第几个),$O(logn*C!*2^C)$,应该已经能通过本题,接下来讨论一些更优秀的做法

对于更大的C,阶乘肯定要想办法去掉,而且指数级枚举也很不好,注意到对于某个颜色,并不关心其他颜色的顺序、是a还是a+1,明显可以考虑dp,设$f(n,S)$表示处理了前n个,使用过的颜色集合为S的最大子序列长度,转移考虑是否用这一位,$O(logn*n2^C)$,C可以出到13

CF599E Sandy and Nuts

题意:统计有多少棵满足条件的、以1为根的n个点的树;给出树边中的m条、q组两点的lca,$m<n \le 13,q \le 1e2$

请先思考后再展开

设$f(x,S)$表示以x为根,子树点集为S(不包括x)的方案数,每次枚举编号最小节点所在子树集合T

然后考虑怎么check转移合法性:

对于lca的限制$(a,b,c),若c=x,则ab不能同时在T中,若c \ne x,则ab不能在这个点分开$

对于树边的限制$(a,b),确认(a,b) \ne (x,y)后,若a在T内而b不在,则非法$

$O(n*3^{n-2}*(nm+q))$,code

可能有看起来稍微更好的$O(n*3^{n-2}*(n+q))$做法,但意义不大,常数极小,因为限制不会真的很多,否则记忆化下可达状态很少

CF595E Edo and Magnets

题意:给定平面上n个可重点(坐标为$(\frac{x1+x2}{2},\frac{y1+y2}{2})$),删除最多k个点,求用平行于坐标轴的边长为正整数的矩形覆盖剩下的点所需的最小面积,$n \le 1e5,k \le 10$

请先思考后再展开

明显这么多点是来卖萌的,只有横或纵坐标在前、后10的点可能被删掉,有用的最多40个点

然后明显某维坐标肯定是删除连续的前后缀,直接4个for枚举删多少即可,code

CF908D New Year and Arbitrary Arrangement

题意:在一个空序列上 ,给定概率p末尾加A,否则末尾加B,当子序列AB数量$\ge k$的时候停止,求最后AB数量的期望,$k \le 1e3$

请先思考后再展开

$$
\\设f(t,aa)=子序列个数为t,共计aa个A的概率,倒推正推都行
\\对于t+aa<k,f(t+aa,aa)+=f(t,aa)*(1-p),f(t,aa+1)+=f(t,aa)*p
\\注意如果序列第一个元素是B,直接忽略,故f(0,1)=1
\\对于t+aa \ge k,再加入一个B就结束,可以直接计算E(剩下的长度)=\sum_{i=0}^\infty i*p^i(1-p)=\frac{p}{1-p}
\\ans=\sum_{t+aa \ge k} f(t,aa)*(t+aa+\frac{p}{1-p} ),O(k^2)
$$
code

CF1174E Ehab and the Expected GCD Problem

题意:设一个n的排列的权值为前缀gcd的不同数量,求多少个n的排列的权值在所有n的排列中是最大的,$n \le 1e6$

请先思考后再展开

先考虑怎么求最大值,设第一个数为fir,那么上界就是fir的标准分解质因子个数+1,而显然这个上界是可以达到的

直觉上fir肯定很少,打个表理性分析果然发现对于任意n,最多只有两个合法的$fir=2^k,2^{k-1}*3$,第一种的g仅一种,第二种最多k种g序列,枚举每种计算,下面以2为例,3并没有太大区别

将每个数按照其可行贡献放到每个g位置上(例如$2^4可以放在2^4、2^3…2^0$,这个可行后缀位置可以$O(1)$求出),那么每个组都能够选择放在后面(更小)的格子中,只要保证不会有某个格子留空。从后往前处理每个数,这样每个数的可选方案数和前面的数的选择无关,留空可以用容斥计算(即所有数都不插在最左边数左侧的空位)

$O((1+19)n)$,没看懂建议看代码,code,复杂度瓶颈在于对于每个g序列,找到每个数的后缀贡献位置并放到具体组里面,感觉这个经过一些讨论可能能优化到线性?

CF506D Mr. Kitayuta’s Colorful Graph

题意:n点m边连通无向图,边有颜色,但保证重边的颜色互不相同,q次询问一组点对,问多少颜色可以只使用这种颜色使两点连通,$n,m \le 1e5$

请先思考后再展开

基本思路肯定是每种颜色都建dsu,怎么建没有所谓,不影响复杂度,关键是求答案

做法一(显式根号分治):考虑每种颜色,如果内部的点数<B,枚举点对更新答案;每次回答询问的时候枚举每种大颜色统计即可,$O((\sum in)*B+q \frac{m}{B})=O(m \sqrt q)$,code

做法二(隐式根号分治):考虑一个点在$c_x$种颜色中,询问$(x,y),c_x \le c_y$去重,枚举$c_x$中每种颜色check

对于$c_x \ge B,最多min(q,B^2)次,复杂度上界为(\sum c_x)*\frac{m}{B}=\frac{m^2}{B};其他情况每次check的复杂度为B,O(\frac{m^2}{B}+qB)=O(m \sqrt q)$

code

GYM101102D Rectangles

题意:给出一个矩形,问有多少个子矩形满足内部只有一种元素,$n,m \le 1e3$

请先思考后再展开

对于每列,把相同元素缩成一个块;枚举矩形的上边界,求出以这个上边界为起点向下,每列能延伸多少

下边界从下往上扫,记录当前的答案,每次通过预处理的东西精准找到「再往上都是完全相同元素」的列,用并查集合并同色可用块并更新当前答案,每个下边界都把答案累计到总和里面。$O(n*(n+m)*\alpha (m))$,code

loj6609 无意识的石子堆

请先思考后再展开

经典转化为m点n边,点和边都带标号,每条边度数不超过2,有重边无自环无向图计数;那么一定是若干个环(重边就是二元环,但要特判)、链(一个点算是链,但要特判)组成,具体而言,一定是m-n条链,若干个环;然后只要图形态确定且点带标号且先不考虑二元环,边的标号可以最后再乘上$n!$,下文不考虑边,且边少考虑以边为上标、下标
$$
对于n=m,一个大小为s的环有f(2)=1/2(因为边最后标号),f(s>2)=(s-1)!/2\\
递推式ff(n)=\sum_{i=2}^n C_{n-1}^{i-1} ff(n-i)*f(i)=\frac{(n-1)!}{2}*\sum_{i=2}^n \frac{ff(n-i)}{(n-i)!},O(n)计算 \\
链有g(0)=1,g(s)=(s+1)!/2,与一般的EGF稍有不同 \\
考虑到EGF本质上是多重集的染色,A= \sum_{i=0}^{\infty} \frac{g(i)}{(i+1)!} x^i,G(边数t,链的个数k)=A^k[x^t]/k!*(t+k)!
\\A^k=\frac{1}{2^k}*(2-x)^k* \frac{1}{(1-x)^k}
=(\sum_{i=0}^k C_k^i (-1/2)^i x^i )*
(\sum_{i=0}^{\infty} C_{i+k-1}^{k-1} x^i ),原根为7,FFT即可
\\ans=n! * \sum_{a=0}^n ff(a)*G(n-a,m-n)*C_m^a,O(nlogn)
$$
code

另外出题人zjt还有一种做法,感觉一般性没有上面的好,而且看了半天没看懂

CF1236E Alice and the Unfair Game

题意:n个盒子,一个小球,长度为m的序列a,要求时刻t的时候$a_t$中不能有小球,最开始、每个时刻结束时都可以将小球移动到相邻的盒子,问有多少个合法的二元组$(x,y)$,表示第一次操作前放在x,时刻m结束被操作后放在y,$n,m \le 1e5$

请先思考后再展开

问题等价于初始在$(0,x)$上放球,每次$(i,j) \to (i+1,j-1/j/j+1)$,$(t,a_t)$是障碍点,问能到达哪些$(m+1,y)$

不难发现因为时刻0和时刻m末尾都能移动,对于每个x,可行的y都是一段连续区间,所以可以分别求出左右端点,以求左边为例

那么一个简单的dp就是$f(m+1,i)=i,f(t,1)=1$

$f(i,j)=f(i+1,j-1),如果存在障碍点(t,a_t),f(t-1,a_t+1)=f(t,a_t+1),f(t,a_t)=\infty$

发现只需要除了特殊点,只需要移动一下下标,可以指针实现,$O(n+m)$

要特判n=1……因为是空集,code

CF360E Levko and Game

题意:给出一个n点m+k边的有向图,给出定点s1、s2、f,前m条边权值固定,后k条边是区间$[l_i,r_i]$,构造边权方案使得$s1\to f<s2 \to f$,不行就问能否平手,或必败,$n,m \le 1e4,k \le 1e2$

请先思考后再展开

等价于最大化$(s2 \to f)-(s1 \to f)$,注意终点相同,然后这种选择区间内数的题目猜一手结论只用到两个端点;因为是最短路,肯定是先$r_i$然后弄小会好做

这样做一次最短路后,先追求WIN,注意到$\forall (x \to y) \in E,若d1[x]<d2[x],将边改成l_i不会使d2[f]-d1[f]从正变0或负,也不会从0变负$,所以每次找出这种边改掉即可;如果还是LOSE就追求DRAW,条件改成$d1[x] \le d2[x]$即可

$O(k*mlogm)$,code

loj2710「BalkanOI 2018 Day1」Election

请先思考后再展开

主要想说下,给出一个串要怎么求「每个前缀后缀都非负」

考虑贪心,显然只会删除-1,从后往前贪心地将后缀保证合法后(即只在不得不删的时候删,这样保证了删掉的-1一定是靠前的),保证前缀的答案就是$-min(0,所有前缀和)$,正确性还是比较明显的

现在区间询问,离线后用线段树维护前缀和就好了

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/d9e23b83.html
转载请注明出处,谢谢!