题目大意：给出一个字符串，要求你在这个字符串里面加入符号，，使得结果为2000
解题思路：直接暴力
;char str[maxn];bool flag;int num[maxn], sign[maxn], len;char s[5]= ” *+-“;bool judge(int num_s, int num_n) {vector<int> Num, Sign;for(int i = 0; i < num_s; i++)Sign.push_back(sign[i]);for(int i = 0; i < num_n; i++)Num.push_back(num[i]);for(int i = 0; i < Sign.size(); i++)if(Sign[i] == 1) {Num[i + 1] *= Num[i];Num.erase(Num.begin() + i);Sign.erase(Sign.begin() + i);i–;}int t = Num[0];for(int i = 0; i < Sign.size(); i++)if(Sign[i] == 2)t += Num[i + 1];elset -= Num[i + 1];return t == 2000;}void dfs(int cur, int cur_sign, int cur_num) {if(cur == len – 1) {if(judge(cur_sign, cur_num)) {flag = true;printf(” “);for(int i = 0; i < cur_num – 1; i++)printf(“%d%c”, num[i], s[sign[i]]);printf(“%d=\n”,num[cur_num – 1]);}return;}int t = 0;for(int i = cur ; i < len – 1; i++) {if(i == cur && str[i] == ‘0’) {num[cur_num] = 0;if(i != len – 2) {for(int j = 1; j <= 3; j++) {sign[cur_sign] = j;dfs(i + 1, cur_sign+1, cur_num+1);}}elsedfs(i + 1, cur_sign, cur_num + 1);break;}t = t * 10 + str[i] – ‘0’;num[cur_num] = t;if(i != len – 2) {for(int j = 1; j <= 3; j++) {sign[cur_sign] = j;dfs(i + 1, cur_sign + 1, cur_num + 1);}}else {dfs(i + 1, cur_sign, cur_num + 1);}}}int main() {int cas = 1;while(scanf(“%s”, str) != EOF) {if(str[0] == ‘=’)break;flag = false;len = strlen(str);printf(“Problem %d\n”, cas++);if(strcmp(str,”2000=”) == 0) {printf(” IMPOSSIBLE\n”);continue;}dfs(0,0,0);if(!flag)printf(” IMPOSSIBLE\n”);}return 0;};const string sign[] = {“*”,”+”,”-“,””};map<char,int> Map;set<string> Set;bool judge(string s) {vector<int> num, sign;int cur = 0;while(1) {int t = 0;while(isdigit(s[cur]))t = t * 10 + s[cur++] – ‘0’;num.push_back(t);if(s[cur] == ‘=’)break;sign.push_back(Map[s[cur++]]);}for(int i = 0; i < sign.size(); i++)if(sign[i] == 1) {num[i+1] *= num[i];sign.erase(sign.begin() + i);num.erase(num.begin() + i);i–;}int t = num[0];for(int i = 0; i < sign.size(); i++)if(sign[i] == 2)t += num[i + 1];elset -= num[i + 1];return t == 2000;}void dfs(string s, int pos, bool f) {if(pos == s.size() – 1) {if(judge(s))Set.insert(s);return;}for(int i = 0; i < 4; i++) {if(!f && i == 3)continue;string t = s;if(s[pos] != ‘0’)dfs(t.insert(pos,sign[i]), i == 3? pos+1: pos+2, true);elsedfs(t.insert(pos,sign[i]), i == 3? pos+1: pos+2, i == 3);}}int main() {int cas = 1;Map[‘*’] = 1, Map[‘+’] = 2, Map[‘-‘] = 3;string str;while(cin >> str) {if(str[0] == ‘=’)break;Set.clear();printf(“Problem %d\n”, cas++);dfs(str,1,str[0] != ‘0’);if(!Set.size() || str == “2000=”) {printf(” IMPOSSIBLE\n”);continue;}for(set<string>::iterator it = Set.begin(); it != Set.end(); it++)cout << ” ” << *it << endl;}return 0;}
你曾经说，等我们老的时候，
