这个题倒是不难，但是我当时对于题目的理解导致写出来很复杂，所以记一下踩的坑。其实就是最短路树的应用，我的想法是先删掉不在树上的边，然后对于树上的边先删除连叶子的边，以此类推。这样写倒是没有错也可以过。
但是！这个题题面里说的是最多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/UVA-1634
最近有把紫书dp这一章的习题搞完的打算。。。这个题本来看vjudge上就不到20个人做想放弃的，强迫症导致开了题就得ac。
其实和之前的那个极角排序的题目感觉很像，只不过如果还是按照那个思维来的话会遇到一个问题无法解决，就是不能在保证为凸多边形的情况下满足无后效性。。。这个光从样例就可以试出来，所以就卡了半小时没有头绪。索性直接搜了。。。但是没想到这个搜题解讲的也很迷而且做的人很少，就直接去vjudge看了代码，看到dp是二维的和转移方程顿时懂了，和之前那个题一样都是枚举左下角的点，但是这个要求dp的时候考虑两维，也就是dp[i][j]表示当前左下角点对应的以i为顺时针倒数第一个点（也就是紧挨着枚举点s的点）且以就j为顺时针倒数第二个点的最大多边形面积。 继续阅读“[紫书][DP][计算几何] UVA1634 The Picnic”
题目链接 https://cn.vjudge.net/problem/UVALive-4080
最短路基础题，有意思的部分在于最短路树这个东西的应用，还有对复杂度的正确估算（莽
看题目意思，基本上能确定枚举那条要去除的边然后算每种情况的c，但是如果直接这样的话复杂度会是n*m²*logn,就题目数据量而言基本上不可能过的。所以就要找其他方法来降低复杂度，考虑到，去掉一条边也许不会对以某些点为原点的到每个点的单源最短路产生影响（也就是不在这些点的最短路树上的边），可以试着预处理出来初始状态下每个边的影响到的点的集合，在枚举到这条边的时候只需要重新计算这些点的最短路而不用每次都计算所有点的最短路，这样的话可以把复杂度降低到n²mlogn。不得不吐槽一下这个解法，说实话感觉并没有降低多少就卡过了时限，数据刻意友好么。。。。比赛的话就算能想到这个也不一定敢写吧emmm
坑点是有重边，果然做图论最重要的是搞清楚图的类型。。。重边啊自环啊什么的真的烦,还有一开始小根堆写成大根堆了，又是wa又是t的 继续阅读“[蓝书][图论][最短路][坑] UVALive 4080 Walfare And Logistics”
题目链接 https://cn.vjudge.net/problem/UVA-11529
（复习期末期间日常的小题
想到了考虑每个点被多少个三角形包围，但是没想到怎么算。。。主要还是计算几何太萎le，完全没有想到可以极角排序处理emmm。
具体的就是，考虑每一个点被多少个三角形包含，但是直接考虑也不好计算，可以考虑反向计算出不被多少个三角形包含，这个计算就要用到极角排序了。。。循环遍历每个点，在每个xi点，都对所有的其他点（姑且称为角点吧）相对于这个xi点的极角做一个排序，然后利用三角形的性质，选一个方向（顺时针或者逆时针都行），依次考虑“以每个角点为最小极角与之角度差小于pi的最大角度点之间有多少个点“，可能难以理解，画个图就好了，算出来点的数量p（p包含最大的那个点）之后C(p,2)就是“包含当前最小角点的所有的不覆盖xi点的三角形数量”，依次累加就好了。。。
另外，画个图就会发现，还需要考虑圆周转一圈的情况，所以要把排序后的极角数组复制一遍，而且复制出来的这个数组每个元素还要加2pi！（这个自己试试就知道了）
然后就是找最大点的步骤要小心，很容易写错。。莫名其妙，也可能是我最近复习微机原理复习傻了。 继续阅读“[数学][计算几何][极角排序][递推] UVA 11529 Strange Tax Calculation”
题目链接 https://cn.vjudge.net/problem/UVA-1543
复习微机原理复习到吐，随便翻了个题写了写缓和一下脑子。。。。
一开始看题目给的信息总想着怎么能用到那个1/2sinα，然后就没什么头绪（后来发现给这公式只是用来计算三角形的）。后来开始想正常的dp套路，也就是以xx为结尾/开头的xx的大小，然后发现这个形状的大小不能只由一边来确定，所以加了一维表示另外一边的位置，最后整出来状态就是dp[i][j][k]表示在i到j之间选k个点能组成的最大的多边形大小 继续阅读“[DP][紫书][计算几何] UVA 1543 Telescope”
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/1061/problem/D
嗯。。。又是这种一维的区间最优化策略问题了。。。似乎已经感觉到了套路。。。（赛场上贪心有感觉就直接上了
这种题一般是先排序（以左端点或者右端点）搞出来一个顺序，然后在这个顺序的基础上逐个考虑。考察到某一段时候一般需要做决策，然后这时候可以根据具体题目来看是贪心决策还是dp，如果直觉是贪心（毕竟真正证明有时候确实不好弄），那一般决策都跟满足条件的极端值有关，比如在这里就是如果存在能合并的点（如果连最基本的两段合并后小于各买一台电视机都不满足那一定不能合并），那么一定是和这段左边最靠近他的一个点合并。具体证明可以分情况讨论，一般真的证明的时候就是得考虑，如果不这么合并，计算出来的结果和原来的结果对比，一般要考虑之后的seg的影响，在考虑的时候可以分情况讨论（反正我一般有直觉就上233
然后在实现的时候，有时候没有头绪可以想想STL！（想起了ccpc网络赛被set支配的恐惧），这个东西有时候真的有妙用，它既保持了单调的性质（可以用来贪心）又有着动态维护的特性（贪心的动态调整）。
wa点又是精度，嗯万年精度，这次竟然LL也炸了，而且是因为add的两个参数本身可以达到LL，然后一加给爆了。。。。我去
很有意思的一个组合数学题。
整个题的最核心的思想就是，两个线段共线的判断！只要有两个点就可以确定一条线段（直线），那么只要再多一个点就可以确定这个点是否在和当前的这条线段共线了！所以两种算法的思想都在于一个2
第一种方法：最纠结的问题还是在于，怎么去重。想到了枚举角度的方法却没有想到怎么去重，还是思维不行。第一种方法是每次枚举所有可能的矩形，然后计算对角线的数量，这个很好算也就是有多少个矩形，直接(n-i+1)*(m-j+1)就行了。但是我们考虑的时候首先只考虑gcd(i,j)==1的情况，这种情况一定说明这种对角线的角度第一次出现（因为我们从小到大枚举i和j），所以对答案贡献为正，还有一种情况是gcd(i,j)==2，这说明之前已经出现过了这种对角线，所以这里要减去对应的数量，注意这里是最重要的：减去的是对应的数量，然后其他的gcd值不用+也不用-。原因就在于，如果你有一个4*4的或者3*3的矩形对角线重算了，那么在清除gcd为2的那一步当中其实就已经清除了所有的重复对角线！因为这个2会按照不同的起始点一直推下去。 继续阅读“[组合数学][数论][思维][空间对称转化][充要条件] UVALive 3720 Highways”
自己写了个有点繁杂的数位dp，本来一发过还有点高兴，但是看了前排dalao代码发现自己写的太复杂了。。。。这个题其实只用组合数学就可以解emmmm
先上自己的屌丝做法：分段dp，从前往后，组合数学算下可以知道能预处理出来一段长度为n的可以包含前导0的数据的所有0的个数，我本来想的是用f(p,m,isf)表示当前是第p个数字，最大为m然后是否为上限isf表示状态，但是写着写着发现不用这么来。。。。所以其实到最后程序里的isf就没有用（在发现这一点的时候我就该想到其实不用这么“dp“），把当前位为0特判一下加上后面的所有可能数字（这个也可以预处理），算完当前这一位之后往下一位继续算。。。最后由于我在f里面的枚举都是从0开始，所以等于说算出来的是”可以包含前导0的数的0的个数“，所以在cal里面还要减去所有的前导0的个数。。。麻烦一批
再说dalao们的做法：其实这个前导0的问题很容易解决。。。从后往前算就ok了，每次算到一位的时候判断是不是0，不是0的话，可以想到当前位为0的话总共出现的次数是容易计算的：把整个数字从这个点分开成左右两段（不包括当前这一位），那么左边的数字*10^(右边的位数),如果当前为0那就不能这么算了（跟数位dp一个道理，isf的时候不能当成所有的情况来做）,但是仍然很简单：只要左边不是最大的那个数字，右边仍然可以取到所以情况，所以这时候把左边-1乘上右边的10幂，再加上右边所有的本身的上限就行了。。。还是看代码比较好说。
