Team Shirts/Jerseys
题意：给你n个数，然后你随便选一个数（1~99），问你这n+1个数是否可以拼接成给定得数字
解释：dfs，注释在代码中给出。
链接：https://nanti.jisuanke.com/t/44152
#include<bits/stdc++.h> using namespace std; const int maxn=1e2+10; typedef long long ll; ll str; ll n,len,a[maxn],b[maxn],c[maxn]; ll vis[maxn]; void init() { cin>>str>>n; ll temp=str; while(temp) { len++; temp/=10; } for(int i=len-1;i>=0;i--) { a[i]=str%10; //先把str换成数组保存 str/=10; } for(int i=0;i<n;i++) { cin>>temp; b[i]=temp/10; c[i]=temp%10; //分解每一个数得十位和个位 } } ll dfs(ll pos,ll flag) //pos表示当前dfs到哪个为止，flag表示是否使用了特殊数字 { if(pos==len) return 1; // 成功得到答案 if(pos>len||a[pos]==0) return 0; //如果超出数字范围，或者遍历位置是0(不会出现前导0der) if(flag==0&&(dfs(pos+1,1)||dfs(pos+2,1))) return 1; //使用特殊数字，跳过一位或者两位 for(int i=0;i<n;i++) { if(!vis[i]) { int t=0; for(int j=0;j<i;j++) { if(!vis[j]&&b[j]==b[i]&&c[j]==c[i]) { t=1; break; } } /*上面的for是剪枝效果，如果我当前 之前已经遍历过和我相同地数字，而且没又 采用，这这次必不可能采用*/ if(t) continue; if(b[i]==0) //下面就是很常规的判断了 { if(c[i]==a[pos]) { vis[i]=1; if(dfs(pos+1,flag)) return 1; vis[i]=0; } } else if(pos+1<len) { if(b[i]==a[pos]&&c[i]==a[pos+1]) { vis[i]=1; if(dfs(pos+2,flag)) return 1; vis[i]=0; } } } } return 0; } int main() { std::ios::sync_with_stdio(false); init(); cout<<dfs(0,0)<<endl; return 0; }