谁给个思路，有那些特殊情况要考虑。自己写了一个，但不对
#include "iostream.h"
#include <memory.h>
#include "math.h"
#define N 100
int find_common_factor(int *arrary , int x)
{//找出一个数的所有公因子，并放在arrary中，
int i , j , k , l , n;
n = (int)sqrt(x) ;
if(x != n * n)
++n ;//x刚好为完全平方
for(l = 2 , j = 0 ; l < n ; ++l )
if(x % l == 0)
arrary[j++] = l ;
i = (2 * j - 1) ;
for(k = 0 ; i >= j && k < j ; --i , k++)
arrary[i] = x / arrary[k] ;
arrary[2 * j] = x ;
return 2 * j + 1 ;
}
int findX(int *arrary , int n , int x)
{
int min , mid , max ;
min = 0 ;
max = n ;
mid = (min + max) / 2 ;
if(x < arrary[0] || x > arrary[n-1])
return 0 ;
while(min <= max)
{
if(x > arrary[mid])
min = mid + 1 ;
else if(x < arrary[mid])
max = mid - 1 ;
else return 1 ;
mid = (min + max) / 2 ;
}
return 0 ;
}
int main()
{
int arrary1[N] = {0} ;
int arrary2[N] = {0} ;
int i ;
int n , m ;
int flag ;
int len1 , len2 ;
while (cin>>n>>m) {
len1 = find_common_factor(arrary1 , n) ;
len2 = find_common_factor(arrary2 , m) ;
if((arrary1[len1 - 1] > 100) && (arrary2[len2 - 1] > 100))//大家都撒谎
{
cout<<(n > m ? n : m) <<endl ;
continue ;
}
if((n <= 100) && (m <= 100) && (n != m))
{
cout<<(n > m ? n : m) <<endl ;
}
else if(n >= m)
{
flag = 0 ;
for(i = 0 ; i < len2 ; ++i)
if(findX(arrary1 , len1 , arrary2[i]) && len2 < 3)
{
cout<<m<<endl ;
flag = 1 ;
break ;
}
if(!flag)
cout<<n<<endl ;
}
else if(n < m)
{
flag = 0 ;
for(i = 0 ; i < len1 ; ++i)
if(findX(arrary2 , len2 , arrary1[i]) < 3)
{
cout<<n<<endl ;
flag = 1 ;
break ;
}
if(!flag)
cout<<m<<endl ;
}
}
return 1 ;
}
5 个解决方案
#1
以前写的程序：
//#include <iostream>
#include <fstream>
#include <set>
using namespace std;
ifstream cin("1003.in");
ofstream cout("1003.out");
int low,up;
int mark[101]={0};
int ln,sn;
bool decodeu(int n)
{
if(n == 1)
return true;
for(int i=2;i<(n+1<101?n+1:101);i++)
{
if(!mark[i])continue;
if(n%i)continue;
mark[i]=0;
if(decodeu(n/i))
return true;
mark[i]=1;
}
return false;
}
bool decodel(int n)
{
if(n == 1)
{
ln++;
if(decodeu(up))
sn++;
return true;
}
for(int i=2;i<(n+1<101?n+1:101);i++)
{
if(!mark[i])continue;
if(n%i)continue;
mark[i]=0;
decodel(n/i);
mark[i]=1;
}
return false;
}
bool proc()
{
int i,j;
sn=0; ln=0;
decodel(low);
if(ln == 0)
return false;
if(sn == 0)
return true;
else
return false;
}
int main()
{
while(cin>>up>>low)
{
for(int i=0;i<101;i++)
mark[i]=1;
if(up<low) // ×¢Òâ:ÌâÄ¿²¢Ã»ÓÐ˵Ã÷Ç°ÃæµÄÊÇup,ºóÃæµÄÊÇlow
{int t=up;up=low;low=t;}
if(proc())
cout<<low<<endl;
else
cout<<up<<endl;
}
return 0;
}
//#include <iostream>
#include <fstream>
#include <set>
using namespace std;
ifstream cin("1003.in");
ofstream cout("1003.out");
int low,up;
int mark[101]={0};
int ln,sn;
bool decodeu(int n)
{
if(n == 1)
return true;
for(int i=2;i<(n+1<101?n+1:101);i++)
{
if(!mark[i])continue;
if(n%i)continue;
mark[i]=0;
if(decodeu(n/i))
return true;
mark[i]=1;
}
return false;
}
bool decodel(int n)
{
if(n == 1)
{
ln++;
if(decodeu(up))
sn++;
return true;
}
for(int i=2;i<(n+1<101?n+1:101);i++)
{
if(!mark[i])continue;
if(n%i)continue;
mark[i]=0;
decodel(n/i);
mark[i]=1;
}
return false;
}
bool proc()
{
int i,j;
sn=0; ln=0;
decodel(low);
if(ln == 0)
return false;
if(sn == 0)
return true;
else
return false;
}
int main()
{
while(cin>>up>>low)
{
for(int i=0;i<101;i++)
mark[i]=1;
if(up<low) // ×¢Òâ:ÌâÄ¿²¢Ã»ÓÐ˵Ã÷Ç°ÃæµÄÊÇup,ºóÃæµÄÊÇlow
{int t=up;up=low;low=t;}
if(proc())
cout<<low<<endl;
else
cout<<up<<endl;
}
return 0;
}
#2
中间一段注释竟变成乱码了，
把main函数重贴：
int main()
{
while(cin>>up>>low)
{
for(int i=0;i<101;i++)
mark[i]=1;
if(up<low)
{int t=up;up=low;low=t;}
if(proc())
cout<<low<<endl;
else
cout<<up<<endl;
}
return 0;
}
把main函数重贴：
int main()
{
while(cin>>up>>low)
{
for(int i=0;i<101;i++)
mark[i]=1;
if(up<low)
{int t=up;up=low;low=t;}
if(proc())
cout<<low<<endl;
else
cout<<up<<endl;
}
return 0;
}
#3
感觉自己的方法比较笨，但是被accepted了。
思路就是：两层回溯。
你可以看到在对小的数字分解的过程中（decodel），调用了对大数字分解的decodeu。
需要想清楚状态的记录问题
思路就是：两层回溯。
你可以看到在对小的数字分解的过程中（decodel），调用了对大数字分解的decodeu。
需要想清楚状态的记录问题
#4
原来帖在ZJU的讨论区里了 今天再往这里帖一次 请大家提出意见:)
(*)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的代码。
(*)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的代码。
#5
mark
#1
以前写的程序：
//#include <iostream>
#include <fstream>
#include <set>
using namespace std;
ifstream cin("1003.in");
ofstream cout("1003.out");
int low,up;
int mark[101]={0};
int ln,sn;
bool decodeu(int n)
{
if(n == 1)
return true;
for(int i=2;i<(n+1<101?n+1:101);i++)
{
if(!mark[i])continue;
if(n%i)continue;
mark[i]=0;
if(decodeu(n/i))
return true;
mark[i]=1;
}
return false;
}
bool decodel(int n)
{
if(n == 1)
{
ln++;
if(decodeu(up))
sn++;
return true;
}
for(int i=2;i<(n+1<101?n+1:101);i++)
{
if(!mark[i])continue;
if(n%i)continue;
mark[i]=0;
decodel(n/i);
mark[i]=1;
}
return false;
}
bool proc()
{
int i,j;
sn=0; ln=0;
decodel(low);
if(ln == 0)
return false;
if(sn == 0)
return true;
else
return false;
}
int main()
{
while(cin>>up>>low)
{
for(int i=0;i<101;i++)
mark[i]=1;
if(up<low) // ×¢Òâ:ÌâÄ¿²¢Ã»ÓÐ˵Ã÷Ç°ÃæµÄÊÇup,ºóÃæµÄÊÇlow
{int t=up;up=low;low=t;}
if(proc())
cout<<low<<endl;
else
cout<<up<<endl;
}
return 0;
}
//#include <iostream>
#include <fstream>
#include <set>
using namespace std;
ifstream cin("1003.in");
ofstream cout("1003.out");
int low,up;
int mark[101]={0};
int ln,sn;
bool decodeu(int n)
{
if(n == 1)
return true;
for(int i=2;i<(n+1<101?n+1:101);i++)
{
if(!mark[i])continue;
if(n%i)continue;
mark[i]=0;
if(decodeu(n/i))
return true;
mark[i]=1;
}
return false;
}
bool decodel(int n)
{
if(n == 1)
{
ln++;
if(decodeu(up))
sn++;
return true;
}
for(int i=2;i<(n+1<101?n+1:101);i++)
{
if(!mark[i])continue;
if(n%i)continue;
mark[i]=0;
decodel(n/i);
mark[i]=1;
}
return false;
}
bool proc()
{
int i,j;
sn=0; ln=0;
decodel(low);
if(ln == 0)
return false;
if(sn == 0)
return true;
else
return false;
}
int main()
{
while(cin>>up>>low)
{
for(int i=0;i<101;i++)
mark[i]=1;
if(up<low) // ×¢Òâ:ÌâÄ¿²¢Ã»ÓÐ˵Ã÷Ç°ÃæµÄÊÇup,ºóÃæµÄÊÇlow
{int t=up;up=low;low=t;}
if(proc())
cout<<low<<endl;
else
cout<<up<<endl;
}
return 0;
}
#2
中间一段注释竟变成乱码了，
把main函数重贴：
int main()
{
while(cin>>up>>low)
{
for(int i=0;i<101;i++)
mark[i]=1;
if(up<low)
{int t=up;up=low;low=t;}
if(proc())
cout<<low<<endl;
else
cout<<up<<endl;
}
return 0;
}
把main函数重贴：
int main()
{
while(cin>>up>>low)
{
for(int i=0;i<101;i++)
mark[i]=1;
if(up<low)
{int t=up;up=low;low=t;}
if(proc())
cout<<low<<endl;
else
cout<<up<<endl;
}
return 0;
}
#3
感觉自己的方法比较笨，但是被accepted了。
思路就是：两层回溯。
你可以看到在对小的数字分解的过程中（decodel），调用了对大数字分解的decodeu。
需要想清楚状态的记录问题
思路就是：两层回溯。
你可以看到在对小的数字分解的过程中（decodel），调用了对大数字分解的decodeu。
需要想清楚状态的记录问题
#4
原来帖在ZJU的讨论区里了 今天再往这里帖一次 请大家提出意见:)
(*)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的代码。
(*)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的代码。
#5
mark