首页 > 代码库 > USACO zerosum DFS 1A
USACO zerosum DFS 1A
USER: Kevin Samuel [kevin_s1] TASK: zerosum LANG: C++ Compiling... Compile: OK Executing... Test 1: TEST OK [0.003 secs, 3508 KB] Test 2: TEST OK [0.003 secs, 3508 KB] Test 3: TEST OK [0.005 secs, 3508 KB] Test 4: TEST OK [0.000 secs, 3508 KB] Test 5: TEST OK [0.005 secs, 3508 KB] Test 6: TEST OK [0.008 secs, 3508 KB] Test 7: TEST OK [0.014 secs, 3508 KB] All tests OK.YOUR PROGRAM (‘zerosum‘) WORKED FIRST TIME! That‘s fantastic -- and a rare thing. Please accept these special automated congratulations.
Here are the test data inputs:
------- test 1 ---- 3 ------- test 2 ---- 4 ------- test 3 ---- 5 ------- test 4 ---- 6 ------- test 5 ---- 7 ------- test 6 ---- 8 ------- test 7 ---- 9Keep up the good work!
Thanks for your submission!
it‘s a easy problem of dfs
/* ID:kevin_s1 PROG:zerosum LANG:C++ */ #include <iostream> #include <cstdio> #include <string> #include <cstring> #include <vector> #include <map> #include <set> #include <algorithm> #include <cstdlib> #include <list> #include <cmath> using namespace std; //gobal variable==== int N; vector<string> result; //================== //function========== char NumToChar(int i){ char ch = i + 48; return ch; } void DFS(int i, int sum, string str, int last_operator){ if(i > N + 1) return; if(i == N + 1){ if(sum == 0){ result.push_back(str); } return; } //plus string tmp1 = str; tmp1 = tmp1 + "+" + NumToChar(i); DFS(i + 1, sum + i, tmp1, i); //minus string tmp2 = str; tmp2 = tmp2 + "-" + NumToChar(i); DFS(i + 1, sum - i, tmp2, -i); //multiply string tmp3 = str; tmp3 = tmp3 + " " + NumToChar(i); int cc = 0; if(last_operator > 0) cc = 1; else cc = -1; int mt = cc * (abs(last_operator) * 10 + i); int sum_tmp = sum - last_operator + mt; DFS(i + 1, sum_tmp, tmp3, mt); return; } //================== int main(){ freopen("zerosum.in","r",stdin); freopen("zerosum.out","w",stdout); cin>>N; string str = "1"; DFS(2, 1, str, 1); sort(result.begin(), result.end(), less<string>()); vector<string>::iterator iter; for(iter = result.begin(); iter != result.end(); iter++){ cout<<*iter<<endl; } return 0; }
USACO zerosum DFS 1A
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。