1 条题解
-
1Orina_zju LV 8 MOD @ 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_permutation
和std::next_permutation
函数。3.DFS(100分)
4.打表(100分)
- 1