洛谷B3621 枚举元组 题解

题目链接：B3621 枚举元组

题目描述

\(n\) 元组是指由 \(n\) 个元素组成的序列。例如 \((1,1,2)\) 是一个三元组、\((233,254,277,123)\) 是一个四元组。

给定 \(n\) 和 \(k\)，请按字典序输出全体 \(n\) 元组，其中元组内的元素是在 \([1, k]\) 之间的整数。

「字典序」是指：优先按照第一个元素从小到大的顺序，若第一个元素相同，则按第二个元素从小到大……依此类推。详情参考样例数据。

当 \(n=2,k=3\) 时就是下面这样

1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3

输入格式

仅一行，两个正整数 \(n, k\)。

输出格式

若干行，每行表示一个元组。元组内的元素用空格隔开。

数据范围

对于 \(100\%\) 的数据，有 \(n\leq 5, k\leq 4\)。

可以发现，我们每一行需要输出 \(n\) 列数字，并且输出的方式就像是套了 \(n\) 层循环，每层从 \(1\) 到 \(k\) 。

找到规律就知道怎么做了，考虑 dfs 来控制输出。具体的，我们需要设计一个像下面这样的程序

int num[15]; // 用数组临时记录
void dfs( 当前是第几层循环，记为 u )
{
	if( 现在到第n+1层了 ) -> 过头了，输出，然后return;
	否则枚举 num[u] 填 1~k 的哪个数字
        -> 填好了进入 dfs(u + 1) ，等 dfs(u + 1) 做完它的任务，就继续
}

算了我觉得不如直接放代码。

时间复杂度是 \(O(nk^n)\) ，因为 \(n\) 层循环，每层循环到 \(k\) ，共 \(k^n\) 种状态，每个状态输出还要 \(O(n)\) 。

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
template<typename T> void up(T &x, T y) { x < y ? x = y : 0; }
template<typename T> void down(T &x, T y) { x > y ? x = y : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N ((int)())

int n, k, num[15];
void dfs(int u)
{
    if(u > n) { rep(i, 1, n) cout << num[i] << " \n"[i == n]; return; }
    rep(i, 1, k) { num[u] = i; dfs(u + 1); }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> k; dfs(1);
    return 0;
}

题外话：

最近打算做点难度比较简单的题练习一下代码水平。