文章

排列小球(2021模拟赛)

排列小球1.png排列小球2.png

深度优先搜素,依次递归。。。。。。。。。。

#include<bits/stdc++.h>
using namespace std;
long long int cnt=0,maxn;
long long int a[100];
void dfs(int num,int key){//前一颗颜色 前面球数 
    int i;
    if(a[1]==0&&a[2]==0&&a[3]==0) {
        cnt++;
//      cout<<"yes"<<endl;
        return ;
    }
    if(num!=1&&a[1]>key){
    //不是同颜色的小球&&满足单调递增 
        maxn=a[1];
//      cout<<"a[1]"<<maxn<<endl;
        for(i=key+1;i<=maxn;i++){
            a[1]-=i;
//          cout<<"r"<<i<<' ';
            dfs(1,i);
            a[1]+=i;
        }
    }
    if(num!=2&&a[2]>key){
    //不是同颜色的小球&&满足单调递增 
        maxn=a[2];
//      cout<<"a[2]"<<maxn<<endl;
        for(i=key+1;i<=maxn;i++){
            a[2]-=i;
//          cout<<"g"<<i<<' ';
            dfs(2,i);
            a[2]+=i;
        }
    }
    if(num!=3&&a[3]>key){
    //不是同颜色的小球&&满足单调递增 
        maxn=a[3];
//      cout<<"a[3]"<<maxn<<endl;
        for(i=key+1;i<=maxn;i++){
            a[3]-=i;
//          cout<<"b"<<i<<' ';
            dfs(3,i);
            a[3]+=i;
        }
    }
    if(a[1]!=0||a[2]!=0||a[3]!=0) {
//      cout<<endl;
        return ;
    }
}
int main()
{
    long long int i;
//  a[1]=3;
//  a[2]=6;
//  a[3]=0;
    for(i=1;i<=3;i++) cin>>a[i];
//  for(i=1;i<=3;i++){
//      cout<<a[i]<<' ';
//  }cout<<endl;
    dfs(-1,0);
//  cout<<"cnt";
    cout<<cnt<<endl;
    return 0;
}

原题链接

https://www.lanqiao.cn/problems/546/learning/

License:  CC BY 4.0