求区间图字典序最小的最大点独立集。n<=20W
Category Archives: 数据结构
HRBUST 2209 LRU
和HDU 2835 Operating system很像，都以页面置换算法为背景，HDU的是最佳置换算法，而本题是最近最久未使用置换算法。
用STL::map查找某个结点的时间复杂度为O(logn)
用map找到位置后双链表删除一个元素的时间降为O(1)
时间复杂度O(mlogn)
继续阅读
ZOJ 3659 Conquer a New Region [并查集]
给出了n个点和n-1条边，每条边都有容量为w，且每两点之间有且只有一条边，若选一个点作为起点，求从这个点出发能得到的流量和最大是多少？
POJ 1733 Parity game
有一个长度为n的”01″序列，和m个问题。每个问题有[L,R] 代表连续区间从L到R，odd代表这个区间有奇数个’1’，even代表这个区间有偶数个’1’，判断这m个问题从第k个开始是矛盾的，输出k-1。
Gyf's Blog 