路终会有尽头，但视野总能看到更远的地方。

题目大意

略

题目分析

显然这道题是一道1D/1D动态规划的问题，我们可以尝试写出方程。
显然，我们如果在每一天要买或卖，不会部分操作，肯定要么全部买要么全部卖。

状态转移

那么设第$i$天没有A、B券，可以买入的A、B券分别有$X_i$和$Y_i$个，能够兑换的人民币为$f_i$。
显然有：

题目大意

给定$n$个点，$m$条边的无向图，可以从图中删除一条边，问删除哪些边可以使图变成一个二分图。

题目分析

有关$O(n)$的做法可以见这里->传送门
在这里主要谈一谈CDQ分治的做法。
还记得之前有一道题叫做消失之物吗？

题目大意

给定$n$个点，$m$条边的无向图，可以从图中删除一条边，问删除哪些边可以使图变成一个二分图。

题目分析

二分图不能包含奇环，只能包含偶环，这是二分图的第二定义。
显然，我们要删除的边只能在奇环的交上。
并不显然的还有：要删除的边不能在偶环上。

题目大意

略

题目分析

这题我考试的时候没有看到一个条件啊！！！
对于所有数据，都满足$x1\lt x2 \lt \cdots \lt xn-1 \lt xn,1\le s\le n,0\le L\le n-1$ 。

那这道题其实看完题解后并不是很难。（废话）

比赛题目

A. Fair Game

题目大意： A和B在玩一个游戏，每个人选一个数字，然后取走所有写有这个数字的卡牌，游戏是公平的定义为有一种方案使得A和B可以取走所有卡牌且使得A和B取走的数目相同。
题目分析： Hash判一下如果有两个不同的且个数相同即可判为YES。

题目大意

有$N$个物品,体积分别是$W_1$,$W_2$,…,$W_N$，第$i$个物品丢失了。要使用剩下的$N$-$1$物品装满容积为$x$的背包，有几种方法呢？。把答案记为Count($i$,$x$)，输出$1\le i\le N,1\le x\le M$的Count($i$,$x$)表格。

题目分析

这道题是有$O(nm)$的做法的，但是此处不做解释，可以参考PopoQQQ或hzwer的博客。
我们谈一种普适性更强，思维要求更低的方法：CDQ分治。

题目大意

给定一棵$n$个节点的树，每条边的长度为1，同时有一个权值$w$。定义一条路径的权值为路径上所有边的权值的最大公约数。现在对于任意$i\in [1,n]$，求树上所有长度为$i$的简单路径中权值最大的是多少。如果不存在长度为$i$的路径，则第$i$行输出0。

题目分析

这道题第一眼看成了点分治，然后开始思考如何处理$i$个询问。
嗯？这不是点分治+FFT。
正当我准备开始写的时候，我才发现最大公约数不具有最优合并性。
两个最大公约数合起来说不定更小。

题目大意

动态加点，询问距离一个点曼哈顿距离最近的点。

题目分析

考虑距离点$(x,y)$曼哈顿最近的点$(x0,y0)$。那么曼哈顿距离$\mid x-x0 \mid+\mid y-y0\mid$最小。

讨论四种情况，若点$(x0,y0)$在点$(x,y)$的左下方，则曼哈顿距离转为$x-x0+y-y0=(x+y)-(x0+y0)$。
那么我们就可以统计在$(x,y)$左下方的点中$(x0+y0)$最大的点。
动态加点->维护时间轴，再加上维护$x$、$y$轴，共维护三维偏序，使用CDQ维护。

题目大意

给一个序列，动态删除一些数，求删除元素前整个序列的逆序对数。

题目分析

若不包含删除操作，那此题就是一个二维偏序问题。
满足$i\lt j$且$a_i\gt a_j$的个数，树状数组维护即可。（因为编号已经有序，所以不需排序）

但是我们有删除操作怎么办呢？那么我们加入时间轴代表删除操作，时间轴$t$前表示在执行某次删除操作前的情况。

显然，这是一个三维偏序问题，我们可以用CDQ分治维护时间维。
关于三维偏序可以看这两篇文章：传送门1、传送门2。

题目大意

平面上有n个圆，给定起点和终点，你只能在圆内及圆周上行走，问从起点到终点的最短路程。

题目分析

根据路径规划问题的套路，我们需要把不定的路径转化为定的路径。
考虑哪些路径是一定不会被用到的。

这样的路径一定不会用到，为什么，因为我们把拐点移动到圆的交点处长度一定会变小。