11 thestoryofsnow

尚未进行身份认证

学生 研一

等级
TA的排名 1w+

POJ 1101 解题报告

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

2016-08-31 00:04:22

POJ 1661 解题报告

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

2016-08-19 03:44:03

POJ 1154 解题报告

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

2016-08-18 07:22:40

POJ 3983 解题报告

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

2016-08-17 01:06:31

POJ 3723 解题报告

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

2016-08-10 00:52:22

POJ 2536 解题报告

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

2016-08-04 00:14:27

POJ 2482 解题报告

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

2016-08-03 04:37:26

POJ 3087 解题报告

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

2016-05-25 08:51:48

POJ 2499 解题报告

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

2016-03-30 00:58:13

POJ 3255 解题报告

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

2016-03-25 02:33:41

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

POJ 3637 解题报告

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

2016-02-27 01:54:47

POJ 1230 解题报告

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

2016-02-27 01:23:58

POJ 1635 解题报告

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

2016-02-20 05:53:18

POJ 1523 解题报告

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

2016-02-06 02:12:38

POJ 1828 解题报告

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

2016-02-02 02:39:40

POJ 2892解题报告

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

2016-02-02 01:42:12

POJ 2723 解题报告

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

2016-01-08 02:03:40

POJ 3280 解题报告

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

2015-12-16 06:20:57

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

查看更多

勋章 我的勋章
    暂无奖章