题解 P1057 【传球游戏】

· · 题解

对于这一题，我已无语。。。

广搜：


#include<algorithm>  
#include<cstdlib>  
#include<iostream>  
#include<ctime>  
#include<cmath>  
#include<map>  
#include<vector>  
#include<queue>  
#include<iomanip>  
#include<cstring>  
#include<cstdio>  

using namespace std;  

struct ball  
{  
    int time;  //次数
    int s;  
};  

int m,n,h=0,t=1,tmp[3]={0,1,-1},ans=0;  
ball a[100000001];  

int main()  
{  
    //for(int n=3;n<=30;n++)  
    //for(int m=1;m<=30;m++)  
    //{  
    cin>>n>>m;  //输入
    a[1].s=1,a[1].time=0; // 初始化
    do  
    {  
        //cout<<"! ";  
        if(a[h].time>m)  //如果队头的次数超过条件，跳出
            break;  
        h++;  //出队
        for(int i=1;i<=2;i++)  
        {  
            t++;  //入队
            a[t].s=a[h].s+tmp[i];  
            a[t].s=a[t].s==0?n:(a[t].s==n+1?1:a[t].s);  //围成一圈
            a[t].time=a[h].time+1;  
            if(a[t].time==m&&a[t].s==1) //到达条件，答案+1
                ans++;  
        }  
    }while(h<t);  
   cout/*<<"a["<<n<<"]["<<m<<"]="*/<<ans<</*";"<<*/endl;//不要在意注释
    //}  
    return 0;  
}

然而只有40分，因为炸空间。。。

所以我想到深搜。


#include<algorithm>  
#include<cstdlib>  
#include<iostream>  
#include<ctime>  
#include<cmath>  
#include<map>  
#include<vector>  
#include<queue>  
#include<iomanip>  
#include<cstring>  
#include<cstdio>  

using namespace std;  

int m,n,ans=0;  

int search(int a,int tot)  
{  
    if(tot>m)//如果超过条件，返回  
        return 0;  
    if(a==1&&tot==m)//达到条件，答案+1  
        ans++;  
    else  
    {  
        search(a==n?1:a+1,tot+1); // 访问右边
        search(a==1?n:a-1,tot+1); // 访问左边
    }  //三目将人围成圈
}  

int main()  
{  
    cin>>n>>m;
    search(1,0);  
    cout<<ans<<endl;  
    return 0;  
}

然而还只有40分，因为炸时间。。。

所以我模仿楼下，交表。。。