HDOJ 基础题

文章目录
  1. 1. 1000 A+B
  2. 2. 1001 Sum Problem
  3. 3. 1004 Let the Balloon Rise
  4. 4. 1005 Number Sequence
  5. 5. 1008 Elevator
  6. 6. 1012 u Calculate e ★
  7. 7. 1013 Digital Roots ★
  8. 8. 1019 Least Common Multiple ★
  9. 9. 1021 Fibonacci Again
  10. 10. 1028 Ignatius and the Princess III
  11. 11. 1029 Ignatius and the Princess IV
  12. 12. 1032 The 3n + 1 problem
  13. 13. 1037 Keep on Truckin’
  14. 14. 1040 As Easy As A+B
  15. 15. 1048 The Hardest Problem Ever
  16. 16. 1056 HangOver
  17. 17. 1058 Humble Numbers
  18. 18. 1061 Rightmost Digit
  19. 19. 1070 Milk
  20. 20. 1076 An Easy Task
  21. 21. 1089 A+B for Input-Output Practice (I)
  22. 22. 1090 A+B for Input-Output Practice (II)
  23. 23. 1091 A+B for Input-Output Practice (III)
  24. 24. 1092 A+B for Input-Output Practice (IV)
  25. 25. 1093 A+B for Input-Output Practice (V)
  26. 26. 1094 A+B for Input-Output Practice (VI)
  27. 27. 1095 A+B for Input-Output Practice (VII)
  28. 28. 1096 A+B for Input-Output Practice (VIII)
  29. 29. 1098 Ignatius’s puzzle
  30. 30. 1106 排序
  31. 31. 1108 最小公倍数
  32. 32. 1157 Who’s in the Middle
  33. 33. 1063 Eddy’s digital Roots
  34. 34. 1164 Eddy’s research I
  35. 35. 1170 Balloon Comes!
  36. 36. 1194 Beat the Spread!
  37. 37. 1196 Lowest Bit
  38. 38. 1197 Specialized Four-Digit Numbers
  39. 39. 1201 18岁生日
  40. 40. 1202 The calculation of GPA
  41. 41. 1235 统计同成绩学生人数
  42. 42. 1236 排名
  43. 43. 1248 寒冰王座(DP模板)
  44. 44. 1266 Reverse Number

HDOJ基础题刷题记录
HDOJ目录链接：http://www.cnblogs.com/kuangbin/archive/2011/07/26/2117153.html

1000 A+B

http://acm.hdu.edu.cn/showproblem.php?pid=1000

1
2
3
4
5
6
7
8
9
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int a,b;
    while(cin>>a>>b)
        cout<<a+b<<endl;
    return 0;
}

1001 Sum Problem

http://acm.hdu.edu.cn/showproblem.php?pid=1001

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    while(cin>>n)
    {
        int sum=0;
        for(int i=1;i<=n;i++)
            sum+=i;
        cout<<sum<<endl<<endl;
    }
    return 0;
}

1004 Let the Balloon Rise

http://acm.hdu.edu.cn/showproblem.php?pid=1004

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <bits/stdc++.h>
using namespace std;
string colors[1005];
int main()
{
    int n;
    while(cin>>n)
    {
        if(n==0) break;
        map<string,int>ball;
        for(int i=0;i<n;i++)
        {
            string color;
            cin>>color;
            colors[i]=color;
            ball[color]+=1;
        }
        string b;
        int maxn=0;
        for(int i=0;i<n;i++)
        {
            if(ball[colors[i]]>maxn)
            {
                maxn=ball[colors[i]];
                b=colors[i];
            }
        }
        cout<<b<<endl;
    }
    return 0;
}

1005 Number Sequence

http://acm.hdu.edu.cn/showproblem.php?pid=1005

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <bits/stdc++.h>
using namespace std;

int f(int A,int B,int n)
{
    if(n==1 || n==2) return 1;
    else return (A*f(A,B,n-1)+B*f(A,B,n-2))%7;
}

int main()
{
    int A,B,n;
    while(cin>>A>>B>>n &&A&&B&&n)
    {
        cout<<f(A,B,n%49)<<endl;
    }
    return 0;
}

1008 Elevator

http://acm.hdu.edu.cn/showproblem.php?pid=1008

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    while(cin>>n&&n)
    {
        int a[1005];
        for(int i=0;i<n;i++)
            cin>>a[i];
        int sum=0;
        for(int i=0;i<n;i++)
        {
            if(i==0) sum+=a[i]*6+5;
            else
            {
                if(a[i]<a[i-1]) sum+=(a[i-1]-a[i])*4+5;
                if(a[i]>a[i-1]) sum+=(a[i]-a[i-1])*6+5;
                if(a[i]==a[i-1]) sum+=5;
            }
        }
        cout<<sum<<endl;
    }
    return 0;
}

1012 u Calculate e ★

http://acm.hdu.edu.cn/showproblem.php?pid=1012

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <bits/stdc++.h>
using namespace std;

double cal(int x)
{
    double ans=1;
    if(x==0) return 1;
    for(int i=1;i<=x;i++)
        ans*=i;
    return ans;
}

int main()
{
    int n=9;
    double sum=0;
    vector<double>vec;
    for(int i=0;i<=9;i++)
    {
        double j=cal(i);
        double j2=1/j;
        sum+=j2;
        vec.push_back(sum);
    }
    cout<<"n e"<<endl;
    cout<<"- -----------"<<endl;
    for(int i=0;i<=9;i++)
    {
        if(i<3)
            cout<<i<<" "<<vec[i]<<endl;
        else
            cout<<i<<" "<<fixed<<setprecision(9)<<vec[i]<<endl;
    }
    return 0;
}

1013 Digital Roots ★

http://acm.hdu.edu.cn/showproblem.php?pid=1013

这里学到了一个新的知识点。
九余数定理：某数除以9所得的余数为该数的数根（某数各个数位的数相加，若结果为两位数，继续相加，直到结果为一位数，即为数根）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <bits/stdc++.h>
using namespace std;
int main()
{
    char d[100005];
    while(cin>>d && d[0]!='0')
    {
        int sum=0;
        for(int i=0;i<strlen(d);i++)
        {
            sum+=d[i]-'0';
        }
        cout<<(sum-1)%9+1<<endl;
    }
    return 0;
}

1019 Least Common Multiple ★

http://acm.hdu.edu.cn/showproblem.php?pid=1019

这里有一个知识点，a*b/gcd(a,b)，即使是32位的限制，a*b也会超内存，所以必须先除再乘。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <bits/stdc++.h>
using namespace std;

int gcd(int a,int b)
{
    if(a<b)
    {
        int temp=a;
        a=b;
        b=temp;
    }
    while(a%b)
    {
        int temp=a%b;
        a=b;
        b=temp;
    }
    return b;
}

int main()
{
    int n,m,LCM;
    while(cin>>n)
    {
        while(n--)
        {
            cin>>m;
            cin>>LCM;
            while(--m)
            {
                int a;
                cin>>a;
                LCM=a/gcd(a,LCM)*LCM;
            }
            cout<<LCM<<endl;
        }
    }
    return 0;
}

1021 Fibonacci Again

http://acm.hdu.edu.cn/showproblem.php?pid=1021

下面的递归写法直接超内存（在计算斐波那契数列的时候容易出现这个问题），递归太深，栈溢出。
堆栈溢出的产生是由于过多的函数调用，导致调用堆栈无法容纳这些调用的返回地址，一般在递归中产生。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;

int Fibonacci(int n)
{
    if(n==0) return 7;
    else if(n==1) return 11;
    else return Fibonacci(n-1)+Fibonacci(n-2);
}

int main()
{
    int n;
    while(cin>>n)
    {
        int ans=Fibonacci(n);
        if(ans%3==0) cout<<"yes"<<endl;
        else cout<<"no"<<endl;
    }
    return 0;
}

很不喜欢这种题，这是需要找规律的题目，可以发现以下规律：
F(0)=7,F(1)=11,F(2)=18,F(3)=29,F(4)=47,F(5)=76,F(6)=123,F(7)=199,F(8)=322,F(9)=521,F(10)=843
当n%8==2或者n%8==6的时候输出为yes…

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    while(cin>>n)
    {
        if(n%8==2 || n%8==6) cout<<"yes"<<endl;
        else cout<<"no"<<endl;
    }
    return 0;
}

1028 Ignatius and the Princess III

http://acm.hdu.edu.cn/showproblem.php?pid=1028

这是一道母函数的模板题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    while(cin>>n)
    {
        int c1[10005],c2[10005];
        //把所有x的系数全部置为1
        for(int i=0; i<=n; i++)
        {
            c1[i]=1;
            c2[i]=0;
        }
        for(int i=2; i<=n; i++)
        {
            for(int j=0; j<=n; j++)
            {
                for(int k=0; k+j<=n; k+=i)
                    c2[j+k] += c1[j];
            }
            for(int l=0; l<=n; l++)
            {
                c1[l]=c2[l];
                c2[l]=0;
            }
        }
        cout<<c1[n]<<endl;
    }
    return 0;
}

1029 Ignatius and the Princess IV

http://acm.hdu.edu.cn/showproblem.php?pid=1028

这个水题唯一的坑点在于如果同时存在多个满足次数大于等于n/2的数，要取出现次数最多的那个。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <bits/stdc++.h>
using namespace std;
#define maxn 999999
int a[maxn],b[maxn];
int main()
{
    int n;
    while(cin>>n)
    {
        int temp=n/2;
        for(int i=0;i<n;i++)
        {
            int x;
            cin>>x;
            b[i]=x;
            a[x]+=1;
        }
        int maxx;
        for(int i=0;i<n;i++)
        {
            if(a[b[i]]>=temp)
            {
                maxx=b[i];
            }
        }
        cout<<maxx<<endl;
    }
    return 0;
}

1032 The 3n + 1 problem

http://acm.hdu.edu.cn/showproblem.php?pid=1032

注意：一定要先输出n和m，因为如果n<m的话后面会有变动，最后输出会改变n和m的位置，导致wa…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <bits/stdc++.h>
using namespace std;
int n,m;
int cal(int x)
{
    int cnt=0;
    while(x!=1)
    {
        cnt+=1;
        if(x%2!=0) x=x*3+1;
        else x/=2;
    }
    return cnt+1;
}

int main()
{
    while(cin>>n>>m)
    {
        cout<<n<<" "<<m<<" ";
        int maxn=0;
        if(n>m) swap(n,m);
        for(int i=n;i<=m;i++)
        {
            int ans=cal(i);
            if(ans>maxn) maxn=ans;
        }
        cout<<maxn<<endl;
    }
    return 0;
}

递归版，这次幸好没有爆栈…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
using namespace std;
int n,m;

int cal(int x,int cnt)
{
    if(x==1) return cnt+1;
    else
    {
        if(x%2!=0) return cal(3*x+1,cnt+1);
        if(x%2==0) return cal(x/2,cnt+1);
    }
}

int main()
{
    while(cin>>n>>m)
    {
        cout<<n<<" "<<m<<" ";
        if(n>m) swap(n,m);
        int maxn=0;
        for(int i=n;i<=m;i++)
        {
            int ans=cal(i,0);
            if(ans>maxn) maxn=ans;
        }
        cout<<maxn<<endl;
    }
    return 0;
}

1037 Keep on Truckin’

http://acm.hdu.edu.cn/showproblem.php?pid=1037

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
const int maxn=10005;
int a[maxn];
int main()
{
    int n=3;
    for(int i=0;i<n;i++)
        cin>>a[i];
    int flag=0;
    for(int i=0;i<n;i++)
    {
        if(a[i]<168)
        {
            flag=1;
            cout<<"CRASH "<<a[i]<<endl;
        }
    }
    if(!flag) cout<<"NO CRASH"<<endl;
    return 0;
}

1040 As Easy As A+B

http://acm.hdu.edu.cn/showproblem.php?pid=1040

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <bits/stdc++.h>
using namespace std;
#define maxn 1005
int main()
{
    int n,a[maxn];
    while(cin>>n)
    {
        while(n--)
        {
            int m;
            cin>>m;
            for(int i=0; i<m; i++)
                cin>>a[i];
            sort(a,a+m);
            for(int i=0;i<m;i++)
            {
                if(i==m-1) cout<<a[i]<<endl;
                else cout<<a[i]<<" ";
            }

        }

    }
    return 0;
}

1048 The Hardest Problem Ever

http://acm.hdu.edu.cn/showproblem.php?pid=1048

这里唯一需要的注意的地方是，读入包含空格的string串：getline(cin,str);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <bits/stdc++.h>
using namespace std;
#define maxn 1000005
string str;
int main()
{
    string start,ends;
    while(cin>>start)
    {
        getchar();
        if(start=="ENDOFINPUT") break;
        if(start=="START") getline(cin,str);
        vector<char>vec;
        for(int i=0;i<str.size();i++)
        {
            if(str[i]-'A'<5&&str[i]-'A'>=0)//中间出现了一个逗号，相减以后会小于0，导致错误
            {
                int temp=str[i]-'A';
                char v='Z'-(4-temp);
                vec.push_back((char)v);
            }
            else if(str[i]-'A'>=5)
            {
                vec.push_back((char)(str[i]-5));
            }
            else//保存除了A-Z以外的所有字符
            {
                vec.push_back(str[i]);
            }
        }
        cin>>ends;
        for(int i=0;i<vec.size();i++)
            cout<<vec[i];
        cout<<endl;
    }
    return 0;
}

1056 HangOver

超级水题，就是题目有点复杂…

http://acm.hdu.edu.cn/showproblem.php?pid=1056

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <bits/stdc++.h>
using namespace std;
int main()
{
    double n;
    while(cin>>n)
    {
        if(n==0) break;
        double cnt=2,ans=0;
        while(ans<n)
        {
            ans+=1/cnt;
            cnt+=1;
        }
        cout<<cnt-2<<" card(s)"<<endl;
    }
    return 0;
}

1058 Humble Numbers

http://acm.hdu.edu.cn/showproblem.php?pid=1058

这道题有难度，如果直接模拟会在1000的时候直接超时，起码要运行几分钟才能出结果…
下面这个就是典型的超时代码…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <bits/stdc++.h>
using namespace std;

bool calSu(int x)
{
    int cnt=0;
    for(int i=2;i<=x-1;i++)
    {
        if(x%i==0) cnt+=1;
    }
    if(cnt==0) return true;
    else return false;
}


vector<int> calFactor(int x)
{
    vector<int>vec;
    for(int i=1;i<=x;i++)
    {
        if(x%i==0 && calSu(i))
            vec.push_back(i);
    }

    return vec;
}


int main()
{
    int n;
    while(cin>>n)
    {
        if(n==0) break;
        int cnt=0;
        for(int i=1;;i++)
        {
            vector<int>vec=calFactor(i);//计算该数因子
            //vec=calSu(vec);//计算因子中的素数
            bool flag=true;
            for(int i=0;i<vec.size();i++)
            {
                if(!(vec[i]==1||vec[i]==2||vec[i]==3||vec[i]==5||vec[i]==7))
                {
                    flag=false;
                    break;
                }
            }
            if(flag)
            {
                cnt+=1;
                //cout<<"cnt:"<<cnt<<endl;
                if(cnt==n)
                {
                    //cout<<"00000"<<endl;
                    if(n>=10&&n<=20) cout<<"The "<<cnt<<"th humble number is "<<i<<"."<<endl;
                    else
                    {
                        int temp=n;
                        while(temp>10)
                        {
                            temp%=10;
                        }
                        if(temp==1) cout<<"The "<<cnt<<"st humble number is "<<i<<"."<<endl;
                        else if(temp==2) cout<<"The "<<cnt<<"nd humble number is "<<i<<"."<<endl;
                        else if(temp==3) cout<<"The "<<cnt<<"rd humble number is "<<i<<"."<<endl;
                        else cout<<"The "<<cnt<<"th humble number is "<<i<<"."<<endl;
                    }
                    break;
                }
            }
        }
    }
    return 0;
}

下面给出AC代码，这是一道寻找丑数的问题，本质上就是寻找对应的数的2倍，3倍，5倍，7倍，只要找到其中最小的值去乘即可。
重点是，代码还比我上面那个短…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <bits/stdc++.h>
using namespace std;
#define maxn 5842+5
int f[maxn],n;
int i,j,k,l;

int min(int a,int b,int c,int d)
{
    int minn=a;
    if(minn>b) minn=b;
    if(minn>c) minn=c;
    if(minn>d) minn=d;

    if(a==minn) i++;
    if(b==minn) j++;
    if(c==minn) k++;
    if(d==minn) l++;
    return minn;
}

int main()
{
    i=j=k=l=1;
    f[1]=1;
    for(int t=2;t<=5842;t++)
    {
        f[t]=min(2*f[i],3*f[j],5*f[k],7*f[l]);
    }
    while(cin>>n&&n)
    {
         if(n%10==1&&n%100!=11)
            printf("The %dst humble number is %d.\n",n,f[n]);
        else if(n%10==2&&n%100!=12)
            printf("The %dnd humble number is %d.\n",n,f[n]);
        else if(n%10==3&&n%100!=13)
            printf("The %drd humble number is %d.\n",n,f[n]);
        else
            printf("The %dth humble number is %d.\n",n,f[n]);
    }
    return 0;
}

1061 Rightmost Digit

http://acm.hdu.edu.cn/showproblem.php?pid=1061
这道题属于快速幂，又学到一种新姿势了~

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll f(ll a,ll b,ll n)
{
    ll t=1,y=a;
    while(b>0)
    {
        if(b&1) t=t*y%n;
        y=y*y%n;
        b=b>>1;
    }
    return t;
}

int main()
{
    ll t;
    while(cin>>t)
    {
        while(t--)
        {
            ll n;
            cin>>n;
            ll ans=f(n,n,10);
            //mod 10是因为要求个位是多少~
            cout<<ans<<endl;
        }
    }
    return 0;
}

1070 Milk

http://acm.hdu.edu.cn/showproblem.php?pid=1070

水题一把梭！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <bits/stdc++.h>
using namespace std;
#define maxn 105
#define INF 0x3f3f3f3f
struct milk
{
    string name;
    int p,v,days,ave;
}mi[maxn];

bool cmp(milk a,milk b)
{
    if(a.ave!=b.ave) return a.ave<b.ave;
    else return a.v>b.v;
}

int main()
{
    int n,m;
    while(cin>>n)
    {
        while(n--)
        {
            cin>>m;
            for(int i=0;i<m;i++)
            {
                cin>>mi[i].name>>mi[i].p>>mi[i].v;
                if(mi[i].v/200>5) mi[i].days=5;
                else mi[i].days=mi[i].v/200;
                if(mi[i].v<200) mi[i].ave=INF;
                else mi[i].ave=mi[i].p/mi[i].days;
            }
            sort(mi,mi+m,cmp);
            cout<<mi[0].name<<endl;
        }
    }
    return 0;
}

1076 An Easy Task

http://acm.hdu.edu.cn/showproblem.php?pid=1076

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
using namespace std;

bool check(int y)
{
    if(y%400==0 || (y%4==0 && y%100!=0))
        return true;
    else
        return false;
}

int main()
{
    int m;
    while(cin>>m)
    {
        while(m--)
        {
            int Y,n,cnt=0;
            cin>>Y>>n;
            int cur,i;
            for(cur=Y,i=0;i!=n;cur++)
            {
                if(check(cur)) i+=1;
            }
            cout<<cur-1<<endl;
        }
    }
    return 0;
}

1089 A+B for Input-Output Practice (I)

http://acm.hdu.edu.cn/showproblem.php?pid=1089

一开始我以为是大整数之类的…抱着试试的心态交了下面这个…A了…A了…

1
2
3
4
5
6
7
8
9
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int a,b;
    while(cin>>a>>b)
        cout<<a+b<<endl;
    return 0;
}

1090 A+B for Input-Output Practice (II)

http://acm.hdu.edu.cn/showproblem.php?pid=1090

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int a,b,n;
    while(cin>>n)
    {
        while(n--)
        {
            cin>>a>>b;
            cout<<a+b<<endl;
        }
    }
    return 0;
}

1091 A+B for Input-Output Practice (III)

http://acm.hdu.edu.cn/showproblem.php?pid=1091

1
2
3
4
5
6
7
8
9
10
11
12
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int a,b;
    while(cin>>a>>b)
    {
        if(b==0&&a==0) break;
        else cout<<a+b<<endl;
    }
    return 0;
}

1092 A+B for Input-Output Practice (IV)

http://acm.hdu.edu.cn/showproblem.php?pid=1092

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    while(cin>>n&&n)
    {
        int sum=0;
        for(int i=0;i<n;i++)
        {
            int x;
            cin>>x;
            sum+=x;
        }
        cout<<sum<<endl;
    }
    return 0;
}

1093 A+B for Input-Output Practice (V)

http://acm.hdu.edu.cn/showproblem.php?pid=1093

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    while(cin>>n)
    {
        while(n--)
        {
            int sum=0,m;
            cin>>m;
            for(int i=0; i<m; i++)
            {
                int x;
                cin>>x;
                sum+=x;
            }
            cout<<sum<<endl;
        }

    }
    return 0;
}

1094 A+B for Input-Output Practice (VI)

http://acm.hdu.edu.cn/showproblem.php?pid=1094

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    while(cin>>n)
    {
        int sum=0;
        while(n--)
        {
            int x;
            cin>>x;
            sum+=x;
        }
        cout<<sum<<endl;
    }
    return 0;
}

1095 A+B for Input-Output Practice (VII)

http://acm.hdu.edu.cn/showproblem.php?pid=1095

1
2
3
4
5
6
7
8
9
10
11
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int a,b;
    while(cin>>a>>b)
    {
        cout<<a+b<<endl<<endl;
    }
    return 0;
}

1096 A+B for Input-Output Practice (VIII)

http://acm.hdu.edu.cn/showproblem.php?pid=1096

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n,m;
    while(cin>>n)
    {
        while(n--)
        {
            cin>>m;
            int sum=0;
            while(m--)
            {
                int x;
                cin>>x;
                sum+=x;
            }
            cout<<sum<<endl;
            if(n) cout<<endl;
        }
    }
    return 0;
}

1098 Ignatius’s puzzle

http://acm.hdu.edu.cn/showproblem.php?pid=1098

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
using namespace std;
int main()
{
    //(18+k*a)%65==0
    int k;
    while(cin>>k)
    {
        int flag=0;
        for(int i=0;i<=65;i++)
        {
            if((18+i*k)%65==0)
            {
                flag=1;
                cout<<i<<endl;
                break;
            }
        }
        if(!flag) cout<<"no"<<endl;
    }
    return 0;
}

1106 排序

http://acm.hdu.edu.cn/showproblem.php?pid=1106

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
char a[5005];
int b[5005];
int main()
{
    while(scanf("%s",a)!=EOF)
    {
        memset(b,0,sizeof(b));
        int t=0;
        int n=strlen(a);
        int flag=0;
        for(int i=0; i<n; i++)
        {
            if(a[i]!='5')
            {
                b[t]=b[t]*10+(a[i]-'0');
                flag=1;
            }
            else if(flag==1)
            {
                t++;
                flag=0;
            }
            if(a[i]!='5'&&a[i+1]=='\0')
            {
                t++;
            }
        }
        sort(b,b+t);
        for(int i=0; i<t-1; i++)
        {
            printf("%d ",b[i]);
        }
        printf("%d\n",b[t-1]);

    }
    return 0;
}

1108 最小公倍数

http://acm.hdu.edu.cn/showproblem.php?pid=1108

gcd使用~

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <bits/stdc++.h>
using namespace std;

int gcd(int a,int b)
{
    if(a<b) swap(a,b);
    while(a%b)
    {
        int temp=a%b;
        a=b;
        b=temp;
    }
    return b;
}

int main()
{
    int n,m;
    while(cin>>n>>m)
    {
        int ans=gcd(n,m);
        cout<<(n*m)/ans<<endl;
    }
    return 0;
}

1157 Who’s in the Middle

http://acm.hdu.edu.cn/showproblem.php?pid=1157

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    while(cin>>n)
    {
        vector<int>a;
        for(int i=0;i<n;i++)
        {
            int x;
            cin>>x;
            a.push_back(x);
        }
        sort(a.begin(),a.end());
        cout<<a[n/2]<<endl;
    }
    return 0;
}

1063 Eddy’s digital Roots

http://acm.hdu.edu.cn/showproblem.php?pid=1063
九余数定理！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    while(cin>>n&&n)
    {
        int tmp=n;
        for(int i=2;i<=n;i++)
            tmp=tmp*n%9;
        if(tmp==0) cout<<9<<endl;
        else cout<<tmp<<endl;
    }
    return 0;
}

1164 Eddy’s research I

http://acm.hdu.edu.cn/showproblem.php?pid=1164 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    while(cin>>n)
    {
        bool flag=false;
        int tmp=sqrt(n);
        for(int i=2;i<=tmp;i++)
        {
            while(n%i==0)
            {
                n/=i;
                if(flag==false)
                {
                    cout<<i;
                    flag=true;
                }
                else cout<<"*"<<i;
            }
        }
        if(n!=1)
        {
            if(flag) cout<<"*"<<n;
            else cout<<n;
        }
        cout<<endl;
    }
    return 0;
}

1170 Balloon Comes!

http://acm.hdu.edu.cn/showproblem.php?pid=1170

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        int a,b;
        char c;
        cin>>c>>a>>b;
        if(c=='+')
            cout<<a+b<<endl;
        if(c=='-')
            cout<<a-b<<endl;
        if(c=='/')
        {
            if(!(a%b))
            {
                printf("%d\n",a/b);  //如果a除以b是整数，输出整数，
            }
            else
            {
                double sum=double(a)*1.0/b;
                printf("%.2lf\n",sum);  //否则保留两位。
            }

        }
        if(c=='*')
            cout<<a*b<<endl;
    }
    return 0;
}

1194 Beat the Spread!

http://acm.hdu.edu.cn/showproblem.php?pid=1194

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    while(cin>>n)
    {
        while(n--)
        {
            int x,y;
            cin>>x>>y;
            bool flag=false;
            for(int i=1; i<=x; i++)
            {
                int temp=i;
                if(fabs(temp-(x-temp))==y&&temp+(x-temp)==x&&temp>(x-temp))
                {
                    flag=true;
                    cout<<i<<" "<<x-i<<endl;
                }
            }
            if(!flag) cout<<"impossible"<<endl;
        }
    }
return 0;
}

1196 Lowest Bit

http://acm.hdu.edu.cn/showproblem.php?pid=1196

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <bits/stdc++.h>
using namespace std;

string getBinary(int n)
{
    string str="";
    while(n)
    {
        str+=n%2+'0';
        n/=2;
    }
    return str;
}

int main()
{
    int n;
    while(cin>>n&&n)
    {
        string str=getBinary(n);
        int cnt=0;
        for(int i=0;i<str.size();i++)
        {
            if(str[i]=='1')
            {
                cout<<pow(2,cnt)<<endl;
                break;
            }
            else cnt+=1;
        }
    }
    return 0;
}

1197 Specialized Four-Digit Numbers

http://acm.hdu.edu.cn/showproblem.php?pid=1197

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int a,b,c,d;
    for(int i=2992;i<=9999;i++)
    {
        a=i%10;
        b=(i/10)%10;
        c=(i/100)%10;
        d=i/1000;
        int sumt=a+b+c+d;
        a=i%12;
        b=(i/12)%12;
        c=(i/144)%12;
        d=i/1728;
        int sumb=a+b+c+d;
        if(sumt==sumb)
        {
            a=i%16;
            b=(i/16)%16;
            c=(i/256)%16;
            d=i/4096;
            int suml=a+b+c+d;
            if(suml==sumb) cout<<i<<endl;
        }
    }
    return 0;
}

1201 18岁生日

http://acm.hdu.edu.cn/showproblem.php?pid=1201
这道题有点绕，容易漏掉判定条件，很危险。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <bits/stdc++.h>
using namespace std;

int month[]= {0,31,28,31,30,31,30,31,31,30,31,30,31};

bool checkY(int y)
{
    if(y%400==0||(y%4==0&&y%100!=0))
        return true;
    else
        return false;
}
int main()
{
    int n;
    while(cin>>n)
    {
        while(n--)
        {
            string date;
            cin>>date;
            int y=0,m=0,d=0;
            for(int i=0; i<4; i++)
                y=y*10+date[i]-'0';
            for(int i=5; i<=6; i++)
                m=m*10+date[i]-'0';
            for(int i=8; i<10; i++)
                d=d*10+date[i]-'0';
            //cout<<m<<" "<<d<<endl;
            if(m==2&&d==29)
                cout<<"-1"<<endl;
            else
            {
                int days=18*365;
                if(checkY(y)&&(m<2||m==2&&d<29))
                    days+=1;
                for(int i=y+1; i<=y+18; i++)
                {
                    if(checkY(i))
                    {
                        if(i!=y+18) days+=1;
                        else
                        {
                            if(m==2&&d==29||m>=3) days+=1;
                        }
                    }
                }
                cout<<days<<endl;
            }
        }
    }
    return 0;
}

1202 The calculation of GPA

http://acm.hdu.edu.cn/showproblem.php?pid=1202

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n,i;
    double s,p;
    double sums,sum,gpa;
    while(cin>>n)
    {
        sums=sum=0;
        for(i=1; i<=n; i++)
        {
            cin>>s>>p;
            if(((int)p)!=-1)
            {
                sums=sums+s;
                if(p>=90) s=s*4;
                else if(p>=80) s=s*3.0;
                else if(p>=70) s=s*2.0;
                else if(p>=60) s=s*1.0;
                else if(p<=59) s=s*0.0;
                sum=sum+s;
            }
        }
        if((int)sum==0) cout<<"-1"<<endl;
        else
        {
            gpa=sum*1.0/sums;
            cout<<fixed<<setprecision(2)<<gpa<<endl;
        }
    }
    return 0;
}

1235 统计同成绩学生人数

http://acm.hdu.edu.cn/showproblem.php?pid=1235

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF&&n!=0)
    {
        map<int,int>m;
        for(int i=0;i<n;i++)
        {
            int x;
            scanf("%d",&x);
            m[x]+=1;
        }
        int tar;
        scanf("%d",&tar);
        cout<<m[tar]<<endl;
    }
    return 0;
}

1236 排名

http://acm.hdu.edu.cn/showproblem.php?pid=1236

结构体AC版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <bits/stdc++.h>
using namespace std;

struct node
{
    int sum;
    char num[25];
}stu[10005];

bool cmp(node x,node y)
{
    if(x.sum!=y.sum) return x.sum>y.sum;
    else return strcmp(x.num,y.num)<0;
}
int main()
{
    int n,m,g;
    while(scanf("%d",&n)!=EOF&&n!=0)
    {
        scanf("%d %d",&m,&g);
        int score[15];
        for(int i=1;i<=m;i++)
        {
            scanf("%d",&score[i]);
        }
        int cnt=0;
        for(int i=0;i<n;i++)
        {
            char id[25];
            int k;
            scanf("%s %d",&id,&k);
            strcpy(stu[i].num,id);
            int sum=0;
            for(int j=0;j<k;j++)
            {
                int x;
                scanf("%d",&x);
                sum+=score[x];
            }
            if(sum>=g) cnt+=1;
            stu[i].sum=sum;
        }
        cout<<cnt<<endl;
        if(cnt!=0)
        {
            sort(stu,stu+n,cmp);
            for(int i=0;i<cnt;i++)
                cout<<stu[i].num<<" "<<stu[i].sum<<endl;
        }

    }
    return 0;
}

不知道为什么一直wa，比对过AC代码，除了别人用的struct，我用的map。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <bits/stdc++.h>
using namespace std;
typedef pair<string,int>PAIR;
bool cmp(pair<string,int>x,pair<string,int>y)
{
    if(x.second!=y.second) return x.second>y.second;
    else return x.first<y.first;
}
int main()
{
    int n,m,g;
    while(scanf("%d",&n)!=EOF&&n!=0)
    {
        scanf("%d %d",&m,&g);
        int score[15];
        for(int i=1;i<=m;i++)
        {
            scanf("%d",&score[i]);
        }

        map<string,int>m;

        int cnt=0;
        while(n--)
        {
            string num;
            int solve;
            cin>>num;
            scanf("%d",&solve);
            int sum=0;
            for(int i=0;i<solve;i++)
            {
                int x;
                scanf("%d",&x);
                m[num]+=score[x];
                sum+=score[x];
            }
            if(sum>=g) cnt+=1;
        }
        cout<<cnt<<endl;
        if(cnt!=0)
        {
            vector<PAIR>vec(m.begin(),m.end());
            sort(vec.begin(),vec.end(),cmp);
            for(int i=0;i<vec.size();i++)
                if(vec[i].second>=g) cout<<vec[i].first<<" "<<vec[i].second<<endl;
        }

    }
    return 0;
}

1248 寒冰王座(DP模板)

http://acm.hdu.edu.cn/showproblem.php?pid=1248

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <bits/stdc++.h>
using namespace std;
int dp[10100];
int main()
{
    int t,money;
    int i,j;
    int value[3]={150,200,350};
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&money);
        memset(dp,0,sizeof(dp));
        for(i=0;i<3;i++)
        {
            for(j=value[i];j<=money;j++)
            {
                dp[j]=max(dp[j],dp[j-value[i]]+value[i]);
            }
        }
        printf("%d\n",money-dp[money]);
    }

    return 0;
}

1266 Reverse Number

http://acm.hdu.edu.cn/showproblem.php?pid=1266

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    while(cin>>n)
    {
        while(n--)
        {
            string str;
            cin>>str;
            string mark;
            if(!(str[0]>='0'&&str[0]<='9')) cout<<str[0];
            string note="";
            bool flag=true;
            for(int i=str.size()-1;i>=0;i--)
            {
                if(str[i]=='0'&&flag)
                {
                    note+=str[i];
                }
                else
                {
                    flag=false;
                    if(str[i]>='0'&&str[i]<='9') cout<<str[i];
                }
            }
            if(note.size()!=0)
                cout<<note;
            cout<<endl;
        }
    }
    return 0;
}