首页 > ACM题库 > HDU-杭电 > hdu 2057 A + B Again[解题报告]C++
2013
12-26

hdu 2057 A + B Again[解题报告]C++

A + B Again

问题描述 :

There must be many A + B problems in our HDOJ , now a new one is coming.
Give you two hexadecimal integers , your task is to calculate the sum of them,and print it in hexadecimal too.
Easy ? AC it !

输入:

The input contains several test cases, please process to the end of the file.
Each case consists of two hexadecimal integers A and B in a line seperated by a blank.
The length of A and B is less than 15.

输出:

The input contains several test cases, please process to the end of the file.
Each case consists of two hexadecimal integers A and B in a line seperated by a blank.
The length of A and B is less than 15.

样例输入:

+A -A
+1A 12
1A -9
-1A -12
1A -AA

样例输出:

0
2C
11
-2C
-90

#include<iostream>
#include<string>
#include<algorithm>

struct num_t
{
	int flag;
	std::string str;
};
int conv(char c)
{
	if(c>='0'&&c<='9'){
		return c-'0';
	}else{
		return c-'A'+10;
	}
}
char r_conv(int n)
{
	if(n<10){
		return '0'+n;
	}else{
		return 'A'+n-10;
	}
}

bool cmp_str(const std::string& l,const std::string& r){
	if(l.size()>r.size()){
		return true;
	}else if(l.size()<r.size()){
		return false;
	}
	return l>r;
}
std::string plus(const num_t& l,const num_t & r)
{
	std::string res;
	int cap=0;
	char l_n,r_n;
	int tmp;
	int size=std::max(l.str.size(),r.str.size());
	if((l.flag==1&&r.flag==1)||(l.flag==-1&&r.flag==-1)){
		for(int i=0;i!=size;i++){
			l_n=i>l.str.size()-1?'0':l.str[l.str.size()-1-i];
			r_n=i>r.str.size()-1?'0':r.str[r.str.size()-1-i];
			tmp=conv(l_n)+conv(r_n)+cap;
			if(tmp>=16){
				res.insert(res.begin(),r_conv(tmp%16));
				cap=1;
			}else{
				res.insert(res.begin(),r_conv(tmp));
				cap=0;
			}
		}
		if(cap==1){
			res.insert(res.begin(),'1');
		}
		if(l.flag==-1){
			res.insert(res.begin(),'-');
		}
	}else{
		if(l.str==r.str){
			return "0";
		}
		bool flag=true;
		if(((cmp_str(l.str,r.str))&&l.flag==-1)||((!cmp_str(l.str,r.str))&&r.flag==-1)){
			flag=false;
		}
		std::string l_s,r_s;
		if(!cmp_str(l.str,r.str)){
			l_s=r.str;
			r_s=l.str;
			
		}else{
			l_s=l.str;
			r_s=r.str;
		}

		for(int i=0;i!=size;i++){
			l_n=i>l_s.size()-1?'0':l_s[l_s.size()-1-i];
			r_n=i>r_s.size()-1?'0':r_s[r_s.size()-1-i];
			tmp=conv(l_n)-cap-conv(r_n);
			if(tmp<0){
				res.insert(res.begin(),r_conv(16+tmp));
				cap=1;
			}else{
				res.insert(res.begin(),r_conv(tmp));
				cap=0;
			}
		}
		int  k=0;
		if(res[0]=='0'){
			for(k=1;k!=res.size();k++){
				if(res[k]!='0'){
					break;
				}
			}
		}
		res=res.substr(k);
		if(flag==false){
			res.insert(res.begin(),'-');
		}
	}

	return res;
}
num_t num[2];
std::string str[2];
int main()
{
	while (std::cin>>str[0]>>str[1]){
		for(int i=0;i!=2;i++){
			if(str[i][0]=='+'){
				num[i].flag=1;
				num[i].str.assign(str[i].substr(1));
			}else if(str[i][0]=='-'){
				num[i].flag=-1;
				num[i].str.assign(str[i].substr(1));
			}else{
				num[i].flag=1;
				num[i].str.assign(str[i]);
			}
		}
		std::cout<<plus(num[0],num[1])<<std::endl;
		memset(num,0,sizeof(num));
	}
}

解题转自:http://blog.csdn.net/emiyasstar__/article/details/9018165


  1. 换句话说,A[k/2-1]不可能大于两数组合并之后的第k小值,所以我们可以将其抛弃。
    应该是,不可能小于合并后的第K小值吧

  2. 思路二可以用一个长度为k的队列来实现,入队后判断下队尾元素的next指针是否为空,若为空,则出队指针即为所求。