/ TYWZ / 题库 / Decimal /

题解

1 条题解

  • 1
    @ 2019-01-28 13:51:43

    1.暴力枚举(40~70分)
    枚举所有的七位数,如果满足所有限制条件则更新答案。

    2.优化枚举的状态数(100分)
    显然暴力枚举时会有很多无用状态。设\(x_1 = 5\),那么5000000~5999999这100万个数都是无效的,但枚举时还会逐个检查一遍。
    我们可以对枚举过程进行优化:首先枚举所有的“10选7”组合,也就是\(0,1 \cdots 9\)这10个数字中选出7个,然后对所有不含\(x_1,x_2\)的组合枚举其全排列。
    枚举“10选7”组合的参考代码:

    int arr[7] = {0, 1, 2, 3, 4, 5, 6}
    bool finish = false;
    while (!finish) 
    {
        //Output a[]
        int p = 6;
        for (; p >= 0 && arr[p] == p + 3; --p) {}
        if (p == -1)
            finish = true;
        else 
        {
            arr[p] += 1;
            for (++p; p < 7; ++p)
                arr[p] = arr[p - 1] + 1;
        }
    }
    

    枚举全排列的过程可以直接调用<algorithm>中的std::prev_permutationstd::next_permutation函数。

    3.DFS(100分)

    4.打表(100分)

  • 1

信息

难度
8
分类
搜索 | 枚举搜索与剪枝 点击显示
标签
(无)
递交数
45
已通过
6
通过率
13%
上传者