|
区间贪心
|
|
为了艾尔
题目 1179 [郑州101中学] 圣战
2014-08-20 11:25:52
|
|
最简单的方法，预处理成01背包
|
|
|
BFS+dp
|
|
|
拓扑排序版
|
|
|
先用Floyd找到直径，由于这是一棵无根树，树中两点最短距离最大的就是直径的两个端点
或者从任意点v为根找到v点距离最大的点u 然后以u为直径的一个端点找距离u最大的点f为直径的另一个端点 然后就是枚举路径长度取最小值 |
|
|
|
开几个数组记录，O(n)扫描一下，注意对正在处理的区间的操作
|
|
|
线性匹配使用O(n)的算法
|
|
|
迭代实现+打表
|
|
单调队列搞定。。。代码55行，好像还是太长了
|
|
|
要么优先队列O(nlogn)过，要么计数排序然后直接用单调队列O(n)过，要么开O2暴力O(n^2)卡过，那些手写堆的大爷都是什么心态。。。
|
|
|
|
|
终于过了= =........................................先说下思路，二分答案然后最短路，关键就是最短路,我先是写的SPFA一直WA是因为排序的时候忘记记录以前的顺序了，然后有一个点T，因为SPFA更适合跑稀疏图，而倒数第二个点有1W个点，5W条边，然后开始想打dijk,一个点一直WA，最后发现原来是dijk写错了，这居然可以过9个点！！！不可思议......虽然花了很长时间但纠正了一些毛病....
|
|
原先（在2012-3-31添加的题目）这道题的数据是错误的（全是NIE），现在我改成了POI的官方数据，然后重评了所有提交O(∩_∩)O~~
|
|
|
线性规划模板题，数据淼求轻虐……
|
|
|
题目 30 [FZYZOJ 1273] 坦克游戏
2014-08-14 10:32:07
|
|
|
方展鹏《浅谈如何解决不平等博弈问题》，用超现实数解决，犇于上青天！！！！！
|
|
|
哈希出奇迹！！！
（貌似这题可以用后缀树啥的？） |
|
感谢C++，感谢STL！
感谢你们让我AC了第100题！ |