洛谷P1118-Backward_Digit_Sums_G/S-题解

Backward Digit Sums G/S

题目描述

FJ and his cows enjoy playing a mental game. They write down the numbers from $1$ to$ N(1 \le N \le 10)$ in a certain order and then sum adjacent numbers to produce a new list with one fewer number. They repeat this until only a single number is left. For example, one instance of the game (when $N=4$) might go like this:

3   1   2   4
  4   3   6
    7   9
     16

Behind FJ's back, the cows have started playing a more difficult game, in which they try to determine the starting sequence from only the final total and the number $N$. Unfortunately, the game is a bit above FJ's mental arithmetic capabilities.

Write a program to help FJ play the game and keep up with the cows.

题面翻译

有这么一个游戏：

写出一个 $1\sim n$ 的排列 $a$，然后每次将相邻两个数相加，构成新的序列，再对新序列进行这样的操作，显然每次构成的序列都比上一次的序列长度少 $1$，直到只剩下一个数字位置。

下面是一个例子：

• $3,1,2,4$；
• $4,3,6$；
• $7,9$；
• $16$。

最后得到 $16$ 这样一个数字。

现在想要倒着玩这样一个游戏，如果知道 $n$，以及最后得到的数字的大小 $sum$，请你求出最初序列 $a_i$（应该是一个 $1\sim n$ 的排列）。若答案有多种可能，则输出字典序最小的那一个。

我们称序列 $a=\langle a_1,a_2,\cdots,a_n\rangle$ 的字典序小于序列 $b=\langle b_1,b_2,\cdots,b_n\rangle$ 的字典序，当且仅当存在一个位置 $p$，满足 $a_1=b_1,a_2=b_2,\cdots,a_{p-1}=b_{p-1},a_p<b_p$。

输入格式

共一行两个正整数 $n,sum$。

输出格式

输出包括一行，为字典序最小的那个答案。

当无解的时候，请什么也不输出。

样例 #1

样例输入 #1

4 16

样例输出 #1

3 1 2 4

提示

• 对于 $40\%$ 的数据，$1\le n\le 7$；
• 对于 $80\%$ 的数据，$1\le n \le 10$；
• 对于 $100\%$ 的数据，$1\le n \le 12$，$1\le sum\le 12345$。

P1118 [USACO06FEB] Backward Digit Sums G/S - 洛谷

思路

这题我一开始刚看的时候，想着就直接暴力枚举n个数的排列，结果就只有50分，十个点里，一个WA，四个TLE。~~WA的原因是没用判断两个输入都是1的情况。~~这个思路肯定不大行。

分析题目规律可以发现，这题很像一个杨辉三角形，只不过这个是倒过来的，并且满足一个性质————给定我n个数，这n个数最后的结果，就是这n个数以杨辉三角形第n行的数为系数的数的和。

说通俗点就是$$target = (1\times{a}) + (x_1\times{b}) + (x_2\times{c}) + (x_3\times{d}) + (x_2\times{e}) + (x_1\times{e}) + (1\times{g})$$
如：$16 = 3\times{1} + 1\times{3} + 2\times{3} + 4\times{1} = 3 + 3 + 6 + 4$

附：杨辉三角形前12层

                      1
                    1 , 1
                  1 , 2 , 1
                1 , 3 , 3 , 1
              1 , 4 , 6 , 4 , 1
            1 , 5 , 10, 10, 5 , 1
          1 , 6 , 15, 20, 15, 6 , 1
        1 , 7 , 21, 35, 35, 21, 7 , 1
      1 , 8 , 28, 56, 70, 56, 28, 8 , 1
    1 , 9 , 36, 84,126,126, 84, 36, 9 , 1
  1 , 10, 45,120,210,252,210,120, 45, 10, 1
1 , 11, 55,165,330,462,462,330,165, 55, 11, 1

这样，我们就可以通过杨辉三角形来快速算出每个排列最后的和了，接着，我们搜索每一种排列即可

对于熟悉STL的同学，我们知道algorithm库里包含了next_permutation()函数，这个函数可以求出容器的下一个全排列（按照字典序），这样便省去了我们手写搜索的问题。不会STL才是亏

但即使用了杨辉三角形，我们还是会出现TLE的情况，为此，我们可以在搜索的过程再优化

当我们的累加和的过程的数大于我们的target的时候，说明从这个点开始，后面的数都不满足了，我们可以通过排序，来跳过这段求和，这样就可以跳过这段搜索了

构建杨辉三角形表

vector<vector<int> > table(n);
table[0] = {1};
for (int i = 1; i < n; ++i) {
    table[i].resize(i + 1);
    table[i][0] = table[i][i] = 1;
    for (int j = 1; j < i; ++j)
        table[i][j] = table[i - 1][j - 1] + table[i - 1][j];
}

全排列搜索及优化（虽然用goto是个不好的习惯，但是，cpp没有continue label的设计，那为了方便我就用goto了，当然，这里不用goto也可以，改一下逻辑就好）

for (int i = 0; i < n; ++i)
    ans[i] = i + 1;
for (int tmp = 0;
     (next_permutation(ans.begin(), ans.end()) or target == 1);
     tmp = 0) {
    for (int i = 0; i < n; ++i) {
        tmp += ans[i] * table[n - 1][i];
        if (tmp > target) {
            sort(ans.begin() + i, ans.end(),
                 [](auto a, auto b) {
                     return a > b;
                 });
            goto EndOfFor;
        }
    }
    if (tmp == target) {
        for (auto &j: ans)
            cout << j << ' ';
        return 0;
    }
    EndOfFor:
    continue;
}

完整代码

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie();
    cout.tie();
    int n, target;
    cin >> n >> target;
    vector<int> ans(n);
    vector<vector<int> > table(n);
    table[0] = {1};
    for (int i = 1; i < n; ++i) {
        table[i].resize(i + 1);
        table[i][0] = table[i][i] = 1;
        for (int j = 1; j < i; ++j)
            table[i][j] = table[i - 1][j - 1] + table[i - 1][j];
    }
    for (int i = 0; i < n; ++i)
        ans[i] = i + 1;
    for (int tmp = 0;
         (next_permutation(ans.begin(), ans.end()) or target == 1);
         tmp = 0) {
        for (int i = 0; i < n; ++i) {
            tmp += ans[i] * table[n - 1][i];
            if (tmp > target) {
                sort(ans.begin() + i, ans.end(),
                     [](auto a, auto b) {
                         return a > b;
                     });
                goto EndOfFor;
            }
        }
        if (tmp == target) {
            for (auto &j: ans)
                cout << j << ' ';
            return 0;
        }
        EndOfFor:
        continue;
    }
    return 0;
}

AC截图