新建 文本文档.txt

平时acm训练时ac的源代码

(*)ZJU 1003 - Crashing Balloon - 00:00.18 688K 
http://acm.zju.edu.cn/show_problem.php?pid=1003 
WA 2次 AC 1次 
这道题我初看的时候想找数学方法，不过看来行不通。用回溯搜索就可以了。 

先将题目判断胜负的标准列出来： 
1.如果肯定获胜者说谎而挑战者说真话，则挑战者成功。 
2.如果获胜者和挑战者都有可能说了真话，则挑战者失败。 
3.如果挑战者说谎，挑战者失败。 

列表就是： 
获胜者　挑战者　胜方 
　假　　　真　　挑战者 
　真　　　真　　获胜者 
　　　　　假　　获胜者　　 

作法1：那我们只需要先判断挑战者的分数是否能正确分解，不能则输出获胜者的分数。能则进行搜索，先将获胜者的分数进行分解，将用过的因数标记，分解成某一形式后检查挑战者的分数是否能分解为剩下的因数之积。能，说明获胜者有说真话的情况，输出获胜者的分数。一直不能或是获胜者的分数无法分解，说明获胜者说假话，输出挑战者的分数。(见Starfish的程序) 

作法2：用回溯搜索，从2开始一直搜索因数到100。设获胜者的分数为m，挑战者的分数为n(m>n)，当前搜索到的因数为p，flag1为是否两人分数能分解成一合法形式，flag2为挑战者的分数是否符合要求。搜索函数为f(m, n, p)，初始时flag1 = flag2 = FALSE。由于每个因数只能出现一次，所以：如果p|m，则f(m DIV p, n, p+1)，如果p|n，则f(m, n DIV p, p+1)。还有可能不分解出因数p，所以当p<m或p<n时，f(m, n, p+1)。当搜索到m=1且n=1时，说明存在一种没有出现相同因数的分解，设flag1为TRUE。如果发现n=1，则挑战者的分数可以分解，符合要求，设为TRUE。最后的分析表格同上表。优化：flag1和flag2的初始状态都是FALSE，我们由上面的分析可以发现，flag1只要变成TRUE，最后的答案也就定下来了，于是，当flag1发生改变时就可以退出搜索了。(见Bamboo或我的程序) 

错误总结：第一次错在“如果搜索到m和n在2-100之间且m和n相等时，说明存在出现相同因数的情况，设flag2为TRUE”，反例：12 = 2*6 = 3*4。由此发现，是否出现相同因数并不好计算。还有读题目的时候也没理解好，第3点错了。 

另：附有Bamboo，Starfish的代码。我和代码和Bamboo的一样。还有Idler的经验：他的程序和我的几乎一样，但是速度飞快，从大到小搜一般都比较快！最好是看Starfish的代码。