[USACO][Section 2.3][枚举] Zero Sum

题目大意


给出序列1 2 3 … n,在序列的每个数字之间可以决定是否插入符号“+”、“-”。输出所有结果等于0的式子。

思路


简单枚举,用广搜枚举所有情况即可。

代码


/*
ID: lujunda1
LANG: C++
PROG: zerosum
*/
#include
#include
#include
#include
using namespace std;

struct state
//结构体state用于存储式子。 
{
    char str[20];
};

bool check(char* str,int n)
//判断式子str的结果是否为0。 
{
    int len=n*2-1;
    int sum=0,op=1,temp=1;
    //sum式子临时的结果。
    //op当前运算数的符号。
    //temp当前运算数的大小。 
    for(int i=1;i q;
    state head;
    head.str[0]='1';
    head.str[1]='\0';
    q.push(head);
    int temp=1;
    while(++temp<=n)
    {
        int size=q.size();
        while(size--)
        {
            head=q.front();
            q.pop();
            head.str[temp*2-3]=' ';
            //按字典序,先' ',后'+',最后'-'。 
            head.str[temp*2-2]='0'+temp;
            head.str[temp*2-1]='\0';
            q.push(head);
            head.str[temp*2-3]='+';
            q.push(head);
            head.str[temp*2-3]='-';
            q.push(head);
        }
    }
    while(q.size())
    {
        if(check(q.front().str,n))
            printf("%s\n",q.front().str);
        q.pop();
    }
}

int main()
{
    freopen("zerosum.in","r",stdin);
    freopen("zerosum.out","w",stdout);
    int n;
    scanf("%d",&n);
    bfs(n);
}

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注