RT,题面不是求最大的反质数吗,那么如果假设有两个数a,b,两者的约数个数相同,答案不应该取max(a,b)吗
但我这样写的DFS:
void dfs(int cur,int step,int sum,int top)
{
if(sum>maxn)
{
maxn=sum;
ans=cur;
}
else if(sum==maxn)ans=max(ans,cur);
int tmp=cur;
for(int i=1;i<=top;++i)
{
if(tmp*p[step]>n)return;
tmp*=p[step];
int k=sum*(i+1);
if(tmp<=n)dfs(tmp,step+1,k,i);
}
}
这样就WA穿了,只有30分
30分记录
但如果,我们把上述代码的max改成min,就能AC
代码如下:
void dfs(int cur,int step,int sum,int top)
{
if(sum>maxn)
{
maxn=sum;
ans=cur;
}
else if(sum==maxn)ans=min(ans,cur);
int tmp=cur;
for(int i=1;i<=top;++i)
{
if(tmp*p[step]>n)return;
tmp*=p[step];
int k=sum*(i+1);
if(tmp<=n)dfs(tmp,step+1,k,i);
}
}
100分记录
所以,究竟是我的理解出问题了,还是题面出现问题了QAQ(虽然这题过了这么多人大概率是我的理解有问题,但从题面我真的没有分析出取最小值的意思来QAQ)