题单解题记录-POJ题目分类推荐 （很好很有层次感）

题单链接： POJ题目分类推荐 （很好很有层次感）_发飙的小白-CSDN博客

11.6

• poj1753 -60min 1A
  • 　　sol：枚举中心点，1个点只有2个方案（翻/不翻），枚举要翻的点的方案。
• poj1328 -55min CE-T-W-A
  • 　　sol：->线段重叠取最少点选到所有线段。细节：位置相同左点排前。2*n个点依次入栈，右点入栈则栈中线段共用1点（相应vis置1），然后清空栈。
• poj1860 -3h=180min W-A 啊好慢！！
  • 　　sol：->找图中有无某个环，转一圈财富增加，若存在，则可以转足够多的圈直到原路走回S还能是正利润。这个环中不必包含S，但是实际找的过程中如果能找到环则必是从S能走到这个环。
  • 　　没用bellman-ford算法（其实想到了，但是看复杂度想直接手写，不存邻接表），而是循环了所有边，若当前边的起点被更新过，则更新终点的值，我认为这样能满足“所有被更新过的点必是从S能走到的点”。(虽然没用模板但是还是自己思考出了类似bf的思路)
  • 　　WA代码比AC代码多了这么一句错误“优化”（循环边的过程中如果更新了之前更新过的点则确定已找到财富增加的环）： if(pt[e[i].b]>eps)printf("YES");return 0;}  错因：唉我指定是忽略了一种情况，但是目前还没构造出来（
• poj1789 -40min RE-A
  • 　　sol：->并查集总边权。RE原因： int findf(int x){if(f[x]!=x)return f[x]=findf(f[x]);}  findf函数写成这粑粑样了，f[x]==x时没返回值/吐血。
• poj1035 -17min 1A 
  • 　　sol：复习三个常用字符串函数用法。坑：函数里定义char[]一定一定要memset初始化！！
• poj2388 -40min W-A 
  • 　　sol：注意：快排的基准值是值不是下标，所以不可能用它实现O(N)找第K大。 不信邪非得想个O(N)的做法，没想出来，最后桶排序交的。
• poj2488 -48min
  • 　　sol：OutputLimitExceeded-WA-PE-A 搜索写错了出现死循环 -> 理解错题意，没注意 lexicographically first 得理解为求字典序最小的path -> 太坑了，每组答案之间有2个换行。