Any questions?
Reply Back New Topic
View Topic

蒟蒻求助。。不清楚哪里RE 洛谷上可AC


#include<bits/stdc++.h>
using namespace std;
int a[70];
int b[70];
int v[70];
int nn,n,m;
int l,r;
int len;
bool victory;
void dfs(int num,int remain,int k)
{
    if(k>n+1) return;
    if(!remain)
    {
        int tmp;
        if(num==m){victory=true;return;}
        for(int i=1;i<=n;i++) if(!v[i]){tmp=i;break;}
        v[tmp]=1;
        dfs(num+1,len-a[tmp],tmp);
        v[tmp]=0;
        if(victory) return;
    }
    int l=k+1,r=n;
    while(l<r)
    {
        int mid=(l+r)/2;
        if(a[mid]<=remain) r=mid;
        else l=mid+1;
    }
    for(int i=l;i<=n;i++)
    {
        if(!v[i])
        {
            v[i]=1;
            dfs(num,remain-a[i],i);
            v[i]=0;
            if(victory) return;
            if(remain==a[i]||remain==len) return;
            i=i+b[i];
            if(i==n) return;
        }
    }
}
bool cmp(int x,int y)
{
    return x>y;
}
int main()
{
    while(scanf("%d",&nn)!=EOF)
    {
        if(nn==0) break;
        n=0;
        l=0;
        r=0;
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        memset(v,0,sizeof(v));
        for(int i=1;i<=nn;i++) 
        {
            int x;
            cin>>x;
            if(x<=50) a[n+1]=x,l=max(a[++n],l),r+=x;    
        }
        sort(a+1,a+n+1,cmp); 
        for(int i=n-1;i>=1;i--) if(a[i]==a[i+1]) b[i]=b[i+1]+1;
        bool flag=0;
        for(int i=a[1];i<=r;i++)
        {
            if(r%i!=0) continue;
            victory=0;
            m=r/i;
            len=i;
            v[1]=1;
            dfs(1,i-a[1],1);
            if(victory) 
            {
                flag=1;
                cout<<i<<endl;
                break;
            }
            memset(v,0,sizeof(v));
        }
        if(!flag) cout<<r<<endl;
    }
    return 0;
}
View Replies

Replied by ljc20020730 2 months ago 赞:0

Floating point exception 应该是某个地方除以0
但是不应该啊
你使用mo法的地方是r%i 和r/i 而a[1]不可能为0,
应该是我AK的锅


Replied by 1243303647qqcom 2 months ago 赞:5

好的,谢谢!