2016.9.17 Codeforces Round #372 (Div. 1)
B【】给出一个图，其中一些边的长度可以为任意值，问从s到t的距离能否恰好是L，如果能，输出每条边的长度。
HRBUST 1044 Line Cover [题意优化]
平面上有n[0, 200]个点，每个点的横纵坐标范围为[0, 1000]，问最少5条直线能不能把这些点全部覆盖，时限15000ms。
想法：1.n^2枚举任意两个点构成的直线，在[0, 1000]的范围内枚举是否有其它点在这条线上。问题转化为有m个集合，每个集合有Ki个点，求最少几个集合的并集能成为全集。
2.二分图的最小点覆盖
正解：找出能覆盖5个以上点的直线，如果超过5条，则不可以；否则把这些直线放入解的集合，然后搜索减枝。
HRBUST 1788 Chocolate
一维数轴上有一些线段，每个线段有一个权值和头尾位置，选取一些线段使权值最大，线段不能相交，求得到的最大权值。
开始打算最小费用流套区间线段覆盖的模型，两个线段向切的情况没法处理…
正解DP：dp[0][i]表示选第i个线段，从i到n能得到的总价值，dp[1][i]表示不选第[i]条线段，从i到n能得到的总价值，那么答案就是max(dp[0][1], dp[1][1])
状态转移方程：如果选第i条线段的时候，i的右边还有线段j可选： dp[0][i] = val[i] + max(dp[0][j], dp[1][j]) 否则 dp[0][i] = val[i] dp[1][i] = max(dp[0][i+1], dp[1][i+1])
螺旋矩阵的两种算法
题目链接: HRBUST 1564螺旋矩阵 HRBUST 2192螺旋的矩阵
1564题的矩阵是这样的：
4x4的矩阵 第一层 第二层 ---------- ---------- ----- 1 2 3 4 1 2 3 4 12 13 14 5 12 5 13 14 11 16 15 6 11 6 16 15 10 9 8 7 10 9 8 7
第一种方法按照右下左上右下左上的顺序构造出整个矩阵，第二种方法能在O(1)时间求出坐标为（i, j)的位置上的数字是多少
HRBUST 2209 LRU
和HDU 2835 Operating system很像，都以页面置换算法为背景，HDU的是最佳置换算法，而本题是最近最久未使用置换算法。
用STL::map查找某个结点的时间复杂度为O(logn)
用map找到位置后双链表删除一个元素的时间降为O(1)
时间复杂度O(mlogn)
继续阅读
Gyf's Blog 