自动搬运

查看原文

来自洛谷，原作者为

	ShanCreeperPro DILL QQTeam：746219450

搬运于2025-08-24 21:13:59，当前版本为作者最后更新于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);
}