首页 > 代码库 > 杭电算法题 HDU 1000-1004
杭电算法题 HDU 1000-1004
1000 A+B Problem
#include <iostream>
using namespace std;
int main(int argc, const char * argv[]) {
int a,b;
while(cin>>a>>b){
cout<<a+b<<endl;
}
return 0;
}
Tips:
这题唯一需要注意的地方应该就是读取数据的问题,知道怎么样使用while(cin>>a>>b)
或者while(scanf("%d %d",&a,&b) != EOF)
来保证读数据读到数据末。
1001 Sum Problem
#include <iostream>
using namespace std;
int main(int argc, const char * argv[]) {
int n;
int sum;
while(cin>>n){
if(n%2 == 0)sum = n/2*(n+1);
else sum = (n+1)/2 * n;
cout<<sum<<endl;
cout<<endl;
}
return 0;
}
Tips:
首先第一个要注意的就是这题要求再每个输出后面再多加一个换行,这是一个可能漏看的点。这题如果用1到n的循环累加提交应该不会报错。但如果用高斯公式的话,用(n+1)*n/2会造成数据溢出,需要先除2再相乘,但因为int类型不能整除会被自动略去小数部分,所以需要先判断n和n+1哪个可以被2整除。
1002 A+B Problem II
#include <iostream>
using namespace std;
//将字符转为数字
int transCtoI(char c){
switch (c){
case ‘0‘:return 0;
case ‘1‘:return 1;
case ‘2‘:return 2;
case ‘3‘:return 3;
case ‘4‘:return 4;
case ‘5‘:return 5;
case ‘6‘:return 6;
case ‘7‘:return 7;
case ‘8‘:return 8;
case ‘9‘:return 9;
}
return 0;
}
//将数字转为字符
char transItoC(int i){
switch (i){
case 0:return ‘0‘;
case 1:return ‘1‘;
case 2:return ‘2‘;
case 3:return ‘3‘;
case 4:return ‘4‘;
case 5:return ‘5‘;
case 6:return ‘6‘;
case 7:return ‘7‘;
case 8:return ‘8‘;
case 9:return ‘9‘;
}
return 0;
}
//将字符串翻转
string trans(string s){
char temps;
for(int i = 0 ;i < s.length() / 2 ; i++){
temps = s[i];
s[i] = s[s.length() -i - 1];
s[s.length() -i - 1] = temps;
}
return s;
}
int main(int argc, const char * argv[]) {
int cnt = 1,max,next = 0,temp = 0 , num1 = 0 , num2 = 0;
string str1,str2,sum="";
cin>>max;
while(max > 0){
sum = "";num1 = 0 ;num2 = 0;next = 0;temp = 0;
cin>>str1>>str2;
cout<<"Case "<<cnt++<<":"<<endl;
cout<< str1 << " + "<<str2 <<" = ";
str1 = trans(str1);
str2 = trans(str2);
for(int i = 0 ;i <str1.length()||i < str2.length();i++){
//取每个字符将它转为数字,如果该字符下标已超出字符串长度,则将它设置等于0
if(i < str1.length())
num1 = transCtoI(str1[i]);
else
num1 = 0;
if(i < str2.length())
num2 = transCtoI(str2[i]);
else
num2 = 0;
//计算出当前位相加后的数字并取模
temp = (( num1 + num2 + next) % 10);
//如果当前位数字相加大于10则进位
if((num1 + num2 + next) >= 10)
next = 1;
else
next = 0;
sum += transItoC(temp);
}
//如果最后的一位加法有进位,那要再字符串首加一
if(next == 1)
sum += "1";
//注意要逆序输出
for(int i = sum.length() - 1;i >=0 ;i--)cout<<sum[i];
cout<<endl;
max --;
if(max > 0 )
cout<<endl;
}
return 0;
}
Tips:
这个应该考验的是大家高精度算法。首先第一个要注意的就是要用字符串来存储数字而不是int、long等,这样依然会造成数据溢出。第二就是要如何将字符类型和数字类型的进行转换,因为c++本身似乎不提供这个函数,自己写一个也是很方便的。最后要注意的就是进位问题。
1003 Max Sum
#include <iostream>
using namespace std;
int main(int argc, const char * argv[]) {
int t,n,max = -1001;
int a[1000001],sum = 0 , cnt = 1;
int head = 0 ,tail = 0;
int temphead = 0 , temptail = 0;
cin>>t;
while(t-- > 0){
cin>>n;
sum = temphead = temptail = head = tail = 0;
max = -1001;
for(int i = 0 ;i < n ; i++){
cin>>a[i];
sum += a[i];
if(sum > max){
max = sum;
head = temphead;
tail = i;
}
if(sum < 0 ){
temphead = i + 1 ;
sum = 0;
}
}
cout << "Case "<<cnt++<<":"<<endl;
cout << max << " " <<head+1 << " " << tail+1 <<endl;
if(t != 0)cout<<endl;
}
return 0;
}
Tips:
本题就是求一个最大子序列问题,一开始我以为会超级复杂。后来在网上看了题解之后惊讶才这么点代码?果然学好数学很重要。
这题可以用暴力求解的方式,遍历每种子序列的组合。比如序列(6,-1,5,4,7)
子序列组合:
6,(6,-1),(6,-1,5),(6,-1,5,4),(6,-1,5,4,7)
-1,(-1,5),(-1,5,4),(-1,5,4,7)
5,(5,4),(5,4,7)
4,(4,7)
7
这题要求的是子序列的最大和,所以如果一个子序列的和小于0,那么这个序列加上下一个数字,一定比单独这个数字的值还要小,所以可以重新以下一个数字开始计算子序列。这就是这个代码变的如此简洁的原因。
1004 Let the Balloon Rise
#include <iostream>
#include <map>
using namespace std;
int main(int argc, const char * argv[]) {
string str[1001];
string s = "";
map<string,int> amap;
map<string,int>::iterator iter;
int n , max = 0;
cin>>n;
while (n != 0) {
max = 0;s = "";amap.clear();
for(int i = 0; i < n; i++){
cin>>str[i];
//查找是否在map中已存在这个颜色,存在则该颜色数量加一,不存在则在map中插入该颜色
iter = amap.find(str[i]);
if(iter != amap.end()){
amap[str[i]] = amap[str[i]] + 1;
}
else{
amap[str[i]] = 1;
}
}
//遍历map,查找其中次数最多的颜色
for(iter = amap.begin() ; iter != amap.end(); iter++){
if(iter->second > max){
max = iter->second;
s = iter->first;
}
}
cout<<s<<endl;
cin>>n;
}
return 0;
}
Tips:
这题主要就是统计出现过的字符串,这里用了map这个容器来实现,其中map<string,int>::iterator iter
声明的iter是一个类似于指针的变量,从代码中可以看出要找一个map中存在的键值或者是遍历map中的值都需要借助iter来实现。当然也可以开两个一维数组,一个存字符串一个存出现的个数,那样可能就会比较简单一点。
杭电算法题 HDU 1000-1004