我决定把《挑战》的题目，从前到后刷，尽量每一道都给一些简短的解释！至于什么时间能全部完成，那就看造化了- -，也可能永远都完不成:|。
第二章
- 1 / 1 Problem A POJ 2386 Lake Counting
A 是例题啊，就直接 dfs 就好了，注意是 8 连块。 - 1 / 1 Problem B POJ 1979 Red and Black
B 就直接 dfs 数有多少个联通块。 - 1 / 1 Problem C POJ 3009 Curling 2.0
C 题算法也简单，可是实现麻烦。我是一步一步模拟的，并且用了"迭代深搜"。如果之前的搜索是可以最优化剪枝的，那直接每次设置最优解就好了，第一次找到的解就是最优的。直接 bfs 也是可行的，只不过需要记录整张图。迭代深搜看似好写，但是在深度过大时，可能会超时。 - 1 / 2 Problem D POJ 3669 Meteor Shower
这一题我看了 POJ 的 discuss，很多同学认为数据有问题，其实不然。数据是正确的，人的活动范围是第一象限，输入的坐标最多是 (300, 300)，也就是最多会影响到 301，那么数组开到 303，就可以过了。 - 1 / 1 Problem E POJ 2718 Smallest Difference
后面几道题目都是枚举的了。这个直接全排列枚举，如果不符合数字规范就 continue 掉。直接认为前一半是一个数字，后一半是一个数字，这是贪心，可以证明。如果是奇数个数字，就认为前一半少一个数字，可以证明不丢失最优解。 - 1 / 2 Problem F POJ 3187 Backward Digit Sums
暴力枚举了，我发现下面一行的数字对原数组的使用其实跟组合数有关。所以我先算了一个组合数，然后全排列枚举原数组，对每个排列，O(n) 计算结果。我觉得这个是可以二分的，不深究了。 - 1 / 1 Problem G POJ 3050 Hopscotch
这题为什么我觉得是 DP 呢？反正我是 DP 解的，DP[i][j][k]，表示在 (i, j) 位置，长度为的 k 的串的集合。 DP[i][j][k] = U{ DP[与 (i, j) 相邻][k - 1] }。最终答案为 U{ DP[ALL][6] } 的元素个数。
――以上结束于 2014 年 5 月 24 日上午 1:18
终于结束这一节了，贪心题真是太蛋疼了- -，说来又感到对高神真是无限膜拜啊 Orz。贪心对我来说，基本靠猜，而且猜的基本都是错的。
- 1 / 2 Problem A POJ 3617 Best Cow Line
这是书上的例题，每次可以取一列字母的最前面的或者最后面的，贪心策略是，如果前面的小，就拿前面的，后面的小就拿后面的。关键是如果相同怎么办？相同的话递归比较两个后继字母，到最后一直都相同，那就随便拿一个吧- - - 1 / 1 Problem B POJ 3069 Saruman's Army
这个题是给定数轴上一些点，要求每个点都要有东西覆盖，你可以选择一些点，这些被选择的点就默认被覆盖了，而且它旁边 [-R, R] 的点也会被覆盖，问你最少应该选几个点？
我算是用了一个偷懒的办法吧，我把所有的点都放到集合里面去了，然后每次拿出最前面的一个点，去看离他 [0, R] 范围有没有点，有的话就选最远的那个，并且把被选中的点右边 R 范围的点去掉。这一系列操作都可以调用 TreeSet 的接口，复杂度也不高。 - 1 / 2 Problem C POJ 3253 Fence Repair
这个题是告诉你，你现在需要很多根木棒，而你有一根长度恰为那些木棒的和的长木棒，现在让你把长木棒切割。每次切割的花费是这个木棒的长度，让你求最小木棒。
这个题上来完全没想到怎么做嘛 - -，不过现在应该能想到了，因为像这种可以合并的问题大部分都是优先队列，后面还有好几道呢。之前想成了先和最小的，不对，先和最大的，也不对。正确的做法是按照哈夫曼树来合并。 - 1 / 2 Problem D POJ 2376 Cleaning Shifts
这题是最少区间覆盖问题，给你很多个区间，问你，现在如果要让你选择一些区间，使得一个新给定的区间被完全覆盖，最少应该选择的区间的数目是多少？
之前区间覆盖问题一直不能解决，现在我应该是有一些想法了。如果你直接去看别人的代码，会很迷惑的，虽然代码不长，但是不好理解。而且这种区间贪心的代码，还有很多边界要处理- -，超级烦。不过现在我终于找到一个对我来说有效的办法了。
那就是，先去包含区间。你发现，如果题目保证所有的区间互不包含，那么区间贪心的问题都很简单了。那现在如果我能去除包含区间，不就解决关键问题了吗？
如何去除包含区间呢？一个简单的想法是平方枚举，但这显然 TLE，我看见别人给了一个（排序后）线性的解法，那就是让可能相互包含的区间放在一块，然后就好办了。如果你要小区间，就优先按右端点从小到大，然后按左端点从大到小排序；如果你要大区间，那就优先按左端点从小到大，然后按右端点从大到小排序。不知道你理解了没有？虽然这样代码很麻烦，但是复杂度跟别人的是一样的，想法容易实现。 - 1 / 3 Problem E POJ 1328 Radar Installation
这一题果断查题解了，开始想成了，从左到右贪心取每个点，但是正解是对每个点，可以算出一个区间，然后对区间做贪心就好了，区间的贪心又是经典的。 - 1 / 2 Problem F POJ 3190 Stall Reservations
经典的区间贪心问题。哦，不对，如果是只选择最多的独立区间，那就是经典问题，但是现在问题变了，所以我又去查题解了。经典的最多独立区间问题也可以按先去包含区间的做法来解。这一题是优先队列，搞不定啊- -。 - 1 / 1 Problem G POJ 2393 Yogurt factory
这一题是一个简单的贪心问题，对每天的奶酪，有两个选择，一是过往的最放到现在最便宜的奶酪，而是当前的奶酪。每次更新过往最便宜的奶酪就好了。 - 1 / 2 Problem H POJ 1017 Packets
这道题，记得很久以前做过。现在做，明显感到代码能力大增，虽然还是错了一次。就每次选择最大的放，然后放不满的话，就尽量填最大的 - - - 1 / 1 Problem I POJ 3040 Allowance
神贪心，查题解的，理解不能。 - 1 / 1 Problem J POJ 1862 Stripies
这题瞎猜一发，按霍夫曼树的做法，然后样例跑不出来，按反霍夫曼的做法，对了- - ，这证明，我做贪心真的靠瞎猜 - -！ - 1 / 2 Problem K POJ 3262 Protecting the Flowers
最后一题也是瞎猜，考虑两头牛的情况，然后不假思索的推广到多头牛，然后排序，贪心处理 - -。
这一套贪心做的真是爽啊 T T。
――以上结束于 2014 年 5 月 28 日下午 6:35
- 1 / 1 Problem A POJ 3176 Cow Bowling
最基础的 dp 问题了 - 1 / 1 Problem B POJ 2229 Sumsets
给你一个 n(≤ 1e6)，问你 n 的全部划分方案数，划分的数字里面只能含有 2 的幂。
dp[i][j] := i 的 最大数 ≤ 2^j 的划分方案数目。
dp[i][j] = dp[i][j - 1] + dp[i - 2^j][j] - 1 / 1 Problem C POJ 2385 Apple Catching
每分钟掉一个苹果，可能掉在 1 树下面，也可能掉在 2 树下面，你最多可以移动 w 次，问你最多能接到多少个苹果。
状态很明显了：
dp[i][j] := 第 i 分钟已经移动 j 次时，能接到的最多苹果数目。
转移也很简单，不写了。 - 1 / 1 Problem D POJ 3616 Milking Time
这道题跟以前的区间贪心问题类似，给你很多区间，问你最多能选出多少个互不重叠的区间。只不过现在每个区间有了一个权值，让你求最大的权值。我是直接线段树做的，状态是：
dp[i] := 第 i 个位置没有被覆盖，能获得的最大权值。
把所有区间按左端点从小到大排序，然后，对于每个区间，去跟新状态：
dp[i] = max(dp[i], dp[l] + e) for each i >= r
注意到整个 dp 数组在维护的过程中一定是单调增的，所以，可以二分出一个需要更新的区间，然后用线段树去在对数时间内更新掉。不过高神想到了一个更神的 - -，把区间离散化，f**k！
- 1 / 1 Problem E POJ 3280 Cheapest Palindrome
经典区间 dp：
dp[i][j] := 从 i 到 j 区间内，更新到满足题意，需要的最小花费。
dp[i][j] = { max(dp[i + 1][j] + e[i], dp[i][j - 1] + e[j]) if (A[i] != A[j])
else dp[i + 1][j - 1]} - 1 / 2 Problem F POJ 1742 Coins
这跟书上的一道例题很像，状态是一样的。
先说题意，给你 n(≤ 100) 种货币，告诉你每种货币的币值(≤ 1e5) 以及数目(≤ 1000)，问你在 1 到 m(≤ 100000) 中，有哪些价格是能用这些货币表示的。
按照我以前的想法是这样的：
dp[i][j] := 用前 i 个货币能不能拼出 j。
这样的话，暴力更新复杂度就是 100 x 1000 x 100000，显然超了。
现在把状态改成这样：
dp[i][j] := 用前 i 种货币拼出 j，第 i 个货币还剩下的数目，为负表示不能用前 i 种货币拼出 j。
仔细想一下，这个状态确实刚好是我们想要的。
dp[i][j] = { c if dp[i - 1][j] >= 0
else dp[i][j - a] - 1} - 1 / 2 Problem G POJ 3046 Ant Counting
大致就是给你一个可重集，问你从这个集合的有 k 个元素的可重子集的数目，s ≤ k ≤ b.
数据量不大，随便搞一个状态就好了：
dp[i][j] := 前 i 种数组成的有 j 个元素的可重子集的数目。
状态转移很简单，但是不好描述，具体等代码公开了，看代码吧 - - - 1 / 1 Problem H POJ 3181 Dollar Dayz
n 用 1..k 来划分的划分数。
dp[i][j] := i 用 1..j 划分的划分数。
dp[i][j] = dp[i][j - 1] + dp[i][j - i] - 2 / 3 Problem I POJ 1065 Wooden Sticks
这题相当于，在坐标轴上给你 n(≤ 5000) 个点，你可以连线，从一个点出发，你只能往右上连接下一个点，可以平着走也可以竖着走，问你最少连几个点能把所有的点都连上。
以前做过所有的点的横坐标和纵坐标都不会相同的版本，直接求一个最长下降子序列就可以了，序列长度就是连线的条数。
现在这个稍微麻烦一点，高神搞了一下，也是最长下降子序列，必须严格下降，才算下降，就是 x 和 y 都不能有相同的。
不过没想到证明 - - - 1 / 1 Problem J POJ 1631 Bridging signals
经典最长上升子序列 - 1 / 1 Problem K POJ 3666 Making the Grade
给你一个序列，A1, A2, ... An (Ai ≤ 1e9, n ≤ 2000), 现在让你生成另一个序列 B1, B2, ... Bn 是非降序列或者非增序列，使得花费最小，花费是 |A1 - B1| + |A2 - B2| + ... + |An - Bn|.
易知 B 序列中的数字都是 A 序列中的数字（反过来不对），先只考虑非降序列，状态是：
dp[i][j] := B 序列的第 i 个数 ≤ A 序列的第 j 小的数字时，当前的最小花费。
dp[i][j] = min(dp[i][j - 1], dp[i - 1][j] + |Ai - A[P[j]]|) - 1 / 1 Problem L POJ 2392 Space Elevator
给你 k(≤ 400) 个箱子，以及每个箱子的高度 h(100)，数目 c(10)，以及不能超过的海拔 a(40000)，问你最多能堆出多高的高度。
将箱子按 a 排序，算是一个贪心。
然后对每个箱子，暴力更新这个状态就好了：
dp[i] := 高度 i 是否能达到。 - 1 / 2 Problem M POJ 2184 Cow Exhibition
给你平面上的 n (100) 个点，以及坐标 x(-1000, 1000), y(-1000, 1000)，让你选出一些点，使得 sum(x) + sum(y) 最大，但是要求 sum(x) ≥ 0 && sum(y) ≥ 0.
我给了这样的状态：
dp[i][j] := 前 i 个点，sum(x) = j 时，最大的 sum(y)。
更新很简单了吧 - -
写了这么多，发现这样效率有点低下啊，还是得多刷题啊，以后尽量多刷题，少写博客吧 - -
以上完成于 2014 年 6 月 2 日下午 10:44
2.4
一些数据结构的简单题
- 1 / 1 Problem A POJ 2431 Expedition
可以发现，在走过的加油站中，在哪个地方加油是无所谓的，所以我们在油量最多的地方加油就好了。
每走过一个站，如果油不够了，就试图在以前的加油站里加油。用优先队列维护。 - 1 / 1 Problem B POJ 3253 Fence Repair
这题，贪心模块里面也有，是哈夫曼树。 - 1 / 2 Problem C POJ 1182 食物链
经典的食物链，带权并查集，不推荐用《挑战》上面的方法，应该用维护到父亲距离的方法。 - 1 / 2 Problem D POJ 3614 Sunscreen
给你一些区间，和一些点，问你，如果每个点最多对应一个区间，最多能有多少个区间得到对应。
包含区间中优先对应小的区间。 - 1 / 5 Problem E POJ 2010 Moo University - Financial Aid
这题应该还有简单的方法，我是 O(c log^2 c) 过的。二分答案，每次对数组排序。 - 1 / 1 Problem F POJ 2236 Wireless Network
简单建图后，就是普通并查集了。 - 1 / 1 Problem G POJ 1703 Find them, Catch them
一个简单的带权并查集。
带着考试的压力，水完了简单数据结构题。
因为，总是有比看书更有趣的事情可以做 - - ！
最后完成于 2014 年 6 月 3 日下午 7:53
- 1 / 2 Problem A POJ 3255 Roadblocks
例题了，找次短路，对理解最短路算法很有帮助。 - 1 / 1 Problem B POJ 3723 Conscription
最小生成树，做这道题目突然感受到了最小生成树与最短路奇妙的联系 - - 因为我最开始当成最短路做了 - 1 / 1 Problem C POJ 3169 Layout
查分约束，例题。 - 1 / 2 Problem D POJ 2139 Six Degrees of Cowvin Bacon
floyd - 1 / 2 Problem E POJ 3259 Wormholes
询问是否有负环。这题的数据里面，图都是联通的。 - 1 / 1 Problem F POJ 3268 Silver Cow Party
所有的点到 x，然后再回去的总路程最小是多少？
是有向图，我突发奇想存了个反向图，做了两次 dij，就好了。 - 1 / 2 Problem G POJ 1258 Agri-Net
最小生成树 - 1 / 2 Problem H POJ 2377 Bad Cowtractors
最大生成树 - 1 / 3 Problem I POJ 2395 Out of Hay
找最小生成树的最大边 - -
于 2014 年 6 月 13 日下午 11:16
时间过得好快，没想到竟然是 10 天后我才完成图论这部分题目。最近都在准备考试 - -，其实也没有准备什么，我也不知道时间都跑哪去了。总之，后面要刷出节奏来 - - 不能再被其他事情耽搁了！
- 1 / 1 Problem A UVA 10006 Carmichael Numbers
按照公式来就可以了，不是素数而且满足费马小定理的式子，就是 Carmichael number。 - 1 / 6 Problem B POJ 2429 GCD & LCM Inverse
这道题超级坑，我一直 RE，在我写这个报告的时候都还没有用正统的方法通过它，被搞死了 - - 。
后来看到岐哥以前的博客上面用 Java 水过了这道题目，利用 POJ 对 Java 多给的时限，用暴力的方法通过了。但是如果数据严格一点就没有办法了。 - 1 / 1 Problem C POJ 1930 Dead Fraction
这个题也巨恶心，不过挺实用的 - - ，用到一点数学知识，无限循环小数如何转化成分数。 - 1 / 1 Problem D POJ 3126 Prime Path
素数表 + bfs - 1 / 2 Problem E POJ 3421 X-factor Chains
因式分解，求组合公式 - 1 / 1 Problem F POJ 3292 Semi-prime H-numbers
唉，这个题目好烦啊。后来查结题报告 加 乱水过的。 。 。 - 1 / 1 Problem G POJ 3641 Pseudoprime numbers
水题 - 1 / 1 Problem H POJ 1995 Raising Modulo Numbers
水题，快速幂一下就好了。
数学渣要被 B 题折磨哭了 - -
于 2014 年 6 月 16 日下午 10:33
第三章
- 1 / 1 Problem A POJ 1064 Cable master
经典的二分，先转换成整数搞。 - 1 / 1 Problem B POJ 2456 Aggressive cows
最小距离最大化 - 1 / 1 Problem C POJ 3258 River Hopscotch
大致是河上有一些石头，问你，拿走 M 个石头后，石头间的最小距离，最大可能为多少。
虽然也是最小距离最大化，可是二分最小距离的时候，是否可行，却不是那么容易。
虽然也是贪心，但是我只是查了题解照着写了写就过了 - - 。 - 1 / 2 Problem D POJ 3273 Monthly Expense
分组，让每组之和的最大值，最小。 - 1 / 2 Problem E POJ 3104 Drying
明显二分时间之后，判定变得很简单。 - 1 / 4 Problem F POJ 3045 Cow Acrobats
这个不是二分吧，反正我不会，查了题解是贪心，排个序就确定了。还有题意我也没有怎么读懂 - - 。 - 1 / 2 Problem G POJ 2976 Dropping tests
卧槽这道是个好题，书上的例题。需要小小的转化一下。 - 1 / 1 Problem H POJ 3111 K Best
同上一题。 - 1 / 2 Problem I POJ 3579 Median
这道题真是经典啊 - - ，二分答案，然后统计小于答案的数字的个数。
这个统计可以在 O(n log n) 时间内完成。无非就是对每个数，二分在这个差值之内的数的个数，然后累加。 - 1 / 3 Problem J POJ 3685 Matrix
这个也好玩。观察发现这个矩阵每列都是单增的。于是对每行统计，统计的时候可以二分，也可以直接解方程。 - 1 / 2 Problem K POJ 2010 Moo University - Financial Aid
这个题以前好像做过一次，我又犯了同样的错误。每次判断的时候，只要 O(n) 就可以了。 - 1 / 2 Problem L POJ 3662 Telephone Lines
此题经典。问题可以这么描述：从 s 到 t 的路径，路上第 k 大的权值最小可能是多少？
二分权值之后，就是让比答案大的路的数目最小。于是路上的权就变成了只有 0 和 1 的了。 - 1 / 3 Problem M POJ 1759 Garland
观察（写程序）可发现 B 的值与 A 右边的第一个值相关，可以二分。 - 1 / 1 Problem N POJ 3484 Showstopper
最后一题描述的好烦啊 - - ，好像只有一个数字出现了奇数次，让你找到这个数。
这样说其实一点都不难了。
好棒的二分的题目:)
于 2014 年 6 月 18 日下午 7:06
这套题也不错，学到了几个小技巧：two pointer、折半枚举、开关灯……
- 1 / 1 Problem A POJ 3320 Jessica's Reading Problem
书上的例题，我用 map 乱搞的。。。 - 1 / 2 Problem B POJ 3276 Face The Right Way
暴力枚举翻转长度，每次枚举 O(n) 的到翻转次数。 - 1 / 1 Problem C POJ 3279 Fliptile
这个是开关灯的，要找最优解 - - 我本来还想用高斯消元试试的，但是想想好麻烦啊，放弃了 - - 。 - 1 / 1 Problem D POJ 3684 Physics Experiment
物理题 - - 好无聊啊 - - 我没有解公式，直接抄书上的 - - 。 - 1 / 1 Problem E POJ 2785 4 Values whose Sum is 0
折半枚举，很棒 - 1 / 2 Problem F POJ 2566 Bound Found
这里我才感受到 two pointer 的强大 - -，简单来说，就是刘汝佳说的"窗口"的概念，就是说两个指针之内的元素形成了一个窗口，这个窗口的最优解要能得到，而且能在移动两个指针的时候，方便维护。而且能证明最优解一定出现在两个指针移动的过程中，这是一个贪心 - - 。 - 1 / 2 Problem G POJ 2739 Sum of Consecutive Prime Numbers
这道就稍微简单一点了，也是 two pointer - 1 / 1 Problem H POJ 2100 Graveyard Design
同上 - 1 / 1 Problem I POJ 3185 The Water Bowls
这个我直接两面都搞了一次，求了一个最小值。 - 1 / 1 Problem J POJ 1222 EXTENDED LIGHTS OUT
这道题我现在已经可以写得很快了，10 分钟左右。以前沈老师出这道题的时候我还没有一点思路呢 - - 真是弱啊 - - 。 - 1 / 1 Problem K POJ 2674 Linear world
这道题我算是做得很简洁的了，跟网上其他的代码比较。首先可以算出最后一个掉落的时间。然后不考虑碰撞，不考虑掉落，看每一个蚂蚁能到达什么位置，记录到数组中。把这个数组排序，刚好在边缘的那个数的下标就是输入的蚂蚁的下标。 - 1 / 1 Problem L POJ 3977 Subset
艹 这竟然是没有多项式解法的题 - - ，关键是 discuss 里面有人说他一眼就看出来了。 。 。 折半枚举 - - - 1 / 7 Problem M POJ 2549 Sumsets
也是折半枚举 - -
这套题中间简短了一下，因为有课要上 - - 。现在熬夜把它搞完了 - - 挺不错的题目。
刷题一定要连贯，断断续续没有长进啊 - - 。
于 2014 年 6 月 22 日上午 1:18
- 1 / 1 Problem A POJ 2991 Crane
书上的例题，我不会做，只能抄一遍代码 - - - 1 / 1 Problem B POJ 3468 A Simple Problem with Integers
这个，学线段树的人应该都做过吧 - - - 1 / 3 Problem C POJ 2104 K-th Number
这次竟然用分块过掉了 - - 以前不知道怎么的都过不掉的啊。归并树也可以过掉。 - 1 / 2 Problem D POJ 1990 MooFest
这个大概是让你统计一个值，然后这个值，如果你真的暴力统计的话，是会超时的。
于是就可以每次统计多个，复杂度就降下来了。 - 1 / 1 Problem E POJ 3109 Inner Vertices
竟然是扫描线 - - 好难啊 - - 其实也不是很难，还是可以做的。 - 1 / 2 Problem F POJ 2155 Matrix
楼教的题目，做过很多次了。直接二维 BIT 就可以了。 - 1 / 1 Problem G POJ 2886 Who Gets the Most Candies?
这道题，让我终于发现我的 BIT 里面的一个函数是用来干什么的了。
当然如果没有那个函数，也是可以做的，只不过复杂度得乘上一个 log n，因为需要二分。 - 1 / 1 Problem H POJ 3264 Balanced Lineup
RMQ 裸题 - 1 / 1 Problem I POJ 3368 Frequent values
LRJ 给了 RMQ 的做法，不过我还是用更直接的线段树过掉了。 - 1 / 1 Problem J POJ 3470 Walls
这道题有点难，题目中也没有说明坐标的范围，看来应该很大，快到达 int 的最大值了。
也是扫描线做的。 - 1 / 1 Problem K POJ 1201 Intervals
这个贪心就好，只不过要用 BIT 来维护信息。 - 1 / 1 Problem L UVA 11990 ``Dynamic'' Inversion
分桶法，外加一个二维 BIT
这套题目还是做得很快的，但是还是过了这么长时间，因为中间有点小插曲，VJ 挂了一次，所以我就出题去了。
于 2014 年 6 月 24 日下午 9:54
- 1 / 1 Problem A POJ 2686 Traveling by Stagecoach
例题，状压 dp - 1 / 1 Problem B POJ 3734 Blocks
例题，矩阵 - 1 / 1 Problem C POJ 3233 Matrix Power Series
裸的矩阵优化，就是写成来有点麻烦 - - - 1 / 1 Problem D POJ 1769 Minimizing maximizer
也是例题，注意到每个组件的顺序不能改变就好做了。 - 1 / 1 Problem E POJ 2441 Arrange the Bulls
状压 dp，这后面的状压 dp 一般不难，除了插头 dp。。。 - 1 / 1 Problem F POJ 3254 Corn Fields
同上。 - 1 / 5 Problem G POJ 2836 Rectangular Covering
这个题很无语啊 - - ，很多网上的题解都是错的，但是却能 AC - - 我瞎抄了一份 - - - 1 / 1 Problem H POJ 1795 DNA Laboratory
这个题好难啊 - - 不知道为什么我都排序了，还是出不了字典序最小的解，非要再去 dfs 一次才行 - - 而且裸的 dfs 还不行，TLE，还要回溯剪枝 - - - 1 / 1 Problem I POJ 3411 Paid Roads
这个题把经过的点集也看做状态，就可以了。 - 1 / 1 Problem J POJ 3420 Quad Tiling
这就是传说中的插头 dp 的基础版本 - - 卧槽，太难了 - - ，《挑战》上面也没有好好讲他的状态表示，导致我完全看不懂他的代码，只能按照网上的做法解了 - - 。 - 1 / 2 Problem K POJ 3735 Training little cats
做过一次类似的，前面就简单的矩阵乘法，因为每一次操作，就相当于乘了一个特殊的矩阵。
后面直接矩阵快速幂就好了。但是会 TLE，看 discuss，要稀疏矩阵优化 - - - 1 / 1 Problem L POJ 3171 Cleaning Shifts
这个我就直接线段树加个二分搞了一下 - -
这套题目做的好慢啊 - - 距离上次已经有 3 天了，而且我也没有什么其他的事情，基本就是这些题目了 - - 。
还是题目难度加大了 - - 已经有点吃力了 - -
不过后面终于到了网络流了 - - ，看到曙光了有木有:)
于 2014 年 6 月 27 日下午 4:52
- 1 / 1 Problem A POJ 3041 Asteroids
二分图的例题 - 1 / 3 Problem B POJ 3057 Evacuation
二分图，现在我应该能独立解出这道题了吧~ - 1 / 1 Problem C POJ 3281 Dining
好像是最大流 - 1 / 2 Problem D POJ 3469 Dual Core CPU
最小割，分成两个集合（s-t 割） - 1 / 1 Problem E POJ 2135 Farm Tour
最小费用流（两条不同的最短路） - 1 / 4 Problem F POJ 2175 Evacuation Plan
这道题神烦，直接费用流还会超。得消负圈。不过对于了解最小费用流的原理还是挺有帮助的~ - 1 / 1 Problem G POJ 3686 The Windy's
这道题神难~ 不知道现在会不会~ - 1 / 1 Problem H POJ 3680 Intervals
好题，让我对最短路建模有了更深的理解 - 1 / 1 Problem I POJ 3713 Transferring Sylla
这题也是神烦，问是否 3 联通。不知道怎么跟网络流联系在一块，看了题解是枚举去掉一个点，然后看是否双连通。 - 1 / 1 Problem J POJ 2987 Firing
最大权闭合图。感觉是很一般性的问题，但是论文和原理我都搞不大懂，现在只能记住结论啊。 - 1 / 1 Problem K POJ 2914 Minimum Cut
全局最小割，感觉也是一般性问题，只能搞专门算法，不知道怎么放到网络流里面~ - 1 / 1 Problem L POJ 3155 Hard Life
有人说，题如其名~ 求最大密度子图。论文里面本来有一个是转化成最大权闭合图问题的方法，但是我看不懂啊~后来直接读了建图水过了，这道题我不会T.T - 1 / 2 Problem M POJ 1274 The Perfect Stall
水二分图。后面几道好像都是的。 - 1 / 3 Problem N POJ 2112 Optimal Milking
二分图之前还要 floyd。。。 - 1 / 2 Problem O POJ 1486 Sorting Slides
神烦 二分图。 - 1 / 2 Problem P POJ 1466 Girls and Boys
数据格式有问题。简单题。 - 1 / 1 Problem Q POJ 3692 Kindergarten
二分图最大团。取补图转化成最小点覆盖。 - 1 / 1 Problem R POJ 2724 Purifying Machine
好高兴，终于有一个自己想出来 AC 的。不过我还没有证明它是 二分图。 - 1 / 2 Problem S POJ 2226 Muddy Fields
经典的建图。需要先扫描把一个团变成一个点。 - 1 / 1 Problem T POJ 3068 "Shortest" pair of paths
经典最小费用流建图。 - 1 / 1 Problem U POJ 2195 Going Home
同上。 - 1 / 1 Problem V POJ 3422 Kaka's Matrix Travels
艹 这道题好经典啊~
网络流搞了 20 多天，真是破纪录了，以前都是一般 两三天搞一节的，现在直接翻了 10 倍~~~
还有两天不到题目时间就结束了~下面的计算几何能不能搞完呢~~~
- 1 / 1 Problem A POJ 1127 Jack Straws
例题，判线段相交 - 1 / 2 Problem B POJ 2932 Coneology
例题，还有点不懂。。。 - 1 / 1 Problem C POJ 2187 Beauty Contest
最远点对，凸包然后旋转卡壳 - 1 / 1 Problem D POJ 1981 Circle and Points
单位圆最多能覆盖多少点。考虑极限情况，肯定有一个点在单位圆的圆周上。那么对于那个在圆周上的点，我们思考圆心应该在哪？圆心肯定在以这个点做单位圆的圆周上。我们考虑在这个圆周上选点作为圆心，最多能覆盖多少点。以其他点做圆心画单位圆跟这个圆周相交，把这个圆周分成了很多弧，对每个弧单独考虑就行了。 - 1 / 1 Problem E POJ 1418 Viva Confetti
按顺序放一些圆盘到平面上，问你从上往下看，能看到几个圆。考虑你会在什么地方看到圆。很多圆相交的圆弧上往外（远离这个圆弧圆心方向）或往里一点距离的点，枚举这些点就可以了。 - 1 / 1 Problem F POJ 3168 Barn Expansion
这个可以用扫描线简单水过。 - 1 / 1 Problem G POJ 3293 Rectilinear polygon
这个有点麻烦，解法感觉需要证明。不太会。 - 1 / 1 Problem H POJ 2482 Stars in Your Window
扫描线。不算难题。 - 1 / 1 Problem I POJ 1113 Wall
简单凸包。 - 2 / 4 Problem J POJ 1912 A highway and the seven dwarfs
问你是否所有的点都在直线的一侧。可以先做一个凸包，问你等价于这个凸包在直线的一侧。
直线与凸包的交点是可以二分的。但是我太渣了写不出来。。。
然后考虑凸包上的线段的角度是（可以做成）递增的。而且可以知道如果这条直线跟凸包相交，等价于凸包上一定有两个（距离最远的）点连的线段跟这条直线相交。而这两个点是可以利用角度特征二分查找出来的，所以只需要判断这两个点就行了。 - 1 / 2 Problem K POJ 3608 Bridge Across Islands
凸多边形的距离。搞成点到凸多边形的距离。然后套的模板（log n） - 1 / 1 Problem L POJ 2079 Triangle
最大面积三角形。可以知道三角形的点一定在凸包上。然后平方枚举一条边来搞。网上的线性解法似乎不太对，过不了我自己的随机数据，虽然能AC。 - 1 / 2 Problem M POJ 3246 Game
n 个点里面，选出 n - 1 个点，使得这 n - 1 个点搞成的凸包面积最小。
去掉的那个点一定是 n 个点的凸包上的点。用角度扫描法，去掉一个点后，去掉的这个点旁边的点拿出来再搞一次（小范围的）凸包。总复杂度还是 n log n。 - Problem N POJ 3689 Equations
这道题还不会，看以看 yygy 的解法。
最近刷题太松散了。
最后完成于 2014 年 8 月 19 日上午 12:47
Read full article from 《挑战程序设计竞赛》题解 | shu_mj 的博客
No comments:
Post a Comment