Luogu练习

Published: by Creative Commons Licence

  • Tags:

LUOGU2371

题意

https://www.luogu.org/problem/P2371

题解

神奇的题目,很显然DP是不可能的,暴力也是不可能的。

真正的解法,是从${a_i}$选取任意一个数,记作k。之后我们建立k个顶点,分别代表模k时余数为$0,1,\ldots,k-1$。

之后对于顶点$i$和数$a_j$,我们建立边$(i,(i+a_j)\mod k)$。之后我们寻找以顶点0为起点的单源最短路径。

对于数x,记$r=x\mod k$,如果顶点r距离顶点0的最短距离为d,那么根据d与x的大小关系,我们可以快速判断出是否能找到一组非负整数解${x_i}$,使的$\sum_ia_ix_i=x$。如果$d<x$,不存在解,如果$d\geq x$,那么就有解。

LUOGU4292

题意

https://www.luogu.org/problem/P4292

题解

先用分数规划将问题转换为二分+长链剖分。

由于允许的路径边数是范围,所以需要用线段树维护。时间复杂度为$O(n(\log_2n)^2)$。

LUOGU4220

题意

https://www.luogu.org/problem/P4220

题解

我们先理解题目要我们求的到底是个啥,定义$dist(i,j)=dist_1(i,j)+dist_2(i,j)+dist_3(i,j)$,其中$dist_k(i,j)$表示在第k树中i、j的距离。可以进行简化:

\[\max\quad dist(i,j)=\sum_{k=1}^3dist_k(i,j)=\sum_{k=1}^3depth_k(i)+depth_k(j)-2\cdot depth_k(L_k(i,j))\]

这里$depth_k(i)$表示的是i在第k颗树中的深度,$L_k(i,j)$表示i、j在第k个树中的LCA。我们记$depth(i)=depth_1(i)+depth_2(i)+depth_3(i)$,之后公式为:

\[\max\quad dist(i,j)=depth(i)+depth(j)-2depth_1(L_1(i,j))-2depth_2(L_2(i,j))-2depth_3(L_3(i,j))\]

利用边分治处理第一颗树,删除边重心后,得到两个连通块,包含根的记作A,不含根的记作B。将A中顶点全部染成白色,B中染成黑色,记边的。记录$w_A(i)=depth(i)-2depth_1(L_1(i,B))$,$w_B(i)=depth(i)$。之后为这些点按照第二颗树的结构建立虚树。现在我们要求的是:

\[\max \quad dist(i,j)=w_A(i)+w_B(j)-2depth_2(L_2(i,j))-2depth_3(L_3(i,j))\]

在虚数上处理第t个顶点时,由于LCA一定是t,因此可以认为$2depth_2(L_2(i,j))$是常数。此时我们要计算的是

\[\max \quad dist'(i,j)=w_A(i)+w_B(j)-2depth_3(L_3(i,j))\]

这里需要用到一个在树上所有边非负的时候成立的命题。

命题1:如果树上边权非负,对于两个顶点集合A、B,设A中最远点对为$a_1,a_2$,而B中最远点对为$b_1,b_2$,那么在A、B合并后,其中最远点对一定可以从${a_1,a_2,b_1,b_2}$中得到。

我们可以继续扩展这个命题得到:

命题2:如果树上边权非负,并定义树上距离为路径距离加上两点的点权,对于两个顶点集合A、B,设A中最远点对为$a_1,a_2$,而B中最远点对为$b_1,b_2$,那么在A、B合并后,其中最远点对一定可以从${a_1,a_2,b_1,b_2}$中得到。

转换公式令其得到符合命题2:

\[\max \quad dist'(i,j)=(w_A(i)-depth_3(i))+(w_B(j)-depth_3(j))+dist_3(i,j)\]

因此在递归处理虚树的同时维护子树dist'最大的白点对、黑点对,在向上贡献的时候合并到父结点的信息中。

LUOGU4565

题意

https://www.luogu.org/problem/P4565

题解

首先用边分治将树1分为两块,包含根的记作R,不含根的记作B。给R中顶点上黑色,B中顶点上白色,之后根据树2建立虚树。

记一个顶点x在树中到树根的路径的总边权记作prefix(x),记B中深度最浅的顶点为y。

那么黑色顶点a的点权为:weight(a)=prefix(a)-prefix(lca(a, y))

白色顶点b的点权为:weight(b)=prefix(b)

建立好虚树后,我们要找到虚树上距离最远的一对黑白点,其中虚树中a,b距离的定义为:$weight(a)+weight(b)-weight(lca(a,b))$。这个问题dfs就能解决了。

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

LUOGU4152

题意

https://www.luogu.org/problem/P4151

题解

好题。

首先我们考虑两条不同的从1到n的路径。将两条路径进行亦或操作(公共路径去除,非公共路径保留),我们一定得到若干个环。这也预示着任何从1到n的路径,都可以通过任选一条从1到n的路径后,并亦或上一些环得到。

因此,我们可以找到所有的环,并用线性基处理。之后我们取得任意一条从1到n的路径之后,计算线性基能提供的最大亦或和即可。

要寻找所有的环,我们实际上只需要找到简单环即可,即没有重复边的环,其它环都可以通过这些环的亦或操作得到。我们可以通过LCT维护生成树,之后一旦新加的边构成了环,就不加入该边同时将环的亦或和加入到线性基中。

LUOGU4137

题目

https://www.luogu.org/problemnew/show/P4137

题解

有两种做法。

第一种莫队,但是使用块状链表维护每个出现的数,这样每次查询mex只需要$O(\sqrt{n})$的时间复杂度。总的时间复杂度为$O(n\sqrt{n})$

第二种线段树。首先将数据离散化,之后按照请求的右边界从小到大排序请求。之后从左往右遍历数组,遍历到第i个元素的时候,将$a_i$在线段树中的值更新为i。这样我们要查询mex,只需要查询第一个值小于查询左边界的数。这种方法的时间复杂度为$O(n\log_2n)$

LUOGU3431

题目

https://www.luogu.org/problemnew/show/P3431

题解

首先可以知道抵达点$(i,j)$之前,上一次接客一定发生在点$(x,y)$,其中$(x,y)$落在由$(0,0)$和$(i,j)$确定的矩形中。

现在要计算k个点的最优值,我们可以认为是k次查询。只是查询之间有拓扑关系。我们可以将离线处理查询,将查询按照y值排序,之后用线段树维护x轴。每处理一次请求(a,b),只需要查询线段树中处于区间[0,a]之间的最大值,之后将查询结果一同更新到线段树中去。

LUOGU3332

题目

https://www.luogu.org/problemnew/show/P3332

题解

一开始看错题目了,以为是为区间中每个数增大c,始终想不出解法。后来发现原来是往区间每个下标放入一个数c。

怎么解决呢。我们发现每个数都有两个属性,所在的下标,以及它的值,记作(i,v)。由于是二维向量,我们将其绘制在二维坐标系中。每次查询操作都对应查询某个矩形中第k高的点,我们可以借助二分来猜测该点的高度。

到此容易想到用二维线段树来维护。由于预先开点需要消耗过多内存,因此可以改成动态开点。但是修改操作呢,该如何实现。我们可以调整线段树的含义,外部的线段树表示的是权值线段树,内部的线段树表示的是区间线段树,这样修改操作对于外部来说仅更新了一个点,是不需要打标记的,而内部线段树一次性更新了一段区间,是需要打标记的。

之后由于我们查询操作是之前是通过二分来做的,但是在我们将外部线段树改成权值线段树后,可以发现外部线段树的每次查询也带有二分操作,因此我们就不需要二分了,直接在外部线段树上进行二分。

总的时间复杂度为$O(m(\log_2n)^2)$,空间复杂度和时间复杂度一致。

LUOGU2839

题意

https://www.luogu.org/problem/P2839

题解

题目的数据范围使用int就足够了,题目中序列的意思是连续的一段区间。

要给数x是区间[l,r]的中位数,当且仅当在区间[l,r]中大于等于x的数占了至少半成。

对于每个询问a,b,c,d,我们可以二分中位数x。当x确认时,我们希望判断中位数是否大于等于x,可以通过下面流程得到:我们将数组中所有大于等于x的数替换为1,其它数我们替换为0,这样如果我们找到了一个区间[l,r],其中l落在[a,b]中,r落在[c,d]中,区间中数字的和大于等于0,那么我们可以断定中位数至少为x。

现在我们考虑如何快速判断这样的子区间[l,r]是否存在,由于[b+1,c-1]是无论如何都需要统计的,而[a,b]中只需要统计一个非空后缀,[c,d]则只需要统计一个非空前缀。容易想到这是个动态规划问题,但是由于询问无法预先处理,因此我们需要做的实际是要利用线段树上合并动态规划实现动态询问。

我们可以为每个值域中的数建立一个线段树,这里我们需要建立的是持久化线段树,否则空间会不足。每个数组中的元素,随着x的增大,会从1变为0,因此每个元素对应两次插入操作,建树的时空复杂度为$O(n\log_2n)$。

回答询问q次,由于使用二分,因此发生了$q\log_2m$次的询问(m是值域的大小),每次询问由线段树处理,总的实际复杂度为$O(q\log_2m\log_2n)$。

LUOGU4463

题意

https://www.luogu.org/problem/P4463

题解

很容易想到DP,定义$f(i,j)$表示从[1,i]中选择j个不同数的所有序列的累乘的和。从而推出:

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

但是由于a的范围过大,使得DP不可行。

神奇的是$f(i,j)=p(j)(i)$,其中p(j)是仅关联于j的多项式。当$j=0$时,$p(j)=1$。注意到对于一个n阶多项式g,能够保证$g(x)-g(x-1)$一定是$n-1$阶多项式。

\[f(i,j)-f(i-1,j)=i\cdot f(i-1,j-1)\\ \Rightarrow p(j)(i)-p(j)(i-1)=i\cdot p(j-1)(i-1)\\ \Rightarrow |p(j)|-1=|p(j-1)|+1\\ \Rightarrow |p(j)| = 2j\]

由于$p(n)$的阶数是$2n$,因此我们利用$2n+1$个点就可以确认$p(n)$。随便算出$2n+1$个点,用拉格朗日公式插值出最终结果就行了。时间复杂度为$O(n^2)$。

LUOGU1728

题意

https://www.luogu.org/problem/P1728

题解

假如这个问题没有限制可以选择的技能数,那么实际上问题就可以转换成最大权闭合子图问题。但是很可惜并不是。

4 5
1 1 1 1
1 2 1
1 1
1

注意到每个数可以选择仅要求其上方和右上方的两个数被选择过即可。

假如我们从右往左处理(即先处理第n列,最后处理第1列),那么就非常简单了。

记$f(i,j,k)$表示第$i$列所有行号小于等于$j$行的数字都被选中,并且总共选择了$k$个数的最大选择值总和。

这样得出的递推关系为: \(f(i,j,k)=\max(f(i+1,j-1,k-j)+\sum_{t=1}^jgrid[t][i],f(i,j+1,k))\)

最终结果为$f(1,0,m)$。

LUOGU1285

题意

https://www.luogu.org/problem/P1285

题解

看上去问题是要将图划分为两个团,使得团的差距尽可能小。看上去是个2-SAT问题,但是由于需要求尽可能平均,2-SAT是做不到的。

容易发现,找团是不容易的,但是如果a不认识b,那么我们会得到一个重要的性质,a、b必定处于不同的组。因此我们在不彼此认识的人之间加上一条边。

对于一个连通分量,其黑白染色要么不存在,要么只有两种可能性。对每个图上的连通分量染色后,计算每个连通分量的黑色顶点数和白色顶点数。

之后我们需要才从每个连通分量,要么选择全部黑色顶点加入组1,要么选择全部白色顶点加入组2。这实际上就是一个普通的DP问题了。

记 \(DP(i,j)\) 表示考虑前i个连通分量,是否可能正好选择j个人加入到组1中。之后就是DP了。

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

LUOGU5419

题意

https://www.lydsy.com/JudgeOnline/problem.php?id=5419

题解

首先题目上已经给出了最短上升路径的下界,n-1。下面就需要我们构建这样一个可能的完全图。

如果我们能将n(n-1)/2条边均分为n个不相交子集,每个子集大小为(n-1)/2,且相同子集中的边不共享端点。这样我们为相同的子集中的边分配连续的权重,就能保证每次移动都会经过不同子集中的边,从而保证最多移动n-1次,即最长上升路径的长度为n-1。

下面我们考虑分组的策略。

考虑n是奇数的情况,首先我们建立一个顶点序列[1,2,…,n],之后我们构建第一个子集,加入边(2,n),(3,n-1)…之后我们旋转序列一个单位,得到[n,1,2,…,n-1],之后用类似的方法构建第二个子集,加入边(1,n-1),(2,n-2)…。重复上面过程直到构建了n个子集。可以证明每个子集的大小都是(n-1)/2,且子集中的边无公共端点。接着考虑顶点u,v。由于u、v在序列中的距离一端为奇数,一端为偶数,边(u,v)被处理仅在u、v为奇数一端的中间顶点作为序列起点的时候才会发生,且仅发生一次。这样我们就得到了n个满足条件的大小为(n-1)/2的分组了。

现在考虑n是偶数的情况,先处理1~n-1顶点(奇数个顶点),得到n-1个满足条件的大小为n/2-1的分组后,考虑每个分组,向分组中加入缺少的那个顶点和顶点n组成的边之后,我们就得到了n-1个满足条件的大小为n/2的分组。

LUOGU1729

题意

https://www.luogu.org/problem/P1792

题解

神奇脑回路题。

维护一个双端链表表示环,每次从双端链表中取权重最大的顶点(用堆优化),同时移除它的前驱和后继。

假设被移除的顶点为y,y的前驱为x,后继为z。那么我们能保证必定存在一个最优方案S,其要么包含y,要么同时包含x和z。先假设S不包含x、y、z,那么我们知道S中一定有权重比y小的顶点,我们将其替换为y可以得到更大的总权,因此不可能。若y出现,那么很显然x、z一定不出现与S,下面考虑y不出现的情况。由之前的证明知道x、z至少出现一个,假如仅出现一个,那么可以直接将出现的那个替换为y得到更优解,因此x、z一定成对出现。

考虑到上面提到的内容,我们已经处理了y出现的情况,但是并没有考虑x与z同时出现的情况。我们可以将x、y同时出现的情况作为一个新的结点w替换x、y、z,同时w的权值为x-y+z(因为我们弹出y时已经加上了y的权值,这里换成x、z同时出现的策略,那么总权需要先减去y之后加上x+z)。

LUOGU3620

题意

https://www.luogu.org/problem/P3620

题解

同LUOGU1729。

很显然最终结果中电线只会连接相邻的大楼。

首先我们可以将电线视作点,那么问题就变成了给出若干个带权的点组成的链表,允许选取k个不相邻的点,问最小可能总权值。

我们可以加入一条权值为无穷的点,这个点连接链表的头尾,这样就形成了环。之后就和LUOGU1729一致了。

LUOGU4131

题意

https://www.luogu.org/problem/P4131

题解

首先因为$a|b-c|=|ab-ac|$,所以可以将$C_i$直接乘到对应的属性里。

接下来考虑到$|x-y|\geq x-y$,因此我们可以直接暴力枚举前k-1个属性的符号,来获得前k-1个属性和的上界。

但是第k个属性的符号是负数,而我们没有技术可以枚举其上界怎么办?我们注意到存在遍历顺序,我们可以提前将生物按照第k个属性排序后,按序逐一处理生物,这样就能直接使用减法而不用考虑绝对值问题了。

LUOGU4528

题意

https://www.luogu.org/problem/P4528

题解

观察公式:

\[f(1324)-f(1243)-f(1432)\\ =(f(1x2x)-f(1423))-f(1432)-f(1243)\\ =f(1x2x)-f(14xx)-f(12xx)+f(1234)\\ =f(1x2x)-f(1xxx)+f(13xx)+f(1234)\]

最后得出的就是我们要算的。

  • f(1x2x),考虑将第i个值作为2,难点在左边元素的计数,首先统计i左边的小于$y_i$的数的数目c,并统计这些数的下标和s,左边的序列数目应该为$c(i-1)-s-{c \choose 2}$。
  • f(1xxx),非常简单
  • f(13xx),考虑价格第i个值作为3,4的可选值为i右边大于$y_i$的数的数目。现在仅考虑2对应的值,我们需要统计形如$a<i<b,y_a < y_b < i$的数对数目,这个用线段树可以完成,只需要注意到每当i自增1时,实际上带来的影响可以通过线段树批量操作快速完成。
  • f(1234),这个就是一般的统计长度为4的递增序列问题。用线段树统计即可。

LUOGU4643

题意

https://www.luogu.org/problem/P4643

题解

将边权平摊到顶点上,之后统计的时候能保证二者的差值不变。

LUOGU4298

题意

https://www.luogu.org/problem/P4298

题解

首先要理解问题要我们求的是有向无环图的最大独立集。我们将单向边视作偏序关系,那么我们可以将求最大独立集理解为求反链。

利用Dilworth定理得知求反链实际上求的就是最小链覆盖,而最小链覆盖实际上就是最小相交路径覆盖。

LUOGU1263

题意

https://www.luogu.org/problem/P1263

题解

比较典型的二分图问题了。

考虑同一行,如果中间有墙隔开,那么我们可以将其拆做两行也不会影响结果。用这种方法我们只给连续的处于同一行的空地(包括陷阱)分配唯一的行号,同理对于连续的处于同一列的空地分配唯一的列号。我们知道每一列最多只能放一个守卫,而每一行也最多只能放一个守卫。建立一副二分图,左边的顶点代表行,右边的顶点代表列,我们将每个空地(行列编号为i、j)当做一条连接左边顶点i和右边顶点j的边加入到二分图中。

这样我们希望尽可能多的守卫被放置,等价于取得二分图最大匹配。

LUOGU3980

题意

https://www.luogu.com.cn/problem/P3980

题解

这道题可以用线性规划解决,但是由于内存不够,因此会MLE。下面讲一种线性内存的费用流做法。

我们可以将费用流中的流理解为工作,而将管道理解为处理工作的工人。那么管道中的流量就等价于工人的工作量。而每一天要求的最少人数就等于当天工作量的峰值。当工作量峰值突然增大的时候,我们就需要招聘更多的短工来完成工作。由于峰值的存在是因为人手不足,那么我们就可以将峰值理解为有一部分长期工人请假回家了,所以导致了峰值。

好了,清楚了这些,我们来讲一下怎么建图。

我们为每一天建立一个顶点,从第$i$天到$i+1$天连一个管道,管道的费用为0,容量为$\inf-A_i$。这代表当天有$A_i$个员工请假回家,对应我们也要招$A_i$个短工来弥补。之后对于每个志愿者$i$,我们从第$s_i$天连一条费用为$c_i$,容量为$\inf$的管道到$t_i+1$天,表示从第$s_i$天开始可以花$c_i$来找短工工作到$t_i$天。

这样由于我们可以请到足够的短工来完成工作,因此最大流一定为$\inf$,而最小费用就是请短工花的最少的钱。

LUOGU2893

题意

https://www.luogu.com.cn/problem/P2893

解法

首先我们可以将问题看做是找到一种方案使得序列递增,且费用最小。如果转换为递减序列费用更低的话,我们只需要将序列倒序后重新调用流程就可以了。

剩下就是玄学建图。我们将每段路都映射为网络流中的两个顶点,第i段路,对应两个顶点$L_i$,$R_i$。我们如何保证第i个路的海拔一定不高于第i+1个呢?我们从源点向$L_i$连流量为A[i]费用为0的边,从$R_{i+1}$向汇点连流量为A[i+1]费用为0的边,同时我们从$L_i$向$R_{i+1}$连一条容量为A[i],费用为0的路径。这样要做到最大流必定会导致流经$R_{i+1}$的流超过A[i]。

那么我们可以增大一条路的海拔又怎么实现呢,我们从$R_i$到$L_i$连容量为无穷费用为1的边。而至于减少一条路的海拔,我们可以从$L_i$到$R_i$连容量为A[i]费用为1的边。

最后$R_1$和$L_N$需要与汇点相连。

跑出最小费用最大流后,最小费用就是结果。

看了其他人题解才发现动态规划才是正解。。但是这种做法可以在不同路径的海拔的减少和增加费用不同的情况下依旧有效。

LUOGU3175

题意

https://www.luogu.org/problem/P3175

题解

对于一次实验,记录$X_i$表示第i为第一次变作1的时间。记$X=(X_1,X_2,\ldots, X_n)$,那么实际上数字变作$2^n-1$的时间实际上是 \(\max\{X\}\) 。但是要计算这东西不太容易,我们用min-max容斥将问题转换为下面形式:

\[\max\{X\}=\sum_{T\subseteq X}(-1)^{|T|+1}\min\{T\}\]

其中 \(\min\{T\}\) 指的是T指代的二进制集合第一次改变的时间。之后利用期望的线性性质:

\[E[\max\{X\}]\\ =E[\sum_{T\subseteq X}(-1)^{|T|+1}\min\{T\}]\\ =\sum_{T\subseteq X}(-1)^{|T|+1}E[\min\{T\}]\]

其中 \(E[\min\{T\}]\) 的计算方式如下,首先设T代表的二进制掩码为m,那么这相当于问在若干次投掷硬币实验中,每次正面概率为p,求第一次投掷出硬币的期望次数。这是几何分布,因此期望时间为$1/p$。

下面考虑p该如何计算,要计算p,我们通过计算$q=1-p$得到。q等于所有$2^n-1-m$子集的概率之和。而什么时候无解呢,假如某个二进制的所有超级的概率之和为0,则无解。

这边计算子集和,超级和可以通过FWT算法得到。

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

LUOGU4827

题意

https://www.luogu.org/problem/P4827

题解

对于点x,我们推一下它的指标:

\[f(x)=\sum_{i=1}^ndist(x,i)^k\]

带入第二类斯特林数公式:

\[x^n = \sum_{k=0}^n \begin{Bmatrix} n\\ k \end{Bmatrix} x^{\underline{k}}\]

得到:

\[f(x)=\sum_{i=1}^n \sum_{j=0}^k \begin{Bmatrix} k\\ j \end{Bmatrix} dist(x,i)^{\underline{j}}\\ =\sum_{i=1}^n \sum_{j=0}^k \begin{Bmatrix} k\\ j \end{Bmatrix} {dist(x,i)\choose j}j! \\ =\sum_{j=0}^k \begin{Bmatrix} k\\ j \end{Bmatrix} j! \sum_{i=1}^n {dist(x,i)\choose j}\]

为了计算上式,我们记

\[down(x,j)=\sum_{i\in T(x)} {dist(x,i)\choose j}\\ up(x,j)=\sum_{i\notin T(x)} {dist(x,i)\choose j}\\\]

其中$T(x)$表示以x为根的子树中的所有顶点组成的集合。记$C(x)$表示x的所有直接的子结点。下面继续推导:

\[down(x,j)=\sum_{i\in T(x)}{dist(x,i)\choose j}\\ =\sum_{i\in C(x)}\sum_{t\in T(i)}{dist(i,t)+1\choose j}\\ =\sum_{i\in C(x)}\sum_{t\in T(i)}{dist(i,t)\choose j}+{dist(i,t)\choose j-1}\\ =\sum_{i\in C(x)}down(i,j)+down(i,j-1)\]

同理推导$up$,记录$fa(x)$表示x的父结点:

\[up(x,j)=\sum_{i\in T(fa(x)) \land i\notin T(x)}{dist(fa(x),i)+1\choose j}+\sum_{i\notin T(fa(x))} {dist(fa(x),i)+1\choose j}\\ =\sum_{i\in T(fa(x)) \land i\notin T(x)}[{dist(fa(x),i)\choose j}+{dist(fa(x),i)\choose j-1}]\\+\sum_{i\notin T(fa(x))} [{dist(fa(x),i)\choose j}+{dist(fa(x),i)\choose j-1}]\\ =down(fa(x),j)+down(fa(x),j-1)-down(x,j)-2down(x,j-1)-down(x,j-2)\\+up(fa(x),j)+up(fa(x,j-1))\]

之后我们用一般的树上DP就可以预处理$up$和$down$函数。而结果则是:

\[f(x)=\sum_{j=0}^k \begin{Bmatrix} k\\ j \end{Bmatrix} j! (up(x,j)+down(x,j))\]

LUOGU1829

题意

https://www.luogu.org/problem/P1829

题解

\[\sum_{i=1}^n\sum_{j=1}^mlcm(i,j)\\ =\sum_{i=1}^n\sum_{j=1}^m\frac{ij}{gcd(i,j)}\\ =\sum_{g=1}\sum_{i=1}^n\sum_{j=1}^m\frac{ij}{g}[gcd(i,j)=g]\\ =\sum_{g=1}\sum_{i=1}^{\lfloor \frac{n}{g} \rfloor}\sum_{j=1}^{\lfloor \frac{m}{g} \rfloor}ijg[gcd(i,j)=1]\\ =\sum_{g=1}g\sum_{i=1}^{\lfloor \frac{n}{g} \rfloor}\sum_{j=1}^{\lfloor \frac{m}{g} \rfloor}ij\sum_{d|gcd(i,j)}\mu(d)\\\]

LUOGU3773

题意

https://www.luogu.org/problem/P3773

题解

根据卢卡斯定理,知道${m \choose n} = 1$在模2的情况下发生,当且仅当n是m的子集,即n&m=n。

我们直接暴力计算,记录处理完前i-1个元素后,最后一个元素为j的递减子序列数目。之后枚举所有$a_i$的超集,并统计。可以证明总的时间复杂度为$n^{\log_23}$。

\[\sum_{b_0=0}^1(2-b_0)\sum_{b_1=0}^1(2-b_1)\ldots\sum_{b_k=0}^1(2-b_k)\\ =3\cdot 3 \cdot \ldots \cdot3=3^k\]

LUOGU1613

题意

https://www.luogu.org/problem/P1613

题解

分别找出距离为$2^k$的顶点,并在其之间加上一条长度为1的边,结果就是最终图上的最短距离。

LUOGU4308

题意

https://www.luogu.org/problem/P4308

题解

一开始以为是在图上跑DP,但是算了一下精度,至少需要跑一千万轮BFS才能保证精度,这肯定要超时。

题目很好地使用了倍增思想。简单计算可以知道在$10^9$后继续移动带来的收益已经不足以影响后面的精度。我们记$f(i,x,y)$表示从x点到y点,共经过$2^i$次移动可以得到的收益。那么可以推出下面公式:

\[f(i,x,y)=\max_z f(i-1,x,z)+p^{2^{i-2}}f(i-1,x,z)\]

我们i枚举到30就够了。

LUOGU4548

题意

https://www.luogu.org/problem/P4548

题解

神奇的题目。假设字符串的长度为$m$,字符集为$n$。记模式串为p,构造串为c。对于字符串s,若s[1..i]=s[len-i+1..len],那么称i为s的一个border。记变量$a_i$,当i是p的一个border,那么$a_i$为1,否则为0。

首先我们定义生成函数$F(z)=\sum_{i=0}f_iz^i$和$G(z)=\sum_{i=0}g_iz^i$。其中$f_i$表示c[i-m+1…i]是第一个与p完全匹配的子串。而$g_i$表示c[1…i]中不存在与p匹配的子串。

可以推出公式1:

\[F(z)+G(z)=1+G(z)z\]

公式1左边的$z^i$系数$f_i+g_i$表示第一个与p匹配的c的子串出现在i或i之后。

公式1右边的$z^i$系数$g_i-1$表示第一个与p匹配的c的子串出现在i或i之后。

对公式1两端求导并带入$z=1$后得到:

\[F'(1)+G'(1)=G'(1)+G(1)\Rightarrow F'(1)=G(1)\]

之后我们需要推出公式2:

\[G(z)\cdot (\frac{1}{n}z)^m=\sum_{i=1}^ma_iF(z)(\frac{1}{n}x)^{m-i}\]

公式2左边$z^{i+m}$系数$g_i(\frac{1}{n})^m$,它表示的是c[1..i]中无子串p,但是c[i+1..i+m]正好匹配p的概率。

公式2右边$z^{i+m}$系数$sum_{j=1}^ma_jf_{i+j}(\frac{1}{n})^{m-j}$表示的是第一次出现在$k\in (i,i+m]$之间且c[i+1..i+m]正好匹配p的概率。可以发现c[i+1..k]即匹配p的前缀也匹配p的后缀,因此$k-i$一定是一个border,系数里用$a_j$对这个条件进行了过滤。

将$z=1$代入到公式2中可以得出:

\[G(1)=\sum_{i=1}^ma_iF(1)n^i=\sum_{i=1}^ma_in^i\]

这样我们就得到了快速计算期望的算法。

LUOGU2624

题意

https://www.luogu.org/problemnew/solution/P2624

题解

要统计有多少树,可以通过统计不同prufer编码的数量。即给定一个长度为n-2的序列,要求我们向其中填入1~n,有些数字有限定出现次数,有的没有,组合数学就好了。

LUOGU4602

题意

https://www.luogu.org/problem/P4602

题解

当m=1的时候,问题很明显就是二分。但是m可能很大,我们不能为每个小朋友跑一次二分。

考虑到二分到mid的时候,我们需要判断大于mid的果汁L升至少需要花费多少费用。这个过程可以用线段树进行优化。

先对果汁按照美味程度进行排序,我们可以建立n株线段树,第i株线段树区间[l,r]表示美味不小于第i个果汁,价钱处于[l,r]的果汁总升数和总费用。

注意到第i株线段树和第i+1株线段树实际上只差了一次修改,因此我们可以用持久化线段树维护,时间复杂度为$O(n(\log_2n)^2)$,空间复杂度为$O(n\log_2n)$。

LUOGU4716

题意

https://www.luogu.org/problemnew/show/P4716

题解

树形图算法裸题。

LUOGU3377

题意

https://www.luogu.org/problemnew/show/P3377

题解

左偏树模板题。

LUOGU4555

题意

https://www.luogu.org/problem/P4555

题解

定义函数$f(i)$表示以i为最后一个字符的最长回文长度,定义$g(i)$表示以i为第一个字符的最长回文长度。因此最终结果就是$f(i)+g(i+1)$,枚举所有的切分点i即可。

$f$和$g$都可以通过最长尾回文算法得出,比如哈希,manacher或者回文树都可以。

LUOGU2617

题意

https://www.luogu.org/problem/P2617

题解

有树套树的做法,这里介绍的是整体二分的做法。

将所有的修改操作拆成删除元素和增加元素的操作,初始的元素就对应n次新增操作。

之后我们将所有的查询请求和修改请求按照执行时间排序。用整体二分处理请求。

对于中心m,如果是修改操作,且操作的元素值不大于m,那么就处理,否则就跳过。之后将请求拆分成两部分,第一部分就是修改的元素值小于m、或者查询到区间中小于等于m的数目达到或超过k的请求。

整体的时间复杂度为$O(n\log_2n\log_{2}10^9)$。

LUOGU3332

题意

https://www.luogu.org/problem/P3332

题解

将所有数取反,问题实际上就是第k个。用整体二分可以以$O(n(\log_2n)^2)$的时间复杂度解决。

问题与LUOGU2617是相同的,只不过用线段树替换BIT。