Beyond the Void
BYVoid
USACO 2.3.3 Zero Sum 和为零

穷举每一种可能,然后计算求值,输出和为0的解(其实很多地方可以优化,鉴于这道题数据规模很小n<=9,没有优化也全过了)

关键在于表达式求值,只有加减和空格,所以很容易求值

/*
ID: cmykrgb1
PROG: zerosum
LANG: C++
*/

#include <stdio.h>
#include <string.h>

FILE *fi,*fo;
int n;

int ev(char *s)
{
    int thr, opt, sum;
    char *p;
    opt=1;
    thr=sum=0;
    for(p=s; *p; p++) 
    {
        switch(*p)
        {
        case '+':
        case '-':
            sum+=opt*thr;
            thr=0;
            opt=(*p=='+')?1:-1;
            break;
        case ' ':
            break;
        default:
            thr=thr*10+*p-'0';
        }
    }
    }
    sum+=opt*thr;
    return !sum;
}
 
void search(char *s, int k)
{
    char *p;
    if(k == n-1) 
    {
        if(ev(s))
            fprintf(fo, "%sn", s);
        return;
    }
    for(p=" +-";*p; p++) 
    {
        s[2*k+1]=*p;
        search(s,k+1);
    }
}
 
 
int main(void)
{
    int i;
    char str[20];
    fi=fopen("zerosum.in", "r");
    fo=fopen("zerosum.out", "w");
    fscanf(fi, "%d", &n);
    fclose(fi);
    strcpy(str, "1 2 3 4 5 6 7 8 9");
    str[2*n-1]=0;
    search(str, 0);
    return 0;
}

上次修改时间 2017-02-03

相关日志