这个题倒是不难，但是我当时对于题目的理解导致写出来很复杂，所以记一下踩的坑。其实就是最短路树的应用，我的想法是先删掉不在树上的边，然后对于树上的边先删除连叶子的边，以此类推。这样写倒是没有错也可以过。
但是！这个题题面里说的是最多k个，所以其实根本不用考虑去掉非树边什么的，假如k>n-1的话只输出n-1条树边也是对的！这就省了好多代码了。其次，根本不用使用拓扑排序那样的处理过程（就是先去掉叶子这种），因为想一下dijkstra的过程就可以发现，每次从优先队列中取出来一个节点后，这个节点的前驱最短路其实已经确定了，只要在这时候把其前驱记录下来，根据dijkstra的每一步往外扩展一步的操作，按照这个顺序搞下去最后的记录表中的顺序其实就是拓扑序。。。。依次输出即可。 继续阅读“[CF][图论][最短路树] codeforces 1076D Edge Deletion”
https://cn.vjudge.net/problem/UVALive-4064
简单的极角排序应用，枚举每个点作为角点，然后按照角度顺时针枚举另一个点，在这个过程中递推记录下对于枚举的点有多少个钝角/直角出现。由于一个钝角/直角唯一的对应一个钝角/直角三角形，因此最后只需要把C(n,3)-钝角数量作为答案即可。
坑点：lrj的书上和各位dalao的blog都说的是锐角或直角，呵呵，wa了两个多小时最后翻别人代码发现是只能锐角不能直角，服了，改了就过了，也不知道网上这么多人都写得锐角或者直角是怎么写出来只能锐角的代码的。
继续阅读“[坑][计算几何][极角排序][利用已有信息] UVALive 4064 Magnetic Train Tracks”
题目链接 https://cn.vjudge.net/problem/UVALive-4080
最短路基础题，有意思的部分在于最短路树这个东西的应用，还有对复杂度的正确估算（莽
看题目意思，基本上能确定枚举那条要去除的边然后算每种情况的c，但是如果直接这样的话复杂度会是n*m²*logn,就题目数据量而言基本上不可能过的。所以就要找其他方法来降低复杂度，考虑到，去掉一条边也许不会对以某些点为原点的到每个点的单源最短路产生影响（也就是不在这些点的最短路树上的边），可以试着预处理出来初始状态下每个边的影响到的点的集合，在枚举到这条边的时候只需要重新计算这些点的最短路而不用每次都计算所有点的最短路，这样的话可以把复杂度降低到n²mlogn。不得不吐槽一下这个解法，说实话感觉并没有降低多少就卡过了时限，数据刻意友好么。。。。比赛的话就算能想到这个也不一定敢写吧emmm
坑点是有重边，果然做图论最重要的是搞清楚图的类型。。。重边啊自环啊什么的真的烦,还有一开始小根堆写成大根堆了，又是wa又是t的 继续阅读“[蓝书][图论][最短路][坑] UVALive 4080 Walfare And Logistics”
https://vjudge.net/problem/UVALive-3295
这个题目和3720很像，尤其是在应用对称性的时候。这种题目有个很有趣的地方就是他每次都是对局部进行刻画然后得到了全局的信息，或者可以这么说，按照某一种策略使得某种属性所有的状态都被考虑进去。在这里就是计算一个共线的点的问题，按照和题目3720算法本身的推其实是只能算出来“斜率为正”的一类斜线，但是算的是“所有的斜率为正”的斜线，也就是覆盖了每一种情况，那么剩下的情况其实只有水平竖直和斜率为负的斜线，但是由对称性可知斜率为负的斜线一定和斜率为正的斜线数量相等，因此只需要*2即可，而我自己一开始一直在纠结的问题就是怎么算出来这些反向斜线，其实最后全局考虑只需要把算出来的正向斜线情况*2即可。最后的结果就是C(3,(m+1)*(n+1))-共线的三点数量。
wa的话有一个问题是，在gcd的算法中如果a和b有一个数字为0那么返回值就会是0，这种情况在这里的递推过程中是会出现问题的，需要注意让循环从2开始，也算是一个小小的坑吧。。以前没有注意到。
http://codeforces.com/contest/1064/problem/E
又是喜闻乐见的交互+二分，这个已经在cf的讨论区被吐槽两次了，每次出交互题都是二分。。。我一开始没有搞懂题意，以为是你随便给他出点它会自动调整让点可以分为两片区域，后来才意识到他是给定了点的颜色分布，就是第几个点你只要问就是安排好的，也就是说这个需要你掌握问的点的坐标。。。
但是在不知道下一个点是什么的时候如何发问呢，首先想简化的过程，如果问的点全在一条线上会发生什么：假设左边为白点右边为黑，那么那个分界线一定是先往一个方向走了几步，然后又得回头往另一个方向走，如此反复。那么如何保证每次“回头”都可以有足够的余地让继续走下去而不与之前定好的界限相交？想到了一个叫二分的东西。。在倍增法的实现里其实就可以发现，他每次都会减半所以每次都不会覆盖到原来的部分。
但是这个题目直接二分又是有问题的，因为最多可以有30个点，而[log2(1e9)]==29，也就是说有一种情况可能最后会有俩点重合，为了避免这种情况可以先ask一个(0,0)，并且以此确定左半边的颜色，而不是像一开始说的一样自己定左右颜色。这样的话就剩下了29个点需要处理了，1e9的范围可以保证无论如何二分都可以达到没有任何两个点重合的结果。这样的话只需要在分界处的两个点之间画一条斜线就可以了。
因为这个29的坑wa了n发。。。
继续阅读“[二分][精度][思维] codeforces1064E Dwarves, Hats and Extrasensory Abilities”
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个点，这里面又有两种具体的情况，也就是之前说的，一种只有一个桥另一种有两个桥，如果不是这两种情况那么直接取全部的边然后删除掉最小权值边，如果是这两种情况则单独特判即可。。需要注意的是这两种情况需要循环一遍所有的边来确定最大值，因为删除的可能是其他的边也可能是桥。
二分答案倒是容易想到，实现的话需要排序后贪心，但是坑在精度上
我用了printf(“%.0f\n”,ans); WA cout<<(int )(ans+0.5)<<endl; AC 就很玄学。。。。学到了学到了
继续阅读“[01分数规划][二分][精度][坑] POJ2976 Dropping tests”
