首页 > 代码库 > 杭电算法题 HDU 1000-1004

杭电算法题 HDU 1000-1004

<style>h1,h2,h3,h4,h5,h6,p,blockquote { margin: 0; padding: 0 } body { font-family: "Helvetica Neue", Helvetica, "Hiragino Sans GB", Arial, sans-serif; font-size: 13px; line-height: 18px; color: #737373; background-color: white; margin: 10px 13px 10px 13px } table { margin: 10px 0 15px 0; border-collapse: collapse } td,th { border: 1px solid #ddd; padding: 3px 10px } th { padding: 5px 10px } a { color: #0069d6 } a:hover { color: #0050a3; text-decoration: none } a img { border: none } p { margin-bottom: 9px } h1,h2,h3,h4,h5,h6 { color: #404040; line-height: 36px } h1 { margin-bottom: 18px; font-size: 30px } h2 { font-size: 24px } h3 { font-size: 18px } h4 { font-size: 16px } h5 { font-size: 14px } h6 { font-size: 13px } hr { margin: 0 0 19px; border: 0; border-bottom: 1px solid #ccc } blockquote { padding: 13px 13px 21px 15px; margin-bottom: 18px; font-family: georgia, serif; font-style: italic } blockquote::before { content: "“"; font-size: 40px; margin-left: -10px; font-family: georgia, serif; color: #eee } blockquote p { font-size: 14px; font-weight: 300; line-height: 18px; margin-bottom: 0; font-style: italic } code,pre { font-family: Monaco, Andale Mono, Courier New, monospace } code { background-color: #fee9cc; color: rgba(0, 0, 0, 0.75); padding: 1px 3px; font-size: 12px } pre { display: block; padding: 14px; margin: 0 0 18px; line-height: 16px; font-size: 11px; border: 1px solid #d9d9d9; white-space: pre-wrap } pre code { background-color: #fff; color: #737373; font-size: 11px; padding: 0 } sup { font-size: 0.83em; vertical-align: super; line-height: 0 } * { }</style>

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