UOJ Logo Isonan的博客

博客

题解

2020-09-12 18:15:26 By Isonan

仅作个人学习用途,如果有地方写的不对请指正,如果写的不清楚我也不会改的/cy

CF623E

题意:对具有下列性质的序列$\{a_n\}$计数: $$ |a|=n \\ 1\le a_i <2^k \\ a_i的前缀或和单调递增 $$ 答案$\mod 10^9+7$。

做法:

首先可以发现条件等价于每个$a_i$都拥有一个之前的数没有的数位。

可以列出生成函数 $$ F=e^x\prod_{i=1}^{n}(e^{2^{i-1}x}-1) $$ 答案即为 $$ k![x^k]F $$ 我们可以ln+exp解决这个问题,但是过于繁琐,而且在任意模数条件下不够优秀。

考虑另一种做法:

令$f_{i,j}$表示$n=i$且$pop(a_n)=j$时的答案,则对于任意$n=a+b$,有如下转移: $$ f_{n,k}=\sum_{j=0}^{k}\binom{k}{j}2^jf_{a,j}f_{b,k-j} $$ 令$F_i$为$f_{i,j}$的EGF,则 $$ F_n(x)=F_a(2x)F_b(x) $$ 这样就可以快速幂/倍增解决了。

CF576E

题意:

给出一张图,初始时每条边都没有颜色。每次询问会尝试将一条边染色,如果染色后会导致出现同色奇环则输出NO,否则输出YES并染色。

做法:

LCT可轻松解决。但这题有高贵的dsu做法。

考虑分治。类似线段树分治的,先预处理出每条边的存在区间。

dfs每个节点,做到叶结点时讨论当前加入的边会不会导致同色奇环,如果会就将(这条边的存在区间,这条边之前的颜色)加入,否则加入(这条边的存在区间,这条边当前的颜色)。

这种半在线的思路很有趣。

loj#140

题意:

最小树形图模板题。

做法:

1.对除根以外的每个点找一条最小入边。

2.如果存在环就缩环。

3.不存在环就结束。

缩环用可并堆维护可以polylog。

CF1307G

题意:

给出一张有向图,q次询问,每次给出$x_i$,求给边加边权,增量和$\le x_i$的情况下$S$到$T$的最短路最长多少。

做法:

也许是最小费用最大流对偶唯一的应用?

考虑最小费用最大流的线性规划式子:

令边$(u,v)$的流量为$x_{u,v}$,费用为$c_{u,v}$,流量上限为$u_{u,v}$,

$b_i$为$i$点的流量和。(只有$x$是变量)

则最小费用最大流即为 $$ min\quad\sum c_{u,v}x_{u,v}\\ s.t. \sum(x_{u,v}-x_{v,u})=b_v\\ 0\le x_{u,v}\le u_{u,v} $$ 对偶后为 $$ max\quad\sum b_vy_v-\sum u_{u,v}z_{u,v} \\ s.t. \quad y_v\le y_u+c_{u,v}+z_{u,v} \\ z_{u,v}\ge 0 $$ 如果我们令$u_{u,v}=0,b_S=-F,b_T=F$,则跑一遍最小费用最大流等价于求 $$ max\quad FD-C $$ 其中$D$为$y_T-y_S$,可以发现就是$S$到$T$的最短路。$C$就是增量和。

考察最小费用最大流的算法,发现我们只需在每次增广以后记录$(F,max\{FD-C\})$即可。

求答案时,我们硬点当前的$F$,并假装最优解的$C$就是$x_i$。

由于这里是一个最大化问题,当最优解不是$(D_i,x_i)$时,答案的$D$只会变大,即: $$ FD_i-x_i\le FD_{ans}-x_i \\ D_{ans}\ge D_i \\ $$ 那么我们的答案即为 $$ \min_{F}{{max_F+x_i\over F}} $$

CF1007E

题意:

有一排$n$个车站,每个车站初始时有$a_i$人,每天会增加$b_i$人,人数上限$c_i$。

每次你发一辆车,车会从$1$号站开始,选择最靠前的$K$个人运走(也就是在之前的车站还有人时不会运后面车站的人)。

求最少发几辆车能使得最后每个车站都不爆。

题解:

这题的主要难度应该在设计DP。

首先很容易可以发现应当枚举最后一个车站的人最后一次被运走的时间,在那之后就不用考虑这个车站了。

这就相当于我们有两种问题:一种开始时第$i$个车站有$a_i$人,一种开始时没有人。

但是每次贪心的运人不是最优的。

于是我们在dp时附加一个限制:每辆车必须运满$K$个人,不然不许走。

这样就不存在溢出的问题了。(当然需要在最后加一堆假人)。

mu2020-1 1002

题意:

有若干件活,每件活可以在$t_i$时间以后开干,并需要连续$d_i$的时间干完。设计干活顺序,最小化每件活的等待时间的最大值。

做法:

和上题一样,问题仍然在于设计DP。

首先显然的二分,然后如果我们从前往后DP的话,容易发现DP式子跟屎一样。

我们先发掘一些性质。

令$x_i$表示开始干活$i$的时间。

首先可以发现,不存在三件活$i,j,k$满足$t_ix_k,t_jx_k$。

证明:

首先可以发现$k$的限制没有意义,只要$i$没事,它也没事。(引理1)

在这样的情况下,首先让$t$小的先做肯定对后面是优的,其次这样更能减少$j$的等待时间。

我们考虑定义$f_i$为从$i$开始的后缀的最晚开始时间。

那我们肯定要枚举一个$k$,使得操作序列的前缀形如$i+1,i+2,\dots,k-1,i$。

此时$f_i$应更新为 $$ min(f_k,t_i+d_i+mid)-sumD[i,k-1] $$ 通过引理1可得,只要我们保证$i$没有问题,$[i+1,k-1]$中的活也不会有问题,只要满足$x_j\ge t_j$即可。

所以如果能满足,则式子就长这样。如果不能满足,也无法调整。

接下来还有一个结论:

如果$t_ix_j$,则一定有$t_i+d_i>t_j+d_j$。

容易证明,反之将两者的位置调换不会更劣。

通过此可以说明有用的转移状态数是$O(n)$的。

EZOI20200803T2

题意:给出两个长度为$n$的排列$p,q$,定义一个排列$r$的权值为$\sum_{i=1}^{n}[p_i=r \vee q_i=r]$,分别求权值为$0\dots n$的排列数。

题解:

我们先连接所有的$p_i,q_i$。一个$r_i$可以抽象为一个点。

可以发现问题一定要二项式反演解决。

如果我们硬点图中的一个环要被选,则方案数为$2$。

否则如果硬点一条链,则这条链的方案数为$len$。

考虑一些环排列的问题,在一个长度为$C$的环上硬点$C-j$条边被选的方案数是 $$ F_{C,j}=(j-1)!C[x^Cy^j]e^{(\sum_{i=1}^{\infty}x^ii)y} $$ 简单展开可得 $$ F_{C,j}=(j-1)!C[x^Cy^j]\sum_{k=0}^{\infty}{((\sum_{i=1}^{\infty}x^ii)y)^k\over k!} \\ =(j-1)!C[x^C]{(\sum_{i=1}^{\infty}x^ii)^j\over j!} \\ ={C[x^C]({x\over (1-x)^2})^j\over j} \\ ={C[x^{C-j}]{1\over (1-x)^{2j}}\over j} \\ ={C\binom{C+j-1}{C-j}\over j} $$ 算完把每个环的答案卷起来就好了。

CF932G&CF906E

题意:

给出一个字符串,求把它划分成若干回文串的方案数/最小数量。

做法:

定义$f_i$为$[1..i]$的答案,$g_i$为上一次$i$为某个前缀的某组回文后缀等差数列的开头时的答案,$diff_i=len_i-len_{fa_i}$,$an_i$为$i$的祖先中第一个$diff$不同的。

可以发现,每当我们枚举当前$i$的一组回文后缀等差数列时,转移有两种形式:

  • 转移来自这组串的最短串,可以$O(1)$枚举,该串的长度为$len_{an_j}+diff_j$,其中$j$是这组串开头(最长串)
  • 转移来自其他串,在$g_{fa_j}$处已经枚举过了。

一边做过去一边更新$f_i$和$g_i$。

CF713E

题意:

环上给出若干个点,每个点可以选择顺/逆时针遍历,求把环遍历完的最小时间。

做法:

首先肯定考虑二分,问题变成每个点向左或向右延伸x段,能否覆盖整个环。

讨论第一段的方向,然后可以定义$f_i$表示已确定了$1\dots i$中的点延伸的方向,已覆盖了$1\dots i$的所有位置,最多能往反方向延伸多少($m-f_i+1\dots m$)。

可以讨论接下来第一个往左延伸的点是哪个。容易发现这个点必定是距$i$最近或次近的点。如果是次近的点,则需要更新最近的点往右延伸最远能延伸到哪里。这里如果该点覆盖的范围内有一个点,则它的延伸范围也包括在内,以此类推。

CF1209H

题意:

在一条数轴上走路,每个位置有一个初始速度$v$,你可以花费$x\in[-1,1]$的能量,以$x+v+1$的速度行走。求在任意时刻消耗能量总和$\ge 0$的情况下,最少花多少时间可以走完。

做法:

可以发现,如果花费$x$的能量在一段初始速度为$v$的路径上,所用的时间一定为$(l-x)\over v$。

我们显然要把更多的能量放在$v$小的位置上。所以可以把段按照$v$排序,线段树进行处理。

CF526G

题意:

给一棵带边权的树,q次询问,每次给出$x,y$,求包含点$x$,能被不超过$y$条链覆盖的连通块的最大权值。

做法:

容易发现$y$的限制条件实际上就是限制连通块中叶结点个数$\le 2y$。

进一步的,可以发现对于任意一条直径,一种最优方案肯定包含其一个端点(实际上是从中间劈开后,一定包含其中一段,但取其他点不好讨论),所以可以取直径的两个端点作为根,问题就变成了:求一个包含根和$x$、叶结点个数$\le 2y-1$的连通块的最大权值。

令$S_i$表示包含根与$i$个叶结点的权值最大的连通块。可以说明,$S_{i-1}\subset S_i$。

如果$x\in S_{2y-1}$,直接输出$val(S_{2y-1})$即可。

否则我们的答案肯定是由$S_{2y-1}$删去一个叶节点,再加上$x$子树中最深叶节点(称为$leaf(x)$)得到的。

如果删去一个叶节点后不会影响$x$到根路径上的权值,则答案就是$S_{2y-2}\cup{leaf(x)}$。

如果会的话,这个叶节点必然是最深的叶节点,找到它然后讨论即可。

CF878E

题意:

给一个序列,每次你可以取两个相邻的数$x,y$,删除这两个数并加入$x+2y$。你需要使得最后剩下的数尽量大。

多次询问取原序列的一个区间出来操作的答案。

做法:

可以发现合法的值形如$\sum_{i=1}^{n}a_i2^{d_i},d_1=0,1\le d_i\le d_{i-1}+1(i>1)$。

讨论当前序列的末尾,如果是负数则$d_x=1$,否则$d_x=d_{x-1}+1$。

那么可以离线推右端点,一个一个合并。

CF639F

过于简单,不写

CF607E

题意:

给出$n$条直线,求其两两交点中到$p$距离前$m$小的点到$p$的距离和。$m\le 3e7$

做法:

可以二分距离排名为$m$的点的距离。做一个圆心为$p$,半径为$mid$的圆。

两条直线在距$p\space mid$的距离内相交当且仅当他们与圆的交弧相交。可以直接计算。

算完暴力就好了。

CF986F

同余bfs+特判两个质数

CF718E

题意:

给出$a_i$,建一张图,两个点之间有边当且仅当他们相邻或$a_i$相同。求直径与距离$=$直径的点对个数。

$1\le a_i\le 8$

做法:

令$dist_{i,j}$表示从$i$到任意一个$a_k=j$的$k$的最短距离。可以发现$dist_{i,j}$极差$\le 1$。

那么可以状压每个点解决。

CF865E

题意:

给出一个16进制下的数字$c$,求两个数字$a,b$使得:

  • $a$为$b$在16进制下重排得到。
  • $a-b=c$

求出最小的$b$。

做法:

我们可以枚举进位,得到一组合法的$d_i=b_i-a_i$。容易发现合法的$d_i$最多只有$\binom{13}{6}$种。

有一个结论:答案数位中一定有一个$0$。这是因为如果没有,全部$-1$只会更小。

那么我们可以讨论某一个0的位置,状压计算。

可以发现假设我们已选的位置$\sum{d_i}=x$,新加入一个位置后$b$在这一位上的值就是$x$。

那么就可以直接dp了。

CF704E

题意:

一棵树上有若干人在走,第$i$个人会从$t$时刻出现,以$c$的速度从$u$走到$v$,求第一次有人相撞的时间。

做法:

把路径轻重链剖分,问题变成链上求解。

可以发现由于是求第一次相撞,在这之前人的相对顺序是不会变的。可以用DS维护当前时刻在走的人,每次加入/删除时用新增的相邻人对更新答案。

CF983D

题意:

平面上每次画一个矩形,求最后有多少个矩形能被看到。

做法:

扫描线,每个时刻取出编号最大的能被看到的矩形更新答案。

CF1172E

题意:

给出一棵树,点有颜色。询问$\sum路径上不同颜色数$,多次修改单点颜色。

做法:

考虑计算一种颜色$c$的贡献,就是$n^2-不包含该颜色的路径数$,后者也就是去掉该颜色的点后每个$\sum连通块大小^2$。

可以用$LCT$维护,每个颜色不是$c$的点向父亲连边,父亲处计算若干连通块的权值和。

CF1148G

题意:

给出若干数,求一个大小为$k$的集合使得:

  • 所有数两两不互质,或
  • 所有数都有至少一个数与他互质。

$2k\le n$

做法:

先取出三个数使得有一个数与另两个互质。

如果没有,则每个数都只与一个数互质,可以哈希找到这个数,然后简单处理。

接下来取出和剩余$n-4$个点都不互质的点,如果$\ge k$可以直接出解。

否则:

对于$1\dots c$的前缀,令$f(c)$表示其中与前缀中至少一个数不互质的数的个数。

二分一个$c$使得$f(c)+3

通过调整可以得到答案。

CF1054G

题意:

给出若干集合,构造一棵树使得这些集合在树上均为连通块,或报告不可能。

做法:

可以发现对于一个叶子,所有包含它且$sz>1$的集合都包含它的父亲。

可以每次找一个可以成为叶子的点,将其删去,并更新包含它的集合的大小。

CF1172F

题意:

见1.png.

多次询问某个区间的答案。

做法:

考虑$f(x,l,r)$表示$x$经过$[l,r]$后变成的数。这个函数关于$x$成最多$r-l+2$段,且每一段长度至少为$p$。

令$g(y,l,r)$表示一个最小的$x$使得$f(x,l,r)=x+S[l\dots r]-yp$,可以维护出这个函数。

CF696F

题意:

给一个凸多边形,找出两个半径相同,圆心均在凸多边形中的圆,使得他们与每一条棱所在的直线有交。

做法:

二分半径,每个圆覆盖一个区间,半平面交。

CF1292F

题意:

你有若干$\le 60$的正整数,每次可以找出三个数$i,j,k$,使得$a_i|a_j,a_i|a_k$,并删除$k$。

求有多少种最长的删除序列。

做法:

整除关系构成一个偏序集。

可以发现,在每个弱连通块中,我们一定能删掉$(总数-极大元-1)$个数。

找出极大元,可以发现一个弱连通块中极大元个数不太多。接下来枚举会更新包含的极大元集合的数,状压DP即可。

CF1368H

题意:

给一个网格图,边界上每个点连向源点或者汇点,求最大流。

做法: 最大流=最小割。

可以发现最优方案形如在边界处直接把一个点割掉+横着切掉一些行或纵切掉一些列。

CF1329E

题意:

长度为$n$的序列上已有若干个位置被染色,再染$k$个位置使得极长未染色段长度的极差尽量小。

做法:

对于一个长度为$l$的极长未染色段,使其中所有数都在$[L,R]$范围内的条件是(假设染$k$个位置) $$ L(k+1)+k\le a_i\le R(k+1)+k $$ 即 $$ \lceil {a_i-R\over R+1} \rceil \le k\le \lfloor {a_i-L\over L+1}\rfloor $$ 可以发现$L$与$R$的限制是分开的,那么我们可以对其分别二分求得上/下界。

现在的问题是可能会出现 $$ \lceil {a_i-R\over R+1} \rceil > \lfloor {a_i-L\over L+1}\rfloor $$ 的情况。由于$L_{max}\le R_{min}$,可以发现上式两者之差最多为1,所以最优方案必然是调整$L$或$R$使得上式成立。

讨论即可。

CF1284G

题意:

网格图中有一些点不能使用,把其他点连成一棵树使得$(i+j)\equiv 1 \mod 2$的点均不是叶子。构造方案。

做法:

首先拟阵存在对偶性质。可以发现,一个拟阵的补集与其极大元集合的并仍然是一个拟阵

那么我们可以定义两个拟阵:补图是连通图的图以及补图偶点度数均$>1$的图。

拟阵交即可。

CF737E

题意:

有若干小朋友要玩游戏机,每个种类的游戏机有两台,一台免费,一台付费后可以永久开放。每个小朋友需要在每种游戏机上玩一定的时间,每个时刻一台游戏机只能有一个小朋友玩,且一个小朋友只能玩一台游戏机。你有一些钱,求所有小朋友玩完的最少时间,并构造一组解。

做法:

首先可以发现,k-正则图一定存在完美匹配(无论重边)。

证明是显然的。

我们可以从每个小朋友向每个机器连边,增加一些假小朋友和一些假机器,将其补成一个k-正则图,那么就必定有解。

构造解时,可以先跑一个匹配,然后一直走这个匹配直到有边流量为0,这样跑匹配次数时$O(边数)$的。

CF1392I

题意:

有一个$n\times m$的网格,$(i,j)$的权值($w_{i,j}$)为$a_i+b_j$,两个点$u,v$之间有边当且仅当$[w_u\ge x]=[w_v\ge x]$。如果一个点权值$\ge x$我们认为这个点是好的。定义一个连通块的权值为$2-[与边界相连]$。求好的连通块的权值-坏的连通块的权值。

做法:

我逆向工程但我是一道好题

这题唯一可取的思路就是 对于平面图,点数+边数-面数=联通块数。

然后可以发现一张图的一个非平凡面对应补图中一个与边界不相连的连通块。

评论

暂无评论

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。