thestoryofsnow-CSDN博客

原创 POJ 1101 解题报告

这道题是BFS题。需要注意题意理解：最少segments而不是最短路径。由于边界可以出去，所以实现的时候需要注意坐标。例子之间没有输出空行WA了一次。输入错误WA了多次（最后输入是逐个输入字符，而不是输入行）。thestoryofsnow1101Accepted220K16MSC++2835B/* ID: thestor1 LAN

2016-08-31 00:04:22 982

原创 POJ 1661 解题报告

这道题可以看做是DP也可以看成模拟。从上往下看每个平台能否到达，是否遮挡，是否到地。代码写得重复很多，应该可以简洁许多。需要注意的地方是这里把出发点也看做了一个平台，这样按照平台高度排序的时候需要排N+1个（而不是N个）。thestoryofsnow1661Accepted180K0MSC++3018B/* ID: thestor1

2016-08-19 03:44:03 702

原创 POJ 1154 解题报告

这道题是普通的DFS，不需要优化就可以通过。thestoryofsnow1154Accepted164K32MSC++1326B/* ID: thestor1 LANG: C++ TASK: poj1154 */#include #include #include #include #include #include

2016-08-18 07:22:40 683

原创 POJ 3983 解题报告

这道题是很有意思的快算24的题目。样例本身是有问题的，首先，由于括号的存在，解是不唯一的，其次，样例中给除法左右也加了括号：(1/5)，这导致加括号的规则比较模糊。尽管从disucss知道测试例子只有一个，但还是当做不知道地做了。题目其实不是很好写。一开始用的是string, 用dfs构建expression str，然后再evaluate(str) 看是不是24，找到就退出。但是由于左括号的

2016-08-17 01:06:31 582

原创 POJ 3723 解题报告

这道题是最小生成树问题。由于“收集”每个人只能用一次“关系”，所以利用的关系不能形成环。贪心从最小的关系开始，只要不能形成环就收集。这就是kruskal用并查集的算法。最后没收集的人每人按最大代价加入总代价就可以了。thestoryofsnow3723Accepted908K344MSC++2132B/* ID: thestor1 L

2016-08-10 00:52:22 476

原创 POJ 2536 解题报告

这道题看着就是最大二分匹配的问题。用了之前POJ1274的代码就过了。thestoryofsnow2536Accepted192K32MSC++2788B/* ID: thestor1 LANG: C++ TASK: poj1274 */#include #include #include #include #inclu

2016-08-04 00:14:27 541

原创 POJ 2482 解题报告

三个月以来的第一题。。。这道题是二维的线段树，需要转化为一维。首先只考虑x轴，将每个点看成两条线，入线和出线。入线的x坐标是点的x坐标，亮度是点的亮度；出线x坐标是x+W, 亮度是点的亮度的负值，即-c。这样做的原因是如果我们按照x的大小从左往右处理所有的点（想象一个以每个点再左下那么一点点为左下角的矩形扫描，左下那么一点点是为了包括点），入线表示我们到了点的作用范围，出线会取消掉点的作用

2016-08-03 04:37:26 407

原创 POJ 3087 解题报告

2个多月来的第一道题。。。实际上很简单。按题意模拟就可以了。这里用的是trie查重，如果遇到重复就说明无论接下来洗多少次牌都不会洗出目标序列了。由于本题trie查重每次都需要查找到最后一层才有可能发现重复（所有洗牌后的序列的长度是一样的），所以trie不是很有效。看discuss直接用map也就过了。提交后遇到runtime error是因为char字符串末尾处没有初始化成‘\0’。

2016-05-25 08:51:48 455

原创 POJ 2499 解题报告

这道题是找规律加优化题。一个重要的出发点是从下往上找。对于(a, b)，其左节点是(a+b, b)。我们可以看到新的节点，即左节点，其左边大于右边。同样地，右节点是(a, a + b)，我们可以看到其右边大于左边。我们由此可以总结出如下规律：对于任一节点(a, b)，如果左边大于右边，我们知道它是左节点，其父节点是(a-b, b)；如果右边大于左边，则是右节点，其父节点是(a, b - a)。

2016-03-30 00:58:13 542

原创 POJ 3255 解题报告

这道题是求次短路径。做法比我想象的简单。思路和求最短路径基本一样，只是同时更新最短和次短路径，所以Dijkstra, SPFA等在这里依然可以用。这里用的是SPFA。更新次短路径的逻辑已经比较复杂了。次短路径的来源可能是：1. 该节点的最短路径。如果发现了新的最短路径，那么次短路径就是旧的最短路径。2. 邻接节点的最短路径。邻接节点的最短路径加上一跳可能比该点的最短路径大，但可能比次短

2016-03-25 02:33:41 470

原创 POJ 1286 解题报告

这道题是Polya题。我第一次接触到这个定理。看了别人的解题报告做的这道题：看过的最好的解释：http://www.cnblogs.com/mcflurry/archive/2012/06/20/2556071.htmlACM中的数学问题：http://www.doc88.com/p-910707819004.html （莫名其妙的打不开50页之后的PPT）http://wenku.b

2016-03-22 08:53:37 485

原创 POJ 3637 解题报告

这道题排序下然后每三个中选择最后一个（最小的）加起来就好。题目表述不是很清楚，举例的350不是最大的discount.thestoryofsnow3637Accepted240K94MSC++718B/* ID: thestor1 LANG: C++ TASK: poj3637 */#include #include #in

2016-02-27 01:54:47 645

原创 POJ 1230 解题报告

这道题感觉就是greedy的题。但是还是看了解题报告。知道做法后实现很简单，只需要注意测试数据中有左端点的x坐标大于右端点的x坐标的情况，调换下即可。贪心的策略是按照x从左往右扫描，如果某一列(某一个x值)对应（被覆盖）的墙的个数cnt大于k，那么需要从这些墙中删掉cnt - k 个。删除的顺序是将墙按照右端点的x值从大到小的顺序排序，按顺序删除。这样做的大致思路是因为对每个“覆盖墙”我们

2016-02-27 01:23:58 751

原创 POJ 1635 解题报告

这道题是求树的最小表示。从0开始到1结束，如果0的个数和1的个数相等，说明遍历了一个子树回来了。我们可以递归地处理每棵树。首先每棵树可以按照如上的方式分解成多个子树，在递归地处理完每个子树后，我们把子树排序，然后拼接起来。任何排序应该都是可以的，只要排序后同一棵树的不同的遍历的表达形式是一样的。我们这里按照string从小到大的顺序排的。thestoryofsnow

2016-02-20 05:53:18 897

原创 POJ 1523 解题报告

这道题刚开始看是求割点，还不知道割点算法，以为很难，然后看到是我大纽约的题之后就放心了。暴力做就好了。果然一次提交就顺利过了。想到可能点编号不连续，写起来稍微麻烦点。另外就是知道了c++中传array引用的方法。见http://stackoverflow.com/questions/5724171/passing-an-array-by-referencevoid Func(int (&m

2016-02-06 02:12:38 502

原创 POJ 1828 解题报告

这道题刚开始以为是求凸包(convex hull)，后来发现那样把最小的边界点也统计进去了。所以最终的做法只是按x排序，再对每个点扫描判断（是否存在x,y都不小于它的点）。thestoryofsnow1828Accepted572K1563MSC++1405B/* ID: thestor1 LANG: C++ TASK: poj

2016-02-02 02:39:40 625 1

原创 POJ 2892解题报告

上个月就写了一道题。。。惭愧。这道题看着像是线段树之类的，想想觉得挺复杂。偷懒看了discuss上面这篇帖子，然后就震惊了：竟然有这么简洁的做法！http://poj.org/showmessage?message_id=181975这里面用一个set保存所有被炸毁的村庄。然后如果查询x连接的村庄，只需要知道前后被炸毁的村庄，这两个村庄之前的就是连接的村庄（x在这个区间内）。这里用

2016-02-02 01:42:12 442

原创 POJ 2723 解题报告

这道题是我做的第3道2SAT问题。还是没有完全理解，但是更清楚了些。这道题仍然只是判断2SAT是否有界，不需要求解。这里我把每个钥匙看做2SAT里面的一个元素，即一共2M个，考虑到true和false,即xi和~xi，一共4M个。每对不能同时取，即取xi的时候，必须取~xj.另外一个限制是对门的个数二分查找，即考虑前mid个门。每个门，两把钥匙不能同时不取，即取~xi的时候，必须取xj。这

2016-01-08 02:03:40 800

原创 POJ 3280 解题报告

这道题是比较标准的DP题。DP[left][right]记录str[left...right]变成回文字符串的最小代价。可以考虑删掉left, right, 增加left, right，及左右相同的情况。这样就可以转化为长度更小（已经算过）的状态，从而用DP完成。thestoryofsnow3280Accepted13936K63MSC++/

2015-12-16 06:20:57 420

原创 POJ 3678 解题报告

这道题还是2-SAT的问题。一个variable只能取true或者false, 也就是说a 和 ~a（用a + N记录）只能选取一个。给一个他们之间逻辑操作的结果后，问在这些限制下能不能有可能的取法（对所有的a，取a还是~a）。因为这道题还是不要求求出解法，而只是判断，所以和之前做过的POJ 3207是一样的，都算是“简单”的2-SAT问题。做法也是一样的，都是对a, a + N ..., b

2015-12-12 03:37:53 503

原创 POJ 3752 解题报告

简单题。主要是题目没给M，N的范围，实际上很小。所以直接模拟就可以。thestoryofsnow3752Accepted168K16MSC++1195B/* ID: thestor1 LANG: C++ TASK: poj3752 */#include #include #include #include #incl

2015-12-09 02:02:00 750

原创 POJ 2455 解题报告

这道题是最大流（maxflow）题。要点在于用二分搜索(binary search)限制边的最大长度（即可以想象为比这个最大长度还长的边不存在）。这样逐步逼近边长的最佳限制，保证只利用小于等于此边长的边就可以从0到N-1 T次，而且每条边只使用1次（capacity = 1）。这里使用了之前dinic的模板。thestoryofsnow2455Accepted1

2015-12-08 03:42:19 378

原创 POJ 2063 解题报告

这道题是完全背包问题。每一年都求一次背包，最后输出结果。又重温了大牛的背包九讲，照着书中的伪程序写的。注：memset第三个参数是number of bytes，是字节数而不是“元素个数”，所以需要乘以sizeof(int):memset(backpack, 0, (amount / 1000 + 1) * sizeof(int));这里/1000这个优化（应该）是必须的。因为bo

2015-11-24 02:14:42 568

原创 POJ 1952 解题报告

这道题一部分是求最长递减子序列，但是由于要求不重复的最长子序列的个数，所以难度要大些。我这里用的是用一个set过滤重复。算是比较笨的方法，不过也好理解些。比较聪明的方法见这里：http://blog.csdn.net/Silenceneo/article/details/47405407另外，这道题我用c++提交是WA，但是用g++提交AC。由于discuss上面有测试数据，所以基本肯定是

2015-11-07 03:51:19 734

原创 POJ 3026 解题报告

这道题如果看出来是最小生成树之后就很好做了。求出所有alien（包括起点）之间的最短距离（我是用的bfs）,然后求包含所有alien的最小生成树的距离之和就好了。输入是个麻烦的地方。我用的是fgets，需要多分配2位（即52），因为得给\n和'\0'留位置。这里仍然用的是之前kruskal的代码。构图需要点代码。thestoryofsnow3026Accepte

2015-11-05 03:43:59 418

原创 POJ 1089 解题报告

这道题做的挺顺利的。首先按照起点排序，一一扫描，合并后面能合并的，生成一个新区间，输出即可。thestoryofsnow1089Accepted564K63MSC++1053B/* ID: thestor1 LANG: C++ TASK: poj1089 */#include #include #include #in

2015-10-27 23:55:00 998

原创 POJ 2833 解题报告

这道题挺简单的。维护一个最小堆，一个最大堆（因为堆的大小在10以内，我猜数组也可以？）就可以了。thestoryofsnow2833Accepted204K3391MSC++1099B/* ID: thestor1 LANG: C++ TASK: poj2833 */#include #include #include #

2015-10-24 04:31:31 461

原创 POJ 3207 解题报告

这是我遇到的第一道2-SAT问题。将两条边记为x和y。如果x和y相交，那么x和y不能同时在环外（即都取true）,也不能同时在环内（即都取false）。前者，我们有x->~y, y -> ~x;后者，我们有~x->y, ~y -> x。这道题只问2-SAT是否能满足，而没有问怎样才能满足，所以只需要求强连通子图部分，而不需要逆向拓扑排序部分（这部分目前还不是很懂）。thes

2015-10-24 02:57:51 426

原创 POJ 1463 解题报告

这道题是DP。之前应该做过类似的题，对每个节点根据子节点的情况进行DP，但是忘了，看了解题报告才知道这个思路。要点在于因为本题是树形结构，我们可以从根节点开始从上到下DP。对每个节点，有两种可能，cover or not：如果cover了，那么和这个节点相连的边都覆盖到了，所以子节点可以cover也可以不cover；如果不cover，那么子节点必须cover。用f标记父节点，用c标记（其中一个

2015-10-13 01:05:51 487 1

原创 POJ 2376 解题报告

这道题是贪心。当然我是看了discuss才知道的。还是需要多想想多尝试才行。知道是贪心后就简单了。对所有时间段按照开始时间进行排序，然后每次在覆盖当前开始时间的时间段里面选择结束时间最靠后的，用结束时间+1更新开始时间。如果出现不连续，那么就不可能。thestoryofsnow2376Accepted352K79MSC++1422B/

2015-10-09 11:25:21 398

原创 POJ 3074 解题报告

这道题也是数独题。做完了2676后想把这道题也提交了凑数，结果发现TLE了。这道题比上道题题难些，简单暴力搜索无法通过了。看了discuss，提到一种新的算法，不想在学个冷僻的算法了。于是想到数独是AI中的基本题目，当时学到的基本策略在这里应该也是适用的。于是看到了AI课本的作者Peter Norvig的post：Solving Every Sudoku Puzzle(http://norvi

2015-10-06 08:16:06 2023

原创 POJ 2676 解题报告

这道题是DFS。看了discuss，说是倒着搜。从8,8到0,0，应该是根据测试数据来的。thestoryofsnow2676Accepted132K16MSC++2172B/* ID: thestor1 LANG: C++ TASK: poj2676 */#include #include #include #inclu

2015-10-02 04:32:15 443

原创 POJ 2828 解题报告

这道题是道巧妙的线段树(segmentTree)的问题。不是很容易想到。最普通的方法是模拟过程，但是需要数组或链表的操作，时间应该是O(N^2)的，对于多组N=200000的数据，应该是无法通过的（没有尝试过）。然后，如果想到，对最后一个人来说，他想在什么位置，比如2，那么他就可以在这个位置，因为前面的人都需要给他让路。依次类推，对于倒数第二个人，他也有很大的自由度，除非最后一个人已经将这

2015-10-02 00:35:06 396

原创 POJ 2411 解题报告

这道题是状态压缩DP。之前应该做过一次类似的，但这道题比较难些。花了比较久理解状态压缩DP。周伟的论文《状态压缩》是最好的资料。这道题是论文中的一道例题。论文中提到，由于合法状态特别多，所以这里对每一行都跑一次DFS，而不是提前保存下来。这样可以节省空间，时间上也没多少影响。事实也确实如此，16ms就过了。整体过程是从上到下一行行往下填，DP[r][s]表示，第r行状态为s时填充方法有多少

2015-09-30 07:51:07 331

原创 POJ 1562 解题报告

这道题是简单题。就是对每个有油的点跑DFS，把相邻的有油点都标记为没油。这称为一趟。输出趟数即可。thestoryofsnow1562Accepted172K0MSC++1318B/* ID: thestor1 LANG: C++ TASK: poj1562 */#include #include #include #in

2015-09-23 23:42:17 441

原创 POJ 2236 解题报告

这道题是并查集(union-find)应用。知道后就简单了。之前已经多次写过了。这里用的是之前1703的程序。刚开始用的DFS搜索，超时了，看了discuss才知道是并查集。thestoryofsnow2236Accepted196K1079MSC++1957B/* ID: thestor1 LANG: C++ TASK: po

2015-09-23 06:48:48 562

原创 POJ 1469 解题报告

这道题是求最大二分匹配，有匈牙利算法（感觉就是DFS）。这里照搬了之前3041和1274的代码，用的还是邻接矩阵，直接就过了。thestoryofsnow1469Accepted192K469MSC++2659B/* ID: thestor1 LANG: C++ TASK: poj1469 */#include #includ

2015-09-23 00:48:15 523

原创 POJ 1195 解题报告

这道题是二维树状数组（BIT）的基本应用。之前已经写过2155，那道题是区域更新，单点输出，比较异常。这道题是基本的单点更新，区域输出，所以比较好理解，一次就过了。thestoryofsnow1195Accepted4276K594MSC++/* ID: thestor1 LANG: C++ TASK: poj2155 */#inc

2015-09-23 00:00:25 339

原创 POJ 2362 解题报告

这道题是DFS+剪枝。能否通过，重点还是在于保证正确性前提下的剪枝。将棒子按照长度从大到小排序。这样做的原因是：1.排序肯定不会成为瓶颈(O(nlogn) vs O(n!))。排序还可以排除出有一根特长的棒子的情况（超过了边长）。2.从大到小找可以fail faster.1.如果找得只剩下一组了，我们就不用再找了。剩下的一组肯定能拼出来。2.如果是找一组的第一个棒子失败了，那么就不

2015-09-18 06:07:05 452

原创 POJ 1035 解题报告

这道题做起来挺有意思的。一开始的做法是求编辑距离（Levenshtein_distance， https://en.wikipedia.org/wiki/Levenshtein_distance）。因为这道题开着就像是编辑距离。对长度在[len - 1, len + 1]范围内的单词都求编辑距离，然后看diff是不是在1以内。结果超时了。编辑距离的算法是动态规划，每次需要O(n^2)的时间复杂

2015-09-16 00:22:28 382

Nehe的OpenGL教程（PDF）

空空如也