Climber.pI的OI之路

NOIp 2008 火柴棒等式

數據范圍很小，暴力枚舉即可.

一開始想復雜了，認為需要枚舉出所有符合條件的數字，然后調整順序，尋找等式 = =

事實上只需要枚舉前兩個數，然后判斷是否符合條件即可.考慮24的情況，若B為1，則還剩下18根火柴.又A<C,所以A為1111.因而只要在[0,1111]內枚舉A、B即可.復雜度不會算.

如果范圍更大的話，可以令A<=B，枚舉A、B.操作數大約是原來的一半.進一步的優化想不到了..

 1#include<stdio.h>
 2#include<iostream>
 3using namespace std;
 4int num[] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6}, t[2230] = {0};
 5int main(){
 6    int n, i, j, ans = 0;
 7    scanf("%d", &n);
 8    for (i = 0; i < 2230; i++){
 9        int tmp = i;
10        t[i] += num[tmp%10];
11        while (tmp/10){
12            tmp /= 10;
13            t[i] += num[tmp%10];
14        }
15    }
16    for (i = 0; i < 1112; i++)
17        for (j =0; j < 1112; j++)
18            if (t[i]+t[j]+t[i+j]+4 == n) ans++;
19    printf("%d\n", ans);
20}
21

posted on 2010-10-03 09:20 Climber.pI 閱讀(835) 評論(0)  編輯 收藏 引用 所屬分類: 模擬