Codeforces练习

Published: by Creative Commons Licence

  • Tags:

Codeforces 1033E

题意

https://codeforces.com/contest/1033/problem/E

题解

我们可以尝试找出一株生成树,我们从前到后处理所有顶点,并且维护处理过的顶点形成边数最多的生成树。这样当新加入一个顶点的时候,我们可以二分查找,找到所有与新顶点存在边的连通块,之后对连通块进行二分查找,找到连通块中与新顶点之间恰好存在边的顶点,加入边即可。由于每次合并两个连通块都对应的会有$O(\log_2n)$次查询,因此最多的查询数目为$O(n\log_2n)$,这里常数不超过2,因此在$n=600$的时候总的请求数也不会超过$12000$。

最后我们找到了生成树就很容易判断是否有奇长环了,将树上顶点进行二分染色,之后观察同色顶点之间是否有边存在,如果有就存在了奇环。我们可以将该色的顶点压成一个序列,然后比遍历序列,直到找到某个特殊的点,这个点后面的所有顶点之间没有边,我们记这个顶为first,之后找到first后第一个顶点second,使得second与first之间有边,这里总共最多为$2n$次查询。要找到奇环,可以以first为根,搜索到second的唯一路径即可。

题目的核心是想到这题目所要求的输出,不需要你得到所有边,只需要一株生成树即可。

Codeforces 1028G

题意

https://codeforces.com/contest/1028/problem/G

题解

定义$dp(l,q)$表示最大的$r-l+1$,满足在知道$x$落在$[l,r]$的前提下能够在$q$次请求内找到$x$。

那么可以很容易推出转移公式,同时利用$dp$也可以快速找到那些分隔点。

这个问题中由于每个请求中的值不能超过$x$,因此不可以直接均匀切分,这也是为什么要借助动态规划的原因。以后遇到这种复杂的二分查值交互题,一定不要嫌麻烦,写个动态规划。

Codeforces 1307E

题目

https://codeforces.com/contest/1307/problem/E

题解

这是一道挺有趣的问题的,优化的空间很大。

首先吃同一类草的牛,一边最多只会有一只。

很容易想到一个$DP$的方式,时间复杂度为$O(n^3)$。但是这个方式铁定不行。

我们可以换一个思路,枚举从左走出走到最靠右的牛,以及从右走出走到最靠左的牛。之后我们发现其它牛就直接被分成了三类,第一类只能出现在左边,第二类只能出现在右边,第三类可以出现在两边。我们可以对吃一类草的牛独立统计贡献,总的方案数可以将所有贡献乘起来得到。

你可能会问,那时间复杂度不还是$O(n^3)$吗?是的,但是这样弄就有了优化的空间,而之前的$DP$绝对是死路一条。我们会发现为啥我们需要枚举左右两边最靠边的牛的位置呢,是为了防止重复统计,但是实际上如果从左边出来最靠右的牛确定了,右边的牛即使不确定也不会导致重复统计。因此我们这样就直接砍掉了一个$n$,时间复杂度降低为$O(n^2)$。

但是还能优化,如果我们从左往右枚举从左出发最靠右的牛时,每次下标变动的时,最多只有两只牛允许出现位置会变动。因此我们可以通过扫描并不断修改,就能保证时间复杂度为$O(n\log_2n)$,这里的$\log_2n$是因为需要用到求逆运算。

Codeforces 1311E

题意

https://codeforces.com/contest/1311/problem/E

题解

很显然当树是一条链表的时候,深度之和会达到最大,而树除了深度最大的一层外,其它第$i$层正好$2^i$个顶点的时候深度最小。

总深度最小记作$m$,总深度最大记作$M$。下面我们给出一个构造性算法,每次操作都能将总深度减少1。我们从链表开始转换。现在我们开始尝试将总深度减少1:如果一个叶子的深度为$k$,且在深度$k-2$处存在一个顶点,它的孩子数少于2,那么我们称这个叶子是有效的。我们选择所有有效叶子中深度最小的,记它的深度为$k$,将其移动到某个孩子数少于2的深度为$k-2$的顶点下面。这个算法可以持续直到树的深度和达到最小。

Codeforces 1253F

题意

https://codeforces.com/contest/1253/problem/F

题解

一类最小瓶颈路问题,问题3。

Codeforces 1301F

题意

https://codeforces.com/contest/1301/problem/F

题解

容易发现我们可以对每个颜色作为源头进行一次BFS,这样就能保证快速得到每个位置到另外一种颜色任意位置的最短距离,记$D(c,i,j)$,表示位置$(i,j)$到颜色为$c$的任意位置的最短距离。

现在我们考虑如何找到两点的最短距离。考虑到最短距离可能出现了同色块之间的转移,也可能没出现。

没出现的情况下,这时候两点的最短距离是二者之间的曼哈顿距离。

在出现的情况下,我们可以枚举第一次发生同色转移的颜色,记这个颜色为$c$,那么此时最短距离可以分解三部分,第一部分是从颜色$c$的任意块转移到$(r_1,c_1)$,第二部分是从颜色为$c$的任意块转移到$(r_2,c_2)$,第三部分就是我们枚举的$c$颜色的两个位置的转移,因此此时的最短距离为$D(c,r_1,c_1)+D(c,r_2,c_2)+1$。

总的时间复杂度为$O(knm+qk)$,需要注意不要用太多$stl$的东西,这道题目卡常严重。

Codeforces 1305G Kuroni and Antihype

题意

https://codeforces.com/contest/1305/problem/G

题解

首先我们先认为每个人的权值都不同。

我们可以加入一个权值为0的人(记作第$n+1$个人),并且认为这个人一开始就加入了Antihype。同时我们可以假设所有的数都不能自主加入Antihype,必须通过他人邀请才能加入。可以发现这样不会改变结果。

首先我们想一个naive的方法,如果两个人$i,j$是朋友,那么我们可以加入两条单向边$(i,j),(j,i)$,前者的权值为$a_j$,后者的权值为$a_i$。现在我们希望选择其中一部分边,并拿到这些边的权值。选择的规则如下:

  • 每个顶点最多有一条入边被激活。
  • 沿着顶点的入边不断后退,最后一定会回到顶点$n+1$。

很显然这最终得到的是一个有向图生成树(树形图),同时我们要求权值最大,即要求求最大权树形图,这可以用最小树形图算法解决,时间复杂度是$O(E\log_2V)$。$V=n+1$,是已知,但是$E$可以有多大呢。

任意两个数且运算后位0,那么我们可以枚举$0$到$2^{18}-1$的每个数$x$,以及$x$的子集$a$,这样就可以找到另外一个数$b=x-a$。这样统计的好处是不会出现重复(我们可以恒要求$a>b$来避免重复)。

通过上面算法,我们可以找到所有的边,以及估计出了边的总数为$O(3^{18})$,数量级是3亿级别的。因此上面的算法自然无法通过。(但是至少我们得出了一个比$O(n^2)$或$O(4^{18})$更好的方法)。

我们可以考虑另外一种统计方案,记$out(v)$表示顶点$v$的出度。那么我们实际要统计的是:

\[\sum_{v}out(v) a_v\]

上面的公式不能帮助我们太多,但是如果我们用无向边来替代有向边,那么我们会发现每个顶点的出度都会增大1(因为原来的唯一入边也转换成了出边),现在我们记$deg(v)$表示顶点$v$的度数,我们要求的就是:

\[\sum_{v}(deg(v)-1) a_v=\sum_{v}deg(v)a_v+\sum_va_v\]

其中$\sum_va_v$是常数,我们可以忽略,现在我们希望$\sum_{v}deg(v)a_v$最大。这个玩意可以将其转换为最小生成树问题(可以参考最小生成树的一些题目-题目1)。

现在我们面对的问题是找到一颗最小生成树。我们可以考虑使用kruskal算法,kruskal要求对边按边权排序,我们可以很自然的从大到小枚举$x$即可。这样我们就给出了一个$O(3^{18}\alpha(n))$,其中$\alpha(n)$是反阿克曼函数,可以直接作为常数看待。

最后还剩下一个问题,就是存在重复的权值。我们可以这样考虑,如果在枚举到$(u,v)$的时候,$u$有$c(u)$个处于不同连通块的人,而$v$有$c(v)$个处于不同连通块的人,我们要让它们连通,只需要加$c(u)+c(v)-1$条边即可,之后他们就连通了,修改$c(u),c(v)$为1即可。

总的时间复杂度为$O(3^{18}\alpha(n))$。

Codeforces1205D

题意

https://codeforces.com/problemset/problem/1205/D

题解

如果我们为根结点赋予权重0,并且为其余结点均赋予不小于父结点权重的权重。那么我们可以通过差分得到连接父子结点的边的权重,并且权重非负。现在考虑要为一株树上的n个顶点赋予一组权重,我们可以遍历整棵树,按照遍历的顺序从小到大赋予权重,这样进行差分后得到的边的权重均非负,且从根结点到树中任意顶点v的路径总权等于v的顶点权重。

考虑星图,我们认为根结点下挂n-1个顶点。我们任意选择一个C,满足$n/3\leq C \leq 2n/3$。并为前C个子结点赋予权重$1,2,\ldots, C$,而后面的$n-C-1$个子结点赋予权重$(C+1),2(C+1),\ldots, (n-C-1)(C+1)$,这样利用前C个顶点和后n-C-1个顶点我们就可以组合得到$[1,2n^2/9]$之间的所有值了。

考虑一般的树,我们找到树的重心,可知重心下最大子树的大小不超过$n/2$。我们可以排序重心下的子顶点,并贪心找到一组子树,使得总大小C落在区间$[n/3,2n/3]$中。之和,我们为这组子树中顶点赋予权重1~C,而其余子树中顶点赋予权重$(C+1),2(C+1),\ldots, (n-C-1)(C+1)$。

Codeforces1209F

题意

https://codeforces.com/contest/1209/problem/F

题解

我的做法和题解的不太一样。

首先观察问题,假设1到x的最短路径为1,..,y, x,那么x的数值则是在y的数值的尾部添加若干数字得到,即x的数值一定大于y的数值。我们发现这个性质有点类似于最短路问题,且在这种意义上,我们可以推出边权是非负的。这样我们就可以堂而皇之地使用Dijkstra算法解决它。

首先我们解决一个问题,如果进行比较操作,即如何判断离1所在连通块最近的顶点。

我们可以用一株前缀树维护所有顶点的最短距离,这样每个顶点所在的最短距离就是前缀树的某个顶点。这里我们需要使用动态开点技术,由于每条边最多建立$\log_2m$个前缀树顶点,因此前缀树的大小是$O(m\log_2m)$的。

之后如果比较两个顶点与1所在连通块的距离,我们知道距离已经被我们映射为了前缀树的顶点。因此就是比较两个顶点所代表的数值的大小。

由于边没有前置0,那么深度不同的顶点的大小,可以完全通过深度进行判断,深度较小的顶点代表的数值一定较小。

之后如何判断深度相同的顶点呢,我们必须找到两者的LCA。而要在一个动态加点的前缀树上找LCA,最简单的方式就是倍增技术,为每个顶点维护一个大小为20的数组bl,其中$bl[i]$表示距离当前顶点$2^i$的祖先顶点。这样判断操作就可以在$O(20)$时间内得到。

考虑总的时间复杂度,由于比较会发生$O((n+m)\log_2n)$次,因此总的时间复杂度为$O(20(n+m)\log_2n)$,是可以通过的。

Codeforces 1312F

题意

https://codeforces.com/contest/1312/problem/F

题解

SG函数的循环节上限为$4^{15}$,但是实际上却往往非常小。暴力找出循环节,之后就可以$O(1)$查SG函数了。之后遇到循环节的问题,一定敢暴力,不要被上限所困,因为理论上的上限一般都很难出现。

Codeforces 1110F

题意

https://codeforces.com/contest/1110/problem/F

题解

我竟然想要用ETT来解决这个问题,重点是我也不会ETT,菜得真实。

我们先求出每个顶点到顶点1的距离。之后以顶点1位根进行深度优先搜索。当我们沿着一条边从父结点移动到子结点的时候,容易发现,所有的顶点可以分成三类,第一类是不属于子结点的子树中ID小于子结点的顶点,第二类是属于子结点的子树中的顶点,第三类是不属于子结点的子树中ID大于子结点的顶点。这三类顶点的ID都是连续的区间,这意味着三次区间修改操作,就可以将距离修正。

维护一个线段树,进入子结点时修正距离,离开子结点的时候恢复距离。访问到某个顶点时顺带处理掉所有与它相关的请求即可。

NOTE:非常多的树上查询问题都可以通过将问题挂载到对应的顶点上,并且利用深度优先搜索进行解决。

Codeforces1260F

题意

https://codeforces.com/contest/1260/problem/F

题解

毒瘤题。

仅考虑颜色c。我们记V(i)为一个指示器,如果$l_i\leq c\leq r_i$,那么$V(i)$为真,否则为假。记$g(i)=r_i-l_i+1$,记$p=\prod_{i=1}^n g(i)$。

于是单独考虑颜色c的贡献,为:

\[\sum_{V(i)\land V(j)\land i<j}dist(i,j)\frac{p}{g(i)g(j)}=p\sum_{V(i)\land V(j)\land i<j}dist(i,j)\frac{1}{g(i)g(j)}\]

这里我们可以稍微变更一下,记$dep(i)$表示顶点i在树中的深度,那么有

\[dist(i,j)=dep(i)+dep(j)-2dep(lca(i,j))\]

其中$lca(i,j)$为顶点i和顶点j的最近公共祖先。代入之前的公式得到:

\[\sum_{V(i)\land V(j)\land i<j}dist(i,j)\frac{1}{g(i)g(j)}\\ =\sum_{V(i)\land V(j)\land i<j}(dep(i)+dep(j)-2dep(lca(i,j)))\frac{1}{g(i)g(j)}\\ =\sum_{V(i)\land V(j)\land i<j}dep(i)\frac{1}{g(i)g(j)}+\sum_{V(i)\land V(j)\land i<j}dep(j)\frac{1}{g(i)g(j)} +\sum_{V(i)\land V(j)\land i<j}2dep(lca(i,j))\frac{1}{g(i)g(j)}\\ =\sum_{V(i)}dep(i)\frac{1}{g(i)}(\sum_{V(j)}\frac{1}{g(j)})-\sum_{V(i)}dep(i)\frac{1}{g(i)^2}+2\sum_{V(i)\land V(j)\land i<j}dep(lca(i,j))\frac{1}{g(i)g(j)}\]

现在我们考虑从颜色c转移到c+1,这时候我们会删除一些顶点,同时加入一些顶点。我们希望能在删除加入顶点的同时维护整个公式。事实上,前两项是很容易维护的,这里不另外讨论。最后一项,我们可以这样统计:

\[\sum_{V(i)\land V(j)\land i<j}dep(lca(i,j))\frac{1}{g(i)g(j)}\\ =\sum_{V(i)}\frac{1}{g(i)}\sum_{V(j)\land i<j}dep(lca(i,j))\frac{1}{g(j)}\]

我们维护一棵树,每次加入一个顶点x时,结果需要增加从顶点x到根顶点的路径上所有顶点的值,同时我们将顶点x到根节点的路径上所有顶点的值加上$\frac{1}{g(x)}$。(这里我们用到了,考虑两个顶点a和b,二者的公共前缀长度为dep(lca(a,b)),因此我们可以路径加总来替代$dep$函数的使用)。这涉及到路径操作,轻重链剖分或者LCT都可以。

Codeforces 1111E

题意

https://codeforces.com/contest/1111/problem/E

题解

挺不错的问题。首先可以发现这个问题是树上DP问题,但是DP非常难推,且推出来的效率也很低。

我们可以换个思路,一个顶点$u$其只有$x$个禁止加入的分组(与集合中祖先数目相同),如果我们按照顶点的深度从小到大处理,那么如果此时已经存在$k$个分组,那么$u$或者加入已经存在的$k-x$个分组,或者重新创立一个分组。

剩下的就是如何快速确认每个顶点到根有多少个祖先顶点被选中,很简单,动态树即可。将选中的顶点的值全部设置为1,其余的设置为0,那么顶点到根之间祖先数目等于顶点到根这条路径上的值之和减去1(顶点自身)。(同时动态树还支持换根操作)

这个问题实际上还可以引出更加有趣的一种组合数学问题,第二类斯特林数,对于$n$个不同的元素,我们希望将它们分成不空的$k$组,有多少种分法。

Codeforces 1083C

题意

https://codeforces.com/contest/1083/problem/C

题解

我们可以将整棵树放到线段树上维护,线段树上[l,r]表示的是从lr排列对应的所有顶点,是否处于一条路径上。于是我们要找的结果就是最大的k使得[0,k-1]对应的顶点都处于一条路径上。这里满足二分的性质,所以我们可以在线段树上二分即可。

下面还需要提到一个问题,如何合并两个区间A和B。如果一个区间的所有顶点处于同一条路径上,我们只需要路径的两个端点就可以得到路径的所有信息了,我们可以在区间中保存路径的两个端点。现在考虑当区间A与B都满足所有顶点处于一条路径上时,是否能将两条路径合并为一条。如果能合并,最后得到的路径的两个端点必定是这四个端点中距离最远的两个,我们可以暴力枚举,找到距离最远的两个端点即可,之后判断所有四个端点是否都落于得到的新的路径上。

这里还可以提一下,线段树是自然支持二分的,因此我们可以在从上向下遍历线段树的时候完成二分过程,因此,总的时间复杂度为$O(n+q\log_2n)$。

CF1174D

题意:

https://codeforces.com/contest/1174/problem/D

题解:

我们可以记构造好的序列为a,而序列a的前缀为b,即b[i]=a[1]^…^a[i]。

任意一段子序列,都可以表示为两个前缀的亦或和,换言之,我们现在需要找到满足条件的一组前缀,使得两两亦或和不为0和x。不为0意味着每个前缀都不同。不为x,意味着对于任意一个数t,t与t^x只能选择一个。因此我们可以通过维护1~2^n个数的可用状况,构造最长的一个前缀,之后将前缀转换为数组。

Codeforces 1033F

题意

https://codeforces.com/contest/1033/problem/F

题解

首先$n$这个东西是障眼法,因为取值只可能有$2^w$种,我们可以一开始就记录下每个数出现的次数。下面考虑单独处理每个请求,对于一个请求,考虑它的第$i$位的运算,我们可以发现要保证这一位为0,那么最多有3种可能性(总共4种可能性,但是由于至少有一种可能性的结果为1,因此最多还剩3种可能性)。于是我们可以递归暴力枚举,这样的时间复杂度为$O(n+m3^w)$,稍微有点大。

但是注意到所有位运算符都满足交换性,因此我们可以把01和10两种情况压缩成一种,我们可以将00记作0,01和10记作1,11记作2(就是1出现的数目而已)。这样我们发现每个运算符最多只能在两种可能性下给出结果0,因此我们可以暴力枚举这两种可能性,总的时间复杂度就降为了$O(n+m2^w)$。

具体实现,我们可以维护一个多维数组,记录每一位和满足某个条件的二元组数目。这里由于会出现动态维护的多维数组,比较麻烦,我们可以直接将其作为三进制进行压缩即可。

总的时间复杂度为$O(n+m2^w+w(2^w)^2)$。

这里还有一个发现,就是如果我们将每个数先转成二进制形式,之后将二进制直接当成三进制处理的话,就可以直接用加法来预处理那个多维数组了。即多维数组的第$k$项的值为$\sum_{i+j=k}C_iC_j$,其中$C_i$表示三进制为$i$的数出现次数,$C_j$同理。这是一个卷积,我们可以直接用FFT计算,这样预处理的时间复杂度就会从$w(2^w)^2$降低到$w3^w$。

Codeforces1208F

题意

https://codeforces.com/contest/1208/problem/F

题解

好题。直接给出解法:

我们先处理 \(a_j \& a_k\) ,我们定义函数$f(x)$,其值表示x的所有二进制超集中的下标,如果不存在则返回-1。我们可以为每个可能值(M个)维护一个集合,之后按x从大到小计算$f(x)$。注意到我们实际上只需要考虑这些集合中最大的两个下标,因此可以用一个大小为2的最大堆替代上面提到的集合。

之后问题就变成了问集合中任取两个下标不同的元素,求最大或。

我们可以遍历所有可能的第一个元素x。之后我们求不在x中出现的最大位对应的值t,判断t是否出现在x右边,如果出现,则表示可以取到,否则取不到。之后继续处理剩余的位。

时间复杂度为$O((N+M)\log_2M)$,其中M为取值范围,N为数组大小。

Codeforces1136E

题意

https://codeforces.com/problemset/problem/1136/E

题解

可以发现,问题可以表述为:

\[\left\{ \begin{array}{lcr} a_2-k_1&\geq& a_1\\ a_3-k_2-k_1&\geq& a_2-k_1\\ \ldots\\ a_n-k_{n-1}-\ldots-k_1&\geq& a_{n-1}-k_{n-2}-\ldots-k_1 \end{array} \right.\]

即我们可以发现我们将每个数字$a_i$分成了两部分$a_i-k_{i-1}-\ldots-k_1$和$k_{i-1}+\ldots+k_1$的和。后面部分是不会改变的,而前面的部分是非严格递增的,因此可以用线段树维护。

Codeforces 1146G

问题:

见链接https://codeforces.com/contest/1146/problem/G

题解:

令$dp(i,j,k)$表示仅考虑地点i..j,建立最高的屋子的高度不超过k时能获得的最大收益,其中惩罚条款仅考虑那些完全限于i..j内部的条款。要计算$dp(i,j,k)$,我们可以记m为房屋i..j中最高的那座,m可以通过枚举得到。之后如果$m<k$,那么很显然$dp(i,j,k)=dp(i,j,k-1)$。现在仅考虑$m=k$的情况。可以推出公式为:

\[dp(i,j,k)=\min_m(dp(i,j,k-1),dp(i,m-1,k)+dp(m+1,j,k)+k^2-penalty)\]

Codeforces 1146H

问题:

见链接https://codeforces.com/contest/1146/problem/H

题解:

记$dp(i,j,k)$表示以顶点i开始结束,长度为k的凸包的数量。为了组成凸包,我们可以将一开始的所有线段按照斜率进行排序。之后我们可以遍历每条线段,并用线段对动态规划公式做补充,这样可以保证得到的折线的联结一定是凸包。

最后统计$\sum_idp(i,i,5)$即可。

CF1168C

问题:

见链接https://codeforces.com/contest/1168/problem/C

题解:

定义dp(i,j)表示所有带j比特中能被i访问到的,且下标最小的数的下标。则可以认为数a[dp(i,j)]或者可以被a[i]直接访问或者被a[i]间接访问,可以被a[i]直接访问的数最多有20个。可以通过动态规划公式得到结果。

CF1168D

问题:

见链接https://codeforces.com/contest/1168/problem/C

题解:

题解说可以通过树链剖分解决,不知道怎么做。按照题解里的来吧。

首先要满足条件,叶结点的深度一定相同。我们记$h_i$表示深度为i的结点的数目,那么不等式一定成立:$h_1\leq h_2 \leq \ldots$,如果我们发现两个相连的深度有等量结点,那么我们可以将两层压缩为一层。由于压缩后的数满足$h_1< h_2 < \ldots$,因此压缩后的树最高为$O(\sqrt(n))$

Codeforces1117F

题意

https://codeforces.com/problemset/problem/1117/F

题解

很容易想到这是一个位压DP,但是如何判断一个删除策略是否合法呢,这是需要解决的问题。

我们为每个序列中的字符,维护两个列表prev、next。prev[i]存储第i个字符之前最近的k种字符的出现顺序,而next[i]存储第i个字符之后最近的k种字符的出现顺序。

接着我们考虑所有的字符。假设处理到的字符为u,且u之前存在某个字符v与其不能相邻,那么记s为u与v之间的字符对应的二进制位的或。那么我们需要对s以及所有父集打一个+1标记,同时由于如果u、v中有一个已经被删除了,那么就不会冲突,我们对s|(1<<u)s|(1<<v)分别打一个-1标记。而由于s|(1<<u)|(1<<v)以及所有父集被多打了一次-1标记,因此我们在上面打一个+1标记。如果一个删除状态被打的+1标记多于-1标记,那么这个状态是非法的。

最后问题来了,如何上推标记,很简单用FWT即可。

总的时间复杂度为$O(pn+p2^p)$。

Codeforces1107F

题意

https://codeforces.com/contest/1107/problem/F

题解

首先容易想到最小费用最大流的做法,但是它是$O(n^3)$的。

我们可以将接受的offer分成两类,第一类是我们在买车之前不能还完的,第二类是我们在买车之前能还完的。

仅考虑第一类,我们会发现按照$b_i$从小到大排序后,我们依次进行贷款所需费用最小,而选择的顺序对于第二类是不重要的。因此我们可以进行DP,记$dp(i,j)$表示仅考虑$b_i$从大到小排序前面$i$个offer,总共有$j$个是属于第一类的,问最多能赚多少钱。之后动态规划即可,总的时间复杂度为$O(n^2)$。

Codeforces1093F

题意

https://codeforces.com/contest/1093/problem/F

题解

初看比较奇怪的问题。很显然得用DP。

记录dp[i][j][k]表示处理前$i$个字符后,最后一个字符为$j$,最后一个字符已经连续出现了$k$次了。

那么很容易推出转移公式,但是状态有$n^2k$种,很显然过不了。但是仔细观察递推项,会发现dp[i][j][k]dp[i-1][j][k-1]完全相同。因此如果我们把状态数组搞成可旋转的,就可以以$O(k)$的时间复杂度从dp[i-1]直接得出dp[i]。这样总的时间复杂度和空间复杂度都为$O(nk)$。

这种做法比较取巧。个人认为官方的做法比较好,官方的做法定义dp[i][j]表示处理完了前$i$个字符后,最后一个字符为j的所有有效方案数。

于是可以直接得出$dp[i][j]=\sum_{t=1}^k dp[i-1][t]$。但是这个公式有一个问题,没有考虑子段不能连续出现$len$个相同字符。这里唯一的一种情况是最后一个字符与前面$len-1$个字符完全相同。我们要减去这些非法状态,非法状态的数目为$\sum_{t=1}^k[t\neq j]dp[i-len][t]$。

Codeforces 1056G

题目

https://codeforces.com/contest/1056/problem/G

题解

由于$n$比较小,所有我们可以先保证$t$能整除$n$(重复操作直到)。

之后我们可以记录$dp(i,j)$表示从第$i$个位置开始移动$j,j-1,\ldots,1$后所抵达的位置。不难发现,当$i\leq m$时有$dp(i,j)=dp(i+j,j-1)$,在其他位置则有$dp(i,j)=dp(i-j,j-1)$。这意味着$dp(i,?)$是由$dp(i-1,?)$的碎片拼接而成的(最多有四个碎片)。我们可以利用持久化平衡树来优化加速,时间复杂度为$O(n\log_2n)$。

要写一个持久化平衡树太麻烦了,直接上rope好了。

Codeforces 1060F Shrinking Tree

题意

https://codeforces.com/contest/1060/problem/F

题解

很诡异的题目,比赛的时候但凡有点思路就又被自己否决了。

树上DP大家应该都知道这么做,可是怎么DP这才是最大的难题。看了其他人的题解后,也没法完全搞懂,这里记录一下。

由于$n$很小,我们可以对每个顶点作为根独立统计一次。下面我们仅考虑1号顶点作为根的情况。

首先统计概率比较麻烦,我们可以统计有多少方案能保证1号顶点最终存活,之后除去$2^{n-1}(n-1)!$得到真实的概率。

为什么这道题难呢,因为每条边对方案数的贡献可能是2,也可能是1(取决于是否与1号顶点相连),且树的形态也会改变。

首先我们避免树的形态改变,我们可以这样理解删边操作,每次删边后,会将边的两端顶点的连通块合并,而实际标号是等概率取两边连通块的标号之1。

我们定义两个辅助函数:

  • $f(u,i)$表示顶点$u$为根的子树对应的所有方案中(共$2^{size(u)-1}(size(u)-1)!$种方案),除了前$i$条删除的边外,后面的所有删除的边都不会修改$u$的标号的方案的数目。
  • 记$p$为$u$的父亲,定义$g(u,i)$表示以$u$为根的子树,加上$(u,p)$这条边的所有方案中(共$2^{size(u)}size(u)!$种方案),除了前$i$条删除的边外,后面的所有删除的边都不会修改$p$的标号的方案的数目。

如果我们为每个顶点算出了$f$和$g$函数值,那么$f(1,0)$就是我们要求的结果。

要计算$f(u,i)$,我们可以假设$u$下有$a,b,c$三个顶点,那么

\[f(u,i)=\sum_{c_a+c_b+c_c=i}g(a,c_a)g(b,c_b)g(c,c_c)\frac{i!}{c_a!c_b!c_c!}\frac{(size(u)-1-i)!}{(size(a)-c_a)!(size(b)-c_b)!(size(c)-c_c)!}\]

这个公式可以通过类似多项式卷积的方式得到,由于是树上DP,且任意两个顶点最多对时间复杂度贡献1,因此计算函数$f$总的时间复杂度为$O(n^2)$。

下面考虑$g(u,i)$怎么计算。这里我们额外加入了边$(u,p)$。可以分两种情况讨论:

  • 如果$(u,p)$是前$i$条删除的边中的一个,即早于$p$的标号被修改为1之前,这时候删除这条边,无论选择使用哪个连通块的标号都是没问题的,而除了$(u,p)$外还有$i-1$条$u$子树内的边被删除。且之后删除的所有$u$子树的边都不应该修改$u$的标号(因为这时候$u$和$p$在一个连通块了,如果修改$u$就会同时修改$p$),因此$g(u,i)$得到了$2if(u,i-1)$的贡献(乘2是因为可以任意选择连通块的标号,乘上i是因为$(u,p)$可能是作为第$1,2,\ldots,i$条边被删除的。)。
  • 否则$(u,p)$不属于前$i$条被删除的边,这时候它可能是作为第$i+1,i+2,\ldots, size(u)$个边被删除的。如果它是作为第$j$条边被删除的,那么它对$g(u,i)$的贡献应该为$f(u,j-1)$,即在$u$的子树下删除了$j-1$条边后,剩余的删除操作都不应该更高$u$的标号。

结合上面讨论的可以得出:

\[g(u,i)=2if(u,i-1)+\sum_{j=i}^{size(u)}f(u,j-1)\]

这里我可以通过预处理后缀的技术,每个顶点以$O(n)$时间复杂度算出函数$g$的值。

对于根选定的情况下,总的时间复杂度为$O(n^2)$,每个顶点都需要作为根算一次,因此总的时间复杂度为$O(n^3)$。

Codeforces1110E

题意

https://codeforces.com/contest/1110/problem/E

题解

很简单的题,只需要注意到对于连续的三个数字$c_{i-1},c_i,c_{i+1}$。对$c_i$进行操作后得到$c_i'=c_{i-1}+c_{i+1}-c_i$。

容易注意到$c'i-c{i-1}=c_{i+1}-c_i$,而$c_{i+1}-c'i=c_i-c{i-1}$。

我们可以记录$d_i=c_i-c_{i-1}$,那么操作实际上,会互换$d_i$和$d_{i+1}$,其它的不变。因此这个问题实际上就是问,允许任意次交换相邻d序列元素,能否使得$c$的d序列最终转换为t的d序列。xjb写吧。

Codeforces1183F

题意

https://codeforces.com/problemset/problem/1183/F

题解

首先由于不能选择相同的数,因此,我们可以在重复的数中仅保留唯一的。

现在来考虑怎么解决这个问题。

首先我们可以暴力枚举每个数$i$,以及以$i$作为选取最大值的所有方案的最大和。

在已知$i$是方案中最大的数的前提下,我们可以继续枚举第二大的数。我们找到比$i$小且不是$i$的因子的最大的数$j$。

接下来我们证明以$i$作为最大值的所有方案中和最大的方案,一定同时包含$j$。为啥呢,因为如果不含$j$,那么就必定包含另外两个数$a$,$b$,且$a,b<j$。由于$a,b$不能与$j$共存,因此$a$,$b$都一定是$j$的因子,即$a+b\leq j(\frac{1}{2}+\frac{1}{3})<j$。而这个方案还不如直接选择$i$,$j$来的好,因此假设不成立。

那么现在我们直到$i$,$j$必选了,最后一个数选啥呢,当然选能选的里面的最大的就可以了。

这个问题,每个数最多有$\sqrt{n}$个因子,因此时间复杂度为$O(n\sqrt{n})$。

Codeforces1144G

题意

https://codeforces.com/problemset/problem/1144/G

题解

我一开始写的是DP的做法,用线段树优化。

后来发现有一位大佬提了个贪心的做法,果然好用。算法非常简单,维护两个列表,一个递增,一个递减。之后从前往后处理$a_i$,如果$a_i$不能放入任意一个列表中,就无解。否则若仅能放入一个列表中,就放到允许的列表中即可。否则,我们根据$a_{i+1}$来做决定,若$a_i<a_{i+1}$,那么就将$a_i$放入递增列表,否则放入递减。

可以证明如果有解,上面算法一定能找到一组解。事实上,仅考虑最后一种情况,若最优结果中,$a_{i+1}$放入递增列表,那么直接我们发现对$a_i$的处理是不会影响最终解的。当然如果我们把$a_{i+1}$放入递减列表,那么我们自然只能间$a_i$放入递增列表。因此可以证明最后一种操作是最优的。

Codeforces1137D

题意

https://codeforces.com/problemset/problem/1137/D

题解

神奇的解法,以前确实做过类似的龟兔赛跑来判环的方法,但是确实从来不知道用三个棋子,3(t+c)步就可以得出t和c的所有信息。

首先,我们可以用棋子0和棋子1做龟兔赛跑,棋子0每次走两步,棋子1每次走一步。直到二者在环上距离入口x处相遇。这时候0走的距离为$t+x+kc$,1走的距离为$t+x$(1肯定没有走完整个循环)。而由于0走的距离是1的两倍,因此可以推出:$t+x=0\mod c$。这意味着当我们将所有棋子每次都向前移动一步,那么至少需要t步才能保证所有棋子都走到循环的入口,同时t步也正好能保证所有棋子来到循环的入口。

CF1097D

题意

https://codeforces.com/contest/1098/problem/D

题解

这是一个大鱼吃小鱼的问题。我们将所有鱼按重量从轻到重进行排序,重量记作$a_1,a_2,\ldots,a_n$。现在如果有一条鱼$a_t$,满足$2\sum_{i=1}^{t-1}a_i<a_t$,那么我们称$a_t$为胖子。下面我们需要证明最重要的一个定理:

最大危险数等于$n-k$,其中$k$为序列中的胖子数。我们利用归纳法进行证明。

当序列中只有第一个数是胖子时,总共发生$n-1$次战斗,因此我们只需要证明存在一种方案,使得$n-1$次战斗都危险即可。

考虑这样的算法,每次都选择最小的两条鱼战斗。我们可以用归纳法证明这一步,只有两条鱼时命题显然成立。假设现在有$k>2$条鱼。我们将最小的两条鱼合并,同时将合并后的鱼插入到序列中,假设新的序列为$a_1',a_2',\ldots,a_i',\ldots,a_{k-1}$。其中$a_i'$为合并后的鱼。我们需要证明此时只有$a_1'$是胖子。由于$a_2'\leq a_3'\leq \ldots \leq a_i'\leq 2a_1'$,因此$a_2',a_3',\ldots,a_i'$中没有胖子存在。而对于任意数$a_j'$,其中$j>i$,由于所有小于它们的和不变,因此也不是胖子。现在我们证明了当只有第一只鱼是胖子,最大危险数等于$n-1$。

现在考虑胖子数$t$多于1的情况,这时候我们将重量第二小的胖子之前的鱼全部安排战斗,将战斗后活下来的鱼与这个胖子战斗,得到的新序列胖子数会减少1,一场战斗是不危险的。利用归纳法可以得出存在一种战斗方案,危险数等于$n-t$。

但是我们还没有证明$n-t$是一个上限。可以发现对于某个胖子$a_i$,要让$a_1,a_2,\ldots, a_{i-1}$中至少一个鱼与$a_i,a_{i+1},\ldots,a_n$中某条鱼合并,至少需要加入一场不危险的战斗。因此我们可以断定$n-t$是一个上界。

接下来我们要处理的问题就是:

  • 删除一个数
  • 插入一个数
  • 计算有多少个数,其前缀和的两倍小于自己

这个问题貌似还是不能解决。但是我们可以将区间划分为$[2^0,2^1),[2^1,2^2),\ldots,[2^{29},2^{30})$,能够发现每个区间中最多有一个胖子(且一定是区间中最小的数),因此可以维护$30$个平衡树统计一下即可。

Codeforces 1268B

题意

https://codeforces.com/contest/1268/problem/B

题解

有一个高度非严格单调减的直方图,希望放置尽可能多的1x2或2x1的多米诺骨牌上去。

首先我们将直方图看成一个棋盘,并对其进行染色,将所有网格染成黑色或白色,且黑色和白色不相邻。

之后我们记黑色的数目为$B$,白色的数目为$W$。

下面我们用归纳法证明结果为:$\min(B,W)$。

在网格总数为0、1的时候结果当然是0,满足命题。之后我们记棋盘第$i$行的长度为$b_i$,第$j$列的高度为$a_j$。如果存在某个下标$j$满足$a_j=a_{j+1}>a_{j+2}$。我们将第$j$列和第$j+1$列的最顶部的两个网格放置一个多米诺骨牌。这样利用归纳法可以推出结果为$\min(B-1,W-1)+1=\min(B,W)$。如果不存在这样的列,就考虑行。下面认为没有两列或两行相同,那么此时一定满足$a_i=n-i+1$。这时候一定有$B-W=\lceil\frac{n}{2}\rceil\geq 1$。我们可以直接删除第一列最顶部的黑色网格,此时依旧满足$\min(B,W)=\min(B-1,W)=W$。因此命题成立。

CF1251E2

题意

http://codeforces.com/contest/1251/problem/E2

题解

首先我们可以将这个问题转换为一般的前缀匹配问题形态2。第$i$个人在有$m_i$个人支持后费用位0,否则费用为$p_i$。转换为我们的问题,就是第$i$个人希望做前$n-m_i$把椅子,否则不满意度为$p_i$。这样就可以直接解决了。

CF1175D

题意 https://codeforces.com/contest/1175/problem/D

题解

记S(i)=a(i)+a(i+1)+…+a(n)。分别记最优解的划分下,第i个分块的第一个元素下标为f(i)。那么问题下面式子在最优解下一定取最大值。

\[1\cdot (S(f(1))-S(f(2)))+2\cdot (S(f(2)) - S(f(3)))\\+\ldots + (n-1)(S(f(n-1))-S(f(n)))+nS(f(n))\\ =\sum_{i=1}^nS(f(i))\]

由于f(1)一定是取到1,我们可以将S(2),S(3),…,S(n)排序后取前面最大的k-1个的和加上S(1)就是结果。

CF1175F

题意 https://codeforces.com/contest/1175/problem/F

题解

我们可以逐个统计每个有效子排列。寻找所有1出现的位置,很显然一个有效排列必定包含且只保护其中之一的1。

我们维护一个函数R,R(i)表示形如a(i),a(i+1),…的无重复元素的最长序列的长度。

之后我们遍历每个1出现的位置i。之后包含i的序列的右边界只可能为j=i,i+1,…, i+R(i)-1。之后假设序列中最大的元素落在i的右边,因此我们只需要知道m=max(a(i),a(i+1),…,a(j)),而序列有效的必要条件是长度等于m,因此我们可以推出左边界k=j-m+1。之后只需要快速判断子序列a(k),…,a(j)是否是一个有效序列就可以了。判断的方法很简单,首先要求R(k)>=max,其次min(a(k),…,a(j))=1且max(a(k),…,a(j))=m。

对于最大元落在左边的情况,只要翻转序列后重新用上面过程处理一次就可以了。

利用线段树就可以在O(nlogn)的时间复杂度内解决。

Codeforces1209B

题意

https://codeforces.com/contest/1209/problem/B

题解

我做的顺序是D、A、C。。。B。这道题还是有点东西的。

一开始看,以为是中国余数定理(怎么可能,C还是一个贪心呢,B怎么可能)。后来搞了搞贪心,没搞出来。最后实际一看,a、b范围很小,只有5。

实际上问题非常简单,由于b范围很小,那么我们可以保证灯下一次亮的时间不会超过10。而a范围很小,我们可以推出灯亮的间隔不会超过10。因此10秒之后,L=lcm(2,4,6,8,10)是所有灯状态的一个周期。因此我们只要暴力枚举到130左右,就能遍历所有可能了。

当然保险起见,枚举个10000也未尝不可。

Codeforces1264E

题意

https://codeforces.com/contest/1264/problem/E

题解

题目同BZOJ2597

首先建图,n个顶点,如果i胜j,那么加入一条有向边(i,j)。可以发现对于任意一个三个顶点,如果它们不组成一个三元环,那么它们中会恰好有一个顶点的入度为2(仅考虑包含这三个顶点的导出子图)。现在考虑任意一个顶点x,如果它的入度为k,那么在所有入边对应的另外一个顶点组成的集合S中,任取两个顶点y、z,那么x、y、z无法组成一个三元环。因此顶点x对最终结果有$-{k \choose 2}$的贡献。

要让图中的三元环最多,那么就需要让负数贡献尽可能小。我们可以用最小费用最大流来解决。

建立n个顶点,每个顶点到终点有m-1条边,第i条边的费用为i-1。为了保证任意两个顶点u、v的比赛结果只有一方胜利,那么我们为每场比赛建立一个顶点u-v。u-v到u和到v各连一条边,而源点向每一场比赛连一条边(容量为1)。

由于一些比赛的结果已知,比如已知u胜v,那么就将u-v比赛到u的边删除即可。

最后跑一波最大流,结果矩阵可以通过取比赛的流出方向得知。

总的图大小为$O(n^2)$个顶点和边。时间复杂度为$O(n^4)$,能过。

Codeforces 786E

题意

https://codeforces.com/contest/786/problem/E

题解

容易发现,问题要求我们求最大权闭合子图,我们需要从市民向守护者建立依赖关系。因此闭合子图中顶点的数目为$O(n+m)$,而边的数目为$O(nm)$。因此我们需要做的是把边的数目降下来。

需要观察到,对于每个市民,其依赖的守护者正好是树上的一条路径。而我们知道有很多技术可以将树上的路径切分为$O(\log_2n)$段的,比如说树上倍增,或者轻重链剖分。我们这里可以选择树上倍增技术,即我们为每个守护者建立$\log_2 n$个顶点,第$i$个顶点代表的是从这个守护者的深度较大的端点向根移动$2^i$步代表的路径上所有的边。

这样闭合子图中的顶点的数目就增大到了$O(n\log_2n + m)$。

而对于市民以来的路径,我们可以算出路径端点的lca,之后分别依赖从端点到lca的路径即可。这样依赖关系也被降低到了$O((n+m)\log_2n)$。

于是我们就可以采用最大流算法来解决这个问题了,时间复杂度为$O(能过)$。

Codeforces1209E2

题意

https://codeforces.com/contest/1209/problem/E2

题解

一开始以为是贪心或匹配问题,算算时间复杂度怎么都超。但是最后看题解发现是DP。

很显然m列我们最多只需要n列,这n列的最大值一定是最大的。因此提前排序后筛选,就只剩下n行n列。

我们用二进制表示某一行是否已经被选定,1为被选定,0为未选择。定义函数$g(i,s)$,表示第i列的选定状态为s,问最大总和是多少。首先每一列最多有n种形态(旋转的周期为n),之后对每种形态枚举即可。这里的时间复杂度为$O(n^32^n)$,可以稍加优化(在计算子集的同时计算总和),可以优化到$O(n^22^n)$。

之后记函数$f(i,s)$,表示只考虑前i列,选定状态为s的最大和。只需要简单枚举第i列的选定状态,就可以得出前i-1列的选定状态,这是一个子集问题,时间复杂度为$O(n3^n)$。

最后总的时间复杂度为$O(40(nm+m\log_2m+n3^n+n^22^n))$,计算量大概几亿,是可以过的。

CF1172C

题意

https://codeforces.com/contest/1172/problem/C2

题解

记f(w,i,j,k)表示初始权值为w的喜欢的图片经过k次操作后的期望权值,其中喜欢的图片权值之和为i,讨厌的图片权值之和为j。

可以推出公式:

\[f(w,i,j,k)=\frac{w}{i+j}f(w+1,i+1,j,k-1)\\ +\frac{i-w}{i+j}f(w,i+1,j,k-1)\\ +\frac{j}{i+j}f(w,i,j-1,k-1)\]

很显然状态过多了。但是可以证明$f(w,i,j,k)=wf(1,i,j,k)$,因此我们只需要计算形如f(1,i,j,k)的函数值。并且当i和k确认时,j也随之确认。因此我们可以将公式变为$f'(i,k)$。总共有$O(m^2)$种状态。

Codeforces 1097D

题意

https://codeforces.com/contest/1097/problem/D

题解

对于形如$n=p^m$的整数,其中$p$是素数,这个问题是非常简单的,简单DP算算前缀和即可。

那么$n$是不同素数的乘积的情况下该怎么处理,这时候有$n=p_1^{c_1}p_2^{c_2}\ldots p_t^{c_t}$。

这时候需要一个重要的发现,不同的素数衰退是独立的。记录$f(a,b,k)$表示形如$p^a$的数经过k步骤变换为$p^b$的概率。那么$n$经过k步转化为$n=p_1^{c'_1}p_2^{c'_2}\ldots p_t^{c'_t}$的概率可以表达为$f(c_1,c'_1,k)f(c_2,c'_2,k)\ldots f(c_t,c'_t,k)$。

首先$10^{15}$以下的数因子最多两万多个,所以可以暴力枚举所有的解决方案。

Codeforces1264C

题意

http://codeforces.com/contest/1264/problem/C

题解

考虑一段区间$[l,r]$,记$f(l,r)$表示从$l$出发,到抵达$r+1$的期望步数,这里假设在$x\leq l$处有最近的复活点。

由于期望可以独立统计。假设复活点为$x_1,x_2,\ldots, x_k$,因此我们需要完成的任务是快速计算$f(x_1,x_2-1)+f(x_2,x_3-1)+\ldots +f(x_k,n)$。每次修改操作最多影响公式中的两项。

考虑$x=x_i$,以及$x_i < l\leq r <x_{i+1}$。我们发现转移关系可以表示为$f(l,r)=a_{l,r}+b_{l,r}f(x,r)$。同时我们可以得到:

\[f(x,r)=(a_{x,l-1}+f(l,r))(1-b_{x,l-1})+(a_{x,l-1}+f(x,r))b_{x,l-1}\\ =(a_{x,l-1}+a_{l,r}(1-b_{x,l-1}))+(b_{x,l-1}+(1-b_{x,l-1})b_{l,r})f(x,r)\]

因此可以推出:

\[a_{x,r}=a_{x,l-1}+(1-b_{x,l-1})a_{l,r}\\ b_{x,r}=b_{x,l-1}+(1-b_{x,l-1})b_{l,r}\]

对于任意$x<l\leq r$成立。

因此我们可以用类似倍增的方式快速求解。这里不能使用ST来进行加速,因为会带来重复合并的问题,但是可以使用猫树这种数据结构。

Codeforces 1025F

题意

https://codeforces.com/contest/1025/problem/F

题解

首先需要发现,对于任意两个不相交的三角形,一定能找到一条线,使得两个三角形属于这条线的两侧(且与线无交点)。我们可以微微旋转这条线,直到与两个三角形都相交,这样就得到了两条切线。

剩下的就没有什么难度了,直接暴力枚举切线即可。

由于暴力枚举线,每次统计切线两侧顶点数比较麻烦,所以可以先选择切线的一个端点,将其余顶点提前排序,之后用两个指针扫描即可。

总的时间复杂度为$O(n^2log_2n)$。

Codeforces 1019D

题意

https://codeforces.com/contest/1019/problem/D

题解

求三角形面积,我们知道三角形的面积可以利用叉积进行计算。我们从几何的角度进行观察,当我们选择了两个顶点之后,这两个顶点将整个平面分成两个半平面,我们要找到这样一个顶点,它距离之前选择的两个顶点的连线的距离为给定值。如果我们能提前将所有顶点按照它们到这两个顶点的连线距离进行排序,那么这个问题就只剩下二分了。

但是很显然每次选择两个顶点的复杂度为$O(n^2)$,而对所有顶点进行排序每次的时间复杂度为$O(n\log_2n)$,这样总的时间复杂度为$O(n^3\log_2n)$,这样还不如暴力枚举的$O(n^3)$时间复杂度呢。

但是神奇的事情是如果我们按照所有顶点之间的连线按照它们的极角进行排序,并依序处理,并且每次我们都利用插入排序重新维护所有顶点到连线的距离,那么在整个过程中最多只会发生$O(n^2)$次邻位交换。即我们不必每次都排序,而只需要花费$O(n\log_2n)$的时间复杂度提前预先排序后,之后总的维护排序关系的时间复杂度仅为$O(n^2)$。

但是这里比较特殊的是我们不在按照距离进行排序,而是按照与当前扫描到连线的向量的叉积进行排序(距离始终非负,而叉积允许出现负数,可以携带更多信息)。我们能看出两个顶点a,b的叉积大小关系什么时候会改变,自然是在扫描到连线$(a,b)$的时候,因此大小关系最多只会发生$O(n^2)$次改变,这里我们可以暴力修复排序。

之后对于每个扫描线,对有序列表进行二分查找即可,非常容易。

总的时间复杂度为$O(n^2\log_2n)$。

Codeforces 1251F

题意

https://codeforces.com/problemset/problem/1251/F

题解

首先弄明白题目到底问的是个啥。

有$a+b$种不同颜色的球,其中$a$种颜色只有一个球,$b$种颜色各有两个球。现在有两个不同的袋子,我们希望往两个袋子中放入总共k个球。问对于所有$k\leq a+2b$,各有多少种不同的放法。

假如$b=0$,那么放法一定是${a \choose k}2^a$,即选出${a \choose k}$个球,之后将每个球放入一个袋子种。

假如$a=0$,那么放法一定是$f(k)=\sum_{i=0}^k{b\choose i}{b\choose k-i}$,即独立考虑装入两个袋子中的球。

我们可以通过枚举只有一个球的颜色加入数目来进行统计:

\[g(k)=\sum_{i=0}^{k}2^i{a\choose i}f(k-i)\]

可以发现$f$函数和$g$函数都是卷积的结果,因此它们的生成函数可以用卷积进行计算,因此总的时间复杂度为$O((a+b)\log_2(a+b))$。

Codeforces449D

题意

https://codeforces.com/problemset/problem/449/D

题解

要统计有多少个序列且运算和为0,可以通过统计有多少序列且运算和非0得到。而要统计后者,容易观察一个序列且运算非0,则至少存在一个二进制位,序列中所有元素在这个二进制位处值都是1。

记$A_i$表示所有且运算结果中第i个二进制位为1的所有序列组成的集合。那么我们实际上要统计的就是$|A_0\cup A_1\cup \ldots \cup A_k |$,这里k取20。这可以利用容斥得到。

下面我们说明如何快速计算上面提到的若干个元素的交集大小。首先我们先统计每个数在序列中出现的次数,记作$f(x)$。之后统计$g(x)$,表示所有x的超集y(y&x=x)出现的次数,这可以利用快速沃什尔变换得到。

最后比如要统计$|A_0\cap A_1|$,即有多少序列的且运算结果是3的超集,首先我们容易得知序列中的所有元素都来自3的超集,而3的超集的大小为$g(x)$,每个数都有出现和不出现两种情况,因此总的序列数为$2^{g(x)}-1$,这里减去1是因为序列的长度不能为0。

Codeforces1204E

题意

https://codeforces.com/contest/1204/problem/E

题解

枚举可能的f取值,0~n,之后用Catalan数统计g(i),其中g(i)表示f取值小于等于i的序列数。之后求解。时间复杂度为$O(n+m)$。

Codeforces960G

题意

https://codeforces.com/contest/960/problem/G

题解

由于无论从左边开始还是右边开始,最后拿的一定是最大值。因此最大值将序列分为了左右两边。称一个数为局部最大,当且仅当这个数之前没有比它大的数。那么我们实际上从左边能拿到a个数,就意味着最大值坐标,共有a-1个局部最大值。同理最大值右边有b-1个局部最大值。

定义函数$f(i,j)$表示拥有j个局部最大值的长度为i的排列数目。那么我们要求的实际上就是:

\[g(n,a,b)=\sum_{i=0}^{n-1}{n - 1\choose i}f(i,a-1)f(n-1-i,b-1)\]

考虑如何放置排列中的最小值,容易发现$f$满足下面递推性质:

\[f(i,j)=f(i-1,j-1)+(i-1)f(i-1,j)\]

这个递推式与第一类stirling数是相同的,同时在边界情况与第一类stirling数拥有相同值,因此可以认为: \(f(i,j)=c(i,j)\)

第一类stirling数表示的是将i个数分成j个环的策略数。利用这个性质我们可以简化要求的结果:

\[g(n,a,b)=c(n-1,a+b-2){a+b-2\choose a-1}\]

stirling数可以通过快速卷积得到。总的时间复杂度为$O(n\log_2n)$。

Codeforces1114F

题意

https://codeforces.com/problemset/problem/1114/F

题解

首先对m做因子分解。之后可以想到用中国余数定理合并结果,因此我们需要处理的模式为$p^c$,其中$p$是素数。

由于除法很讨厌,我们可以维护每个数有多少因子$p$即可,对于除上$x$。从$x$中提取所有的因子p,那么除去这些因子p就等价于做减法。而最后考虑去除所有$p$因子后我们得到了$y$,而$y$与$p^c$互质,用扩展欧几里得算法可以求出$y$在模$p^c$意义下的逆元,除法就变成了乘法。

为所有$m$的因子建立一个线段树,分别进行维护即可。统计总和的时候,用中国余数定理合并结果。

Codeforce1198F

题意

提供n个数,数的范围是[1,1e9],将数分成两个非空集合,要求每个集合中元素的最大公约数为1,问是否可能。

题解

神奇的题目。由于数的范围不大,容易发现每个数最多有k=9个不同的素因子。如果一个集合的最大公约数为1,那么我们一定能通过排除集合部分元素,将集合的大小缩减到不超过$k+1$。

首先当n比较小的时候,我们可以直接枚举所有的划分方式,时间复杂度为$O((2^n+n)\log_2n)$。我们可以接受n=20的情况。

再考虑$n>20$的情况,我们打算构建两个可能的集合A、B。我们将第一个元素$a_1$放入到集合A中,可以保证假如有解,那么一定有一种方案,使得$a_2,a_3,\ldots, a_{k},a_{k+1}$中至少有一个元素属于集合B。我们不妨认为元素$a_2$属于集合B,那么我们可以将$a_1,a_2$进行质因子分解,之后通过动态规划来寻找可能的方案,时间复杂度为$O(n2^{2k})$。

这个时间复杂度是不可行的,但是我们注意到为了消除$a_0$的某个素因子$p$,我们需要向A加入一个不含因子$p$的数,由于B中最多还可以加入$k$个数,因此我们仅需要考虑前$k+1$不含因子$p$的数,这样至少会有一个不含因子$p$的数被加入到A中,从而消除A中的因子$p$。

对每个$a_1,a_2$的素因子都仅考虑前$k+1$个数,这样被考虑的数不会超过$2k(k+1)$个。我们证明如果没有找到一个划分的话,一定无解。假设在缩减后的集合中没有找到划分,但是原来的集合是存在划分的,这意味着我们必须向缩减后的集合加入至少一个被剔除的数x。假设这个数是被加入到集合A中,那么说明集合A中还剩余了某个素因子$p$没有被消除,且x不含有因子$p$。但是考虑到我们缩减后的集合中已经包含了$k+1$个不含$p$的数,而其中至少一个属于A,因此与前提相悖。

我们只需要分别判断当$a_2,a_3,\ldots, a_{k},a_{k+1}$属于集合B时是否有解,如果都没解,就说明无解。

Codeforces 1027G

题意

https://codeforces.com/contest/1027/problem/G

题解

这个问题挺有意思的,考察的面非常广。这里的题解先是我个人的思考过程(当然结果以失败告终),最后是官方的题解。

首先我们可以将每个房间作为顶点建图,同时建立$n$条边,第$i$条边为$(i,ix)$。(这里的乘法运算默认是在模m的意义下的)。

很显然每个顶点都恰好有一条出边,同时由于$gcd(x,m)=1$,因此我们可以找到$x$的逆元,这意味着$ix=j\Rightarrow i=jx^{-1}$,即每个顶点的入边也都正好只有一条,不难证明现在的图是由一些简单环组成的,而我们只需要在每个环中放入一个陷阱,就可以保证抓到老鼠,因此我们实际上要做的就是统计有多少简单环。

由于老鼠可能从任意房间出发,比如如果老师从房间$i$出发,那么经过的顶点就是$ix^0,ix^1,\ldots,ix^n$,其中$ix^n=ix^0$。如果$i$与$m$互质,那么就能推出$x^n=1$。即我们要找到这个$n$,就能确定每个环的长度。这个$n$怎么算呢,我的想法是用离散对数,这样就能在$O(\sqrt{m})$的时间复杂度内找到这样的一个$n$,最后我们只要尝试所有$n$的因子,找到其中最小的因子$d$,满足$x^d=1$。

但是我的思路有一个大的问题,就是假设了$i$和$m$的互质,那么不互质怎么办呢?

下面是官方的题解:

首先我们将所有$1$到$m-1$的数按照其与$m$的最大公约数进行分类处理,假设目前处理的最大公约数是$g$,而与$m$的最大公约数为$g$的数组成的集合为$S_g$,我们会发现对于任意一个$S_g$中的元素$y$,都有$gcd(yx,m)=gcd(y,m)=g$,因此$S_g$中的顶点仅与$S_g$中的顶点有连边。

用之前提到的办法,我们发现$\frac{i}{g}$与$\frac{m}{g}$是互质的,因此我们要做的就是计算$x^n=1\mod \frac{m}{g}$以及$S_g$的大小。

前者实际上可以利用欧拉函数得到这样的一个$n$,之后遍历$n$的所有因子找到其中最小的因子$d$满足$x^d=1$。

后者则可以利用莫比乌斯反演得到。记$F(g)$表示$1$到$m-1$中所有整除$g$的数的数目,而$f(g)$则表示$1$到$m-1$中所有与$m$最大公约数为$g$的数的数目。那么就有:

\[F(g)=\sum_{g|d}f(d)\\ \Rightarrow f(g)=\sum_{g|d}\mu(\frac{d}{g})F(d)\]

Codeforces1109D

题意

https://codeforces.com/contest/1109/problem/D

题解

我们可以暴力枚举a到b之间路径上的顶点数,至少为2,最多为n。现在假设路径上的顶点数为$k$。

由组合数学可以快速得到从a到b这条路径上$k-1$条边总共的权重赋值方案。之后我们需要考虑在固定了a到b这条链后,与其余顶点可以组成多少不同的树。我们可以将a到b中$k$个顶点合并作一个顶点,这样我们问的就是有多少种组成树的方案,最后乘上边权带来的贡献即可。

由prufer编码知道一个顶点度数为d,那么这个顶点会在prufer中出现d-1次。借此我们枚举合并的顶点的度数来求解(每个连接到合并的顶点实际上可能连接到$k$个顶点中的任意一个,这部分贡献不能忘记算)。

记$f(x,n)$表示n个顶点能组成多少树,其中一个顶点是由x个顶点合并得到的。

\[f(x,n)=\sum_{d=1}^{n-1}{n-2\choose d-1}(n-1)^{(n-2)-(d-1)}x^d\\ =x\sum_{d=1}^{n-1}{n-2\choose d-1}(n-1)^{(n-2)-(d-1)}x^{d-1}\\ =x\sum_{d=0}^{n-2}{n-2\choose d}(n-1)^{(n-2)-d}x^{d}\\ =x(n-1)^{n-2}\sum_{d=0}^{n-2}{n-2\choose d}(\frac{x}{n-1})^d\\ =x(n-1)^{n-2}(1+\frac{x}{n-1})^{n-2}\\ =x(n-1+x)^{n-2}\]

套上去就可以得出结果了。时间复杂度是$O(n\log_2n)$。

Codeforces392C

题意

https://codeforces.com/problemset/problem/392/C

题解

可以想出一个矩阵快速幂的做法,矩阵的大小应该是80~90之间。但是矩阵不好算,因为需要用到二项式展开。

直接提前算出前200项的值,之后BM暴力推出其递推因子,之后用递推因子执行多项式取模,快速得出我们要的结果。这里的时间复杂度为$O((2k)^2+(2k)^2\log_2k)$,随便写都能过。

Codeforces1207G

题意

https://codeforces.com/contest/1207/problem/G

题解

首先理解问题,我们有n个字符串和m个匹配串,希望能找到m个匹配串的出现次数。非常明显的一点就是我们要将m个匹配串建立AC自动机。之后可以发现n个字符串实际上对应了大小为n的一棵前缀树。

之后我们遍历前缀树,每遍历一个顶点,就处理与顶点关联的所有匹配串。需要注意的是我们需要实时统计某个匹配串出现次数,我们可以将AC自动机的fail链条建树,之后一个匹配串的出现次数实际是这个匹配串对应的AC自动机结点及其下所有结点匹配次数之和。

还有一点需要注意的是前缀树会发生回溯,因此每次处理完一个顶点并返回时需要回退所做的所有操作。

时间复杂度为$O(20(n+m))$

Codeforces 1336C

题意

https://codeforces.com/contest/1336/problem/C

题解

天哪,这么简单的题我竟然没做出来。被这道题卡了太久还没做出来(卡了一个多小时),结果剩下来的时间不足以去完成E1(我想出来后只剩下10分钟的时间了),导致比赛血崩。不过看到其他一些红名他们也没做出来,感觉大家都应该想复杂了。

我讲一下自己的心路。看到这道题首先考虑的是必须用完整个字符串$S$的前提下有多少成功的操作方案。我们可以给每个数标记$01$,标记为0的表示放前面,标记为1的表示放后面,于是乎,如果我们从后面开始向前扫描,那么可以$O(n^2)$时间复杂度解决这个问题。但是现在题目不要求必须$n$次操作,这样时间复杂度就被提高到了$O(n^3)$,之后我就开始纠结于使用AC自动机来计算后缀的模式,甚至想要设计一个支持双向插入的AC自动机。还想了放在前面的构建的字符串正好是被0标记的子序列的反转,通过枚举0序列长度来求解,但是时间复杂度还是$O(n^3)$,始终没有优化下去。

题目的做法实际上非常简单。就是我们维护的$A$必须是$T$的某个中间的子串,因此我们可以枚举当前构建的左右位置,即定义一个DP公式$f(i,l,r)$表示消耗掉$S$的前$i$个数后,构建的序列恰好是$A[l..r]$的方案数,这里可以发现$r=i+l-1$,因此$i$和$l$一旦确定,$r$也就确定了,因此公式可以简化为$f(i,l)$。注意到每个状态的计算时间复杂度均为$O(1)$,因此可以$O(n^2)$计算$f$。

答案,当然就是$\sum_{i=m}^nf(i-1,0)$。

下面我们证明一下不会出现重复统计的情况,即对于任意一个操作序列,不可能贡献一次以上。对于任意$i$,操作序列的$l$是确定的,因为操作序列中向$A$左边填充的次数是固定的,而最终要求$l$达到$0$。

Codeforces 924E

题意

https://codeforces.com/contest/924/problem/E

题解

对于任意堆叠盒子的方案,我们可以将上下颠倒,记$m=\sum_ia_i$,那么我们记$L=m-r$,而$R=r-l+L$,于是乎现在问题变成了要求我们堆叠盒子,问上边界落在$[L,R]$之间的重要盒子最多有多少个。

不难发现,重要箱子的放置一定是连续的,且上边界不超过$R$的重要盒子的大小从下到上是递减的(这一点可以通过尝试交换相邻盒子证明)。

于是我们可以将所有箱子按照$b$从小到大排,如果$b$相同,则按照$a$从大小排,之后计算一个01背包DP即可。时间复杂度为$O(nm)$。

Codeforces 889D

题意

https://codeforces.com/contest/889/problem/D

题解

这道题最后也没做出来,java代码TLE了。下面讲讲做法。

记$g$为所有顶点的重心。现在我们不考虑过原点的线,我们考虑过重心的线,很显然两者的答案是相同的。

有两种情况,如果每个顶点存在一个相对于$g$的对称点,那么我们可以在这些顶点之间建立匹配关系,这样任意一条过重心的线,所有顶点在上面的投影,对称点依旧相对于重心对称。这时候解有无穷个。

第二种情况,不是所有顶点有对称点。我们将有对称点的从点集中移除(因为它们始终对称),记$m$为剩下的顶点数目。之后如果某条直线满足条件,则一定存在两个顶点不相对于重心对称,但是投影后对称。我们可以暴力枚举这样的点对,从而确认最多$m^2$条线。很显然只有一条直线出现超过$m$次,才有可能成为候选,因此最终我们只需要校验$m$条线即可。

将所有顶点对某条线进行投影,之后排序后校验即可。

总的时间复杂度为$O(n^2\log_2n)$。

codeforces 1342F

题意

https://codeforces.com/contest/1342/problem/F

题解

考虑只有一个测试样例的情况。

最少的操作次数,等价于留下的数最多。我们可以记$dp(i,j,k)$表示用$k$代表的集合中的数,剩下$i$个数,其这$i$个数中最靠右的数为$j$,问最大的数最小可能是多少。

那么就是一个简单的DP,时间复杂度为$O(n^23^n)$,常数大概可以优化到$\frac{1}{4}$或者更小。加一堆剪枝应该能过。

codeforces 870D

题意

https://codeforces.com/contest/870/problem/D

题解

我们可以提前预处理出$p_0$和$b_i$的亦或和,同时处理出$p_i$和$b_0$的亦或和,这样总共$2n$次请求。

接下来,我们可以得出任意两个数的亦或和:

\[p_i\oplus p_j=(p_i\oplus b_0) \oplus (p_j\oplus b_0)\\ p_i\oplus b_j=(p_i\oplus b_0) \oplus (p_0\oplus b_j)\oplus (p_0\oplus b_0)\\ b_i\oplus b_j=(p_0\oplus b_i) \oplus (p_0\oplus b_j)\]

之后由于$n\leq 5000$,我们可以直接暴力枚举$p_0$,由于$p_0$一旦确定,其余数也都确定了。我们需要校验$p$和$b$是否是合法排列其互逆。

总的时间复杂度为$O(n^2)$。

codeforces 871E

题意

https://codeforces.com/contest/871/problem/E

题解

我们这边不考虑无解的情况,无解只是判断一堆case而已。

挺恶心的题目。首先可以选择任意一个特殊点作为根,之后将其余特殊点到根的路径求出来,这部分可以$O(nk)$完成。

之后考虑其余没有加入到树中的顶点。我们按照这些顶点到根的距离从小到大进行处理。设现在在处理的顶点为$a$,注意到$a$与所有特殊顶点的LCA落在$a$到根的路径上,很显然$a$一定落在深度最大的LCA的子树中,记与这个顶点拥有深度最大LCA的特殊顶点为$b$,而二者的LCA为$c$,可以发现$a$到$c$的路径上(不含$c$)没有特殊顶点存在。因此我们可以这样做,为每个顶点做倍增来快速找到LCA。由于两个顶点的距离为$depth(a)+depth(b)-2depth(c)=dist(a,b)$,因此可以对每个特殊顶点确定LCA的深度。

同时为每个顶点维护一个最深的叶子顶点,从这个顶点到叶子顶点的路径上(不含起点)没有特殊顶点。由于我们是按照深度加入顶点的,因此可以直接将$a$挂在$c$的叶子顶点下即可。

最后需要校验每个特殊顶点到其余顶点的距离是否满足要求。

总的时间复杂度为$O(n\log_2n+kn)$。

Codeforces1215D

题意

https://codeforces.com/contest/1215/problem/D

题解

首先我们统计出左边的已知总和s1,未知数数目c1,以及右边的已知总和s2,未知数数目c2。

我们重新理解题目,现在一个数$s=s1-s2$,两类未知数,第一类未知数(c1个)向s增加一个数(0~9),第二类未知数(c2个)从s减去某个数(0~9),最终结果为0判后手胜,否则先手胜利。

问题实际上还是有点复杂,我们可以简化一下,将两类未知数合并。由于减去一个数x(0<=x<=9),等价于增加一个数y-9(0<=y<=9),这里我们可以提前将-9全部提取出来,即$s'=s-9c_2$。之后就只剩下一类未知数了,共$c_1+c_2$个。

那么问题很简单了,如果$s'+9(c_1+c_2)/2$值为0,那么后手必胜,因为后手能根据先手选择的值x,选择9-x。否则如果值大于0,则先手一开始选9,后手必败,同理小于0,则先手一开始选0,后手必败。

Codeforces 1037G

题意

https://codeforces.com/contest/1037/problem/G

题解

很显然我们要求SG函数,容易想到区间DP的方式,这样的时间复杂度为$O(26n^2)$,是过不了的。

对于每个字符$c$,我们可以预处理出字符$c$出现的位置,以及任意两个相邻出现位置之间区间的$sg$值,记作$A$。同时预处理出上述区间的所有前缀和后缀的$sg$值,记作$P$和$S$。

可以发现要预处理的区间其实和后面的区间查询是相同的逻辑,所以我们可以一并处理掉,这样总共我们要处理$O(53n+m)$个查询。

对于每个区间查询,我们实际上可以选择26个字符中的一个删除,而得到的新的状态的$sg$值可以由分裂得到的所有字符串的$sg$值亦或后得到(可以参考棋子分裂问题)。因此每种操作都对应一次$A$上的区间查询和$P$和$S$上的单次查询。由于查询之间存在依赖关系,但是这些依赖关系时无环的(大的区间的$sg$值仅依赖小的区间的$sg$值),因此可以直接利用记忆化搜索解决这些问题,总的时间复杂度仅为$O(26(53n+m))$。

Codeforces 995D

题意

https://codeforces.com/contest/995/problem/D

题解

我们可以先来考虑另外一个简化的问题,我们从前往后设置参数的每一位,设置每一位的时候,由Allen和Bessie两人中的一个等概率来设置。

可以发现,在设置第$i$位的时候,如果Allen想将第$i$位设置为1,那么Bessie一定想将其设置为0。因此实际上每个参数出现的概率都是$\frac{1}{2^n}$。

现在回到原来问题,原问题中不保证每一位设置的顺序。我们来证明期望还是$\frac{1}{2^n}$。

当$n=1$的时候,显然成立。现在考虑$n$任意的时候,假设Allen先手的时候会选择第$i$位将其设置为1。我们知道如果Allen成功的话,那么最后函数的期望会被修正为所有第$i$位为1的数的平均值(归纳法)。事实上,由于第$i$为1和0的数各自有$2^{n-1}$,因此平均值最大意味着总和最大,后面仅考虑总和最大。而Bessie希望将总和尽可能缩小,而第$i$为1和为0的两个集合的总和之和是固定的,因此总和最大的集合的补集自然是总和最大,因此如果Bessie先手,他同样会设置第$i$位,将其设置为0。因此由于两人先手的概率相同,我们就可以证明函数返回值的期望正好是所有数的平均数。

接下来问题就很简单了。

Codeforces 1215F

题意

https://codeforces.com/contest/1215/problem/F

题解

很好的题目,可以内存限制的太死了,不然我的java就能过了。

在不考虑f的时候,问题就是一个简单的2-sat模板。现在我们考虑f,我们可以通过M个条件唯一确定f,第i个条件对应的逻辑为$f\geq i$。如果找到一个j,满足$f\geq j \land f < j+1$,那么我们可以唯一断定f为j。由于$f\geq i\Rightarrow f\geq i-1$,因此我们还需要增加额外的条件。而对于每个站点的l,r范围,对应的就是$f\geq l$且$f\leq r$,增加两个约束关系即可。

Codeforces 1053D

题意

https://codeforces.com/contest/1053/problem/D

题解

我们可以将$f_i^k$分解成两部分,一部分是非循环部分长度$l_i$,后面是周期部分$t_i$。即对于任意$k\geq l_i$,都有$f_i^k=f_i^{k+t_i}$。因此总共不同的元组数应该为$\max_i l_i+lcm_i(t_i)$。

记$f(x)=ax+b$,那么不难发现:

\[f^k(x)=a^kx+b(a^{k-1}+\ldots+1)\\ =a^kx+b\cdot \frac{a^k-1}{a-1}\\ =a^k(x+\frac{b}{a-1})-\frac{b}{a-1}\]

上面要分三类讨论:

  • 第一类是$a=0$,观察上面公式发现序列为$x,b,b,\ldots$,即$l=1,t=1$。
  • 第二类是$a=1$,可以发现$f^k(x)=x+(k-1)b$,因此$l=0,t=p_i$。
  • 第三类是$a>1$,则有$f^{p-1}(x)=f^0(x)$,即$l=0,t=p_i-1$(这里我们可以让$a$为$p$的某个原根)。

很显然如果所有的$p_i$都不同,它们的乘积就是我们要的结果。否则我们必须特殊处理。

我们可以将所有$p_i$按从大到小的顺序进行处理。之后我们维护最小公倍数的每个素因子的出现次数。当我们处理$p_i$的时候,如果$p_i$已经出现在最小公倍数中,那么我们将其转换为周期$p_i-1$进行处理。

上面的算法仅考虑了第二类和第三类情况,但是没有考虑到第一类情况。由于$\max_i l_i\leq 1$,因此我们只需要判断是否存在一个对所有公倍数素因子都没有贡献的值$p_j$。我们可以通过维护每个公倍数素因子的次数和有几个数对这个次数产生贡献来实现这部分内容。

上面提到的贪心算法的时间复杂度很显然是$O(M\log_2M+n\log_2n)$时间复杂度的。

codeforces 1368E

题意

https://codeforces.com/contest/1368/problem/E

题解

我们将顶点分成三类。如果有第二类前驱顶点,那么这个顶点的类型为3;否则如果有第一类前驱顶点,则这个顶点的类型为2,否则类型为1。

很显然所有顶点都可以划分到上面三类中的某一类。

现在考虑移除所有第3类顶点。由于剩下的边都是从第一类顶点指向第二类顶点的,同时第二类顶点没有出边,因此不存在连续的边。

记$C(i)$表示第$i$类顶点的总数,由于$C(1)\geq \frac{C(2)}{2}$,且$C(2)\geq \frac{C(3)}{2}$,因此一定有$C(1)+C(2)+C(3)=n\geq C(3)(1+\frac{1}{2}+\frac{1}{4})\Rightarrow C(3)\leq \frac{4}{7}n$。