退役前的做题记录

[BZOJ5197][CERC2017]Gambling Guide：期望DP+Dijkstra

令(dis[x])表示从(x)出发到终点的期望距离，显然每个点只能从期望值比它小的点转移，也就是我们希望从小到大计算出所有点的期望值，可以发现这个过程类似于Dijkstra，所以直接开个优先队列像Dijkstra那样处理就好了。

[BZOJ5191][USACO2018FEB]Slingshot：二维数点

由于只能使用一次弹弓，所以根据起点终点和弹弓的起点终点的位置关系分类讨论，一共有(4)种情况加(1)种不使用弹弓的情况，然后对每种情况类似二位数点那样统计最小值就好了，可以使用扫描线+树状数组。

[BZOJ5187][USACO2018JAN]Sprinklers：数学统计

先求出每一列的(top)和(bot)，枚举每一个横坐标，统计的时候用总的减去不合法的。

[BZOJ5186][USACO2018JAN]Cow at Large：点分治

考虑让奶牛的出发点作为根，如果一棵子树的根节点到离它最近的度数为(1)的节点的距离(leq)它到奶牛的距离的话，这棵子树内只需要选择这一个节点就可以了。

令(f(x))表示点(x)到离它最近的度数为(1)的节点的距离，所以对于每个点(x)的答案，就是(sum_{y=1}^{n}[f(y) leq dis(x,y)且f(fa[y]) < dis(x,y)])，我们希望每个合法子树只在它的根节点处被统计一遍。有一个很厉害的式子，就是若一棵子树节点数为(n)，因为：

[sum_{i=1}^{n}deg[i]=2n-1 ]

所以有：

[sum_{i=1}^{n}2-deg[i]=1 ]

把这个东西套在这道题的式子里面，就是：

[sum_{y=1}^{n}[f(y) leq dis(x,y)](2-deg[i]) ]

求这个东西可以用点分治解决。

[UOJ#449][集训队作业2018]喂鸽子：min-max反演+DP+NTT

对题意min-max反演后，我们要求的东西变成了(n)只鸽子中的(m)只第一个吃到(k)个玉米的期望时间。

考虑DP，令(f[i][j])表示(i)只鸽子(k)次后不存在鸽子吃到不少于(k)个玉米，这个DP可以使用NTT加速转移，然后用计算好的(f)数组推出上面那个问题的答案即可。

时间复杂度为(O(n^2k log(nk)))。

[BZOJ5250][九省联考2018]秘密袭击：树形DP

正解暂时学不来，所以先写了一个暴力。

枚举每个(k)大值所在的节点，以它为根跑树上分组背包即可。

[BZOJ4872][六省联考2017]分手是祝愿：莫比乌斯反演+DP

这里的异或可以看作是模(2)意义下的加法，然后直接莫比乌斯反演可以知道最少需要进行多少次操作。

令(f[i])表示最少还需要进行(i)次操作时仍需进行操作次数的期望值，可以列出DP方程：

[f[i]=frac{i}{n}f[i-1]+frac{n-i}{n}f[i+1]+1 ]

也就是：

[n imes f[i]=i imes f[i-1]+(n-i) imes f[i+1]+n ]

这个东西没法直接做，但是我们可以稍微转化一下，令(g[i]=f[i]-f[i-1])，(g[i])是可以(O(n))递推的，再用(g[i])推出(f[i])即可。

[BZOJ4284]自古枪兵幸运E：生成函数

写出两种物品的生成函数，乘起来就是：

[egin{aligned} &(frac{1}{1-x})^n(frac{1}{1-x^2})^m\ =&(frac{1}{1-x^2})^{n+m}(1+x)^m\ =&(1+x)^m(1+x^2+x^4+...)^{n+m} end{aligned} ]

枚举左边(x)的次数，用隔板法算右边即可。

[BZOJ5412]circle：拓扑排序+DP

竞赛图有一个性质，其拓扑序靠前的点一定能够到达拓扑序靠后的点，或者可以说它的拓扑序是成一条链的。

对(k)个点和(n-k)个点分别拓扑排序，对(n-k)个点中的每个点(i)，记(l_i)为(k)个点中直接连向(i)的编号最大的点的编号，(r_i)为(k)个点中(i)直接连向的编号最小的点的编号。如果(l_i > r_i)，那么显然必须删除点(i)，否则的话，对于(i < j)，(i)和(j)能同时不被删除的条件是(l_i<r_{i+1})，DP即可。

[BZOJ5244][FJWC2018]最大真因数：min_25筛

在min_25筛第一次处理中减去最小质因子为(P_i)的数的贡献那里统计答案即可。

[BZOJ5254][FJWC2018]红绿灯：set

使用std::set维护所有询问的答案，从左往右扫所有的红绿灯，每次将所有要等红绿灯的询问暴力合并即可。

[洛谷P3731][HAOI2017]新型城市化：匈牙利算法+Tarjan

可以发现补图中的一个独立集对应原图中的一个团，因为原图可以恰好被划分为两个团，所以补图一定是一张二分图。

我们要使补图的最大独立集变大，也就是要使补图的最大匹配减少，所以找出所有二分图最大匹配的必需边即可。

[CodeChef]PUSHFLOW：Link-Cut Tree

可以发现如果流经过一个环，那么最多会分为两股流，且经过了环上容量最小的边的那股流的流量上界是确定的，所以我们可以把这条容量最小的边断开，给环上其他的边的容量加上这个最小的容量就好了，使用LCT动态地维护这个过程即可。

[BZOJ1426]收集邮票：期望DP

令(f[i])表示现在已经取出了(i)种邮票，到取完的期望次数，(g[i])表示现在已经取出了(i)种邮票，代价从(1)开始计算，到取完的期望代价。

(f[i])可以很容易地通过反着递推求出，求(g[i])的话也是反着DP，要考虑花费多少代价取出第(i+1)种邮票，分析过程中要用到错位相减法。

[BZOJ1283]序列：最小费用最大流

这种题的一个小套路就是可以转化为选(k)次，每次选出的任意两个数之间的距离不得小于(m)，然后跑拆点费用流就好了，注意如果有一次选出来的数之和为负就return;掉。

[BZOJ2687]交与并：决策单调性优化DP

把被其他区间包含的区间删去（这时也需要统计答案），剩下的跑个决策单调性优化DP就好了，虽然还是不太会证明决策单调性。