前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >【USACO 2.3】Zero Sum(dfs)

【USACO 2.3】Zero Sum(dfs)

作者头像
饶文津
发布2020-06-02 11:05:47
4330
发布2020-06-02 11:05:47
举报
文章被收录于专栏:饶文津的专栏

按字典序输出所有在123..n之间插入'+','-',' '结果为0的表达式。.

http://train.usaco.org/usacoprob2?a=jUh88pMwCSQ&S=zerosum

代码语言:javascript
复制
/*
TASK:zerosum
LANG:C++
*/
#include<cstdio>
#include<string>
#include<algorithm>
using namespace std;
#define N 15
int n;
int k[N],cnt,s[3]={0,1,-1};
string ans[7000];
void dfs(int d){
    if(d>n){
        int sum=0,c=1;
        for(int i=2;i<=n;i++){
            if(k[i]){
                sum+=c;
                c=i*k[i];
            }else{
                c=c*10+(c>0?i:-i);
            }
        }
        sum+=c;
        if(sum==0){
            ans[++cnt]+="1";
            for(int i=2;i<=n;i++){
                ans[cnt]+=k[i]>0?'+':k[i]<0?'-':' ';
                ans[cnt]+=i+'0';
            }
        }
        return;
    }
    for(int i=0;i<=2;i++){
        k[d]=s[i];
        dfs(d+1);
    }
}
int main(){
    freopen("zerosum.in","r",stdin);
    freopen("zerosum.out","w",stdout);
    scanf("%d",&n);
    dfs(2);
    for(int i=1;i<=cnt;i++){
        printf("%s\n",ans[i].c_str());
    }
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2016-10-27 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档