BZOJ 3508
题意：见上。

可以发现这种翻转的题目，如果弄成异或前缀和，那么如果整个序列是0，则灯全灭。
我们相当于将给定要亮着的灯当成初始状态，那么目标就是全关。
考虑异或前缀和两个1就可以消除，用一个BFS算出每个1和其他1消除的代价。
然后之后就是一个两两配对的过程，弄一个状压DP即可。

知识点：
1、异或前缀和

BZOJ 3505
题意：见上。
先将m++, n++，因为格点数要多一个
我们可以先求出所有格点中选3个点的方案，即$C^{3}_{nm}$，然后就只用求出三点共线的三角形个数即可。
对于$k=0, k=INF$的三点共线三角形很好求，$C^{3}_{m} \cdot n + C^{3}_{n} \cdot m$
对于其他直线，我们可以枚举直线来求。枚举直线相当于枚举两个点。

结论：过$(x_1,y_1)$和$(x_2,y_2)$的直线整数顶点数为$gcd(\Delta x, \Delta y)-1$

根据这个性质，我们可以快速求解，但是还是要枚举两个点。我们发现过$(0,0)$点的直线可以平移得到其他直线，所以只用枚举一个点即可。

Codeforces 716D
题意：$n$个点$0~n-1$和$m$条边的无向图，每条边上有一个正权或0，0可以改成任何正权，求一个方案使得$s$到$t$最短路为$L$.
解：考虑将 0 边先全部删除，然后再进行添加。
先对原图进行一次最短路，如果此时$s$到$t$最短路小于$L$，显然无解，如果等于则直接输出
否则我们开始随意加边，加最小正边权为$1$，注意正边权。然后每次加完边以后做最短路，如果当前最短路小于$L$，则可以直接输出了，但是这条边要改成适当的权来使最短路变为$L$。

Codeforces 1064D
题意：给定一个$n×m$的网格图，有若干个点不能走，上下走无限制，向左和向右走的次数分别被限制为$x$和$y$，给出起点并询问有多少个点能够到达。

这题刚开始写了个裸 BFS 然后 FST 了。。原因是直接 BFS 加的维限制但是不让 vis 加维会让路被堵住让能到那个点的路径不能到那个点。

本题方法：
方法1、在原基础上改。开两个数组分别记录到某个点时左右次数还剩下的最大值，然后 BFS 走时判一下大小。感觉容易 FST
方法2、在原基础上改。将队列开为优先队列，然后用 Dij 思想，使得当前枚举的点左次数剩下的最大，相等则右次数剩下的最大，这样来做就不会堵路了，代码为这种方法。
方法3、观察到本题左走次数和右走次数分开走没有关系，最后答案交起来即可。所以我们分别建两个图，一个图对于左走边权为1，右走边权为0，另一个图反之。然后跑 Dij 答案求交
方法4、观察到本题边权仅有0,1，那么可以使用 0-1 BFS，即如果当前边为 0 ，放在双端队列的front，否则为1则放在双端队列的 back，然后照样 BFS 即可。方法与3类似。

知识点：
1、BFS 状态加维，状态也要加维，否则会堵路
2、两个 if 不要乱并，特别在有 else 的情况
3、0-1 BFS 写法
4、BFS 用堆来优化枚举顺序 (Dij)
5、网格图可以连边跑最短路什么的
6、想过的可能 BUG 不要轻易放过

Codeforces 915F
题意：$n$个点的树，每个点有一个点权$a_i$, 计算树上所有路径的权值的$max(a_i)-min(a_i)$和。

考虑对于每条路径先求$max(a_i)$再求$min(a_i)$，这样就分开成了两个问题。
因为是树上计数问题，而且是整棵树的计数问题，所以我们可以想到求每个点对的贡献。现在求最大值，我们将点排序，取最大的点出来，此时它左边点到右边点的路径最大值一定是它。处理完一个以后删掉这个点(删掉这个点的所有连边)，然后继续操作。我们发现连通性可以用并查集维护集合大小。但是这里要删边显然不方便，我们参考星球大战这题将并查集逆向变删除为添加来做就行了。
并查集维护集合大小很简单，见代码。

Codeforces 1059D
题意：给你平面上一些点，你需要找出一个与直线$y=0$相切的圆使得包含所有点。
彻头彻尾的数学题……
显然如果$y$有正有负就不能构造圆使得与$y=0$相切。
考虑二分半径，然后验证答案。
观察可得，与直线$y=0$相切的圆圆心一定在$y=b$上，也就是圆的纵坐标
我们可以尝试枚举所有点，然后在$y=b$上找到一个范围使得在当前半径下都能覆盖这个点，然后取交集即可。
点$(x,y)$范围相当于解圆不等式$(x-a)^2+(y-r)^2 \leq r^2$，我们解得$a=x±\sqrt{2rt-y^2}$，因为这个不等式是关于$a$的一元二次不等式，二次项系数为正，所以我们取$[x-\sqrt{2rt-y^2},x+\sqrt{2rt-y^2}]$，这个就是范围。

注意二分的范围，也就是最大可能半径的计算：
考虑极端情况$(-10^7, 1), (10^7, 1)$，我们过这两点作圆，将这两点连线后再与圆心形成三角形，根据$(r-1)^2+(10^7)^2=r^2$，可解得$r=\frac{10^{14}+1}{2}$，那么这个就是最大的半径长。

还有就是注意还有可能圆心在$y=-b$上，类似地特判一下即可。如果开方里面是负的说明当前半径无解

知识点：1、浮点数比较
2、二分范围千万不要想当然
3、这种几何题和数学相关，也和二分/三分相关

Bzoj 1053
题意：见上。

本题就是一个打表的典型题。但是打表程序很有学问否则你离开考场都打不完表。
最容易想到$O(n \sqrt n)$的暴力，但是对于$2 \times 10^{9}$太慢了。
我们可以运用这个定理：

给出n的唯一分解式 $n = p^{a1}_1p^{a2}_2p^{a3}_3…p^{ak}_k$ , 求出 $n$ 的正约数的个数
根据乘法原理，$n$ 的正约数的个数为
$\prod_{i=1}^{k}(a_i+1)$

然后就可以打质数表进行分解因数。我们发现一个$2 \times 10^{9}$以内的数字不会有超过$12$个质因子，并且小素因子多一定比大素因子多要优，预处理出前$12$个质数即可。

打完表输出即可。打表直接打出反素数即可，反素数个数很少。

Loj 2318
题意：如上。

70 分暴力：
枚举每个点作为起点并加入集合，然后从集合中找点出来拓展节点继续加入集合，然后当图连通以后就更新答案，加上可行性和最优化剪枝。时间复杂度比较高但是能过去，DFS / 搜索 / 枚举不要约束在那个板子上。
刚开始我想到是枚举整个图的生成树子集然后枚举起点计数，这样的复杂度太高了，我们调换一下搜索顺序，即先枚举起点后形成生成树子集后计数，这样免去了计数时增加的 $m$(去重以后) 的复杂度。据说爆搜剪枝剪得好能 AC Orz

100 分状压 DP :
我们发现暴力的方法很多重复的枚举，所以我们尝试在爆搜中加入 DP 思想。本题 $n$ 小并且 $m$ 可以去重，所以就可以状压 DP 了。设$dp(S)$为当前开通的点的集合的最小代价，转移就枚举每一个在$S$中的点然后再找它的邻接点并且邻接点不在$S$后 DP 转移即可。主体程序很像，但是这个方法节约很多时间。

知识点：
1、调换枚举顺序免除一些难处理的
2、时间复杂度感觉会炸不一定会炸，大胆写，但也不要 sb，剪枝写上
3、DFS 不好搜就按点枚举而不是 DFS，DFS 和搜索还是有区别
4、选择转化为添加
5、暴搜可以加入 DP 思想，所以 DP - 爆搜 - 记忆化搜索 三者有着密切关系

Loj 2316
题意：$n$个点，$m$条边的有向图，$1$到$n$最短路为$d$, 求路径长度不超过$d+k$且长度大于等于$d$的路径条数，答案模$p$。
本题 30 分做法直接 Dij 转移时顺带记录最短路条数。$dp(u)$为到$u$最短路$1,u$路径条数, $dp(u)=(\sum dp(v)|dis(1, v)+w=dis(1, u)), dp(u)=(dp(v)|dis(1, v)+w≠dis(1, u))$

考虑 70 分无 0 边，那么我们可以用 30 分做法的 DP 思想来做。这里 $k$ 很小，所以 DP 状态中肯定有一维这个。所以在原基础上加维即可。设$dp(u,j)$为到$u$点$u , n$实际路径长比$u , n$最短路多$j$的路径条数。对于边$(u,v,w)$转移$dp(u,j)=\sum dp(v, j + dis_u - w - dis_{v})。 dis_i$是$(i,n)$最短路，可以记忆化搜索来做。或者如果枚举的顺序就要先更新$dis$ 大的状态，排序以后 DP 即可

然后就是有 0 边了，如果存在一个 0 环，那么这个路径条数将是无限大的，并且记忆化搜索会出现后效性。在记忆化搜索中，如果有一个状态还没有得出值但是被又访问了，那么图中存在 0 环。
也可以将 0 边弄出来单独一个图做拓扑排序，用 0 边的拓扑序来更新，如果拓扑图中出现 0 环，那么原图中也有 0 环。

注意初值的问题，如果让$dp(n,0)=1$，最后答案是$\sum_{i=0}^k dp(1, i)$。如果让$dp(n,i)=1,0\leq i \leq k$, 那么最后答案是$dp(1, k)$。

知识点：
1、最短路计数思想是 DP 思想
2、任何最优化问题/计数问题都可能 DP，只要调换顺序能保证无后效性就能做
3、DP 不想考虑顺序可以用记忆化搜索
4、图中转移和拓扑序有关
5、学一种做法要理解透彻他的思想，Floyd 是一种 DP 思想，本题也是一种 DP 思想
6、数据小的要合理利用这个数据

Codeforces 1000E
题意：一条路径上必经的边为关键边，现在让你找一条路径，使得其关键边最多，输出最多的数量。
关键边就是无向图中的桥。而桥两边连的连通分量里面不可能有关键边(桥)，所以用 Tarjan 缩边-双连通分量，步骤与有向图相似。然后缩点后就只需要找一条路径最长了，因为缩点了所以最后出来的图就是一个树，所以求树的直径即可。
知识点：
1、一样的代码不要复制，手打
2、缩点，树剖，单调队列注意前后序号的不同，一定要一个字符一个字符的查
3、树的直径就是树中最长路径，长度是树中点对最短距离的最长距离
4、无向图 Tarjan 缩连通分量，留下的边是桥