CF1462-C. Unique Number

题意：

给出一个数字x，让你找出一个由1到9这九个数字组成的数字，这个数字的每一位加起来等于x，并且1到9每个数字只能出现一次。若能找到这样的数字，输出这其中最小的一个，否则输出-1。

思路：

利用二进制枚举，枚举每个1到9这九个数字是否出现。每次枚举若和等于x，则将被选中的数字从小到大排列，取得到的数字中最小的一个。若全部枚举完之后并没有找到符合要求的数字，则不存在这样的数字。由于枚举9个数字是否出现，所以最坏情况是\(2^9\)，也就是\(1e3\)的复杂度，必然不会超时。

AC代码：

#include <cstdio>

#include <algorithm>

const int inf = 0x3f3f3f3f;

int main () {

    int T, x;

    scanf ("%d", &T);

    while (T--) {

        scanf ("%d", &x);

        int ans = inf;

        for (int i = 0; i < (1 << 9); i++) {

            int t = 0, s = 0;

            for (int j = 0; j < 9; j++) {

                if (i & (1 << j)) {

                    t = t + j + 1;

                    s = s * 10 + j + 1;

                }

            }

            if (t == x) {

                ans = std::min(ans, s);

            }

        }

        printf ("%d\n", ans == inf ? -1 : ans);

    }

    return 0;

}

巴特西

CF1462-C. Unique Number

题意：

给出一个数字x，让你找出一个由1到9这九个数字组成的数字，这个数字的每一位加起来等于x，并且1到9每个数字只能出现一次。若能找到这样的数字，输出这其中最小的一个，否则输出-1。

思路：

AC代码：

最新文章

热门文章