题目 1117: K-进制数

解题思路

题目的意思就一个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; // is not zerodfs(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 {
    //The value of this point is 0box[++cnt] = 1;vis[cnt] = 0;dfs(index + 1, n, k);--cnt;//The value of this point is not 0box[++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;
}

代码中需要注意的地方

1. if(vis[index - 1] == 0)，第一次写成了cnt - 1
2. 代码中一共有3处--cnt，只有第一个是可以不写的，下面两个必须要写，不然就得不到正确答案，因为cnt的意义就是当前的第cnt位，在dfs过程中是会不断增加的，某个位置的情况判断完后，这个位置现在的信息就应该被丢弃了，取而代之的是下面我们要存储的信息，如果不删除之前的信息而让新的信息向后存储，那老的信息就会影响到结果，那结果自然就会出错了。第一个可以删除的原因是，它上面的dfs如果结束以为着这个程序也就该结束了，没有后续的操作了，当前的信息删不删除无所谓了，但是为了程序意义的完整性，还是加上为好。