题解 SP6172 【OAE - OAE】
Chinshyo
2020-11-29 17:30:27
# 方法1：暴力
暴力的思路就是每次读个 $ n $ ，然后双重循环暴力地查找所有可能性。
但是这道题如果用暴力仿佛不太行...如果使用暴力就是 $ O(n^3) $ 的时间复杂度面对 $ 10^6 $ 的数据，不爆就神了。
# 方法2：回溯
回溯的思路就是每次记录下 $ 0 $ 的个数以及当前数字的位数。我们用$ zero count$记录下当前的0的个数。如果位数符合条件并且 $ zerocount \; mod \,2\, =0 $ ，就**得到一种解**。代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
int ans = 0, n;
void dfs(int dep, int zero_count){
if(dep > n){//数位 > n就有可能是解
if(zero_count%2 == 0){
ans++;//得到一种，计数器++；
}
} else {
for(int i = 0; i <= 9; i++){
if(i == 0){
dfs(dep + 1, zero_count+1);//是0就记录0的个数
} else {
dfs(dep + 1, zero_count);
}
}
}
}
int main(){
int t;
cin >> t;
for(int i = 1; i <= t; i++){//无脑输入
cin >> n;
dfs(1, 0);
cout << ans << endl;
ans = 0;
}
return 0;
}
```