标题意味着小神童。加减可以计算。
只是说这个小神童的学科知识,究竟有多神,自己给自己找。
最后,因为数据是非常非常巨大的,我听说关闭50k结束了50000数字总和,可以想见他神教。
这似乎也是考试题目IQ什么!
水题,依照一般加减法做,肯定是WA了。
这里给出使用string的加减法运算。由于string是长度可增可减的,所以无论是多少位,仅仅要内存支持,那么本算法都能够支持了。也能够使用vector这些容器。只是string应该更加省点内存。
注意: POJ比較讨厌的就是不支持C++11,并且不支持string的back()和pob_back()操作。希望POJ赶快更新系统啦。
难度是有点的,只是也是算法的基础了,高手们应该都熟悉了。直接使用Java的big number的就弱了点啦。
#include <stdio.h> #include <string> #include <algorithm> using std::string; const int MAX_B = 5120; char buf[MAX_B]; int id = 0, len = 0; inline char getFromBuf() { if (id >= len) { len = fread(buf, 1, MAX_B, stdin); id = 0; } return buf[id++]; } void getIntFromBuf(string &n) { char a = getFromBuf(); while ((a == ' ' || a == ' ') && len) a = getFromBuf(); bool sign = true; if (a == '-' || a == '+') { if (a == '-') sign = false; a = getFromBuf(); } n.clear(); while ((a != ' ' && a != ' ') && len)//老是写&&,错成|| { n.push_back(a); a = getFromBuf(); } if (sign) n.push_back('+'); else n.push_back('-'); } string operator+(string &a, string &b) { string c; int N1 = (int)a.size(), N2 = (int)b.size(); int carry = 0; for (int i = N1-1, j = N2-1; i>=0 || j>=0 || carry; i--, j--) { int an = i>=0? a[i]-'0' : 0; int bn = j>=0? b[j]-'0' : 0; int sum = an + bn + carry; carry = sum / 10; c.push_back(sum % 10 + '0'); } reverse(c.begin(), c.end()); return c; } string operator-(string &a, string &b) { string c; int N1 = (int)a.size(), N2 = (int)b.size(); int carry = 0; for (int i = N1-1, j = N2-1; i>=0 || j>=0 || carry; i--, j--) { int an = i>=0? a[i]-'0' : 0; int bn = j>=0?b[j]-'0' : 0; int sum = an - bn + carry; if (sum < 0) { carry = -1; sum += 10; } else carry = 0; c.push_back(sum % 10 + '0'); } reverse(c.begin(), c.end()); return c; } int cmpAbsStr(string &a, string &b) { if (a.size() < b.size()) return -1; else if (a.size() > b.size()) return 1; if (a == b) return 0; for (int i = 0; i < (int)a.size(); i++) { if (a[i] < b[i]) return -1; else if (a[i] > b[i]) return 1; } return 0; } int main() { int T; scanf("%d", &T); getchar(); string n1, n2; while (T--) { getIntFromBuf(n1); getIntFromBuf(n2); if (n1[n1.size()-1] == '+' && n2[n2.size()-1] == '+' || n1[n1.size()-1] == '-' && n2[n2.size()-1] == '-') { if (n1[n1.size()-1] == '-' && n2[n2.size()-1] == '-') putchar('-'); //n1.pop_back();n2.pop_back(); n1.erase(n1.size()-1); n2.erase(n2.size()-1); string c = n1 + n2; puts(c.c_str()); } else { if (n1[n1.size()-1] == '-' && n2[n2.size()-1] == '+') n1.swap(n2); //n1.pop_back(); n2.pop_back(); n1.erase(n1.size()-1), n2.erase(n2.size()-1); int sign = cmpAbsStr(n1, n2); if (sign == 0) puts("0"); else if (sign == 1) { string c = n1 - n2; puts(c.c_str()); } else { string c = n2 - n1; putchar('-'); puts(c.c_str()); } } } return 0; }
版权声明:笔者靖心脏。景空间地址:http://blog.csdn.net/kenden23/。只有经过作者同意转载。