http://codeforces.com/contest/1064/problem/D
这个题最操蛋的是我把复杂度弄错了导致没有敢写暴力。。不过官方并没有出题解所以我也不知道我的做法是否可行，只能说通过了目前的所有数据。
做的思路就是求出来原点到每个点所用的最小的left和最小的right，求的方法就是暴力bfs，但是这里有个问题是有可能会有一个点可以通过多条路径到达，那么该如何确定最小值？如果直接裸搜不打标记会使得无限循环，如果打标记则会使得多种可能没有考虑，我这里用了一个玄学剪枝就是当当前点的下一个点的数据有被更新的时候才加到queue里，否则就不加，可以保证去掉了很多无用的扩展也可以保证搜索可以结束。另外一个优化是加了点是否已经在queue内的判断，可以避免多余的入队操作（这个貌似也可以用在一般的dij里啊）
这个题wa到最后才意识到是dfs刷表的思想本身是错误的，必须按照拓扑序来处理，这两个是不等价的。不等价的原因是dfs可能会多次刷到同一节点而且这个节点的父节点还没有完全确定下来。比如当某个节点只有一个父节点的时候，本来dfs给了他1，也就是必胜态，但是如果某一次之后的刷新把父节点变成了1，那么由于该节点只有一个父节点所以他只能变成0。而原来写的dfs不能解决的就是这样一个问题：对于一个节点来说，是不是所有的父节点都是1或者至少有一个0，因为单纯的dfs可能会求很多遍这个点（如果不这样又没办法更新），如果用拓扑序的话就可以保证在搜到一个点的时候这个点的父节点已经全部搞定了，这也跟拓扑序处理的时候每次只走“一步”有关系。这样的话就可以保证不会有多余的1没有变成0了。
http://codeforces.com/contest/1013/problem/D
题意：每次可以从矩形的3个角产生第4个角，问至少需要添加多少个方块可以使得让整张图都充满方块。
自己想的是奇怪的思路，因为发现一个联通的块可以扩展到这个块的maxx，maxy，但是之后就不知道怎么做了。看了题解才恍然大悟，原来是把坐标转化成二分图的左右节点，然后考虑连通分量的个数就可以了。证明的时候，首先注意到一点就是二分图中两个点之间的路径个数一定是奇数，对于同一个连通分量中的左右两个点x，y，他们之间的距离如果是1的话那说明二者之间一定有了一条路径了，也就是这个点已经有一个方块了，如果不是1那么至少是3，每次取距离y最近的3个点，按照题目中给的性质，就可以生成一条新的边，也就是从倒数第四个直接联到y，这样的话，每次边的数量都会-2，到最后一定能减少到1，回到之前的情况。所以在同一个连通分量里的左右所有的点一定能连到一起，也就是说所有的方块一定能被涂上。这时候等于说连通分量和能全部染色等价了，我们就只需要计算出来最少需要多少条边使整个图成为连通图就行了。。其实也就是 连通分量数-1
wa点的话因为把n+m写成了2*n错了还以为横纵坐标是一样大的。。。愚蠢的错误emmmm
http://codeforces.com/contest/1040/problem/E
这个做法最重要的是原本的每一条边两端点一定不相等，所以两个点如果同时被异或结果一定仍然不相等。 然后就是考虑一个点被异或另一个点没有被异或的情况，一开始觉得会很复杂？但是实际上不是这样的，远没有想象中的复杂： 当x确定的时候，只有a⊕b==x的那些边会受到影响，这些边必须同时被选中，而剩下的，无所谓。。所以就把这些边连起来的点缩点之后就成了2^q的选择方式了。。
实现细节：①会卡并查集退化，所以必须写按秩合并 ②每次只要记录下被改动的点，然后下一次把这些点并查集复原即可，否则由于并查集的初始化时间复杂度会退化。
http://codeforces.com/contest/1038/problem/E
“这题有点难受”系列。之所以能这么O(n)做完全是有且仅有4个点，玄学。
其实也不是很难受，主要是最后一组测试(test 117)让我意识到原来的处理方法对于那种特殊情况都不适用，然后感觉在这时候只能用n²算法才能解决。。。想了很久反正是，最后终于发现当（奇点数==4&&删去最小边会使得4个点不联通）这种情况只有两种，一种是三个点连成环然后剩下一个挂在外面，另一种是1到2和3到4有1条边，而2到3有两条，所以只要把这两种情况特殊判断一下就还是O(n)的算法了。。
正经地说：把1234看成4个点，n个block相当于边，题目意思就是找出一条最长的路使得每条路都只能走一次，无向图只能走一次，很显然的欧拉路径的操作。但是要分很多情况讨论。
首先分连通分量有几个的时候，当有2，3，4个的时候就是找到这几个连通分量中的最大值，因为这时候每个联通分量都一定是有欧拉路径的，3的时候可能比较难证明，但是可以通过4个点组成的图奇点只有024三种可能推出来。
然后当只有一个连通分量也就是四个点都联通的时候，讨论奇点数量，前面已经说过奇点数量只可能是024，当是02的时候直接全选因为一定有欧拉路径，当是4的时候再分类讨论：找权值最小的那条边，看他是不是去掉后会使得多出来一个连通分量，说是多出来一个联通分量其实只有可能是多出来一个孤立的点，因为其他情况都与（4个点都是奇点）这个条件相矛盾，所以删除这条边如果能使得原图不连通那么一定是分成了一个3个点一个1个点，这里面又有两种具体的情况，也就是之前说的，一种只有一个桥另一种有两个桥，如果不是这两种情况那么直接取全部的边然后删除掉最小权值边，如果是这两种情况则单独特判即可。。需要注意的是这两种情况需要循环一遍所有的边来确定最大值，因为删除的可能是其他的边也可能是桥。
https://hihocoder.com/problemset/problem/1457
要求求出来n个串中所有子串的十进制和。
考虑单个串的情况：顺着sam的边走的话，一个点的所有字串等于它所有的父节点的字串+c，c为从父节点转移来的路径字符，由十进制的性质可以知道当前节点（设为st）的和为则求出sam状态转移图的拓扑序然后刷sum即可；
多个串的情况：考虑把多个串合并为1个串，每两个串之间以‘9’+1填充（也就是: )，然后建立sam。此时要求出sam每个状态中有多少个不含：字符的子串，这里用到了一个性质就是，这个值恰好就是从初始状态S到状态st的所有”不经过冒号转移的边”的路径数目，而有向无环图上的路径数目也是一个经典的拓扑排序问题！
由此只需求拓扑序的过程中把有效子串个数求出来就行了。
wa点的话，注意第一次调用sam前要用init函数初始化。另外，拓扑排序无需纠结数据结构条件是指向父节点还是从父节点指向子节点。
继续阅读“[SAM][多串][不同子串十进制求和][拓扑排序] hihocoder #1457 : 后缀自动机四·重复旋律7”
题目链接：http://newoj.acmclub.cn/problems/2053
只要能想到用最小费用最大流去做，建图还是相对好想的：左边n个点表示n根蜡烛，右边n*m个点（或者m个点但是每个点有n条边连汇点，二者是等价的），然后源点连左边n个点之间cost为0容量为1，表示每个蜡烛最多被用一次，然后从左边到右边i到ai所有的n个分点连容量为1 cost为2*k-1的边，最后右边每个点跟汇点连容量为1 cost为0的边，最后跑最小费用最大流即可。
平方费用处理的话也不难毕竟看过lrj书上的处理平方费用的方法。。。这种平方费用的话可以拆点也可以拆边，但是思路都是新弄出来的边cost都是当流量从i到i+1的时候的增量，也就是i^2-(i-1)^2，因为这个差值是随着i增大而增大的，所以最大流增加的时候一定是从小到大选择这些边的，而这些边的cost从小到大依次选择就可以累加出来x^2，也就是与原来的要求等效了。
继续阅读“[最小费用流][平方费用][拆点/边建图] 2018camp Birthday”
比赛时候其实想的就是正解，但是没时间实现了。
这里并不是把猫狗分离开来，而是把voter分离开，换句话说原来的边变成了点，支持猫的在一边，支持狗的在另一边，如果有冲突的话连一条边，这样的话就是求最大独立集了。
本来看这个输入感觉头疼，后来想了想，忽然意识到：1 重复的人可以不用管，照例读入建立点，因为把他变成点之后对图没有任何影响。2 可以不用管字符后的数字，直接把他们当成一个整体就好了，整个字符串比较。 3 建立图的时候可以不用分左右两边，只要i和j有冲突就line[i][j]=line[j][i]=1；这样会使得建图的过程更简单，然后相当于把二分图对称了一下，最后输出的时候最大匹配数除以2就可以了.
思路全在论文里，实现的话费了点功夫。。感觉写这种复杂一点的题，最好还是先把需要用到的变量都写出来，需要的操作都列出来，不然反复修改会浪费很多时间。
需要注意的错误只发现了一个就是在枚举加度的时候可能会出现没边可删的情况（我也不知道为什么），然后这时候我的代码就开始跑环。。因为每次都会新加入一条边，不删边的话必定在树上形成环。后来的策略是一旦当前的操作不再使得生成树变小，那就直接break，因为显然他之后也不会再变小，而且可能之后会出现跑环，而这之前我的代码都是正确的，这样既可以剪枝又可以避免坑。。。 继续阅读“[生成树][treeDP][图论] 最小度限制生成树 POJ1639 Picnic Planning”
