自动搬运

查看原文

来自洛谷，原作者为

	Sweetlemon 呐，你在这里么？

搬运于2025-08-24 21:21:09，当前版本为作者最后更新于2017-01-24 00:10:03，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

Upd: 这篇题解是我很久以前写的，当时错误也比较多；由于这篇题解的位置比较靠前，为防止误导，现在根据评论区的建议，对这篇题解进行更新。

拿到题目，是不是有一种“手足无措”的感觉呢？

在手足无措之前，先认真审题！

审题有两个要点：一是“$a$ 是 $1\sim n$ 的排列”，二是“字典序”的具体含义。

而且，并不是手足无措——我们可以暴力呢。

暴力的方法当然是，按字典序枚举最开始时的排列，对每一个排列都计算最后得到的数的值，如果这个值和题目给出的 $\mathrm{sum}$ 相等，那么我们就找到答案了。

如何按字典序枚举呢？可以使用 C++ 的 next_permutation 函数，也可以在 dfs 枚举排列时，每一层都从小到大枚举，这样自然就是按“字典序”枚举了。

---

这种方法有什么问题呢？当然是 跑得太慢了。于是我们要考虑优化“枚举”和“计算”的过程。

首先考虑优化“计算”过程。

要优化“计算”过程，就必须搞清楚这个数字三角形究竟是什么。

举例是理解的试金石。

——《数学女孩》

数学上来先打表。

—— OIer 行动准则（雾）

那我们就举例子吧！大家可以自己在草稿纸上写一下，假设 $n$ 为一个比较小的数（比如，按样例，$4$），设第一行的 $n$ 个数分别为 $a,b,c,\cdots$ （我这里是 $a,b,c,d$），然后模拟加一下，就会发现 $\mathrm{sum}$ 是……

如果 $n$ 为 $4$，那么 $\mathrm{sum}$ 是 $a+3b+3c+d$。
如果 $n$ 为 $5$，那么 $\mathrm{sum}$ 是 $a+4b+6c+4d+e$。
如果 $n$ 为 $6$，那么 $\mathrm{sum}$ 是 $a+5b+10c+10d+5e+f$。

观察各项的系数，你发现了什么？

---

如果你有敏锐的数学眼光，你会发现，各项系数恰与杨辉三角有关！恰好是杨辉三角中第 $n-1$ 行的各项系数！

那么我们就可以快速计算出“某个排列玩游戏的结果”了！

注：如果你想要证明这个结论，可以考虑使用“数学归纳法”（如果不了解这个方法，可以查找相关资料），你会发现“相邻两项相加”和杨辉三角（也就是组合数）有密切的联系。不过在 OI 中证明倒显得不是特别重要。

---

下面是算法的过程。

首先，为了避免重复计算，我们算出杨辉三角的值——“预处理”。

由于我们要计算的是杨辉三角一行（第 $n-1$ 行）所有数的值，因此可以使用这个公式：

$$\mathrm{C}^{r}_{n}=\frac{n-r+1}{r}\mathrm{C}^{r-1}_{n} $$

边界是 $\mathrm{C}^{0}_{n}=1$。

上述公式可根据组合数的定义推导。我们还可以利用杨辉三角的对称性，只计算一半（当然算一半和算完并没有显著的效率差异，因为 $n\le 12$ 很小）。

当然，我们也可以用 $\mathrm{C}^r_n=\mathrm{C}^{r-1}_{n-1}+\mathrm{C}^{r}_{n-1}$，边界是 $\mathrm{C}^{n}_{n}=\mathrm{C}^{0}_{n}=1$。

甚至直接根据组合数的定义计算也是可以的，但是要注意避免溢出。

---

然后，使用深度优先搜索。因为 dfs 可以按照题目中的“字典序”依次得出答案，因此我们不需再进行判断。这里使用了一个全局数组 ans 来存储答案。

---

最后，如果有解，输出答案。这个比较简单，就略过了。

---

我们其实还可以进一步优化“枚举”的过程。考虑这个问题：如果一个排列前面的数的（带系数的）和就已经超过了 $\mathrm{sum}$，那它还有可能成为答案吗？当然是不可能的。

因此我们在枚举的过程中可以注意把已枚举出的数的（带系数的）和与 $\mathrm{sum}$ 比较，如果已经比 $\mathrm{sum}$ 大就及时返回（“迷途知返”），从而加快速度。这个优化叫“剪枝”，是加快搜索速度的重要手段。

事实上，题目中的三档子任务，正对应了上面的三级优化！

---

下面是代码。

#include <cstdio>
using namespace std;

int n,sum;
//以下所有数组的大小都比所需值稍大，是为了防止越界
int visited[25]={0}; //防止重复选数，这是 dfs 枚举排列的要点
int ans[25]; //放置答案
int pc[25];//构造所有i C n-1

int dfs(int i,int num,int v); //写函数原型是（我的）好习惯！

int main(void){
    scanf("%d%d",&n,&sum);
    //下面构造杨辉三角(即组合数表)
    pc[0]=pc[n-1]=1; //杨辉三角性质,两边都是1
    if (n>1)
        for (int i=1;i*2<n;i++)
            pc[i]=pc[n-1-i]=(n-i)*pc[i-1]/i; //利用杨辉三角对称性和组合数公式计算
    //下面枚举计算
    if (dfs(0,0,0)) //0 仅起占位符作用
        for (int i=1;i<=n;i++)
            printf("%d ",ans[i]); //输出答案
    return 0;
}

int dfs(int i,int num,int v){
//参数说明：i 表示已经枚举了前 i 个数(数的序号从 1 开始),num 表示第 i 个数是 num，v 表示前 i 个数的“和”为 v
//返回值说明:返回 0 表示不行(不可能)，返回 1 表示找到了可行解。利用返回值就可以在找到第一个解后直接返回了
    if (v>sum) //“剪枝”，及时排除不可能情况，加速枚举
        return 0; //不可能
    if (i==n){ //已经枚举了前 n 个（全部）,判断一下是否是可行解
        if (v==sum){
            ans[i]=num; //放置解
            return 1;
        }
        else
            return 0;
    }
    visited[num]=1; //标记一下“第 i 个数的值已经使用过了”
    //下面寻找第 i+1 个数
    for (int j=1;j<=n;j++){
        if (!visited[j] && dfs(i+1,j,v+pc[i]*j)){ //v+pc[i]*j表示前(i+1)个数的“和”
            //注意，如果数的序号从 1 开始，那么第 i 个数的系数实际上是 (i-1) C (n-1)
            //执行到这里表示已经找到了可行的解
            ans[i]=num;
            return 1;
        }
    }
    visited[num]=0; //如果没有找到，一定记得复位，为进一步的寻找做准备
    return 0; //执行到这里一定是没有找到解
}
Show you my code(C++,94 ms,776 KB).