一个永久离开OI界(超龄)的技术少年的内容杂烩

优化程序过程中一步一步的意外发现

2018-07-14 14:49:04


这道题本身比较容易

本题解的重点不在于讨论本题的算法,而在于探索如何尽可能地一步一步降低时间复杂度。

一个很普通的程序代码如下:

#include<iostream>
using namespace std;
const short cl[10] = { 6,2,5,5,4,5,6,3,7,6 };
short lx(int cn)
{
    short sm=0;
    do
    {
        sm+=cl[cn % 10];
        cn /= 10;
    } while (cn != 0);
    return sm;
}
int main()
{
    short n;
    cin >> n;
    n -= 4;
    long sum = 0;
    for (int a = 0; a <= 711; a++)
        for (int b = 0; b <= 711; b++)
        {
            int c = a + b;
            if (lx(a) + lx(b) + lx(c) == n)
                sum++;
        }
    cout << sum;
    return 0;
}

这个程序的实现方法非常普通,一般人都能写出来。相信大家阅读程序后发现我在程序中的枚举上界是711。

为什么711这么特殊?

通过分析可知,用火柴棒摆出从0到9的每个数字所需要的火柴棒的数量分别是6,2,5,5,4,5,6,3,7,6.其中数字1所用的火柴棒最少,但摆出1仍然要占用1个数位。一个全部由1组成的数比位数相同的其他数字所用的火柴棒数都要少。

因此,稍作思考就可得出一个粗略的上界:1111。

但1111是不是一个完美的上界?答案是否定的。 为了找出这个完美的上界,我编写了一个验证器。

验证器代码如下:

#include<iostream>
using namespace std;
const short cl[10] = { 6,2,5,5,4,5,6,3,7,6 };
short lx(int cn)
{
    short sm = 0;
    do
    {
        sm += cl[cn % 10];
        cn /= 10;
    } while (cn != 0);
    return sm;
}
int main()
{
    bool f = false;
    for(short a=0;a<=1111;a++)
        for (short b = 0; b <= 1111; b++)
        {
            short c = a + b;
            short on = lx(a) + lx(b) + lx(c);
            if (on <= 20)
            {
                cout << a << " " << b << " " << c << " " << on << endl;
                f = true;
            }
        }
    if (!f)
        cout << "No.";
    return 0;
}

这个验证器的作用是输出1111以内的全部存在的满足条件的火柴棒等式关系。

输出结果如下

每行的4个数分别表示:A、B、C、不含运算符的火柴棒数。

0 0 0 18
0 1 1 10
0 2 2 16
0 3 3 16
0 4 4 14
0 5 5 16
0 6 6 18
0 7 7 12
0 8 8 20
0 9 9 18
0 11 11 14
0 12 12 20
0 13 13 20
0 14 14 18
0 15 15 20
0 17 17 16
0 21 21 20
0 31 31 20
0 41 41 18
0 47 47 20
0 51 51 20
0 71 71 16
0 74 74 20
0 77 77 18
0 111 111 18
0 117 117 20
0 171 171 20
0 711 711 20
1 0 1 10
1 1 2 9
1 2 3 12
1 3 4 11
1 4 5 11
1 5 6 13
1 6 7 11
1 7 8 12
1 8 9 15
1 9 10 16
1 10 11 14
1 11 12 13
1 12 13 16
1 13 14 15
1 14 15 15
1 15 16 17
1 16 17 15
1 17 18 16
1 18 19 19
1 20 21 20
1 21 22 19
1 30 31 20
1 31 32 19
1 40 41 18
1 41 42 17
1 42 43 20
1 43 44 19
1 44 45 19
1 46 47 19
1 47 48 20
1 50 51 20
1 51 52 19
1 70 71 16
1 71 72 15
1 72 73 18
1 73 74 17
1 74 75 17
1 75 76 19
1 76 77 17
1 77 78 18
1 110 111 18
1 111 112 17
1 112 113 20
1 113 114 19
1 114 115 19
1 116 117 19
1 117 118 20
1 170 171 20
1 171 172 19
1 710 711 20
1 711 712 19
2 0 2 16
2 1 3 12
2 2 4 14
2 3 5 15
2 4 6 15
2 5 7 13
2 6 8 18
2 7 9 14
2 8 10 20
2 9 11 15
2 10 12 20
2 11 13 16
2 12 14 18
2 13 15 19
2 14 16 19
2 15 17 17
2 17 19 18
2 19 21 20
2 41 43 20
2 71 73 18
2 72 74 20
2 75 77 19
2 77 79 20
2 111 113 20
3 0 3 16
3 1 4 11
3 2 5 15
3 3 6 16
3 4 7 12
3 5 8 17
3 6 9 17
3 7 10 16
3 8 11 16
3 9 12 18
3 10 13 20
3 11 14 15
3 12 15 19
3 13 16 20
3 14 17 16
3 41 44 19
3 44 47 20
3 71 74 17
3 74 77 18
3 111 114 19
3 114 117 20
4 0 4 14
4 1 5 11
4 2 6 15
4 3 7 12
4 4 8 15
4 5 9 15
4 6 10 18
4 7 11 11
4 8 12 18
4 9 13 17
4 10 14 18
4 11 15 15
4 12 16 19
4 13 17 16
4 14 18 19
4 15 19 19
4 17 21 16
4 27 31 19
4 37 41 18
4 41 45 19
4 43 47 20
4 47 51 18
4 57 61 20
4 67 71 18
4 70 74 20
4 71 75 17
4 73 77 18
4 77 81 19
4 111 115 19
4 113 117 20
4 117 121 20
5 0 5 16
5 1 6 13
5 2 7 13
5 3 8 17
5 4 9 15
5 5 10 18
5 6 11 15
5 7 12 15
5 8 13 19
5 9 14 17
5 10 15 20
5 11 16 17
5 12 17 17
5 14 19 19
5 16 21 20
5 17 22 20
5 71 76 19
5 72 77 19
6 0 6 18
6 1 7 11
6 2 8 18
6 3 9 17
6 4 10 18
6 5 11 15
6 6 12 19
6 7 13 16
6 8 14 19
6 9 15 19
6 11 17 15
6 15 21 20
6 41 47 19
6 71 77 17
6 111 117 19
7 0 7 12
7 1 8 12
7 2 9 14
7 3 10 16
7 4 11 11
7 5 12 15
7 6 13 16
7 7 14 12
7 8 15 17
7 9 16 17
7 10 17 16
7 11 18 16
7 12 19 18
7 14 21 16
7 15 22 20
7 17 24 17
7 24 31 19
7 27 34 20
7 34 41 18
7 37 44 19
7 40 47 20
7 41 48 20
7 44 51 18
7 47 54 19
7 54 61 20
7 64 71 18
7 67 74 19
7 70 77 18
7 71 78 18
7 72 79 20
7 74 81 19
7 77 84 20
7 110 117 20
7 111 118 20
7 114 121 20
8 0 8 20
8 1 9 15
8 2 10 20
8 3 11 16
8 4 12 18
8 5 13 19
8 6 14 19
8 7 15 17
8 9 17 18
8 11 19 19
9 0 9 18
9 1 10 16
9 2 11 15
9 3 12 18
9 4 13 17
9 5 14 17
9 6 15 19
9 7 16 17
9 8 17 18
9 12 21 20
10 1 11 14
10 2 12 20
10 3 13 20
10 4 14 18
10 5 15 20
10 7 17 16
10 11 21 19
11 0 11 14
11 1 12 13
11 2 13 16
11 3 14 15
11 4 15 15
11 5 16 17
11 6 17 15
11 7 18 16
11 8 19 19
11 10 21 19
11 11 22 18
11 13 24 20
11 14 25 20
11 16 27 20
11 31 42 20
11 41 52 20
11 61 72 20
12 0 12 20
12 1 13 16
12 2 14 18
12 3 15 19
12 4 16 19
12 5 17 17
12 7 19 18
12 9 21 20
13 0 13 20
13 1 14 15
13 2 15 19
13 3 16 20
13 4 17 16
13 11 24 20
14 0 14 18
14 1 15 15
14 2 16 19
14 3 17 16
14 4 18 19
14 5 19 19
14 7 21 16
14 11 25 20
14 17 31 18
14 27 41 20
14 57 71 19
14 77 91 20
15 0 15 20
15 1 16 17
15 2 17 17
15 4 19 19
15 6 21 20
15 7 22 20
16 1 17 15
16 5 21 20
16 11 27 20
17 0 17 16
17 1 18 16
17 2 19 18
17 4 21 16
17 5 22 20
17 7 24 17
17 14 31 18
17 17 34 19
17 24 41 20
17 54 71 19
17 57 74 20
17 74 91 20
18 1 19 19
19 2 21 20
20 1 21 20
21 0 21 20
21 1 22 19
24 7 31 19
24 17 41 20
27 4 31 19
27 7 34 20
27 14 41 20
30 1 31 20
31 0 31 20
31 1 32 19
31 11 42 20
34 7 41 18
37 4 41 18
37 7 44 19
40 1 41 18
40 7 47 20
41 0 41 18
41 1 42 17
41 2 43 20
41 3 44 19
41 4 45 19
41 6 47 19
41 7 48 20
41 11 52 20
41 71 112 20
42 1 43 20
43 1 44 19
43 4 47 20
44 1 45 19
44 3 47 20
44 7 51 18
46 1 47 19
47 0 47 20
47 1 48 20
47 4 51 18
47 7 54 19
50 1 51 20
51 0 51 20
51 1 52 19
54 7 61 20
54 17 71 19
57 4 61 20
57 14 71 19
57 17 74 20
61 11 72 20
64 7 71 18
67 4 71 18
67 7 74 19
70 1 71 16
70 4 74 20
70 7 77 18
71 0 71 16
71 1 72 15
71 2 73 18
71 3 74 17
71 4 75 17
71 5 76 19
71 6 77 17
71 7 78 18
71 41 112 20
72 1 73 18
72 2 74 20
72 5 77 19
72 7 79 20
73 1 74 17
73 4 77 18
74 0 74 20
74 1 75 17
74 3 77 18
74 7 81 19
74 17 91 20
75 1 76 19
75 2 77 19
76 1 77 17
77 0 77 18
77 1 78 18
77 2 79 20
77 4 81 19
77 7 84 20
77 14 91 20
110 1 111 18
110 7 117 20
111 0 111 18
111 1 112 17
111 2 113 20
111 3 114 19
111 4 115 19
111 6 117 19
111 7 118 20
112 1 113 20
113 1 114 19
113 4 117 20
114 1 115 19
114 3 117 20
114 7 121 20
116 1 117 19
117 0 117 20
117 1 118 20
117 4 121 20
170 1 171 20
171 0 171 20
171 1 172 19
710 1 711 20
711 0 711 20
711 1 712 19

由输出数据可知,711之后不存在符合条件的火柴棒等式。

这样一来,711这个完美的上界就被找到了。

你以为本文会到此结束?

你看到上面的数据难道没有点什么想法吗?我们不是要一步一步降低时间复杂度吗? 将验证器程序的代码稍作修改,就可以得到一个新程序的代码:

#include<iostream>
using namespace std;
const short cl[10] = { 6,2,5,5,4,5,6,3,7,6 };
short lx(int cn)
{
    short sm = 0;
    do
    {
        sm += cl[cn % 10];
        cn /= 10;
    } while (cn != 0);
    return sm;
}
int main()
{
    short ans[12] = { 0,0,0,0,0,0,0,0,0,0,0,0 };
    for (short a = 0; a <= 711; a++)
        for (short b = 0; b <= 711; b++)
        {
            short c = a + b;
            short on = lx(a) + lx(b) + lx(c);
            if (on <= 20)
                ans[on - 9]++;
        }
    for (short i = 0; i <= 11; i++)
        cout << i + 13 << " " << ans[i] << endl;
    return 0;
}

程序输出如下:

13 1
14 2
15 8
16 9
17 6
18 9
19 29
20 39
21 38
22 65
23 88
24 128

这不就是本题的答案的集合吗!

最终程序

#include<iostream>
using namespace std;
int main()
{
    const short a[12] = { 1,2,8,9,6,9,29,39,38,65,88,128 };
    short n;
    cin >> n;
    if (n <= 12)
        cout << 0;
    else
        cout << a[n - 13];
    return 0;
}

注意:为了防止数组引用溢出,需特别设置输入数据小于13时输出0。

。。竟然一步一步做成了打表。