Codeforces 938D
题意：给出一张无向带点权带边权图，你需要对于每个点$i$求出$min(2dis_{i,j}+1|j \in E(i, j))$

此做法不是最短路的思路，只是利用dij的松弛来解带环DP
显然这题的转移方程如题所示。

Bzoj 2120
带修莫队基础题，见此处讲解

模板及讲解

莫队是什么

莫(膜)队是离线处理区间问题的一大武器，由莫队发明，其核心为最优化分块思想排序，用已知区间推区间的算法。

莫队解决什么问题

1、无修改或者修改不苛刻
2、离线
3、能用很小的复杂度从$[l,r]$转移到$[l-1, r], [l, r-1], [l+1, r], [l, r+1]$，例如$O(1), O(logn)$

莫队的实现

例题：Bzoj 1878

HH 有一串由各种漂亮的贝壳组成的项链。HH 相信不同的贝壳会带来好运，所以每次散步完后，他都会随意取出一段贝壳，思考它们所表达的含义。HH 不断地收集新的贝壳，因此，他的项链变得越来越长。有一天，他突然提出了一个问题：某一段贝壳中，包含了多少种不同的贝壳？这个问题很难回答……因为项链实在是太长了。于是，他只好求助睿智的你，来解决这个问题。

暴力

暴力是显然$O(n^2)$的，我们想想暴力是否会有很多重复的计算，比如说
$[1, 6]$和$[2,7]$，暴力会算$11$次，而实际需要那么多次吗？当然不需要，我们直接在询问$[1, 6]$基础上删掉$1$处的贡献，增加$7$处的贡献就可以得到，只用算$8$次。这就是莫队的思想。

一些Trick

1、偶数表示为$2n$, 奇数表示为$2n + 1$
2、正难则反(教材全解必修1 p11 例2)
3、十字相乘解形如$px^2+ax+q=0$的方程
4、集合元素有互异性，可以判断不相等的情况(教材全解必修1 p17 t12)
5、$\in N$或者$\in Z$有分数要讨论奇偶性(教材全解必修1 p20 例5)
6、集合一般能化简就要化简做
7、方程条件转化为范围条件：$px^2+rx+q=0 →(x_1 - a)(x_2 - b) < 0$
8、对勾函数解析式：$f(x)=x+\frac ax$，极值点在$\sqrt a$

集合

分类讨论思想

对应性：教材全解必修1 p13 例8, 教材全解必修1 p17 t12
多情况：教材全解必修1 p15 考例1，教材全解必修1 p16 考例2，教材全解必修1 p16 考例3
正负性：教材全解必修1 p17 t4
方程根：教材全解必修1 p13 例9
分段：教材全解必修1 p21 变式3

集合的含义及表示

元素与集合的关系

构造题

此类题目一般要求某些元素是否是属于某个集合，一般要构造成与条件形式相同的形式。

第一问构造平方差，第二问构造与条件形式相同的形式：教材全解必修1 p11 例1，教材全解必修1 p17 t6

循环带入题

此类题目一般是将代数式循环带入后形成周期。

若$X \in M$, 则$\frac{1+a}{1-a} \in M$，求集合$M$的元素个数/证明集合中各数不同
教材全解必修1 p11 变式1

Codeforces 919D
题意：给出一个有向图，每个点有一个小写英文字母，求一条路径使得路径上有一种字母数出现频率最多
这题如果不是图可以想到DP，设$dp(i,j)$为在$i$处，$j$字母时的最大值
放在图中，如果想DP，又不保证是DAG，那么就要用拓扑序来无后效性转移

ps: 图中要判环的一般是SPFA，拓扑排序，DFS

Codeforces 915D
题意：给出一个有向图，这个图有可能有一条边删去后整幅图变为DAG，求该图是否能变成DAG。
环可以想到拓扑排序，但$m$大，不能枚举边去删。删边的本质在拓扑排序中就是入点的入度减一，所以枚举每一个点入度减一，然后拓扑排序看是否有环，就可以判断了

模板及讲解

分块是什么

主体思想是把序列分块每块长为$\sqrt n$，然后进行处理
(一般是考虑1.处理不完整块2.处理完整块3.预处理的三种情况)。
分块的调试检测技巧：可以生成一些大数据，然后用两份分块大小不同的代码来对拍，还可以根据运行时间尝试调整分块大小，减小常数。

Codeforces 898E
题意：给出一串数字，可以执行操作每次使一个数减一(数字大于0)或加一，问几次操作能使一半数为平方数，一半不是。
先记录数字中的平方数，如果正好一半，则不需要操作。
否则如果大于一半，则要枚举每个平方数改。注意到除了0要加2才能不是平方数，其他平方数加1都能不是平方数，所以优先修改非0平方数
如果小于一半，则要改最接近平方数的数。怎么找？可以考虑开方。$\sqrt a_i$如果小数部分大于0.5，则最接近$a_i$的数是$\sqrt a_i$的整数部分+1，否则是$\sqrt a_i$的整数部分-1.那么全部算出来排序优先改最接近平方数的数就可以了

Codeforces 894E
题意：给出$n$个点和$m$条有向边和出发点$fr$，求从$fr$出发可重复走的最大边权和，其中一条边如果走了一次边权就会减去当前走的次数，比如$w=56$，走过一次以后$w=56-1=55$，走过两次以后$w=56-1-2=55-2=53$，边权扣到0为止，0边权的边亦可以走。

考虑如果图中有一个强连通分量，那么这个强连通分量的所有边都可以走完(所有边权都为0)，所以考虑缩点。一个强连通分量的所有对答案贡献转为这个 强连通分量点 的点权。

如何计算边对答案的贡献? 可以二分解决，但是我这里运用了离线，先把所有边权存下来排序，然后一直进行$1+2+3+…$来决定每条边能过多少次及贡献。

然后新图就是一个DAG，在DAG上求个最长路即可，但是这幅图既有边权又有点权，所以不要忘记加上点权。

(btw: 人生第一题CFR div2E)

Codeforces 841D
题意：给出一个连通图，每个点有一个权值$d_i$, 只有$0,1,-1$三种值。先在在原图中求出一个子边集使得所有点满足$d_i=-1$或者$i$点的度数模$2=d_i$, 输出任何一个方案。

考虑一条边一条边地加。
首先如果不选一条边，那么$di=-1$或者$di=0$的点能满足题意，因为度数都为0。而$d_i=1$的不满足。所以我们从任何一个点开始DFS(连通图可以选择任意节点)，如果某个点有一个儿子$d=1$，那么这条边必须要反选(之前选就不选，之前不选就选)，然后把儿子的$d$置为0，这个点的$d$取反。(因为多了一条边或者少了一条边，度数奇偶性变化)。最后就是如果节点1的$d=1$，那么没有父亲给他反选，怎么办？我们找到一个$d=-1$的点，然后把这个点到节点1的路径全部反选。这样只有节点1和这个点的奇偶性发生变化，而$d=-1$无视奇偶问题，所以这样就完美解决了。
如果节点1的$d=1$，又没有$d=-1$的点，那么无解