PAT_甲级_1065 A+B and C (64bit) (20分) (C++)【大数相加】
程序员文章站
2022-07-13 17:51:59
...
目录
1，题目描述
Sample Input:
3
1 2 3
2 3 4
9223372036854775807 -9223372036854775808 0
Sample Output:
Case #1: false
Case #2: true
Case #3: false
2，思路
如果对基本数据类型的范围都比较熟悉的话，这一题应该是非常简单的了。
而long long（8个字节）的范围[-2^63，2^63 - 1]，接下来就是A+B>C的判断了。
需要注意的是，可能出现溢出的情况，一旦溢出，不管C为何值，均可以确定输出
3，AC代码
#include<bits/stdc++.h>
using namespace std;
int main(){
#ifdef ONLINE_JUDGE
#else
freopen("1.txt", "r", stdin);
#endif // ONLINE_JUDGE
int T;
cin>>T;
long long A, B, C, sum;
for(int i = 1; i <= T; i++){
cin>>A>>B>>C;
sum = A + B;
if(A > 0 && B > 0 && sum <= 0) //比任何C都大
printf("Case #%d: true\n", i);
else if(A < 0 && B < 0 && sum >= 0) //比任何C都小
printf("Case #%d: false\n", i);
else if(sum > C)
printf("Case #%d: true\n", i);
else if(sum <= C)
printf("Case #%d: false\n", i);
}
return 0;
}
4，解题过程及知识补充
（相当讨厌这种题目。。。）
第一搏
主要矛盾有两个：1，长度：64位。。。2，正负号；
考虑将数字和符号部分分开，数字用string类型存储，符号用int flag表示；
涉及到一些string的操作：详细的可以看这里，@tech-chen【C++之string类型详解】
- s.insert(0,”my name”);
- s.erase(13);//从索引13开始往后全删除；s.erase(7,5);//从索引7开始往后删5个
非常繁琐的代码。。。然而只过了一个测试点（中间还被erase的错误用法耽误了好一会，，，参数1：位置 参数2：位置开始几个字符）
测试用例：1 -2 -1
#include<bits/stdc++.h>
using namespace std;
bool judge(string a, string b, string c){
int flagA = 0, flagB = 0, flagC = 0, flagAB = 0;
if(a[0] == '-'){
a.erase(0, 1);
flagA = 1;
}
if(b[0] == '-'){
b.erase(0, 1);
flagB = 1;
}
if(c[0] == '-'){
c.erase(0, 1);//注意erase的用法 参数1：位置 参数2：位置开始几个字符
flagC = 1;
}
//cout<<a<<' '<<b<<' '<<c<<endl;
string ab, s;
int tag = 0, x;//tag是否有进/借位 x暂时存储数据
if(flagA == flagB){//同号
flagAB = flagA;
int i = a.length()-1, j = b.length()-1;
while(i >= 0 && j >= 0){
x = (a[i--] - '0') + (b[j--] - '0') + tag;
if(x > 9){
x -= 10;
tag = 1;//有进位
}else tag = 0;
s = '0' + x;
ab.insert(0,s);
}
if(i < 0){
while(j >= 0){
x = b[j--] + tag;
if(x > 9){
x -= 10;
tag = 1;//有进位
}else tag = 0;
s = '0' + x;
ab.insert(0,s);
}
}else{
while(i >= 0){
x = a[i--] + tag;
if(x > 9){
x -= 10;
tag = 1;//有进位
}else tag = 0;
s = '0' + x;
ab.insert(0,s);
}
}
}else{//异号
if(flagA == 1) swap(a, b);//保证a为正 b为负
//cout<<a<<' '<<b<<endl;
if(a > b) flagAB = 0;
else flagAB = 1;
int i = a.length()-1, j = b.length()-1;
while(i >= 0 && j >= 0){
x = (a[i--] - '0') - (b[j--] - '0') - tag;
if(x < 0){
x += 10;
tag = 1;//有借位
}else tag = 0;
s = '0' + x;
ab.insert(0,s);
}
if(i < 0){
while(j >= 0){
x = b[j--] - tag;
if(x > 9){
x -= 10;
tag = 1;//有进位
}else tag = 0;
s = '0' + x;
ab.insert(0,s);
}
}else{
while(i >= 0){
x = a[i--] - tag;
if(x > 9){
x -= 10;
tag = 1;//有进位
}else tag = 0;
s = '0' + x;
ab.insert(0,s);
}
}
}
if(flagAB != flagC)
return flagAB < flagC;
else{
if(flagAB == 0)
return ab > c;
else
return ab < c;
}
}
int main(){
#ifdef ONLINE_JUDGE
#else
freopen("1.txt", "r", stdin);
#endif // ONLINE_JUDGE
int T;
cin>>T;
string A, B, C;
for(int i = 1; i <= T; i++){
cin>>A>>B>>C;
if(judge(A, B, C))
printf("Case #%d: true\n", i);
else
printf("Case #%d: false\n", i);
}
return 0;
}
第二搏
发现借位 的时候，应保证被减数大于减数（不然会出现0-1=-9的情况），于是加了一行这个：
测试用例：-1 0 -3
第三搏
字符串类型string间的比较 是逐个字符字符比较的，比如“456”>"123456"，所以添加了下面的代码：
然而还是不行。。。
第四搏
搞不动了，，，只好请教大神。然而看了代码后，我。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
long long类型解决一切烦恼（只不过需要考虑溢出的问题）。。。（怪不得题目分数是20.）
对数据类型不太熟悉的同学可以看这里@Steve_Stone【C/C++ 各类型int、long、double、char、long long取值范围（基本类型的最大最小值）】
终于。。。（菜的无话可说）