B3621 枚举元组

ShanCreeperPro · 2022-04-13 13:08:27 · 题解

B3621 枚举元组

前言：

本题解就讲 2 个思路：枚举和 dfs。

但由于我太菜了，4.16 我们的网校才教到 dfs。

所以我现在先提供暴力解法，4.16 更新 dfs。

谢谢大家！

update：4/21 我来更新 dfs 了呜呜。

解法1：枚举：

不懂 dfs 看到这道题的第一思路就是求出 k 进制下的数字。

我们在看一眼这个感人的数据范围：n \leq 5 , k \leq 4。

我们就可以用循环轻松的解决这道问题。

• 当 n=1 时，直接逐个输出从 1 到 n 的所有数，记得换行：

if(n==1){
    fore(i,1,k){
        writeln(i);
    }
}

• 当 n>1 时，设定 n 层循环，每层循环的终止条件均为 k，依次输出从外到内的循环值：

else if(n==2){
    fore(i,1,k){
        fore(j,1,k){
            writesp(i);
            writeln(j);
        }
    }
}
else if(n==3){
    fore(i,1,k){
        fore(j,1,k){
            fore(l,1,k){
                writesp(i);
                writesp(j);
                writeln(l);
            }
        }
    }
}
else if(n==4){
    fore(i,1,k){
        fore(j,1,k){
            fore(l,1,k){
                fore(o,1,k){
                    writesp(i); writesp(j);
                    writesp(l); writeln(o);
                }
            }
        }
        }
    }
else{
    fore(i,1,k){
        fore(j,1,k){
            fore(l,1,k){
                fore(o,1,k){
                    fore(p,1,k){
                        writesp(i); writesp(j);
                        writesp(l); writesp(o);
                        writeln(p);
                    }
                }
            }
        }
    }
}

时间复杂度 O(k^n)，看似是一个极其高的复杂度，我们可以来把题目中最高的值带入：

解法2：dfs：

我们可以写一个 dfs 函数。

• 定义数组 a 来存储每一次的组合，其中 a_i 表示第 i 位的数字；
• dfs(pos)：当我们枚举到 a_{1... \ pos-1} 时，枚举第 pos 位。

比如说 n=3 , k=3 时：

现在枚举到了第 1 位，所以使用 dfs(1+1) 也就是 dfs(2) 来枚举第二位。

那 dfs 怎么写呢？

• 递归一定要设定终止条件：如果枚举到了 n+1 位时，输出数组 a 并 return：

if(pos==n+1){
    fore(i,1,n) writesp(a[i]);
    puts("");
    return;
}

• 否则，填 pos 位：

fore(i,1,k){
    a[pos]=i;
    dfs(pos+1);
}

• 在主程序中，我们从 1 开始枚举：

signed main(){
    n=read(); k=read();
    dfs(1);
}