NOIP2008提高組 火柴棒等式 matches 解題報告

【問題描述】

給你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根火柴棍必須全部用上

【輸入】

輸入文件matches.in共一行，又一個整數n（n<=24）。

【輸出】

輸出文件matches.out共一行，表示能拼成的不同等式的數目。

【輸入輸出樣例1】

matches.in	matches.out
14	2

【輸入輸出樣例1解釋】

2個等式爲0+1=1和1+0=1。

 【輸入輸出樣例2】

matches.in	matches.out
18	9

 【輸入輸出樣例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

【分析】

NOIP2008的第二道模擬題，直接窮舉所有情況即可。

和與加數中較大的一個數位數相同或者大一。理想情況下11111和11111，可是另一個加數爲0也有6個火柴棒的花費，4個“1”的情況也不可能，所以和枚舉到“1111”就可以了。（事實證明也是如此的，因爲1比其他字母少用很多火柴），時間效率已經完全可以承受了。

具體操作時，先枚舉和，在枚舉其中一個加數，另一個加數可以用和減去枚舉的加數得到。

 可以先初始化一個數組，表示拼成1-9每個數字所用的火柴棒個數。

PS.由於N<=24，本題完全可以打表

【我的代碼】

//NOIP2008 火柴棒等式
#include <fstream>
using namespace std;
int M[10]={6,2,5,5,4,5,6,3,7,6};
int Mat[2500];
ifstream fin("matches.in");
ofstream fout("matches.out");
int Cat;
int total=0;
void init()
{
    fin>>Cat;
    fin.close();
    int bai,shi,ge,qian;
    for (int i=0;i<=2225;i++)
    {
        if (i<10)
        {
            Mat[i]=M[i];
            continue;
        }
        if (i>=10&&i<100)
        {
            Mat[i]=M[i/10]+M[i%10];
            continue;
        }
        if (i>=100&&i<=999)
        {  
            bai=i/100;
            shi=(i-bai*100)/10;
            ge=i-bai*100-shi*10;
            Mat[i]=M[bai]+M[shi]+M[ge];
            continue;
        }
        if(i>=1000)
        {
            qian=i/1000;
            bai=(i-qian*1000)/100;
            shi=(i-qian*1000-bai*100)/10;
            ge=i-qian*1000-bai*100-shi*10;
            Mat[i]=M[qian]+M[bai]+M[shi]+M[ge];
            continue;
        }
    }
  
    for (int i=0;i<=1111;i++)
    {
        for (int j=0;j<=1111;j++)
        {
            if (Mat[i]+Mat[j]+Mat[i+j]+4==Cat) total++;
        }
    }
    return;
}

int main()
{
    init();
    fout<<total;
    fout.close();
    return 0;
}