【基础练习】【搜索/枚举】codevs1168 火柴棒等式题解

Dear 丶 2022-08-09 09:41 192阅读 0赞

题目来自NOIP2008

题目描述 Description

给你n根火柴棍，你可以拼出多少个形如“A+B=C”的等式？等式中的A、B、C是用火柴棍拼出的整数（若该数非零，则最高位不能是0）。用火柴棍拼数字0-9的拼法如图所示：

注意：

1. 加号与等号各自需要两根火柴棍

2. 如果A≠B，则A+B=C与B+A=C视为不同的等式（A、B、C>=0）

3. n根火柴棍必须全部用上

![1168.png][]

输入描述 Input Description

输入文件共一行，又一个整数n（n<=24）。

输出描述 Output Description

输出文件共一行，表示能拼成的不同等式的数目。

样例输入 Sample Input

样例1：

样例2：

样例输出 Sample Output

样例1：

样例2：

数据范围及提示 Data Size & Hint

【输入输出样例1解释】

2个等式为0+1=1和1+0=1。

【输入输出样例2解释】

9个等式为：

0+4=4

0+11=11

1+10=11

2+2=4

2+7=9

4+0=4

7+2=9

10+1=11

11+0=11

囧···这题目数据规模太小了，于是掉以轻心没考虑两位数加数的情况···

后来连表都懒得弄了，题解里拖了一个表就交了= =

枚举而已 你会发现每个数字的火柴数不能超过10

代码：

//codevs1168 »ð²ñ°ôµÈÊ½ ËÑË÷ NOIP2008
    //copyright by ametake
    #include
       
        
    #include
        
         
    #include
         
          
    using namespace std;
    
    const int a[] = { 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15 , 16 , 17 , 18 , 19 , 20 , 21 , 22 , 23 , 24 , 25 , 26 , 27 , 29 , 30 , 31 , 32 , 33 , 34 , 35 , 36 , 37 , 39 , 40 , 41 , 42 , 43 , 44 , 45 , 46 , 47 , 48 , 49 , 50 , 51 , 52 , 53 , 54 , 55 , 56 , 57 , 59 , 61 , 62 , 63 , 64 , 65 , 67 , 70 , 71 , 72 , 73 , 74 , 75 , 76 , 77 , 78 , 79 , 81 , 84 , 87 , 91 , 92 , 93 , 94 , 95 , 97 , 101 , 107 , 110 , 111 , 112 , 113 , 114 , 115 , 116 , 117 , 118 , 119 , 121 , 124 , 127 , 131 , 134 , 137 , 141 , 142 , 143 , 144 , 145 , 147 , 151 , 154 , 157 , 161 , 167 , 170 , 171 , 172 , 173 , 174 , 175 , 176 , 177 , 179 , 181 , 191 , 197 , 211 , 214 , 217 , 241 , 271 , 277 , 311 , 314 , 317 , 341 , 371 , 377 , 411 , 412 , 413 , 414 , 415 , 417 , 421 , 431 , 441 , 447 , 451 , 471 , 474 , 477 , 511 , 514 , 517 , 541 , 571 , 577 , 611 , 617 , 671 , 701 , 710 , 711 , 712 , 713 , 714 , 715 , 716 , 717 , 719 , 721 , 727 , 731 , 737 , 741 , 744 , 747 , 751 , 757 , 761 , 771 , 772 , 773 , 774 , 775 , 777 , 791 , 811 , 911 , 917 , 971 , 1111 , 1112 , 1113 , 1114 , 1115 , 1117 , 1121 , 1131 , 1141 , 1147 , 1151 , 1171 , 1174 , 1177 , 1211 , 1311 , 1411 , 1417 , 1471 , 1511 , 1711 , 1714 , 1717 , 1741 , 1771 , 1777 , 2111 , 3111 , 4111 , 4117 , 4171 , 4711 , 5111 , 7111 , 7114 , 7117 , 7141 , 7171 , 7177 , 7411 , 7711 , 7717 , 7771 , 11111 , 11117 , 11171 , 11711 , 17111 , 71111 };
    const int b[] = { 6 , 2 , 5 , 5 , 4 , 5 , 6 , 3 , 7 , 6 , 8 , 4 , 7 , 7 , 6 , 7 , 8 , 5 , 9 , 8 , 11 , 7 , 10 , 10 , 9 , 10 , 11 , 8 , 11 , 11 , 7 , 10 , 10 , 9 , 10 , 11 , 8 , 11 , 10 , 6 , 9 , 9 , 8 , 9 , 10 , 7 , 11 , 10 , 11 , 7 , 10 , 10 , 9 , 10 , 11 , 8 , 11 , 8 , 11 , 11 , 10 , 11 , 9 , 9 , 5 , 8 , 8 , 7 , 8 , 9 , 6 , 10 , 9 , 9 , 11 , 10 , 8 , 11 , 11 , 10 , 11 , 9 , 10 , 11 , 10 , 6 , 9 , 9 , 8 , 9 , 10 , 7 , 11 , 10 , 9 , 11 , 10 , 9 , 11 , 10 , 8 , 11 , 11 , 10 , 11 , 9 , 9 , 11 , 10 , 10 , 11 , 11 , 7 , 10 , 10 , 9 , 10 , 11 , 8 , 11 , 11 , 10 , 11 , 9 , 11 , 10 , 11 , 10 , 11 , 9 , 11 , 10 , 11 , 10 , 11 , 8 , 11 , 11 , 10 , 11 , 9 , 11 , 11 , 10 , 11 , 11 , 9 , 11 , 10 , 9 , 11 , 10 , 11 , 10 , 11 , 10 , 11 , 11 , 11 , 11 , 7 , 10 , 10 , 9 , 10 , 11 , 8 , 11 , 10 , 11 , 10 , 11 , 9 , 11 , 10 , 10 , 11 , 11 , 8 , 11 , 11 , 10 , 11 , 9 , 11 , 11 , 10 , 11 , 11 , 8 , 11 , 11 , 10 , 11 , 9 , 11 , 11 , 10 , 11 , 11 , 9 , 11 , 10 , 11 , 11 , 10 , 11 , 11 , 11 , 9 , 11 , 10 , 11 , 10 , 11 , 11 , 11 , 10 , 11 , 11 , 11 , 11 , 9 , 11 , 10 , 11 , 10 , 11 , 11 , 10 , 11 , 11 , 10 , 11 , 11 , 11 , 11 , 11 };
    int n;
    int ans=0;
    
    int main()
    {
        scanf("%d",&n);
        n-=4;
        if (n<=9)
        {
            if (n==9) printf("1\n");
            else printf("0\n");
            return 0; 
        }
        for (int i=0;i<238;i++)
        {
            for (int j=i;j<238;j++)
            {
                for (int k=0;k<238;k++)
                {
                    if(a[i]+a[j]==a[k]&&b[i]+b[j]+b[k]== n)
                           ans+=(1 +(i!=j));
                }
            }
        }
        printf("%d\n",ans);
        return 0;
    }

我很喜欢新版code的显示风格 有点像rainbow又不一样

但是不知为啥显示到博客上又老样子了···

下面这句是因为今天运动会就想到了 为我们班两位5000米勇士加加油 十里长征 辉煌与荣耀同在

——马作的卢飞快，弓如霹雳弦惊

[1168.png]: http://codevs.cn/media/image/problem/1168.png