解题思路
题目的意思就一个n位的k进制数中不能有2个及2个以上的0是相邻的，问这样的数一共有多少个 首位肯定不能为0，前面的数如果为0则后面的数可以是除了0以外的任意数，前面的数如果不为0则后面的数就可以为任意值。 代码实现只不过是模拟上面的过程，用一个标记指示某一位是不是为0，如果前一位是0，那当前这位就一种情况就是非0，如果前一位为非0，那么当前这位就需要分两步做，先假设为0，再假设为非0，即使是人工计算也需要这么做。
冗余的垃圾代码
#include<iostream>
#include<cstring>
using namespace std
;
typedef long long ll
;
const int SIZE
= 20;
ll sum
= 1, ans
= 0;
int box
[SIZE
], cnt
= 0;
int vis
[SIZE
];
void dfs(int index
, int n
, int k
)
{
if(index
== n
+ 1)
{
sum
= 1;
for(int i
= 1; i
<= cnt
; ++i
) sum
*= box
[i
];
ans
+= sum
;
return ;
}
if(index
== 1)
{
box
[++cnt
] = k
- 1;
vis
[cnt
] = 1;
dfs(index
+ 1, n
, k
);
--cnt
;
}
else
{
if(vis
[index
- 1] == 0)
{
box
[++cnt
] = k
- 1;
vis
[cnt
] = 1;
dfs(index
+ 1, n
, k
);
--cnt
;
}
else
{
box
[++cnt
] = 1;
vis
[cnt
] = 0;
dfs(index
+ 1, n
, k
);
--cnt
;
box
[++cnt
] = k
- 1;
vis
[cnt
] = 1;
dfs(index
+ 1, n
, k
);
--cnt
;
}
}
return ;
}
int main()
{
int n
, k
;
cin
>> n
>> k
;
memset(vis
, -1, sizeof(vis
));
dfs(1, n
, k
);
cout
<< ans
<< endl
;
return 0;
}
代码中需要注意的地方
if(vis[index - 1] == 0)，第一次写成了cnt - 1代码中一共有3处--cnt，只有第一个是可以不写的，下面两个必须要写，不然就得不到正确答案，因为cnt的意义就是当前的第cnt位，在dfs过程中是会不断增加的，某个位置的情况判断完后，这个位置现在的信息就应该被丢弃了，取而代之的是下面我们要存储的信息，如果不删除之前的信息而让新的信息向后存储，那老的信息就会影响到结果，那结果自然就会出错了。第一个可以删除的原因是，它上面的dfs如果结束以为着这个程序也就该结束了，没有后续的操作了，当前的信息删不删除无所谓了，但是为了程序意义的完整性，还是加上为好。
