K-进制数-题解（C++代码）

解题思路:利用深度优先搜索的方法  判断首位不能为零  并且不能存在  多个零相挨的情况（看完大佬写的

我最初开始写的  直接求[k^(n-1),k^n] 区间满足条件的个数  但是在判断是否存在多个零相挨的时候  时间超限（逐个遍历），不知各位大佬

有没有解决办法

注意事项:判断条件哪里不要喽了条件

参考代码:

#include<iostream>

using namespace std;

int a[100];

int n,k,count=0;

void dfs(int cnt)

{

if(cnt==n)//位数达到 n 位 

{

count++;

return ; 

}

for(int i=0;i<k;i++)

{

if((cnt==0&&i==0)||(cnt>1&&i==0&&a[cnt-1]==0))continue;//判断首位不能为 0 并且 不能存在  00 这种状态 

a[cnt]=i;

dfs(cnt+1);//继续下一位 

}

}

int main()

{

cin>>n>>k;

dfs(0);

cout<<count;

return 0;

}