Bzoj练习

Published: by Creative Commons Licence

  • Tags:

BZOJ1016

题意

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

题解

按理来说,这道题是不可做的。但是由于相同权值的边数被限制在了10条,因此就有了一种暴力枚举的做法。

首先观察Kruskal的流程,我们可以发现,当我们交换相同权重的边的处理顺序时,才有可能获得新的生成树。因此我们可以将边按照权重分组,从小到大处理。

一种方案是枚举所有边的排列,但是这样的时间复杂度为$10!$,略大。还有一种方案是,我们枚举每条边是否出现在最终的生成树中,这样的时间复杂度为$2^{10}$,是可以接受的。用可撤销的并查集维护构建的生成树,并统计结果数。

这道题的图不一定连通,要小心。

BZOJ2901

题意

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

题解

K短路。但是题目中的路径是不允许过重复点的,但是题意中已经给出只能从高处到低处,因此路径上一定不会有重复点。

K短路可以用A star算法求解,空间复杂度为$O(kE)$,时间复杂度为$O(kE\log_2kE)$。

BZOJ2429

题意

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

题解

最小生成树或二分。时间复杂度为$O(nlog_2n)$。

BZOJ1196

题意

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

题解

可以如果发现在费用上界设为x时有方案,那么设为任意大于x的值也是有方案的。于是可以用二分,二分费用上界。

之后我们用贪心的方式尽可能多用不超过上界的一级道路。之后如果图还不连通,就用二级道路。最后校验是否用够了k条一级道路,以及最后图是否连通。

BZOJ1715

题意

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

题解

搜负环的模板题。用Spfa,递归版有奇效。

BZOJ1050

题意

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

题解

假如要求最小边的权一定为x,那么我们可以只考虑边权大于等于x的边,按边权从小到大加入到图中,直到s、t连通。这时候最大边的边权为y,则y/x为要求的最小比值。这里是一个贪心的做法。

我们可以枚举最终解中的最小边,提前排序边集,总共有$M$种可能。利用滑动窗口的技巧,我们不必在每次考虑新的最小边的时候重建整个图。这意味着我们只需要做$M$次加边、删边、判连通操作。

我们注意到后加的边一定后删,因此我们可以用LCT判连通。当新的边加入后会成环,那么就剔除环中最早加入的边即可。这样保证连通性检测时的结果不会变动,同时只处理树形结构。

总的时间复杂度为$O(Mlog(N+M))$。

BZOJ1093

题意

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

题解

首先我们可以对图中的环进行缩小点,一个点的点权表示该点由多少点缩点而来。我们希望找到一个最大的半连通图,点权和最大。缩完点后的图是有向无环图。

假设G=(V,E)为我们找到的最大半连通图,观察它满足的性质。首先G一定是有向无环连通图,同时我们一定可以找到一个唯一的顶点v,其入度为0(否则假如找到两个点u、v入度都为0,这意味着u、v之间不存在一条路径,这与G是半连通图相悖)。在移除v后得到的图还是半连通图。我们不断重复移除的过程得到了一个顶点序列$v_1,v_2,\ldots ,v_n$。我们可以保证它们构成一条路径。而一条路径一定是半连通图。因此我们得知一个图是半连通图当且仅当它的所有顶点序列可以构成一条路径。

故,我们实际上要找到的是图中的一个最大权路径,在DAG中,我们可以在顶点的拓扑序上使用动态规划技术得到。

BZOJ3786

题意

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

题解

首先有换父操作,因此我们需要用到动态树。Link-Cut-Tree适合处理路径问题,但是题目中要求支持子树增强权重的操作。

考虑另外一个动态树实现Euler-Tour-Tree。我们利用DFS可以将树转换为括号序列,并用平衡树维护序列。这样将以x为根的子树移除出树,等价于将x的开闭括号从序列中删除。而将以x为根的子树连接到y下,等价于找到y的闭括号,并将x对应的括号序列加到y的闭括号之前。

之后查找x到根所有顶点的权重之和,可以用一种特殊的技巧统计路径信息。我们在遇到开括号时,执行加操作,在遇到闭括号时执行减操作。这样只需要统计根的开括号到x的开括号这段序列的权和即可。

BZOJ1491

题意

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

题解

Floyd+DP

BZOJ1027

题意

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

题解

由于a+b+c=1,因此若(a,b)一旦确定,那么c就随着确定。现在考虑两个点$(x_1,y_1),(x_2,y_2)$。对于$t\in [0,1]$,可以取到形如点$(x_1t+x_2(1-t), y_1t+y_2(1-t))$,这些点组成的实际是$(x_1,y_1)$与$(x_2,y_2)$之间的线段。之后继续加点,我们会得到凸多边形。

至此,我们知道了题目实际上的本意,将需求转换为二维平面上的点,我们要找到尽可能少的原料代表的点,使得这些点唯一确定的凸包能包含所有需求点。

一个点落于凸多边形中当且仅当这个点处于凸多边形的所有边的逆时针方向。

我们可以证明要寻找的n个原料点一定是凸包上的点,且由点数最少,可以推出边数最少。能够形成凸包的边一定满足所有顶点都落在凸包的逆时针方向。

我们将所有满足条件的边的边权设为1,不满足条件的边的边权设为无穷。那么可以得出最小环一定是最优解组成凸包上的边。

最小环可以通过FW算法得到。

BZOJ1232

题意

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

题解

发现USACO的题目质量好高啊。

首先容易发现,在移除多余的边后得到的是一株树。而无论从那个顶点出发遍历整颗树的最短距离为$2\sum_{e\in E}e.w$,即边权之和的两倍。这很容易理解,遍历以某个顶点为根的子树,我们需要依次遍历每个子结点为根的子树,这和深度优先搜索实际上是相同的实现。而每次我们从根下降访问子树,而访问完子树后需要原路返回,因此每条边都会被经历两次。

但是这距离我们最终结果还相距甚远,因为不仅边有权,点也有对应的权。如果点没有权的话这个问题实际上就是算最小生成树而已。

观察树,对于任意一个顶点u,如果顶点的度为d,那么这个顶点在遍历的整个过程中至少会被访问d次。一条边与父节点连接,这里会访问一次u,之后每次从u的子节点搜索返回,都会访问u一次。根结点比较特殊,因此一开始就位于根结点,因此根节点的访问次数会比它的度额外多1。

因此如果树选取好了,我们简单记作$T=(V,E')$。可以推出最小的要花的时间为:

\[root.w + \sum_{u\in V}u.w\cdot u.d + \sum_{(u,v)\in E'}(u,v).w\cdot2\]

因此我们实际上要做的是选取一株树,使得上面式子最小。我们可以将上面公式进行改写:

\[root.w + \sum_{(u,v)\in E'}((u,v).w\cdot 2+u.w+v.w)\]

由于root的选择仅影响上面式子中$root.w$这一部分,因此我们始终选择权最小的顶点作为根。而右边和式中,如果我们定义每个边的修正权为$(u,v).w'=(u,v).w\cdot 2+u.w+v.w$,和式就变成了:

\[\sum_{(u,v)\in E'}(u,v).w'\]

要使该式最小,只需要基于修正后的边权,生成最小生成树就可以了。

BZOJ1977

题意

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

题解

严格最小生成树。看别人博客说是严格次小生成树能和最小生成树只差一条边,我并不知道怎么证明。先记录一下吧。

我们需要维护路径上的最大权边和次大权边,这个用动态树就好了,时间复杂度$O(n\log_2n)$。

BZOJ3699

题意

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

题解

好题。可以脑补一个网格图,左下角网格坐标为(0,0),横坐标为a,纵坐标为b。之后将所有边按照其a、b分配到网格中。

对于每一个i,我们试图找到最小的一个数j,使得仅使用那些属性a不超过i,属性b不超过j的边,可以保证顶点1和n连通。我们记$f(i)=j$,容易发现f是一个递减函数。

因此,我们可以先从点(-1,50000)出发,之后,不断向右或向下移动一步。可以证明最多移动2L步,L是精灵数要求的上限,这里是50000。

在整个流程中,每条边最多加入图一次,最多被移除一次,因此加入和删除操作会分别发生最多m次。而每次一定后都要重新判断顶点1和n是否连通,即需要查询连通2L次。

可以发现,b越大的边越早被删除。我们以b作为删除时间,那么问题就转换为如何在线维护一副图,图中边有自己的删除时间,要求查询各个时间下的连通性。

这个可以通过动态树实现,我们用动态树维护图的一个生成树。当我们加入一条边时,如果边的两个顶点不连通,这代表加入边后图依旧是森林,即没有环存在。如果边的两个端点连通,那么找到两个端点之间的唯一路径,判断路径上删除时间最小的边,如果该边的删除时间早于我们要加入的边,那么我们可以用新边替换该条边,否则不处理。我们可以保证任意时刻,如果两个顶点在动态树中不连通,那么没有加入动态树的边一定被过期删除了,因此即使这些边加入图中,此时依旧不连通。当然如果连通自然是确实连通的。而用这种方法,并不需要真的执行删除操作,要判断两个顶点连通,只需要判断两条边之间删除时间最早的边是否以及过期。

BZOJ 1098

题意

http://www.lydsy.com/JudgeOnline/problem.php?id=1098

题解

经典题。我们将员工建立顶点,两个员工有联系方式,那么我们就加入一条边。可以发现,如果两个人没有边,那么他们必须住在一个办公楼里。我们将图反转(两个顶点若之前有边,就删掉,否则加一条边),可以发现题目要求我们求的是有多少个连通块以及每个连通块的大小。

那么怎么求呢,有个技巧,就是发现被删除的边是有限的。我们可以随意从任意一个顶点开始找它所在的连通块,遍历所有其余没有处理过的顶点,查询是否二者之间存在边。成功,就将这个顶点合并进当前连通块,否则就跳过,处理直到当前连通块中所有顶点都被处理过了一次。

我们估计一下时间复杂度,可以发现时间复杂度取决于上面查询发生的次数。由于查询成功的次数不会超过$2m$,而每次失败都会将某个未处理的顶点删除,因此失败最多发生$n$次。总共时间复杂度为$O(2m+n)$。

BZOJ4043

题目要求我们能判断路径的总权值,以及动态更新单点权值和子树权值。

如果只有单点权值,可以使用LCT来维护整颗树,复杂度为$O(nlog_2n)$。但是这里有子树权值,所以还是需要使用树链剖分的。

这题实际上考察的是树链剖分的一个特性,我们为每个结点重新分配序号时,同一条重链上的所有结点的序号是连续的,同时一颗子树下的所有结点的序号恰好形成一个连续的区间。

因此我们只需要寻找轻重链,之后为每个结点分配序号,按照序号创建一个线段树。之后的所有操作都在线段树上完成,实际的时间复杂度为$O(nlog_2^2n)$。

BZOJ4196

将软件表示为结点,软件安装对应结点权值为1,未安装对应权值为0。题目实际上要我们求的是计算子树的总权值和,计算路径权值和,设置路径权值,设置子树权值。之后问题同BZOJ4043。

BZOJ3531

题目

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

题解

我一开始写的是带修改树上莫队,但是,TLE了。本地测了一下,速度还行的啊,10w的数据也就几秒。

正解貌似是用轻重链剖分,只是维护100000+1个动态开点的线段树,每个线段树仅记录一种颜色的顶点的信息。这样时间空间复杂度为$O((n+q)(\log_2n)^2)$。

BZOJ4552

题意

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

题解

线段树分裂合并的模板题。

BZOJ1699

题意

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

题解

裸题,可以用来测模板。St或线段树。

BZOJ1251

题意

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

题解

裸题,可以用来测模板。Treap、Splay都行。

BZOJ2243

题意

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

题解

由于是路径操作,路径操作的题目基本解法都是树链剖分、动态树、树上莫队。

考虑线性结构。类似于这类统计区间不同段数的问题,我们可以维护一个值tag,对于某个段,设置开头元素的tag为1,后续的元素的tag为0。这样,一个区间$[l,r]$存在多少个不同的段,可以统计区间$[l+1,r]$中tag的和,加上1后就是正确结果。

在处理树上路径的时候,也可以同样处理。如果u与其父节点在同一条重链上,且u与父节点的颜色不同,就设置u的tag为1。使用树链剖分,我们每次操作只需要处理$\log_2n$条重链,统计重链上tag的和,并且统计所有处于路径上的连接两个不同的重链的边,如果边的两端颜色不同,那么我们还需要在向结果加1。

而更新操作只需要处理路径上的重链就好了。

BZOJ1036

题意

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

题解

水题,树链剖分或动态树。

BZOJ2038

题目

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

题解

裸的莫队

BZOJ2120

题目

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

题解

裸的带修改莫队

BZOJ1878

题目

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

题解

莫队应该也能过,但是这题有O(nlogn)的解法。

我们从左到右扫描整个贝壳序列,假设当前扫描到i。我们为同类贝壳中最靠近i的贝壳的打上标记,而其余贝壳不打标记,统计以i为右边界的区间中不同贝壳数,可以转为统计区间中打上标记的贝壳数。

提前排序请求,并用BIT维护标记状态即可。

BZOJ2743

题目

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

题解

与BZOJ1878相同,但是需要打标记的花朵是距离扫描点第二近的花朵。

BZOJ1146

题意

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

题解

裸的带修改树上莫队。

BZOJ1109

题意

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

题解

用动态规划,dp(i)表示仅考虑前i个数,并保留第i个数最多有多少满足的块。简单推推可以转移公式:

\[dp(i)=\max_{j<i}([a[j]<a[i]\land i-j\geq a[i]-a[j]]dp(i))+1\]

后面部分我们可以做个转换得到:

\[i-j\geq a[i]-a[j]\Rightarrow i-a[i]\geq j-a[j]\]

我们可以定义$x_i=a[i]$,$y_i=i-a[i]$,$z_i=i$,那么问题就转换了三维最长递增子序列问题。

注意到由前两个条件可以保证第三个条件的成立,因此可以忽略第三个条件,问题转换为二维最长递增子序列问题。

随便写吧。一开始没有想这么多,就直接DP+树套树,结果TLE了。

# BZOJ1040

问题

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

题解

首先把骑士作为结点,将讨厌关系作为边建立。容易发现两个连通分量之间的选择是独立的,因此我们只要为每一个连通分量选择最大的总权,之后加总就好了。

一个连通分量有k个骑士,则必定有k条边。我们知道这样的图本质是一个树加上一条边,即树中最多只有一个环。记X,Y为环的两个顶点,且X讨厌Y。那么我们知道X与Y不能同时出现,那么最优结果要么X不出现,要么Y不出现。我们分别尝试删除X以及删除Y两种策略,计算树形DP,就可以得到最优质值。

BZOJ1079

题意

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

题解

一开始以为是容斥,捂脸。

一种很简单的思路就是定义函数$f(i_1, i_2, \ldots, i_k, c)$表示用$i_j$种颜色j,有多少种有效排列,排列以颜色c作为结尾。但是函数的状态有$5^15\cdot k$种,这样的动态规划会超时。

实际上颜色具体是什么并不重要,重要的是数量为1的颜色有多少种,数量为2的颜色有多少种…因此我们定义的动态规划公式为$f(i_1,i_2,i_3,i_4,i_5, c)$,表示数量为j的颜色有$i_j$种,其中以数量为c的某种颜色作为开头的有效排列数目。这样总共状态为$15^5\cdot 5$,是可以求解的。

BZOJ1010

题意

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

题解

利用动态规划,定义$f(i)$表示要打包前i个物品的最小费用。容易推出:

\[f(i)=\min_{j=0}^{i-1}(f(j)+(\sum_{k=j+1}^ic_k+(i-j-1)-L)^2)\]

用原始的动态规划时间复杂度为$O(n^2)$,会超时。我们稍微简化一下公式,记$pre_i=\sum_{i=1}^nc_i$,$a_i=pre_i+i-L$,$b_i=pre_i+i+1$。代入上面式子中:

\[f(j)+(\sum_{k=j+1}^ic_k+(i-j-1)-L)^2\\ =f(j)+(pre_i+i-L-(pre_j+j+1))\\ =f(j)+(a_i-b_j)^2\\ =f(j)+a_i^2+b_j^2-2a_ib_j\]

我们可以改写递推公式:

\[f(i)=a_i^2+\min_{j=0}^{i-1}(-2b_ja_i+f(j)+b_j^2)\]

由于我们在计算$f(i)$的时候与j关联的变量都是已知的,因此可以视作常量,换一种表示,我们就会发现有min中的表达式对应一条直线,即$y=ax+b$,其中x需要我们用$a_i$代入。如果我们为这些直线维护一个上凸包,就可以利用凸包优化以$O(\log_2i)$的时间复杂度直接得到最优的j,而不需要以$O(i)$的时间复杂度遍历。这样时间复杂度就优化到$O(n\log_2n)$。

但是由于java没有long double类型,而数值的数据范围过大,所以精度不足会给出约莫的值,会WA。所以需要换种方法。

下面我们考虑使用斜率优化的方式。若存在$j>k$,且$-2b_ja_i+f(j)+b_j^2 \leq -2b_ka_i+f(k)+b_k^2$。继续推导:

\[-2b_ja_i+f(j)+b_j^2 \leq -2b_ka_i+f(k)+b_k^2\\ \Rightarrow (f(j)+b_j^2)-(f(k)+b_k^2)\leq (2b_j-2b_k)a_i\\ \Rightarrow \frac{(f(j)+b_j^2)-(f(k)+b_k^2)}{2b_j-2b_k}\leq a_i\]

记$Y(i)=f(i)+b_i^2$,记$X(i)=2b_i$,那么公式就转换为

\[\frac{Y(j)-Y(k)}{X(j)-X(k)}\leq a_i\]

而由于$a_i$是递增函数,因此可以利用斜率优化,时间复杂度为$O(n)$。

BZOJ1222

问题

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

题解

一开始以为是最大流,没想到解法。容易发现每个任务的费时都非常小,最多为5,因此需要在这里动手脚。

定义动态规划f(i,j,k),表示是否有可能完成前i个任务,任务占用了机器A时间不超过j,任务占用了机器B时间不超过k,f(i,j,k)的返回值是布尔值。很显然当i和j固定时,f随着k的增大从false变为true,即$f_{ij}(k)=f(i,j,k)$使单调增函数。类似这类函数,我们只需要记录变为true的最小的k。因此我们将函数优化到了二维$g(i,j)=minarg_{k}f(i,j,k)=true$。这时候函数的整个状态只有$O(5n^2)$,是可以通过时限的。

我们将$g(i,j)$解读为当使用机器A时间少于等于j时,完成前i个任务至少需要占用机器B时间多少。这样就可以很容易推出递推公式。

BZOJ1030

问题

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

题解

要算有多少字符串合法,可以通过算多少字符串非法得到。首先对所有的子串通过AC自动机状态压缩,之后利用动态规划解决。$f(i,j)$表示有多少长度为i并处于状态j的字符串,之后递推就好了。

BZOJ2326

问题

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

题解

一开始想要使用数学公式推导。

\[\sum_{i=1}^nix^i=x\sum_{i=1}^nix^{i-1}=x(\sum_{i=1}^nx^i)'\\ =x\cdot (\frac{x^{n+1}-x}{x-1})'=\frac{nx^{n+2}-(n+1)x^{n+1}+x}{(x-1)^2}\]

但是模数m不一定是素数,因此除法不能实现。当然如果m是不同的素数的乘积,那么可以分解因子后对因子计算出结果,之后用中国余数定理恢复。但是这里也不能保证m一定是不同素数的乘积,捂脸。

但是实际上,公式是非常简单的,所以用动态规划试一下:

\[f(i)=10^{D(i)+1}f(i-1)+i\]

这里是一个线性方程。那么我们用矩阵乘法来表示:

\[\left( \begin{array}{ccc} 10^{D(i)+1} & 1 & 0 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{array} \right) \left( \begin{array}{c} f(i-1)\\ i\\ 1 \end{array} \right) = \left( \begin{array}{c} f(i)\\ i+1\\ 1 \end{array} \right)\]

用矩阵快速幂,分段处理就好了。

BZOJ1037

题意

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

题解

这个问题有一个弱化的版本,不允许出现k个连续男孩或女孩的情况,问有多少种方案。这个问题比较简单,令$f(i,j,t)$表示排列i个男孩和j个女孩,使得不出现k个男孩或女孩连坐,且以t个男孩连坐作为结尾的情况下的方案数。同时令$g(i,j,t)$,表示排列i个男孩和j个女孩,使得不出现k个男孩或女孩连坐,且以t个女孩连坐作为结尾的情况下的方案数。计算所有结果,并最后加总就好了。

这个问题稍微有点绕。现在再简化成另外一个问题,给出一个排列,判断该排列是否出现某个连续段男孩与女孩数的差大于k。这可以通过动态规划实现。用同样的思路,我们记$f(i,j,a,b)$表示排列i个男孩和j个女孩,且该排列有效,且排列的所有的后缀中,男孩最多比女孩多a个,女孩最多比男孩多b个。之后统计即可。

BZOJ1898

题意

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

题解

题面比较复杂。记$f(i,j)$表示从起点出发,经过i秒后,落脚于j处的方案数。当鱼的位置都是固定的时候,可以发现存在一个复杂的动态规划关系,但好歹也是可以推导的。

再看看K特别的大,即动态规划需要迭代非常多轮,自然会想到用矩阵来做优化。

但是每个时刻食人鱼的位置也会变动该怎么办呢,题目给出了鱼的位置的周期仅为2,3,4,而对于三者的公倍数12来说,鱼一定会归位。因此容易想到分段DP的思路。

先将代表前面12秒的12个矩阵连乘,之后用快速幂进行迭代。最后会余下不超过12次的迭代,这时候暴力即可。

时间复杂度为$O(12\cdot n^3)$。

BZOJ1260

题意

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

题解

首先很容易发现连续的相同颜色可以合并。

之后定义$f(l,r,d)$表示绘制区间$[l,r]$所需要的最少步骤,且区间此时的默认色为$d$。很显然,在处理区间$[l,r]$时,点$l$可以第一个绘制。假设最优策略中我们将区间$[l,m]$绘制成点$l$所需的颜色,那么能够保证区间$[l+1,m]$上点的着色一定发生在该步骤之后(因为之前会浪费步骤)。

之后记忆化搜索就好了。好像别人的解法是$O(n^2)$的。。

BZOJ1096

题意

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

题解

很显然得用动态规划来解决。记$dp(i)$表示仅考虑前i个工厂,在第i个工厂建仓库的最小费用。可以得到递推公式:

\[dp(i)=\min_{j<i}dp(j)+C(i)+\sum_{k=j+1}^{i-1}(X(i)-X(k))P(k)\\ =\min_{j<i}dp(j)+C(i)+X(i)\sum_{k=j+1}^{i-1}P(k)-\sum_{k=j+1}^{i-1}X(k)P(k)\\ =\min_{j<i}dp(j)+C(i)+X(i)(S(i-1)-S(j))-(F(i-1)-F(j))\\ =C(i)+X(i)S(i-1)-F(i-1)+\\ \min_{j<i}dp(j)-X(i)S(j)+F(j)\]

很显然最后的min里面的内容可以用凸包技巧或斜率优化给优化掉。这里考虑斜率优化:

\[dp(j)-X(i)S(j)+F(j)\leq dp(k)-X(i)S(k)+F(k)\\ \Rightarrow \frac{(dp(j)+F(j))-(dp(k)+F(k))}{S(j)-S(k)}\leq X(i)\]

BZOJ1057

题意

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

题解

首先我们记R(i,j)表示网格(i,j)右侧最多可以扩展的长度,这个可以通过递推在O(nm)时间复杂度内计算完成。

记T(i,j)表示网格(i,j)上方可以扩展的长度,这里可以扩展还有一个条件,上方的网格的R必须大于等于当前网格的R。

同理定义B(i,j)表示网格(i,j)下方可以扩展的长度。

T(i,j)和B(i,j)都可以通过单调队列以$O(nm)$的时间复杂度完成。

记H(i,j)=T(i,j)+B(i,j)+1。

我们注意到一个最大的矩形,其左侧边缘网格中,记R最小的网格为(i,j),那么我们可以保证矩形的长度为R(i,j),且高度为H(i,j),否则我们可以扩大矩形。

同理对于一个最大的正方形,其左侧边缘网格中,记R最小的网格为(i,j),同时我们一定能得出H(i,j)是所有左侧边缘网格中最小的。而此时正方形的边长为min(R(i,j), H(i,j)),否则我们可以扩大正方形。

找最大的矩形和最大的正方形都可以通过遍历所有的网格得到。

总的时间复杂度为O(nm)。

BZOJ1063

题意

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

题解

首先题目保证了无环,并且在不连通的情况下不需要处理。因此我们实际上要处理的是以首都为根的树形结构。

很容易能想到树上DP,利用树上DP我们可以以$O(n)$的时间复杂度,计算最少需要的不便利值。

但是方案数如何统计呢???

首先我们知道轻重链剖分,是一个合法的方案(重链代表铁路),因此不便利值最多为$O(\log_2n)$。

之后我们可以就可以用DP来处理了。记$f(i,j,k)$表示以i为根,i与不多于j个子结点之间修了铁路,此时子树的不便利值不超过k的方案数。记$g(i,j,k)$表示以i为根,i与正好j个子结点之间修了铁路,此时子树的不便利值不超过k的方案数。可以推出公式:

\[g(i,0,j)=\sum_{c}^{children(i)}f(c,2,j-1)\\ g(i,1,j)=\sum_{x}^{children(i)}f(x,1,j)\sum_{c\neq x}^{children(i)}f(c,2,j-1)\\ g(i,2,j)=\sum_{x\neq y}^{children(i)}f(x,1,j)f(y,1,j)\sum_{c\neq x,y}^{children(i)}f(c,2,j-1)\\ f(i,k,j)=\sum_{t=0}^kg(i,t,j)\]

每个等式都可以以线性的时间复杂度计算完成,因此,总的时间复杂度为$O(n\log_2n)$。

BZOJ1095

题目

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

题解

好题。

首先,假如不考虑修改,我们可以直接用树上DP算出结果。但是由于有修改的存在,因此我们需要利用特殊的技术实现可修改动态规划。

输入是一颗树,我们可以求出其括号序列。比如一个跟结点带两个子结点的括号序列为(0(1)(2))

选择两个顶点u,v,并找到其lca(u,v)=x,记d(u)表示u的深度。那么u与v之间的距离为$d(u)+d(v)-2d(x)$。我们可以这样理解括号序列,每遇到一个左括号,我们深度加1,遇到一个右括号,深度减少1,这样我们就可以将括号序列的每个元素映射为一个深度。这样我们实际上要找的是两个左括号,其在括号序列中的下标为l,r,且$l\leq r$。我们记M(l,r)表示括号序列的第l个元素到第r个元素中深度的最小值。那么l、r对应的结点的距离为$d(l)+d(r)-2M(l,r)$。

对于一个括号序列,我们可以将其均分为两部分,并分治处理。这样最大的好处就是可以使用线段树结构进行维护,从而支持$O(\log_2n)$时间复杂度的修改和查询。

在分治的时候,假设括号序列分为两部分A和B,我们希望能求$d(l)+d(r)-2M(l,r)$,有三种可能:

  • l, r均属于A
  • l, r均属于B
  • l, r分别属于A、B

下面仅讨论第三种情况,我们知道l、r之间拥有最小深度的元素或者落在A中,或者落在B中,枚举两种情况求解就好了。记dlr表示一个块中的最大元素,dlSub表示一个块能提供的最大d(l)-2M(l..),drSub表示一个块能提供的最大的d(r)-2M(..r)。那么在第三种下答案应该为:

\[\max(A.dlr+B.drSub,A.dlSub+B.dlr)\]

我们可以在pushUp的时候维护这些属性,整体的时间复杂度为$O(m\log_2n)$。

BZOJ1025

题意

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

题解

记$f(x,y,n)$表示将边长为x,y的矩形分给n个人的最优解。容易知道

\[f(x,y,n)=\min(\\ \min_i(\max(f(x\cdot \frac{i}{n},y,i),f(x\cdot \frac{n-i}{n},y,n-i))),\\ \min_i(\max(f(x,y\cdot \frac{i}{n},i),f(x\cdot \frac{n-i}{n},y\cdot \frac{i}{n},n-i)))\\ )\]

记$T(n)$表示执行形如$f(x,y,n)$所需要的时间。那么有

\[T(n)=2nT(n-1)+1=\ldots\approx 2^n\cdot n!\]

注意到

\[\max(f(x\cdot \frac{i}{n},y,i),f(x\cdot \frac{n-i}{n},y,n-i)) =\max(f(x\cdot \frac{n-i}{n},y,n-i),f(x\cdot \frac{i}{n},y,i))\]

我们在遍历$i$时,只需要遍历$1~\frac{n}{2}$。利用这个优化可以得到修正后的时间复杂度:

\[T(n)=nT(n-1)+1\approx n!\]

由于n只能取到10,而$10!=3628800$,因此足够通过题目了。

BZOJ1029

题意

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

题解

解法是贪心,我们先对t2按从小到大排序,之后按序处理所有建筑。

  1. 如果还有多余的时间分配给当前建筑用于修复,那么就修复建筑。
  2. 否则如果之前修复的建筑的中修复时间最长的建筑的修复时间多余当前建筑的修复时间,则取消对该建筑的修复,转而将时间分配给当前建筑。
  3. 否则,就跳过当前建筑。

在处理完第i个建筑后,得到的策略是能修复最多建筑的策略中花费总时间最少的。如果单独将策略中前k个费用最小的建筑提出来,那么提出来的建筑会组成新的策略,是处理完前i个建筑后,共修复k个建筑且费用最小的策略。

BZOJ1106

题意

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

题解

记i的出现的左边坐标为l(i),右边坐标为r(i)。

那么如果l(i)<l(j)<r(j)<r(i),那么先消除j会让之后消除i少交换两次,而先消除i并不会减少j消除需要的交换次数。其余的值对没有明显先后要求。

我们可以对r(i)-l(i)的大小对所有的值对位置进行排序,从区间较小的开始消除就可以了。

BZOJ1854

题意

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

题解

一开始想的是二分图匹配,但是数据量太大,会TLE。 可以用并查集,如果一个联通块中存在环,则联通块必定可以全选,否则至少有一个结点可以选。

BZOJ1854

题意

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

题解

一开始想的是二分图匹配,但是数据量太大,会TLE。 可以用并查集,如果一个联通块中存在环,则联通块必定可以全选,否则至少有一个结点可以选。

BZOJ1345

题意 https://www.lydsy.com/JudgeOnline/problem.php?id=1345

题解

很显然最后留下的是序列中的最大值。选择最大值,处于最大值左侧区间中的最大值最后只能与全局最大值合并,对于右侧同理。这提示了我们可以以全局最大值为根建立一棵树,根的左节点是左侧区间最大值,右节点是右侧区间最大值。建树可以通过递归实现。而对于每个结点,其提供的费用是结点对应的值乘上结点的子节点数目,汇总所有结点的费用就是结果。

还有注意如果你利用递归建树,那么就需要用到一些平衡树结构,这样时间复杂度为$O(n\log_2n)$。但是实际上我们建出的是一个树堆,而建立树堆是可以通过单调栈实现的,这样时间复杂度就优化到了$O(n)$。

BZOJ1816

题意

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

题解

如果能组成k+1副牌,那么组成k副牌肯定不是难事。因此二分可以组成的牌数。

如果组成k组牌,需要x张joker,x满足x<=k且x<=m,那么我们就一定能组成k组牌。

BZOJ1863

题意

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

题解

对于分配给将军1的奖牌,我们称为特殊奖牌。假设我们我们造好了k种颜色,那么是不是存在一种符合需求的分配方案。这里可以用贪心的方法,对于将军i,如果i与n同奇偶性,则分配尽可能少的特殊奖牌,否则分配尽可能多的特殊奖牌。如果最后将军n得到了至少一个特殊奖牌,那么方案不存在,否则存在。

贪心也可以替换为动态规划,记f(i)、g(i)表示分配前i个人后,第i个人可以得到最多多少特殊奖牌以及最少多少特殊奖牌。这里不考虑第1个人和第n个人的邻接关系。很显然$f(i)=\min(a_1-g(i-1), a_i)$,$g(i)=\max(0, a_i-(k-a_1-(a_{i-1}-f(i-1))))$。如果$g(n)>0$那必定无解,否则有解。

由于方案的存在性随着k的增加递增,因此可以用二分法优化。

BZOJ3293

题意

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

题解

咋一看,最小费用最大流。但是看看数据量,10w级别,再见。

这个问题可以转换为另外一个耳熟能详的形式。记$s_i$表示第i个人初始的金币,$x_i$表示第i个人给后面那个人的金币数,记t为平均金币。那么在进行交换后,第i个人持有的金币应该满足:

\[s_i+x_{i-1}-x_i=t\]

$x_1$一旦确认,其他几个未知变量也会对应确认。将所有的变量用$x_1$来表示,可以得出:

\[x_i=\sum_{j=2}^i(s_j-t)+x_1\]

我们要做的就是最小化式子

\[\sum_{i=1}^n|x_i|=\sum_{i=1}^n|\sum_{j=2}^i(s_j-t)+x_1|=\sum_{i=1}^n|x_1-p_i|\]

这个问题,可以转化为这样的形式:在x轴上放置n个点$p_1,p_2,\ldots ,p_n$,要求我们选择一个点,这个点到其它所有点距离和最小。

很显然无论在哪个位置,当$x_1$向中点靠近时,距离和会递减。因此我们可以选择$x_1$为中点即可。

BZOJ1150

题意

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

题解

比较奇怪的一道题。很容易发现电线只会连接邻近的两个点,我们可以根据点下标的奇偶性生成二分图,之后要求的实际上是这副二分图上的最小费用最大流。但是数据量有点大,费用流是过不了的。

仔细观察,可以发现这幅二分图是很特殊的,每个顶点的度都不超过2。我们知道费用流是不断找最短费用路进行增广,最短费用路在这里一定是交错路,我们可以动态维护所有的路径,再手动模拟增广,就可以在不使用费用流算法时达到费用流的效果。

我的方法的时间复杂度是$O(n\log_2n)$。记$d_t$表示第$t$与$t+1$的距离,那么从$i$到$j$的交错路的费用为$\sum_{k=i}^{j-1}(-1)^{k-i}d_k$,这个可以通过前缀和技术预先处理。之后我们将所有的路径维护在一个树集中,并维护一个左结点的可行点集合和右结点的可行点集合。每次我们增广后,都可能会向路径集合增加四条路径。

BZOJ1053

题意

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

题解

要计算一个数$x$的因子数,我们需要先利用算术基本定理将其分解为若干个不同的素数的幂的乘积。

\[x=p_1^{c_1}\ldots p_k^{c_k}\]

而$x$的因子数可以表示为$g(x)=\prod_{i=1}^k(1+c_i)$。

而我们要找的是小于等于N的因子数最多的x,如果有多个拥有相同因子数的数,那么需要取最小的。很显然要让因子数尽可能多,那么我们可以选择较小的几个素数组成x,实际上较小的素数可以获得的x也是较小的,这与我们目标吻合。

这里只需要小于等于23的所有素数即可,之后深搜暴力,时间复杂度这种东西不重要。

BZOJ1112

题意

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

题解

枚举所有可能的区间,共n-k+1种。之后对于每个区间,我们将其中的高度从小到大排序,而在最终高度取到区间高度的中位数时费用最小。

因此用平衡树维护一下区间,之后找一下中位数就好了。

BZOJ1834

题意

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

解法

每条边我们会建两条边,一条边容量指定但是费用为0,而另外一条边容量无限但是费用为c。之后跑最小费用最大流就能得到扩容费用了。

BZOJ3171

题意

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

解法

首先容易发现如果每一个点都处于循环中,那么必定每个顶点的入度一定为1。假如有顶点入度非1,就代表一定有顶点入度为0,自然也意味这个顶点出发不能回到自己。如果每个顶点入度为1,通过倒推可以证明每个顶点出发一定会回到自己。

现在的问题就转换为需要修改多少个单元格的值,才能保证每个顶点的入度为1。我们可以通过最小费用最大流来解决。将每个顶点分裂为两个顶点,出点和入点。每个顶点的入点向周边顶点的出点连一条费用为1的边,表示切换方向的成本,同时向与自己同向的顶点连一条费用为0的边。之后保证所有入点和源点连一条容量为1的边,而所有出点和终点连一条容量为1的边。之后跑最小费用最大流就是结果了。

BZOJ1070

题意

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

解法

暴力的题目。将技术人员分裂为n个结点, 第i个技术人员的第j个结点,表示第i个技术人员修理分配给他的任务中倒数第i个任务。

从每辆车i向每个技术人员j的每个结点k连一条边,容量为1,费用为$t_{ij}\cdot k$。

之后跑最大流就是了。BZOJ的机器太慢了,过不了时限可以去试试洛谷的P2053。

BZOJ3280

题意

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

解法

最小费用最大流的模板题吧。

BZOJ1797

题意

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

题解

好题。

在我们跑完最大流后,我们为整个网络求所有强连通分量。

之后我们来分别描述可能出现在最小割和必定出现在最小割的充分必要条件。

命题1:一条边出现在最小割中的充分条件是边的两个端点不属于同一个强连通分量,且边满流

很显然边e没有满流的话,我们从汇点向起点经由e发送与e流量大小相同的流量,从而e不再有流。此时图上的总流量为f-e.f。之后我们割去e后发现,加上图上的剩余流发现割至少为f-e.f+e.c>f,显然e所在的所有割都不是最小割。

之后如果边的两个端点u、v属于同一个强连通分量,这意味从u到v存在增广路径。这样即使我们割去边e,那么我们可以将u的额外流发送到v去,这样也导致e所在的割都不是最小割。必要性证明完毕。

假如一条边e不属于任意最小割中,这意味着稍微减少该边的容量不会影响最大流。我们从t到s经过边e退一部分流,之后显然此时总流减少了,为了保证流最大,因此必定从s到t沿着增广路发送了相同大小的流,只是增广路上不存在e。我们将增广路和退流路合并,可以找到包含e的一个环,即e的两个端点处于同一个强连通分量中。充分性证明完毕。

命题2:一条边必定出现在最小割的充分必要条件是边的两个端点分别属于S、T强连通分量,且边满流。

边e一定出现在最小割中的前提自然是e可能出现在最小割中,因此边满流是必要的。既然e一定出现在最小割中,那么e一定出现在当前得到的最小割中,设e的端点为u,v,那么s到u有增广路,由于s到u有流(这对应残存网络中u到s有路径),因此s与u必定处于相同的强连通分量。如果v到t也有路径,那么v自然处于t的强连通分量中。此时我们稍微增加v的容量,那么最大流必定增加。假如有不含e的一个最小割C,那么C不会改变总边权,这与最小割与最大流相同相悖。因此C一定含有e。充分性证明完毕。

必要性可以类似进行证明。稍微增大e的容量,由于图中不存在增广路,因此最大流不变。假如e属于所有最小割,那么很显然最小割的边权和都增大了,这是不可能的。(这里需要保证增加容量的幅度足够小,以保证所有包含e的割,若非最小割,那么割总权依旧大于修改后的最小割)

BZOJ2661

题意

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

题解

题目类似于匹配问题,可以暴力校验在数据规模下,图是一个二分图。之后先对图中顶点进行染色,构建二分图。

由于边的收益并非是1,我们需要使用费用流,将两个满足条件的x、y之间连一条费用为-x-y的边。

BZOJ1391

咋一看是最大权闭合图,但是实际上租用可以替代购买。我们可以修改最大权闭合图模型,将任务与机器的连线的容量设为租用的费用而非无穷。这样允许我们用割掉任务和机器的连线,来替代割掉机器和终点的连线,即用租用代替购买。

BZOJ3275

题意

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

题解

看上去是最大权闭合图,但是怎么建图呢?首先我们能保证只有奇数和偶数之间才能同时满足两个条件。

对于两个奇数,其平方和模4余2,所以不满足条件1。

对于两个偶数,不满足条件2。

那么我们需要建立一个结点,权为所有奇数之和,表示所有奇数全部选取。而对于每个偶数,权为自己。而所有奇数,权为自己的相反数。之后对于所有满足两个条件的偶数x和奇数y,从x连一条边到y。

BZOJ1001

问题要求我们求最小割。但是数据量是百万级的,最大流过不了。但是网络图是平面图,因此我们可以转换为对偶图后,在对偶图上跑最短路算法通过。

BZOJ2127

容易想到最大权闭合图的解法,一开始认为所有人都选文科。之后选理科就必须放弃一些快乐并得到一些快乐。但是这样做需要建立6倍的结点,会超时。

最大快乐实际上对应放弃的快乐最小,以快乐的大小为边的容量,之后最小割。对于任意人,与源点建立一条边,边的容量为选文科得到的快乐,同样与终点建立一条边,边的容量为选理科得到的快乐。对于任意相邻的两个人u,v,一起选文科的快乐记为h,那么建立容量均为h/2的边(s,u),(s,v),(u,v),(v,u)。

BZOJ2132

题意

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

题解

最大收益等于总收益减去最小损失。比较明显的最小割问题,将损失建边,之后割去的边表示实际发生的损失。需要注意的是如果我们对于相邻结点之间的边,意思是二者取不同值时的损失,这实际上是不对的,因为取不同值时只有收益。我们需要将图中按下标和的奇偶性将结点分为两类,这两类结点对应的是二分图,同类结点之间没有边。之后将下标和为奇的结点的工业区和商业区的语义互换,即在这类结点上建立商业区,实际上建立的是工业区,而反之亦然,这样相邻块中的边意思就是建立不同的区的损失,而这实际上对应原图建立相同的两个区减少的收益。

最后还需要注意割去的边一定是双向边,如果你只会建单向边,那么可以建立一个容量为权的两倍,而流量为权的单向边,这在残存网络实际上就是双向边。

BZOJ1189

题意

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

题解

二分时间,用最大流求解。需要注意的是每个门每个时间点需要建立一个结点,这样才能保证一个门同一时间点只能有一个人通过。

BZOJ1305

题意

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

题解

很显然是一个匹配问题,解决匹配问题就需要用到最大流算法,需要想的就是怎么建图。二分结果t后,我们就只需要判断是否可以组成t个舞曲。将每个男孩和女孩分裂为t个顶点,第i个表示第i首舞曲对应的男孩和女孩。之后实际上就是二分图匹配了。用最大流而非匈牙利算法可以有效减少边和点的数目。

BZOJ3170

题意

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

题解

距离是切比雪夫距离,非常难算。但是如果距离是曼哈顿距离的话,似乎就非常简单了。我们可以先将切比雪夫距离转换为曼哈顿距离(如何转换见切比雪夫距离这一段)。之后假设我们选择$(x_0,y_0)$作为集合点,那么总路程为:

\[\sum_{i=1}^n(|x_i-x_0|+|y_i-y_0|)=\sum_{i=1}^n|x_i-x_0|+\sum_{i=1}^n|y_i-y_0|\]

可以发现x和y坐标可以分开计算,而计算单一维度非常简单,这里不赘述。

BZOJ1337

题意

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

题解

我们可以枚举圆心坐标来求最小半径。当圆心坐标确定时,计算半径时间复杂度为$O(n)$。

记$f(x,y)$表示以(x,y)为圆心时的最小半径。容易发现当x或y一者固定时$f(x,y)$是单峰函数。记$f_X(x)=\min_y(f(x,y))$,容易看出$f_X$也是单峰函数。因此我们需要做的就是三分套三分,分别枚举圆心的横坐标和纵坐标,总的时间复杂度为$O(n(\log_2M)^2)$,其中M是最大坐标。

题目的实际数据量好像并不大,估计只有几千左右。所以速度不是很重要,精度要调整的小些。

BZOJ1052

题意

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

题解

由所有点可以确定唯一的面积最小的矩形R,包含所有点。

先考虑只有一个正方形的情况,这时候边长一定是R的长。

再考虑两个正方形的情况,如果四边形边长小于R的长,那么我们可以保证两个四边形分别与R的两条边接触,即两个四边形落在R的两个对角顶点上。

考虑三个正方形的情况,如果四边形边长小于R的长,那么我们能保证至少一个四边形落在R的一个顶点上。这是必然的,不然所有四边形最多与1条R的边接触,那么有一条R的边将没有与任何四边形接触,即有点没被覆盖。我们可以枚举四个角的情况,用掉一个正方形,接着就是用两个四边形覆盖未被覆盖的顶点的情况了。这总的时间复杂度是$O(n)$。

容易发现随着正方形边增大,覆盖从不可能转换为可能。因此可以二分。总的时间复杂度为$O(nlogn)$。

BZOJ1069

题目

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

题解

四个点一定落在外部凸包上,这个自己在纸上画画就可以得出结论了。

我们可以枚举四边形的一条对角线,这条对角线将四边形分为两个三角形的和,即我们需要去对角线的顺逆时针方向分别取一个点,之后形成两个三角形。

由于这两个三角形可以独立求解,这里总的时间复杂度就已经被优化到了$O(n^3+n\log_2n)$了,是否还可以继续优化呢。

我们可以仅考虑包含顶点i的对角线,这样我们可以利用旋转卡壳算法来计算距离对角线最远的对角线两端的顶点,因此处理包含特定顶点的所有对角线确定的最大四边形,只需要$O(n)$的时间复杂度,总共有$n$个点,因此总的时间复杂度为$O(n^2)$。

BZOJ1074

题目

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

题解

折叠后的图形不一定是凸多边形,因此不好维护。我们可以这样考虑,假设只折叠一次,那么打的这个点会对应原图的两个点,这两个点一个对应原来的点,一个对应沿折叠线镜像的点。如果折叠多次,可以按这个思路不断拆开图纸就可以了。

我们可以用矩阵实现坐标变换,以折叠的起点为原点,以折叠的起点到终点的线为x轴。这样建立坐标系后,对于每个点,我们可以将该点从标准坐标系转换到我们的自定义坐标系,如果转换后的点的y值大于等于精度,那么它对应拆开图纸后的两点,否则没有在图纸上留下任何点。

BZOJ1102

题目

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

题解

沿着y=x的线,将一侧的顶点全部翻转到另外一侧,这时候得到的是周长最小的矩形。如果不理解,可以自己画一下图。

BZOJ1100

题意

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

题解

每个顶点都包含三个信息,顺时针边长,逆时针边长,以及角度。

假设存在对称轴,那么这意味着从对称轴开始,顺逆时针遍历可以得到完全一致的顶点序列。即该序列是回文。

我们可以将顶点序列表示成字符串,寻找对称轴视作在字符串中找指定长度的回文。这部分可以用哈希算法实现。

BZOJ1004

题意

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

题解

题目中少了重要条件,m个置换加上不变置换能构成置换群。之后Polya定理解之。

BZOJ5093

题目

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

题解

先推出公式,记$f(n,k)$为我们要求的:

\[f(n,k)=\sum_{E}\sum_{i=0}^n(\sum_{(i,j)\in E}1)^k\\ =\sum_{i=0}^n\sum_{E}(\sum_{(i,j)\in E}1)^k\\ =\sum_{i}^n\sum_{j=0}^{n-1}j^k{n-1\choose j}2^{n\choose 2}\\ =n2^{n\choose 2}\sum_{j=0}^{n-1}j^k{n-1\choose j}\]

接下来我们计算

\[\sum_{j=0}^{n-1}j^k{n-1\choose j}\]

套入第二类斯特林数定义:

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

得到:

\[\sum_{j=0}^{n-1}j^k{n-1\choose j}\\ =\sum_{j=0}^{n-1}{n-1\choose j}\sum_{i=0}^k \begin{Bmatrix} k\\ i \end{Bmatrix} j^{\underline{i}}\\ =\sum_{j=0}^{n-1}{n-1\choose j}\sum_{i=0}^k \begin{Bmatrix} k\\ i \end{Bmatrix} {j\choose i}i!\\ =\sum_{i=0}^k \begin{Bmatrix} k\\ i \end{Bmatrix} i! \sum_{j=0}^{n-1}{n-1\choose j}{j\choose i}\]

考虑形如 \(g(n,i)=\sum_{j=0}^n{n\choose j}{j\choose i}\) 的组合数的意义,其等价于从n个标记为0的石头中取任意块,之后标记为1,之后从取出的j块石头中再取i块,标记为2。问有多少种标记法。我们可以提前从n块石头取出i块石头标记2,之后其余n-i块石头可以标0或标1。因此总共取法为 \({n\choose i}2^{n-i}\)

代入简化公式得到:

\[\sum_{j=0}^{n-1}j^k{n-1\choose j}\\ =\sum_{i=0}^k \begin{Bmatrix} k\\ i \end{Bmatrix} i! {n-1\choose i}2^{n-1-i}\]

其中斯特林数可以通过快速卷积得到。总的时间复杂度为$O(k\log_2k)$。

BZOJ2190

题意

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

题解

对于n,我们标记左下角左边为(0,0),右上角坐标为(n-1,n-1)。

那么我们可以逐点统计,对于点(i,j),其中i>0且j>0。若gcd(i,j)>1,则与(i/gcd(i,j),j/gcd(i,j))处于一条线上,因此我们可以仅仅统计这些互质的坐标对就可以防止重复统计问题。

但是总共有$n^2$个坐标,这有点多了,所以我们需要用别的方式进行加速。不说废话,直接列式子:

\[\sum_{i=1}^n\sum_{j=1}^n[gcd(i,j)=1]\\ \Rightarrow \sum_{i=1}^n\sum_{j=1}^n\sum_{d|gcd(i,j)}\mu(d)\\ \Rightarrow \sum_{d=1}^n\,u(d)\sum_{d|i}\sum_{d|j}1\\ \Rightarrow \sum_{d=1}^n\,u(d)\sum_{i=1}^{\lfloor \frac{n}{d} \rfloor}\sum_{j=1}^{\lfloor \frac{n}{d} \rfloor}\\ \Rightarrow \sum_{d=1}^n\lfloor \frac{n}{d} \rfloor^2\,u(d)\]

这里莫比乌斯函数可以用欧拉筛预先处理,总共循环n次,时间复杂度为$O(n)$。

BZOJ2818

题意

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

题解

记P为所有小于等于N的素数的集合,那么题目要我们求得是:

\[\sum_{p\in P}\sum_{i=1}^n\sum_{j=1}^n[gcd(i,j)=p]\\ \Rightarrow \sum_{p\in P}\sum_{i=1}^{\lfloor n/d \rfloor}\sum_{j=1}^{\lfloor n/d \rfloor}[gcd(i,j)=1]\\ \Rightarrow \sum_{p\in P}\sum_{i=1}^{\lfloor n/d \rfloor}(\sum_{j=1}^{i}[gcd(i,j)=1]+\sum_{j=i+1}^{\lfloor n/d \rfloor}[gcd(i,j)=1])\\ \Rightarrow \sum_{p\in P}(\sum_{i=1}^{\lfloor n/d \rfloor}\sum_{j=1}^{i}[gcd(i,j)=1]+\sum_{i=1}^{\lfloor n/d \rfloor}\sum_{j=i+1}^{\lfloor n/d \rfloor}[gcd(i,j)=1])\\ \Rightarrow \sum_{p\in P}(\sum_{i=1}^{\lfloor n/d \rfloor}\varphi(i)+\sum_{j=2}^{\lfloor n/d \rfloor}\sum_{i=1}^{j-1}[gcd(i,j)=1])\\ \Rightarrow \sum_{p\in P}(\sum_{i=1}^{\lfloor n/d \rfloor}\varphi(i)+\sum_{j=2}^{\lfloor n/d \rfloor}\varphi(j))\\ \Rightarrow \sum_{p\in P}(2\sum_{i=1}^{\lfloor n/d \rfloor}\varphi(i)-\varphi(1))\\\]

我们可以用线性筛预处理欧拉函数,之后累计前缀后。之后遍历所有小于等于N的素数,累加就好了,实际复杂度O(N)。

BZOJ1968

题意

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

题解

由于n非常小,所以解法很多。

解法1。

\[\sum_{i=1}^nf(i)=\sum_{i=1}^n\sum_{d|i}1=\sum_{d=1}^n\sum_{i=1}^{\lfloor n/d \rfloor}1=\sum_{d=1}^n\lfloor n/d \rfloor\]

之后可以暴力计算$O(n)$或数论分块$O(\sqrt{n})$。

解法2。

很容易发现函数$f$是积性函数,因此利用素数筛在线性时间复杂度内筛出,最后加总就好了。

BZOJ3505

题意

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

题解

先考虑这样一个问题。点(x,y)与原点(0,0)构成的线段上有多少个坐标为整数的点。当(x,y)=(0,0)时,显然只有一个点。现在假设x>0且y>0,那么一共有1+gcd(x,y)个点。

接下来我们要定义函数$f(x,y)$表示从点(x,y)到点(0,0)的线段上坐标为整点的点的数目(不包括两端),可知$f(x,y)=0$当(x,y)=(0,0),否则$f(x,y)=gcd(x,y)+1$。

要计算有多少个三角形,可以通过选取三个点的可能数减去三点共线的情况。三点共线的情况可以通过下面方法得到,枚举所有的点对,统计点对组成线段上有多少个整数点(不包含两端)。可以直接给出公式: \(\sum_{i=0}^n\sum_{j=0}^mf(i,j)(n-i)(m-j)([i\neq0\land j\neq0]+[i\neq0\lor j\neq0])\) 枚举一下就好了,时间复杂度为$O(nm\log_2n)$。

BZOJ4870

题意

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

题解

记从k个元素中取任意数目的元素为一次操作。记向量f(i),其第j个元素表示经过i次操作后总共取得的元素的数目模k是j的取法数目。可以推出$f(i+j)=f(i)\times f(j)$,这里的乘法指的是卷积。由于卷积运算符合结合律,因此我们可以用类似快速幂的方式计算$f(n)$。

共发生$O(\log_2n)$次卷积,每次的时间复杂度为$O(k^2)$。因此总的时间复杂度为$O(k^2\log_2n)$。

BZOJ4773

题意

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

题解

首先为了保证单调性(即存在长度为L的负环就一定存在长度为L+1的负环),我们为每个顶点建立一条长度为0的子环。

记f(i)为矩阵,矩阵中第x行第y列元素表示的是从x出发到y的长度为$2^i$的路径最小总权值。

之后我们处理10个比特位,二分判断每个比特位是否允许为0。从而得到最小的负环长。

BZOJ3098

题意

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

题解

随机生成长度为n的字符串。要求计算有多少种不同的长度为m的字符串。设Hash时模去的素数为p。

对于两个不同的字符串,发生误判的概率应该为$\frac{m}{p}$,总共有$n-m$种不同的字符串。而根据生日悖论知道,需要$\sqrt{p/m}$种字符串才能保证发生至少一次误判。

\[\sqrt{\frac{p}{m}} < n\Rightarrow p<mn^2\]

我们知道增大m的价值不大,而减少m可以有效的提高$n^2$,因此让m尽可能小,只要保证哈希值足够超出p就可以了。

BZOJ1031

题意

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

题解

很显然,问题要我们对所有可能的序列进行排序。想到对子串进行排序,应该能想到后缀数组吧。但是问题中是对序列进行排序,而非后缀,我们可以将输入字符串s变为s+s。之后如果两个后缀的第一个字符下标均小于|s|,那么此时二者的顺序取决于第一个不同的字符,如果这个字符离第一个字符距离超过|s|,那么二者顺序不影响结果,否则这个字符将决定二者的正确顺序。

之后直接用height数组,搞搞最长公共前缀就可以了。

BZOJ1014

题意

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

题解

判断最长公共前缀,可以用二分加哈希的方法快速计算。但是我们发现字符串是会改变的,因此不能提前算哈希值。我们可以将字符串放在平衡树上维护,pushUp时重新计算哈希值,这样不仅支持修改新增操作,而且每次查询某段区间的哈希值的时间复杂度都被优化到了$O(\log_2n)$。

BZOJ2330

题意

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

题解

建立差分约束系统求解。这里需要注意的是,我们要求至少准备多少个糖果,即要最小化糖果总数。而我们通过差分约束系统求解得到的是最大化。因此我们需要建立辅助变量。原始变量记为$a_i$,而辅助变量记为$b_i$,使得$b_i=-a_i$。之后我们要建立的是$b_i$的差分约束系统,求得最优解后取反就是需要的最少糖果数。

为了保证每个$b_i$都一定要小于等于0,我们需要建立一个超级源点,并加入约束条件$b_i-s\leq 0$。之后搜索以s为源点的最短路。但是实际上,理解s真正起到的作用,由于s只有出边没有入边,我们可以去除s,而将所有其他结点的初始距离设为0即可。

还有需要注意的是数据有毒,在负环的时候spfa会被卡,需要使用深度优先版本的spfa。

BZOJ1013

题意

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

题解

假设圆心为$(x_1,x_2,\ldots,x_n)$,那么对于任意球面上的两个点a和b,一定有:

\[\sum_{i=1}^n(x_i-a_i)^2=\sum_{i=1}^n(x_i-b_i)^2\\ \Rightarrow \sum_{i=1}^n((x_i-a_i)^2-(x_i-b_i)^2)=0\\ \Rightarrow \sum_{i=1}^n(b_i-a_i)(2x_i-a_i-b_i)=0\\ \Rightarrow \sum_{i=1}^n2(b_i-a_i)x_i=\sum_{i=1}^n(b_i-a_i)(b_i+a_i)\]

有n(n-1)个组合,可以发现实际上是要求我们求解线性方程组,用高斯消元就好了。解题的时候注意控制精度。

BZOJ1299

题意

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

题解

直接说结论。对于集合S,如果存在一个非空子集C,使得集合中元素的亦或和为0,则先手获得胜利。

先说原因,如果确实存在这样的子集,那必然存在这样一个最大子集C',使得C'的补集中不存在这样的亦或和为0的子集。先手的人将子集C'全部选出。之后如果后手的人吃掉巧克力,先手的人始终可以保证被选出的巧克力的剩余长度的亦或和始终为0。那么如果后手的人从盒子中选出新的巧克力,那么先手的人只需要吃掉多余的巧克力保证被选出的巧克力长度亦或和为0即可。

而实际实现,要判断这样的S的非空子集是否存在,只需要判断集合是否线性无关,用线性基就好了。

BZOJ1188

题意

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

题解

把豆子视为棋子,而豆子所在的瓶子视作棋子的值。之后就是经典的棋子分裂问题了。由于数据量比较小,所以最有解以及解法都可以通过暴力枚举得到。

BZOJ2463

题意

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

题解

如果n为偶数。那么棋盘一定可以被2*1的骨牌覆盖。先手的人每次走到所在骨牌的另外一端,那么后手只能进入新的骨牌。同理如果n是奇数,从棋盘移除左上角点后的剩余位置可以被骨牌覆盖。

BZOJ1022

题意

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

题解

神奇的博弈问题。

首先考虑所有石头堆数量都是1的情况,这时候很显然先手获胜当且仅当堆数是偶数。

假如存在至少一堆石头,数目多于1,记符合条件的堆数为m。如果m为1,那么先手必胜,因为它可以选择拿光这一堆石头,或者留下一个石子,这样就可以决定石头堆数的奇偶性。

下面直接给结论,如果m>=1,那么先手胜当且仅当SG函数非0。当m=1时,结论显然成立。下面仅考虑m>=2的情况。如果SG函数非0,我们始终可以通过一步将将SG函数转换为0,此时m一定大于1,因为m为1时SG函数一定非0。而如果SG函数为0,我们只能移动到SG函数非0的状态,且此时m依旧大于等于1。因此可以通过归纳法证明结论的成立。