POJ 1753 Flip Game

题目

源地址:

http://poj.org/problem?id=1753

理解

我一开始的思路是错误的,企图通过正面的方法来找出从当前情况达到全白和全黑的方法,多次尝试之后,发现很难找到一条通用的方法,只能找出几个比较简单的特例。后来才明白过来,应当从全黑或者全白的情况出发,再来判断给定的图是不是其中的一个子集。因为是一个4X4的格子,不难看出,总共的情况只有2^16种。只要一一枚举即可。最后的步数就是这颗树的深度,使用DFS即可实现。

Read More

POJ 2159 Ancient Cipher

题目

源地址:

http://poj.org/problem?id=2159

理解

一开始的理解是按照题目的意思,先进行一次置换加密再进行一次排列加密。置换只要按照规律一个一个替换就OK,排列加密则用到了next_permutation函数。两重for循环,模拟出去全部的加密方法。Coding出来之后提交,WA。然后才开始审视另外的可能性:谁说置换就一定要按照规律来?事实上,的确如此,按照题意,只需要明文和密文字符形成唯一映射就OK。如果还是按照原来的思路,这道水题还真的不水。其实,在加密过程中,有一样东西是不变的,就是各个字符(对应)出现的频率。这样想的话,就简单了,只要统计出每个字符出现的概率,sort排序后,判断两个数组是否完全一致就好~

Read More

POJ 3299 Humidex

题目

源地址:

http://poj.org/problem?id=3299

理解

我的理解有误。主要是看input里面都是给定T,D求H的情况,便以为这道题就是用一下公式。没想到这道题还有其他的两种情况。说明不管在怎样的条件下,看题都是至关重要的一步。还有就是在输入输出上,%s%c的区别,值得注意。

Read More

POJ 1207 The 3n + 1 problem

题目

源地址:

http://poj.org/problem?id=1207

理解

额,题意很清楚。就是一道关于3n+1的规律题,要求找出给定的i和j之间最长的循环数列。但是我坑了很久,因为错误的使用了A?B:C这样的三元运算符,被学姐学长痛批一顿之后,果断修改了。AC之余,提醒自己一下,良好的代码规范的重要性。

Read More

POJ 1013 Counterfeit Dollar

题目

源地址:

http://poj.org/problem?id=1013

理解

总共有12枚银币,里面有一枚是假货。要求通过三次称量,找出那枚假币,并说出是重了还是轻了。题目中明确指出,三次称量必定能找出那枚假货,使得问题简化了很多。一开始的想法是完全模拟出来,但写到代码的时候感觉过于蛋疼,然后想能不能用一些由计算机来推导的方法。在具体的实现中,发现我很难把问题抽象成计算机可以处理的问题。在一份解题报告的启发下,想到了使用一个数值来度量每个银币可能为假币的可能性的方法。

Read More

POJ 1008 Maya Calendar

题目

源地址:

http://poj.org/problem?id=1008

理解

两种纪年法的转换,另外设一个days的变量保存总天数,然后以它为基准进行变换,没有什么难度。但是在具体的方法上,还是有些优化的余地。比如我不用写那么多长长的if判断语句,使用一个string数组就可以轻松搞定了,这是我不机智的地方。此外,应当注意到,两种纪年法的第一天分别是0和1,要小心。

Read More