PAT B1001:

#include <cstdio>

int main() {
    int n, step = 0;
    scanf("%d", &n);
    while (n != 1) {
        if (n % 2 == 0) {
            n /= 2;
            step++;
        } else {
            n = (3 * n + 1) / 2;
            step++;
        }
    }
    printf("%d", step);
    return 0;
}

PAT B1032:

  • 用hash表存各个学校总分;
  • 注意最低分为0,所以创建max时要小于0;
#include <cstdio>
const int maxn=100005;
int school[maxn] = {0};

int main() {
    int n, id, g;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d %d", &id, &g);
        school[id] += g;
    }
    int max = -1, mid;
    for (int i = 1; i < maxn; i++) {
        if (school[i] > max) {
            mid = i;
            max = school[i];
        }
    }
    printf("%d %d", mid, max);
    return 0;
}

PAT B1011:A+B和C

  • int型范围[-2^31^,2^31^-1],当两个最大int型相加时,会导致溢出,所以使用long long型;
  • 一个整型占32bit,4byte,绝对值在10^9^范围内用int;
  • long long型,输入输出的格式控制字符:%lld;
#include <cstdio>

int main() {
    int n;
    long long a, b, c;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%lld %lld %lld", &a, &b, &c);
        if (a + b > c)
            printf("Case #%d: true\n", i);
        else
            printf("Case #%d: false\n", i);
    }
    return 0;
}

PAT B1016:部分A+B

  • 除10,枚举每位是否等于Di 若相等则pa =pa *10+Di ;

    #include <cstdio>
    
    int main() {
        int a, b, da, db;
        int pa = 0, pb = 0;
        scanf("%d %d %d %d", &a, &da, &b, &db);
        while (a != 0) {
            if (a % 10 == da) {
                pa = pa * 10 + da;
            }
            a /= 10;
        }
        while (b != 0) {
            if (b % 10 == db) {
                pb = pb * 10 + db;
            }
            b /= 10;
        }
        printf("%d", pa + pb);
        return 0;
    }

PAT B1026:程序是怎样

  • 因为题目要求time=c~2~ -c~1~ ,time还要除100,应该得到一个小数,但由于int型 / int型(100)得到的是一个整数(截断掉小数部分),所以利用%100,得到被截断的小数部分,通过判断其是否大于50(因为/100得到的是2位数),从而判断是否进位(进位:time/100+1,否则time/100);
  • 注:%02d:数字宽度为2,向右对齐,若位数不足不到2位左边补0; %2d,左边补空格; %-2d,左对齐;
  • 小时:time/3600; 分钟:time%3600/60; 秒数:time%60;
  • 注:错误写法(time /= 100+1),因为会优先算100+1,正确写法(time=time/100+1);

    #include <cstdio>
    
    int main() {
        int c1, c2, time;
        scanf("%d %d", &c1, &c2);
        time = c2 - c1;
        if (time % 100 >= 50)
            time = time/100 + 1;
        else
            time /= 100;
        printf("%02d:%02d:%02d\n", time / 3600, time % 3600 / 60, time % 60);
        return 0;
    }

PAT B1046:划拳

#include <cstdio>

int main() {
    int n;
    int a, ai, b, bi, ad = 0, bd = 0;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d %d %d %d", &a, &ai, &b, &bi);
        int sum = a + b;
        if (ai == sum && bi != sum)
            bd++;
        else if (bi == sum && ai != sum)
            ad++;
    }
    printf("%d %d\n", ad, bd);
    return 0;
}

PAT B1008:数组元素循环右移问题

  • 用m%=n,保证所移动的步数在数组长度之内(%限制步数在0~n-1);
  • 先输出(n-m)~n之间的数(循环右移导致),再输出0到(n-m)之间的数;

    #include <cstdio>
    
    int main() {
        int n, m, ans[101];
        scanf("%d %d", &n, &m);
        for (int i = 0; i < n; i++) {
            scanf("%d", &ans[i]);
        }
        m %= n;
        for (int i = n - m; i < n; i++) {
            printf("%d ", ans[i]);
        }
        for (int i = 0; i < n - m; i++) {
            printf("%d", ans[i]);
            if (i < n - m - 1)
                printf(" ");
        }
        return 0;
    }

PAT B1012:数字分类

  • 用num[5]来存每个种类出现的次数,若num[i]==0则输出N;
  • 用flag*=-1,来实现加减的交替;
  • %.1f:保留1位小数(注意由于是两个int型相除,(double) int / int或1.0*int /int);

    #include <cstdio>
    
    int main() {
        int n, temp, flag = 1;
        int a[6] = {0};
        int num[6] = {0};
        scanf("%d", &n);
        for (int i = 0; i < n; i++) {
            scanf("%d", &temp);
            if (temp % 5 == 0 && temp % 2 == 0) {
                a[1] += temp ;
                num[1]++;
            } else if (temp % 5 == 1) {
                a[2] += flag * temp;
                flag *= -1;
                num[2]++;
            } else if (temp % 5 == 2) {
                a[3]++;
                num[3]++;
            } else if (temp % 5 == 3) {
                a[4] += temp ;
                num[4]++;
            } else if (temp % 5 == 4) {
                if (temp > a[5])
                    a[5] = temp;
                num[5]++;
            }
        }
        if (num[1] == 0)
            printf("N ");
        else
            printf("%d ", a[1]);
        if (num[2] == 0)
            printf("N ");
        else
            printf("%d ", a[2]);
        if (num[3] == 0)
            printf("N ");
        else
            printf("%d ", a[3]);
        if (num[4] == 0)
            printf("N ");
        else
            printf("%.1f ", a[4] * 1.0 / num[4]);
        if (num[5] == 0)
            printf("N");
        else
            printf("%d", a[5]);
        return 0;
    }

PAT B1018:锤子剪刀布

  • B、C、J分别代表 布、锤子、剪刀,将他们用char mp[3]={'B','C','J'}表示,及0表示B,1表示C,2表示J,0胜1,1胜2,2胜0(注意到关系是0>1>2>0,即有循环关系存在,所以不能简单的a+1=b来判断a赢(2+1=“3”,这个“3”表示的是0,所以还应该把这个“3”对应到0上去,即(a+1)%3,%3操作形成了一个循环,(a+1)%3==b,则表示a胜);
  • 用数组a[3],a[0]表win.....;
  • 通过一个int change(char a),将字符转换为对应的数字;
  • 注:寻找的是show[3] = {'B', 'C', 'J'}中的最多win的下标,即maxa存的是下标而不是awin_by[i]中的数字,所以比较if (awin_by[i] > awin_by[maxa]) maxa=i;
  • 注:scanf在一次输入结束后,不会舍弃最后的回车符(即回车符会残留在数据缓冲区中),所以在使用scanf()读入字符(%c)时注意要用getchar()吸收数据缓冲区中的回车(语法相关);

    #include <cstdio>
    
    int change(char a) {
        if (a == 'B')
            return 0;
        if (a == 'C')
            return 1;
        if (a == 'J')
            return 2;
    }
    
    int main() {
        int n;
        char show[3] = {'B', 'C', 'J'};
        int a[3] = {0}, b[3] = {0};
        int awin_by[3] = {0}, bwin_by[3] = {0};
        char A, B;
        int a1, b1;
        scanf("%d", &n);
        for (int i = 0; i < n; i++) {
                getchar();
            scanf("%c %c", &A, &B);
            a1 = change(A);
            b1 = change(B);
            if ((a1 + 1) % 3 == b1) {
                a[0]++;
                b[2]++;
                awin_by[a1]++;
            } else if (a1 == b1) {
                a[1]++;
                b[1]++;
            } else {
                a[2]++;
                b[0]++;
                bwin_by[b1]++;
            }
        }
        printf("%d %d %d\n", a[0], a[1], a[2]);
        printf("%d %d %d\n", b[0], b[1], b[2]);
        int maxa = 0, maxb = 0;
        for (int i = 0; i < 3; i++) {//注:寻找的是show[3] = {'B', 'C', 'J'}中的下标
            if (awin_by[i] > awin_by[maxa])
                maxa = i;
            if (bwin_by[i] > bwin_by[maxb])
                maxb = i;
        }
        printf("%c %c\n", show[maxa], show[maxb]);
        return 0;
    }

PAT A1042:Shuffling Machine

  • 题目大意:给定一规则序列,按照此序列分别将纸牌数组换到新的位置(例:4,2,1,3表示将init[1]的位置换到4的位置);
  • 建立:最初init[]数组,规则数组rule[],交换后数组ans[],通过rule[i]中的数,将init[i]中的数存放到ans[rule[i]]中,每组完成后遍历使init[i]=ans[i]以便下组的交换;
  • 注:编号1到54,共5种花色,每种13跟序号,建立show[5]={'S','H','C','D','J'},将x序号(属于1到54)转化为对应花色及对应序号。花色:n=(x-1)/13 ,则花色为show[n] (由于13号也是0号‘S',而13/13=1,因此x-1,保证花色对应性);序号:k=(x-1)%13 (由于%13结果为0到12,无法表示13,所以x-1将13转化为12,最后+1得13)
  • scanf("%d",&rule[i]);

    #include <cstdio>
    const int n = 55;
    
    char show[5] = {'S', 'H', 'C', 'D', 'J'};
    
    int init[n], rule[n], ans[n] = {0};
    
    int main() {
        int k;
        scanf("%d", &k);
        for (int i = 1; i < 55; i++) {
            init[i] = i;
            scanf("%d", &rule[i]);
        }
        while (k--) {
            for (int i = 1; i < 55; i++)
                ans[rule[i]] = init[i];
            for (int i = 1; i < 55; i++)
                init[i] = ans[i];
        }
        for (int i = 1; i < 55; i++) {
            printf("%c%d", show[(ans[i] - 1) / 13], (ans[i] - 1) % 13 + 1);
            if (i < 54)
                printf(" ");
        }
        return 0;
    }

PAT A1046:shortest distance

  • 题目大意:N个结点围成一个圈,相邻两点距离已知,每次只能移动到相邻的结点,给出M个查询,找出A,B两点间的最小距离;
  • 由于是一个圆形,结点间可以顺时针或逆时针走,但总周长一定,知道一种时针方向间的两点距离,用周长-距离得到另一种时针方向上该两点的距离;用数组dis[i],来保存1到i+1之间的距离(dis[2]表示1到3结点之间的距离(2段距离之和:1到2和2到3),dis[5]表示5+1=”1“到1之间距离即圆的总长度);用sum存储圆的周长,通过判断ans=dis[right-1]-[left-1]和sum-ans的大小寻找两节点间最短距离;
  • 注:若left<right,则交换数值
  • algorithm; swap(a,b); min(a,b)

    #include <cstdio>
    #include <algorithm>
    using namespace std;
    
    int main() {
       int n, sum = 0;
       int dis[100005] = {0};
       scanf("%d", &n);
       for (int i = 1; i <= n; i++) {
           scanf("%d", &dis[i]);
           sum += dis[i];
           dis[i] = sum;
       }
       int M, left, right;
       int ans = 0;
       scanf("%d", &M);
       while (M--) {
           scanf("%d %d", &left, &right);
           if (left > right)
               swap(left, right);
           ans = dis[right - 1] - dis[left - 1];
           printf("%d\n", min(ans, sum - ans));
       }
       return 0;
    }

PAT A1065:A+B and C

  • long long范围[-2^63^,2^63^) (左闭右开) 格式输入输出:%lld;
  • 对于有符号数注意溢出的错误。例对于char类型[-128,127],1个字节,8位,最高位为符号位。127:0111 1111~原、反、补码~ ,127+1=1000 0000(规定为-128);-127:1111 1111~原码~ -> 1000 0000~反码~ ->1000 0001~补码~ -2:1000 0010~原码~ ->1111 1101~反码~ ->1111 1110~补码~ -127-2:1 0111 1111~补码~ (1:超过最高位被丢弃) ->0111 1111~原码~(127);
  • 正溢出:正+正<0。负溢出:负+负>=0;所以当A,B都大于0或都小于0则可能出现溢出。A、B最大值都为2^63^-1,A+B max=2^64^-2,所以溢出值的区间为[-2^63^,-2] (因为最大值+1=最小值) if (a > 0 && b > 0 && sum < 0) true。A、B最小值为-2^63^ (注意long long范围区间)min:A+B=-2^64^,所以溢出区间[0,2^63](最小值+(-1)=最大值)if (a < 0 && b < 0 && sum >= 0) false
  #include <cstdio>

  int main() {
      int T;
      long long a, b, c;
      scanf("%d", &T);
      for (int i = 1; i <= T; i++) {
          scanf("%lld %lld %lld", &a, &b, &c);
          long long sum = a + b;
          if (a > 0 && b > 0 && sum < 0)
              printf("Case #%d: true\n", i);
          else if (a < 0 && b < 0 && sum >= 0)
              printf("Case #%d: false\n", i);
          else if (sum > c)
              printf("Case #%d: true\n", i);
          else
              printf("Case #%d: false\n", i);
      }
      return 0;
  }

PAT B1010:一元多项式求导

  • 用while(scanf("%d %d",&x,&n)!=EOF)来作为输入条件,(Ctrl+z);
  • scanf()有返回值,其值为成功读入的参数个数,本题中庸scanf输入x,n即返回值为2;
  • EOF(End of file)代表-1;
  • 在输入字符中时可用while(scanf("%s",str)!=EOF) 或者while(gets(str)!=NULL);
  • 思路:用一个数组ans[10005],num=0,来保存求导后的x与n,当x*n=0就跳过(continue),最后判断num是否为0,是则printf("0 0");
  #include <cstdio>

  int main(){
      int x,n;
      int ans[1005],num=0;
      while(scanf("%d %d",&x,&n)!=EOF){
          if(x*n==0)    continue;
          else{
              ans[num++]=x*n;
              ans[num++]=n-1;
          }
      }
      if(num==0)    printf("0 0");
      else{
          for(int i=0;i<num;i++){
              printf("%d",ans[i]);
              if(i<num-1)    printf(" ");
          }
      }
      return 0;
  }

PAT A1002:A+B for Polynomials

  • 两个多项式求和:N~1~ 表示x的次方,a~N~1表示该次方下的系数;
  • double 输入格式:%lf 输出格式:%f,%.1f表示保留1位;
  • 思路:用double 数组ans[1001]={0}来保存结果,其中ans[i]里面存值(a,b相同系数相加的值), i表示x的系数,遍历ans数组,ans[i]!=0,num++,最后在遍历输出结果;

    #include <cstdio>
    
    int main(){
        int k,n;
        double a,ans[1001]={0};
        scanf("%d",&k);
        for(int i=0;i<k;i++){
            scanf("%d %lf",&n,&a);
            ans[n]+=a;
        }
        scanf("%d",&k);
        for(int i=0;i<k;i++){
            scanf("%d %lf",&n,&a);
            ans[n]+=a;
        }
        int num=0;
        for(int i=0;i<1001;i++){
            if(ans[i]!=0)
                num++;
        }
        printf("%d",num);
        for(int i=1000;i>=0;i--){
            if(ans[i]!=0)
            printf(" %d %.1f",i,ans[i]);
        }
        return 0;
    }

PAT A1009:product of Polynomials

  • 两个多项式相乘:N~1~ 表示x的次方,a~N~1表示该次方下的系数;
  • 思路:由于多项式相乘它们的系数是相加的则用ans[2001]来保存结果,先将一个多项式存入temp[1001],再输入另一个时每次遍历temp,ans[i+n]+=temp[i]*a

    #include <cstdio>
    
    int main(){
        int k1,k2,n;
        double a,temp[1010]={0},ans[2001]={0};
        scanf("%d",&k1);
        while(k1--){
            scanf("%d %lf",&n,&a);
            temp[n]=a;
        }
        scanf("%d",&k2);
        while(k2--){
            scanf("%d %lf",&n,&a);
            for(int i=1000;i>=0;i--){
                    ans[i+n]+=temp[i]*a;
            }
        }
        int count=0;
        for(int i=0;i<2001;i++){
            if(ans[i]!=0){
                count++;
            }
        }
        printf("%d",count);
        for(int i=2000;i>=0;i--){
            if(ans[i]!=0)
                printf(" %d %.1f",i,ans[i]);
        }
        return 0;
    }