PAT-B] 1017. A除以B [模拟]

链接：1017. A除以B (20)

题意

给两个数A, B。

其中，A为长度不超过1000位的大数（正整数）。B为长度为1的正整数

然后求出 $A/B$ 的商$Q$和余数$R$。

分析

首先看到A这么长用long double也存不下，立即用字符串存储。
同理，B只有一位，那求出来的商Q也很长，也必须使用字符串。

然后就是要解决怎么除的问题了。

这个问题呢，其实不难。直接模拟做除法的过程就可以了。
没想起来的话可以自己在草稿本上写一写。

比如被除数A为1234， 除数B为3，我们可以得到下面这样的过程。

（哇，这个Latex怎么写除法啊）

总之，在草稿本上写一写应该就出来了！

代码

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 <cstdio>
char A[1005], Q[1005];
int main()
{
    int B;
    while( ~scanf( "%s %d", A, &B ) ){
        if( B == 1 ){
            printf( "%s 0\n", A );
            continue;
        }
        int R = 0, i = 0, j = 0;
        if( A[0] - '0' < B ){
            R = ( A[0] - '0' ) % B;
            Q[0] = '0';
            i++;
        }
        for( ; A[i] != '\0'; i++ ){
            R = R * 10 + A[i] - '0';
            if( R < B ){
                Q[j++] = '0';
                continue;
            }
            Q[j++] = R / B + '0';
            R = R % B;
        }
        if( j ) Q[j] = '\0';
        else    Q[j + 1] = '\0';
        printf( "%s %d\n", Q, R );
    }
    return 0;
}

小结

模拟除法。其实挺简单的。

PAT-B] 1016. 部分A+B [字符串处理]

链接：1016. 部分A+B (15)

题意

分别给四个数：
一个大数A和要找的每位数DA， 一个大数B和要找的每位数DB。然后将找出来的DA, DB分别组合成新的数PA, PB，加起来就是答案了。

比如：A是1646451，然后DA是6，然后看A里面有两个6，拼起来PA就是66啦！

同理再求出PB加起来就好了。

分析

这道题呢，由于已经给了A, B两个数的范围。所以直接用数来做也行，用字符串做也行。
之所以归类字符串处理，是因为他就是对每一位处理的来着。
总之用两种方法都可以。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 直接用大数存 A, B
#include <cstdio>
long long A, B, PA, PB;
int DA, DB;
int main()
{
    while( ~scanf( "%lld %d %lld %d", &A, &DA, &B, &DB ) ){
        PA = 0, PB = 0;
        for( ; A > 0 ; A /= 10 ){
            if( A % 10 == DA )  PA = PA * 10 + DA;
        }
        for( ; B > 0 ; B /= 10 ){
            if( B % 10 == DB )  PB = PB * 10 + DB;
        }
        printf( "%lld\n", PA + PB );
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 用字符串存 A, B
#include <cstdio>
char A[105], B[105];
long long PA, PB;
int DA, DB;
int main()
{
    while( ~scanf( "%s %d %s %d", A, &DA, B, &DB ) ){
        PA = 0, PB = 0;
        for( int i = 0; A[i] != '\0' ; i++ ){
            if( A[i] - '0' == DA )  PA = PA * 10 + DA;
        }
        for( int i = 0; B[i] != '\0' ; i++ ){
            if( B[i] - '0' == DB )  PB = PB * 10 + DB;
        }
        printf( "%lld\n", PA + PB );
    }
    return 0;
}

小结

简单题嘛。

PAT-B] 1015. 德才论 [模拟]

链接：1015. 德才论 (25)

题意

第一行给出三个整数 N, L, H 表示 学生人数，最低录取分数线 和 优先录取线（其实就是优秀和良好的分界线啦）。

然后给出一大堆学生的 学号和其各自的 德才分。让你按司马光的理论给出录取排名。
总结一下排名次的要求如下：

  1. 德才分只要有一个没及格（即没达到最低录取分数线L）直接剔除，不放入排名。
  2. 排名先分类，后在各类别中按德才总分排序。
  3. 分类分四类：
    第一类：“才德全尽”— 德，才两项分数均大于等于优先录取线`H`。
第二类：“德胜才”— 德分大于等于优先录取分数线`H`，但才分没达到。
第三类：“才德兼亡”但尚有“德胜才”— 德才分均未达到优先录取线`H`，但德分不低于才分。
第四类：“才胜德”— 除上述三类之外的其他未不及格考生。
  4. 如果德才总分相同，则德分高排前；若仍相同，则按准考证号升序排列。

最后输出录取人数和排好名次的学生信息即可。

分析

既然排名次的要求写得这么明确，那我们就直接写一个cmp，然后让sort()直接帮我们排好序就好了。

注意好排序的要求，应该不会出错。

代码

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
#include <cstdio>
#include <algorithm>
using namespace std;
#define stuMAX 100005
struct stu{
    int no;
    int d, c;   // 德, 才
};
stu s[stuMAX];
int N, L, H;
int level( stu a ){
    if( a.d >= H ){
        if( a.c >= H )  return 1;
        else    return 2;
    }
    else if( a.d >= a.c )    return 3;
    return 4;
}
bool judge( stu a, stu b ){
    if( a.d + a.c != b.d + b.c )    return a.d + a.c > b.d + b.c;
    if( a.d != b.d )    return a.d > b.d;
    return a.no < b.no;
}
bool cmp( stu a, stu b ){
    int la = level( a );
    int lb = level( b );
    if( la != lb )  return la < lb;
    return judge( a, b );
}
int main()
{
    while( ~scanf( "%d%d%d", &N, &L, &H ) ){
        for( int i = 0; i < N; i++ ){
            scanf( "%d %d %d", &s[i].no, &s[i].d, &s[i].c );
            if( s[i].d < L || s[i].c < L ){
                i--;
                N--;
            }
        }
        sort( s, s + N, cmp );
        printf( "%d\n", N );
        for( int i = 0; i < N; i++ ){
            printf( "%d %d %d\n", s[i].no, s[i].d, s[i].c );
        }
    }
    return 0;
}

小结

一看我这么帅就是德才兼备，德才全尽啊！
请录取我！

PAT-B] 1014. 福尔摩斯的约会 [字符串处理]

链接：1014. 福尔摩斯的约会 (20)

题意

让大家来扮演福尔摩斯，又让大家获得约会的机会。
不得不说这个题的福利很好啊（大雾）。

题目的话是给四行字符串。
然后先对前两行字符串中的字符依次进行匹配。
当遇到第1对相同且满足以下条件的字符对时，则表示为星期几。

  1. 大写字母
  2. 既然是表示星期几，取值范围则为 $( A, A + 7 )$，即 $( A, G )$

然后从当前位置开始继续往后再对前两行字符串进行匹配操作。
当遇到第2对相同且满足以下条件的字符对时，则表示为第几小时。

  1. 大写字母和数字
  2. 取值范围则为 $( 0, 9 )$，表示 $0$点 到 $9$点
    和 $( A, A + 13 )$，即 $( A, N )$，表示 $10$点 到 $23$点

最后则对后两行字符串中的字符依次进行匹配。
当遇到第1对相同且为英文字母的字符对时，
其位置，当前字符的数组下标，即为第几分钟。

分析

题意中已经详细分析了。
注意一下输出时的格式就没问题了。

代码

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>
char a[65], b[65], c[65], d[65];
char *week[] = { "MON", "TUE", "WED", "THU", "FRI", "SAT", "SUN" };
int main()
{
    while( ~scanf( "%s%s%s%s", a, b, c, d ) ){
        int f = 1;  // f 表示现在找的是第几个相同的字符 1 为第一个 0 为第二个
        for( int i = 0; a[i] != '\0' && b[i] != '\0'; i++ ){
            if( a[i] == b[i] ){
                if( f ){
                    if( a[i] >= 'A' && a[i] <= 'G' ){
                        printf( "%s ", week[a[i] - 'A'] );
                        f = 0;
                    }
                }
                else{
                    if( ( a[i] >= 'A' && a[i] <= 'N' ) || ( a[i] >= '0' && a[i] <= '9' ) ){
                        int num;
                        if( a[i] >= '0' && a[i] <= '9' ){
                            num = a[i] - '0';
                            putchar( '0' );
                        }
                        else    num = a[i] - 'A' + 10;
                        printf( "%d:", num );
                        break;
                    }
                }
            }
        }
        for( int i = 0; c[i] != '\0' && d[i] != '\0'; i++ ){
            if( c[i] == d[i] ){
                if( ( c[i] >= 'A' && c[i] <= 'Z' ) || ( c[i] >= 'a' && c[i] <= 'z' ) ){
                    printf( "%02d\n", i );
                    break;
                }
            }
        }
    }
    return 0;
}

小结

非常简单的匹配问题。

PAT-B] 1013. 数素数 [数论]

链接：1013. 数素数 (20)

题意

输入两个数 M, N。
然后输出第M个到第N个素数。

分析

由于这里的M和N都是表示的第几个素数。
所以我们必须先把素数列出来。
（列素数的方法有很多，这里就不一一介绍了）

列完素数之后，就输出对应范围内的素数就好了。

要注意的是：这里的第M个到第N个素数也是要输出的。

代码

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 <cstdio>
#define MAX 200000
int sf[MAX];    // 下标对应的数字是不是素数, 1:非, 0:是
int ss[10005];  // 按升序存放素数
int idx = 0;    // 素数数组的下标
int main()
{
    int M, N;
    for( int i = 2; i <= MAX; i++ ){    // 打素数表
        if( sf[i] == 0 ){
            ss[idx++] = i;
            if( idx > 10000 )   break;
            if( i < 2000 ){
                for( long long j = i * i; j <= MAX; j += i ){
                    sf[j] = 1;  // 素数的倍数标注为非素数
                }
            }
        }
    }
    while( ~scanf( "%d%d", &M, &N ) ){
        int i = M - 1;
        if( i < 0 ) i++;
        printf( "%d", ss[i++] );
        for( int j = 1; i < N; j++ ){
            if( j == 10 ){
                puts( "" );
                j = 0;
            }
            else    printf( " " );
            printf( "%d", ss[i++] );
        }
        puts( "" );
    }
    return 0;
}

小结

题目并不难，但求素数的方法是很值得去多查一查的。

PAT-B] 1012. 数字分类 [模拟]

链接：1012. 数字分类 (20)

题意

给一个N表示接下来要操作的数字的个数
然后给出一串数字，按 $A_1$, $A_2$, $A_3$, $A_4$, $A_5$ 的要求分别算就好了。

分析

可以输入一个数计算一个，然后分别存到 $A_1$, $A_2$, $A_3$, $A_4$, $A_5$ 中去。

要注意如果 $A_i$ 中存在没被用到的，则需做好记录。

代码

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
#include <cstdio>
int f[6]={ 0, 0, 0, 0, 0, 0 };      // 表示 Ai 内是否有数
double A[6]={ 0, 0, 0, 0, 0, 0 };   // 存放 Ai 结果
int main()
{
    int N, n, t = 1, j = 0;
    // t 为 A2 中数字前系数，+1 -1 +1 -1 ……
    // j 为 A3 中数字的个数，方便求平均数
    scanf( "%d", &N );
    for( int i = 0; i < N; i++ ){
        scanf( "%d", &n );
        int y = n % 5;
        if( n % 10 == 0 ){  // A1
            A[1] += n;
            f[1] = 1;
        }
        else if( y == 1 ){  // A2
            A[2] += t * n;
            t = -t;
            f[2] = 1;
        }
        else if( y == 2 ){  // A3
            A[3]++;
            f[3] = 1;
        }
        else if( y == 3 ){  // A4
            A[4] += n;
            j++;
            f[4] = 1;
        }
        else if( y == 4 ){  // A5
            if( n > A[5] ){
                A[5] = n;
            }
            f[5] = 1;
        }
    }
    if( f[1] )  printf( "%.0lf", A[1] );
    else    printf( "N" );
    if( f[2] )  printf( " %.0lf", A[2] );
    else    printf( " N" );
    if( f[3] )  printf( " %.0lf", A[3] );
    else    printf( " N" );
    if( j ) A[4] = A[4] / j;
    if( f[4] )  printf( " %.1lf", A[4] );
    else    printf( " N" );
    if( f[5] )  printf( " %.0lf\n", A[5] );
    else    printf( " N\n" );
    return 0;
}

小结

注意一下细节部分就没有问题啦。

PAT-B] 1011. A+B和C [模拟]

链接：1011. A+B和C (15)

题意

先输入一个T，表示测试的输入数量。

每组输入给三个整数 A, B, C。
判断一下A + B是不是大于C

分析

好简单啊。
唯一注意一下A, B, C三者的范围就好了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <cstdio>
int main()
{
    long long A, B, C;
    int T;
    scanf( "%d", &T );
    for( int i = 1; i <= T; i++ ){
        scanf( "%lld%lld%lld", &A, &B, &C );
        printf( "Case #%d: ", i );
        if( A + B > C ) puts( "true" );
        else    puts( "false" );
    }
    return 0;
}

小结

大大水题。

PAT-B] 1010. 一元多项式求导 [数论]

链接：1010. 一元多项式求导 (25)

题意

给一个一元的多项式，然后按格式输出求导后的多项式。

求导应该不用多说了，指数减一，系数乘上指数，就可以了。

分析

输入是以 “系数 指数 系数 指数” 的形式给的。当然输出也要是这个形式。
所以样例的输入输出分别为：
输入：$3x^4-5x^2+6x-2$
输出：$12x^3-10x+6$

然后注意一下答案为 0 时要输出 0 0 。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <cstdio>
struct unit{
    int xs, zs; // 系数, 指数
};
int main()
{
    int flag = 1;   // 判断答案是否为 0
    unit a;
    while( ~scanf( "%d%d", &a.xs, &a.zs ) ){
        if( a.zs ){
            if( flag )  flag = 0;
            else        printf( " " );
            printf( "%d %d", a.xs * a.zs, a.zs - 1 );
        }
        else if( flag ) printf( "0 0" );
    }
    puts( "" );
    return 0;
}

小结

由于求导前后各项互不影响，所以直接在线处理了。

PAT-B] 1009. 说反话 [字符串处理]

链接：1009. 说反话 (20)

题意

在一行中给出若干个单词，然后从最后一个单词开始逆序输出

分析

逆序输出的话，应该马上就会想到栈这个数据结构。

然后就把每个单词看做一个字符串，按顺序放到栈里去。输出的时候依次出栈，就好了。

硬要再有说的话，就是注意一下格式了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <cstdio>
#include <stack>
#include <string>
#include <iostream>
using namespace std;
stack< string > stk;
int main()
{
    string str;
    while( cin >> str ) stk.push( str );
    str = stk.top();
    stk.pop();
    cout << str;
    while( !stk.empty() ){
        str = stk.top();
        stk.pop();
        cout << " " << str;
    }
    puts( "" );
    return 0;
}

小结

了解一下C++自带的STL就不难解决这个问题。

PAT-B] 1008. 数组元素循环右移问题 [模拟]

链接：1008. 数组元素循环右移问题 (20)

题意

题意应该不难理解。

首先给两个数N, M，分别表示数组的大小和右移几位
也就是说第1位数移动到M + 1位，以此类推。
而多出来的数则放在数组的前面。
很像小时候玩的贪吃蛇。

比如样例：
6 2
1 2 3 4 5 6
先是前面的四个数都右移两位：
_ _ 1 2 3 4
然后多出来的5, 6移动到数组前面：
5 6 1 2 3 4

分析

题目理解起来并不难。不过要注意几点：

  1. 给的M可能会比N要大，也就是说可能右移了好几圈。
    比如在400米的操场上跑步，跑100米和跑500米最后停的位置是一样的。
    所以这里我们要对M进行处理，让M对N取模（M % N），得到有效的偏移量
  2. 说是右移，其实我们可以在存入数组的时候直接把元素放在合适的位置。假装我们已经右移了。
    （当然想要严格按题意来的可以忽略这一点）

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <cstdio>
int num[300];
int main()
{
    int N, M;
    while( ~scanf( "%d%d", &N, &M ) ){
        int m = M % N;  // 偏移量
        for( int i = m; i < N; i++ )
            scanf( "%d", num + i );
        for( int i = 0; i < m; i++ )
            scanf( "%d", num + i );
        printf( "%d", num[0] );
        for(int i = 1; i < N; i++ ){
            printf( " %d", num[i] );
        }
        puts("");
    }
    return 0;
}

小结

毕竟OJ都是只看结果的呢…