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 阅读(817) 评论(0)  编辑 收藏 引用 所属分类: 模拟