【题解】牛客 Numbers⭐⭐ 【Dfs】

牛客 Numbers

Input

Output

For each test case, print an integer which denotes the result.

Examples

输入 复制 999 233333 0123456789 输出 复制 2 0 55

题意:

给出一个数, 问1-99有几种方案组成他

题解:

数位简单Dfs

#include<bits/stdc++.h> using namespace std; #define ms(x, n) memset(x,n,sizeof(x)); typedef long long LL; const int INF = 1 << 30; const int MAXN = 110; string s; int len, ans = 0; bool used[MAXN]; void Dfs(int p){ if(p == len){ ++ans; return; } if(!used[stoi(s.substr(p, 1))]){ used[stoi(s.substr(p, 1))] = true; Dfs(p+1); used[stoi(s.substr(p, 1))] = false; } if(p+2 <= len && s[p] != '0' && !used[stoi(s.substr(p, 2))]){ used[stoi(s.substr(p, 2))] = true; Dfs(p+2); used[stoi(s.substr(p, 2))] = false; } } int main() { ios::sync_with_stdio(false); while(cin >> s){ ms(used, 0); len = s.length(), ans = 0; Dfs(0); cout << ans << endl; } return 0; }