PAT (Basic Level) Practice

发表于 | 分类于 | 评论数：

2019年3月30日，四十题打卡，此篇文章可能因为字数太多编辑器变得很卡很卡，所以我打算重新写一篇文章记后面的题目。再说一下最近的感受，题目难度确确实实不大，不过我的速度也太慢了，转眼快半个月了，我还做了不到一半，可见自己的底子有多差。这几天也改了一下自己写代码的习惯，所谓代码规范…感觉一个人一个规范，这还真不好说。

2019年3月23日，周六，雨天。完成了第三个十题，越到后面越来越复杂，现在还没有到一半，我感觉照这个速度我可能要做一个月，我大概了解了一下其他人的速度，最多最多也就半个月吧…明天就是蓝桥杯了，我这个都没有刷完，有点惭愧。题目的难度不算太难，不比之前做的算法题，这些题目都有固定的思路，只是代码比较繁琐，还有很多坑点。

2019年3月21日，真好，今天是春分。又做了十道题，最近生活及其不规律，十八号晚上和同学通宵去打游戏了，所以十九号睡了一天（还好那天没课）。二十号刷了八道题目吧，从晚上八点肝到了十一点半，之后又去水群水到了晚上十二点多，我估计我睡着应该快一点了，早上六点五十三的闹钟，实在起不来…还是说昨天做的题目吧，感觉比前面十道题目坑了好多，但是还算是简单的，除了那个大数的除法，我打算找个时间好好学学大数的运算，还有就是这十道题目排序算法偏多。

2019年3月18日，我觉得还是得刷一点题，这些题目难度不是很大，没有涉及什么算法，都是一些很基础的东西，自己基础本来就不好，所以打算把PAT的乙级题库刷一遍。水平有限，这里的AC代码没有多少参考性，很多题目都是硬着头皮写过去的，到目前为止，对比其他大佬的AC代码唯一的感觉就是自闭…

什么是PAT:
浙江大学计算机程序设计能力考试（Programming AbilityTest，简称PAT）是由浙江大学计算机科学与技术学院组织的统一考试。旨在培养和展现学生分析问题、解决问题和计算机程序设计的能力，科学评价计算机程序设计人才，并为企业选拔人才提供参考标准。

PAT乙级要求掌握的知识:
1.具备基本的C/C++的代码设计能力，掌握相关开发环境的基本调试技巧；
2.理解并掌握最基本的数据结构，如：线性表、树、图等；
3.理解并熟练编程实现与基本数据结构相关的基础算法，包括递归、排序、查找等；
4.学会分析算法的时间复杂度、空间复杂度和算法稳定性；
5.具备问题抽象和建模的初步能力，并能够用所学方法解决实际问题。

1001 害死人不偿命的(3n+1)猜想

卡拉兹(Callatz)猜想：

对任何一个正整数 n，如果它是偶数，那么把它砍掉一半；如果它是奇数，那么把 (3n+1) 砍掉一半。这样一直反复砍下去，最后一定在某一步得到 n=1。卡拉兹在 1950 年的世界数学家大会上公布了这个猜想，传说当时耶鲁大学师生齐动员，拼命想证明这个貌似很傻很天真的命题，结果闹得学生们无心学业，一心只证 (3n+1)，以至于有人说这是一个阴谋，卡拉兹是在蓄意延缓美国数学界教学与科研的进展……

我们今天的题目不是证明卡拉兹猜想，而是对给定的任一不超过 1000 的正整数 n，简单地数一下，需要多少步（砍几下）才能得到 n=1？

这一题很简单，写法应该就是这样子了，没啥坑点，跟着题意写就可以了。

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

int main()
{
    int n;
    while(cin >> n)
    {   
        int ans = 0;
        while(n != 1)
        {
            if(n % 2 != 0)
              n = 3*n + 1;
                
            n /= 2;
            ans += 1;
        }
        cout << ans << endl;
    }
    return 0;
}

1002 写出这个数

读入一个正整数 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
#include <iostream>
#include <cstring>
using namespace std;

int main()
{
    char arr[105];
    while(cin>>arr)
    {
        int sum = 0, l = strlen(arr);
        for(int i = 0; i < l; i++)
            sum += arr[i] - '0';
        
        int w = sum, x[105], h = 1, k = 1;
        while(w >= 10)
        {
            x[k++] =  w % 10;
            w /= 10;
            h ++;
        }
        x[k] = w;

        char str[15][3] = {"ling", "yi", "er", "san", "si", "wu", "liu", "qi", "ba", "jiu"};
        for(int i = h; i >= 1; i--)
        {
            cout<<str[x[i]];
            if(i != 1)
                cout<<" ";
            else
                cout<<endl;
        }
    }
    return 0;
}

1003 我要通过!

“答案正确”是自动判题系统给出的最令人欢喜的回复。本题属于 PAT 的“答案正确”大派送 —— 只要读入的字符串满足下列条件，系统就输出“答案正确”，否则输出“答案错误”。

得到“答案正确”的条件是：

1.字符串中必须仅有 P、 A、 T这三种字符，不可以包含其它字符；
2.任意形如 xPATx 的字符串都可以获得“答案正确”，其中 x 或者是空字符串，或者是仅由字母 A 组成的字符串；
3.如果 aPbTc 是正确的，那么 aPbATca 也是正确的，其中 a、 b、 c 均或者是空字符串，或者是仅由字母 A 组成的字符串。

现在就请你为 PAT 写一个自动裁判程序，判定哪些字符串是可以获得“答案正确”的。

这题像阅读理解，半天半天没看懂题意，最后看了大佬们的题解，其实也就是一个关键判断条件，P前面的A的总数和中间的A的总数的乘积要等于T后面的A的总数，感觉没啥意思，我写的很乱。

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
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        char str[105];
        cin>>str;

        bool flag = true;
        int len = strlen(str);
        for(int i = 0; i <= len-1; i++)
        {
            if(str[i] != 'P' && str[i] != 'A' && str[i] != 'T')
            {
                flag = false;
                break;
            }
        }
        int p_num = 0, t_num = 0;
        for(int i = 0; i <= len-1; i++)
        {
            if(str[i] == 'P')
                p_num++;
            else if(str[i] == 'T')
                t_num++;
        }
        if(flag == false || len < 3 || p_num > 1 || t_num > 1)
        {
            cout<<"NO"<<endl;
            continue;
        }

        int a, b, c;
        for(int i = 0; i <= len-1; i++)
        {
            if(str[i] == 'P')
                a = i;
            else if(str[i] == 'T')
            {
                b = i;
                break;
            }
        }
        b = b - (a + 1);
        c = len - (a + b + 2);

        if(a * b == c)
            cout<<"YES"<<endl;
        else
            cout<<"NO"<<endl;

    }
    return 0;
}

1004 成绩排名

读入 n（>0）名学生的姓名、学号、成绩，分别输出成绩最高和成绩最低学生的姓名和学号。

用了结构体和一个排序函数，没什么特别的地方，我想题目本意应该是考察冒泡排序这种算法，但是有了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
#include <iostream>
#include <algorithm>
using namespace std;

struct stu {
	char name[20], number[20];
	int score;
};

bool cmp(struct stu a, struct stu b)
{
    return a.score < b.score;
}

int main()
{
	int n;
	while(cin>>n)
	{
        struct stu test[1000];
		for(int i = 1; i <= n; i++)
			cin>>test[i].name>>test[i].number>>test[i].score;

		sort(test + 1, test + 1 + n, cmp);

		cout<<test[n].name<<" "<<test[n].number<<endl;
        cout<<test[1].name<<" "<<test[1].number<<endl;
	}
	return 0;
}

1005 继续(3n+1)猜想

卡拉兹(Callatz)猜想已经在1001中给出了描述。在这个题目里，情况稍微有些复杂。

当我们验证卡拉兹猜想的时候，为了避免重复计算，可以记录下递推过程中遇到的每一个数。例如对 n=3 进行验证的时候，我们需要计算 3、5、8、4、2、1，则当我们对 n=5、8、4、2 进行验证的时候，就可以直接判定卡拉兹猜想的真伪，而不需要重复计算，因为这 4 个数已经在验证3的时候遇到过了，我们称 5、8、4、2 是被 3“覆盖”的数。我们称一个数列中的某个数 n 为“关键数”，如果 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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <iostream>
#include <algorithm>
using namespace std;

bool cmp(int a, int b)
{
    return a > b;
}

int main()
{
    int arr[105], n;
    while(cin>>n)
    {
        for(int i = 1; i <= n; i++)
            cin>>arr[i];
        sort(arr + 1, arr + 1 + n, cmp);

        int brr[105] = {0};
        for(int i = 1; i <= n; i++)
            brr[i] = arr[i];

        bool vis[4500] = {0};
        for(int i = 1; i <= n; i++)
        {
            while(brr[i] != 1)
            {
                if(brr[i] % 2 != 0)
                    brr[i] = brr[i]*3 + 1;
                brr[i] /= 2;
                vis[brr[i]] = true;
            }
        }

        bool flag = true;
        for(int i = 1; i <= n; i++)
        {
            if(vis[arr[i]] == false)
            {
                if(flag == true)
                {
                    cout<<arr[i];
                    flag = false;
                }
                else
                    cout<<" "<<arr[i];
            }
        }
        cout<<endl;
    }
    return 0;
}

1006 换个格式输出整数

让我们用字母 B 来表示“百”、字母 S 表示“十”，用 12…n 来表示不为零的个位数字 n（<10），换个格式来输出任一个不超过 3 位的正整数。例如 234 应该被输出为 BBSSS1234，因为它有 2 个“百”、3 个“十”、以及个位的 4。

这题就不说了，感觉自己捡了个漏子，我把个十百都求出来了，然后输出的…

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 <iostream>
using namespace std;

int main()
{
    int n;
    while(cin>>n)
    {
        int g = n % 10;
        int s = n / 10 % 10;
        int b = n / 100;

        if(n < 10)
        {
            for(int i = 1; i <= g; i++)
                cout<<i;
        }
        else if(n < 100)
        {
            for(int i = 1; i <= s; i++)
                cout<<"S";

            for(int i = 1; i <= g; i++)
                cout<<i;
        }
        else
        {
            for(int i = 1; i <= b; i++)
                cout<<"B";
            for(int i = 1; i <= s; i++)
                cout<<"S";
            for(int i = 1; i <= g; i++)
                cout<<i;
        }
        cout<<endl;
    }
    return 0;
}

1007 素数对猜想

让我们定义d(n)为：d(n)=p(n+1) − p(n)，其中pi是第i个素数。显然有d1=1，且对于n>1有d(n)是偶数。“素数对猜想”认为“存在无穷多对相邻且差为2的素数”。

现给定任意正整数N(<10^5)，请计算不超过N的满足猜想的素数对的个数。

这题写法应该没多大问题，也不知道别人怎么写的，反正我是把所有的素数求了一遍，至少题目的要求范围内没有任何问题，这里我得抱怨一下，我感觉PTA的只有五组的判断数据也太少了一点吧，搞不好我是错的水数据过了我都不知道。

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 <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;

bool is_prime(int x)
{
    if(x <= 3)
        return true;
    for(int i = 2; i <= sqrt(x); i++)
        if(x % i == 0)
            return false;
    return true;
}

int main()
{
    int n;
    while(cin>>n)
    {
        int temp, sum = 0;
        bool flag = false;
        for(int i = 1; i <= n; i++)
        {
            if(is_prime(i) == true)
            {
                if(flag == true && (i - temp) == 2)
                {
                    flag = false;
                    sum++;
                }

                flag = true;
                temp = i;
            }
        }
        cout<<sum<<endl;
    }
    return 0;
}

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
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
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;

int main()
{
    int n, m;
    while(cin>>n>>m)
    {
        int arr[105], brr[105] = {0};
        for(int i = 1; i <= n; i++)
            cin>>arr[i];

        if(m == n)
        {
            for(int i = 1; i <= n; i++)
            {
                if(i == n)
                    cout<<arr[i]<<endl;
                else
                    cout<<arr[i]<<" ";
            }
        }
        else
        {
            if(m > n)
                m -= n;

            for(int i = 1; i <= n; i++)
            {
                if(i + m <= n)
                    brr[i+m] = arr[i];
                else
                {
                    int x = i + m - n;
                    brr[x] = arr[i];
                }
            }

            for(int i = 1; i <= n; i++)
            {
                if(i == n)
                    cout<<brr[i]<<endl;
                else
                    cout<<brr[i]<<" ";
            }
        }
    }
    return 0;
}

1009 说反话

给定一句英语，要求你编写程序，将句中所有单词的顺序颠倒输出。

这题…不会做，参考别人的代码写的。也是很简单的一题，但是我用cin和scanf的时候竟然妄想把空格也输入进去，简直不可理喻…

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 <iostream>
#include <cstdio>
using namespace std;

int main()
{
    char str[100][100];
    int j;
    for(j = 0; ;j++)
    {
        scanf("%s", str[j]);
        if(getchar() == '\n') 
            break;
    }
    
    for(int i = j; i >= 0; i--)
    {
        printf("%s", str[i]);
        if(i != 0)
            printf(" ");
        else
            printf("\n");
    }
    return 0;
}

1010 一元多项式求导

设计函数求一元多项式的导数。（注：x^n（n为整数）的一阶导数为nx^(n−1)。）

这题唯一坑点在输入，以及0多项式也要输出一个”0 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
#include <iostream>
using namespace std;

int main()
{
    int s, e;
    cin>>s>>e;

    if(e == 0)
        cout<<"0 0"<<endl;
    else
    {
        cout<<s*e<<" "<<e-1;

        while(cin>>s>>e)
        {
            if(e != 0)
                cout<<" "<<s*e<<" "<<e-1;
            else
                cout<<endl;
        }
    }
    return 0;
}

1011 A+B 和 C

给定区间 [−2^31,2^31] 内的 3 个整数 A、B 和 C，请判断 A+B 是否大于 C。

这题不用调试了，直接交吧，就是这么简单

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

int main()
{
    int n;
    cin>>n;
    int k = 1;
    while(n--)
    {
        long long a, b , c;
        cin>>a>>b>>c;
    
        cout<<"Case #"<<k++<<": ";
        if(a + b > c)
            cout<<"true"<<endl;
        else
            cout<<"false"<<endl;
    }
    return 0;
}

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
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
76
77
78
79
80
81
#include <cstdio>

int main()
{
    int n;
    while(scanf("%d", &n) != EOF)
    {
        int sum1 = 0, sum2 = 0, sum4 = 0;
        int num1, num3 = 0, num4 = 0, num5 = 0, k = 1;
        bool vis[1005] = {0};

        for(int i = 1; i <= n; i++)
        {
            scanf("%d", &num1);
            if(num1 % 5 == 0 && num1 % 2 == 0)
            {
                sum1 += num1;
                vis[1] = true;
            }
            else if(num1 % 5 == 1)
            {
                vis[2] = true;
                sum2 = sum2 + k*num1;
                k *= -1;
            }
            else if(num1 % 5 == 2)
            {
                vis[3] = true;
                num3++;
            }
            else if(num1 % 5 == 3)
            {
                vis[4] = true;
                sum4 += num1;
                num4++;
            }
            else if(num1 % 5 == 4)
            {
                vis[5] = true;
                num5 = num1 > num5 ? num1 : num5;
            }
        }
        for(int i = 1; i <= 5; i++)
        {
            switch(i)
            {
                case 1:
                    if(vis[i] == true)
                        printf("%d ", sum1);
                    else
                        printf("N ");
                    break;
                case 2:
                    if(vis[i] == true)
                        printf("%d ", sum2);
                    else
                        printf("N ");
                    break;
                case 3:
                    if(vis[i] == true)
                        printf("%d ", num3);
                    else
                        printf("N ");
                    break;
                case 4:
                    if(vis[i] == true)
                        printf("%.1lf ", (double)sum4 / num4);
                    else
                        printf("N ");
                    break;
                case 5:
                    if(vis[i] == true)
                        printf("%d\n", num5);
                    else
                        printf("N\n");
                    break;
            }
        }
    }
    return 0;
}

1013 数素数

令 Pi表示第 i 个素数。现任给两个正整数 M≤N≤10^4，请输出 PM到 PN的所有素数。

题目要求不多，素数而已，很简单的一个东西，也没说不能打表，所以把要求的素数全部求出来记录就好了，然后输出。

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
#include <iostream>
#include <cmath>
using namespace std;

bool is_prime(int x)
{
    if(x == 1)
        return false;
    for(int i = 2; i <= sqrt(x); i++)
    {
        if(x % i == 0)
            return false;
    }
    return true;
}

int main()
{
    int n, m, j = 0, arr[10005] = {0};
    for(int i = 1; j <= 10000; i++)
    {
        if(is_prime(i) == true)
            arr[++j] = i;
    }

    while(cin>>n>>m)
    {
        int num = 1;
        for(int i = n; i <= m; i++)
        {
            if(num == 10 || i == m)
            {
                cout<<arr[i]<<endl;
                num = 1;
            }
            else
            {
                cout<<arr[i]<<" ";
                num++;
            }
        }
    }
    return 0;
}

1014 福尔摩斯的约会

大侦探福尔摩斯接到一张奇怪的字条：我们约会吧！ 3485djDkxh4hhGE 2984akDfkkkkggEdsb s&hgsfdk d&Hyscvnm。大侦探很快就明白了，字条上奇怪的乱码实际上就是约会的时间星期四 14:04，因为前面两字符串中第 1 对相同的大写英文字母（大小写有区分）是第 4 个字母 D，代表星期四；第 2 对相同的字符是 E ，那是第 5 个英文字母，代表一天里的第 14 个钟头（于是一天的 0 点到 23 点由数字 0 到 9、以及大写字母 A 到 N 表示）；后面两字符串第 1 对相同的英文字母 s 出现在第 4 个位置（从 0 开始计数）上，代表第 4 分钟。现给定两对字符串，请帮助福尔摩斯解码得到约会的时间。

不得不说，这种题目真的坑点挺多了，题目越长越应该仔细看，不能漏过任何的内容，不然就是WA警告…前两个字符串，首先要找一对一样的大写字母（A到G），然后要找第二队一样的相同的字符（0到9或者A到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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <iostream>
#include <cstring>
using namespace std;

int main()
{
    char str1[65], str2[65], str3[65], str4[65];
    while(cin>>str1>>str2>>str3>>str4)
    {
        int tag = 1;
        char week[10][16] = {"MON", "TUE", "WED", "THU", "FRI", "SAT", "SUN"};

        for(int i = 0; i < strlen(str1); i++)
        {
            if(str1[i] == str2[i])
            {
                if(tag == 2)
                {
                    if(str1[i] >= '0' && str1[i] <= '9')
                    {
                        cout<<0<<str1[i]<<":";
                        break;
                    }
                    else if(str1[i] >= 'A' && str1[i] <= 'N')
                    {
                        cout<<str1[i] - 'A' + 10<<":";
                        break;
                    }
                }
                else
                {
                    if(str1[i] >= 'A' && str2[i] <= 'G')
                    {
                        cout<<week[str1[i] - 'A']<<" ";
                        tag = 2;
                    }
                }
            }
        }

        for(int i = 0; i < strlen(str3); i++)
        {
            if((str3[i] >= 'a' && str3[i] <= 'z') || (str3[i] >= 'A' && str3[i] <= 'Z'))
            {
                if(str3[i] == str4[i])
                {
                    if(i < 10)
                        cout<<0;
                    cout<<i<<endl;
                    break;
                }
            }
        }
    }
    return 0;
}

1015 德才论

宋代史学家司马光在《资治通鉴》中有一段著名的“德才论”：“是故才德全尽谓之圣人，才德兼亡谓之愚人，德胜才谓之君子，才胜德谓之小人。凡取人之术，苟不得圣人，君子而与之，与其得小人，不若得愚人。”

现给出一批考生的德才分数，请根据司马光的理论给出录取排名。

这题其实挺复杂的，不过总的来说它还是一个分批次排序的题目，写好了排序算法就好了，不过咱们有sort函数，所以写compare就好了。首先把批次分好，然后第二个依据是总分，然后是德分，最后是学号。

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
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

struct stu {
    int id, dscore, cscore;
    int zf, pici;
    bool luqu;
}t[100005];

bool cmp(struct stu a, struct stu b)
{
    if(a.pici != b.pici)
        return a.pici < b.pici;
    else if(a.zf != b.zf)
        return a.zf > b.zf;
    else if(a.dscore != b.dscore)
        return a.dscore > b.dscore;
    else
        return a.id < b.id;
}

int main()
{
    int n, l, h;
    while(cin>>n>>l>>h)
    {
        int sum = 0;
        for(int i = 0; i < n; i++)
        {
            cin>>t[i].id>>t[i].dscore>>t[i].cscore;
            t[i].zf = t[i].dscore + t[i].cscore;

            if(t[i].dscore >= l && t[i].cscore >= l)
            {
                sum ++;
                t[i].luqu = true;
                if(t[i].dscore >= h && t[i].cscore >= h)
                    t[i].pici = 1;
                else if(t[i].dscore >= h && t[i].cscore < h)
                    t[i].pici = 2;
                else if(t[i].dscore < h && t[i].cscore < h && t[i].dscore >= t[i].cscore)
                    t[i].pici = 3;
                else
                    t[i].pici = 4;
            }
            else
            {
                t[i].luqu = false;
                t[i].pici = 0;
            }
        }

        sort(t, t + n, cmp);
        cout<<sum<<endl;
        for(int i = 0; i < n; i++)
        {
            if(t[i].luqu == true)
                printf("%d %d %d\n", t[i].id, t[i].dscore, t[i].cscore);
        }
    }
    return 0;
}

1016 部分A+B

很简单的一个题目，既然题目要求输入的只有10^10，那我就直接把这个数拆解了，然后找出符合的个数，最后把这个合起来，最后再求和，就这样子了，虽然写法很笨，但是不影响什么的…也多亏PTA对程序的空间时间要求都不高…

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 <iostream>
using namespace std;

int main()
{
    long long a, d_a, b, d_b;
    while(cin>>a>>d_a>>b>>d_b)
    {
        int num_a = 0, num_b = 0;
        while(a || b)
        {
            if(a % 10 == d_a)   num_a++;
            if(b % 10 == d_b)   num_b++;

            a /= 10;
            b /= 10;
        }

        int sum_a = 0, sum_b = 0;
        while(num_a || num_b)
        {
            if(num_a)   sum_a += d_a*pow(10, --num_a);
            if(num_b)   sum_b += d_b*pow(10, --num_b);
        }

        cout<<sum_a + sum_b<<endl;
    }
    return 0;
}

1017 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
#include <iostream>
#include <cstring>
using namespace std;

int main()
{
    string s;
    int b;
    while(cin>>s>>b)
    {
        int t = (s[0] - '0') / b;
        if(t != 0 && s.length() > 1 || s.length() == 1)
            cout<<t;

        int p = (s[0] - '0') % b;
        for(int i = 1; i < s.length(); i++)
        {
            t = (p*10 + s[i] - '0') / b;
            cout<<t;
            p = (p*10 + s[i] - '0') % b;
        }

        cout<<" "<<p<<endl;
    }
    return 0;
}

//这题无法理解，大数的加减乘除现在没怎么接触过，有时间再说吧。

1018 锤子剪刀布

两个人玩锤子剪刀布，要计算出各自赢的场数和赢的最多的手势，这题…不可理喻…

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
76
77
78
79
80
81
82
83
84
85
86
#include <iostream>
using namespace std;

int max(int a, int b, int c)
{
    if(a >= b)    return a >= c ? 1 : 3;
    else    return b >= c ? 2 : 3;
}

int main()
{
    int n;
    while(cin>>n)
    {
        char a, b;
        int p, a_win, b_win;
        p = a_win = b_win = 0;

        int a_win_c_num, a_win_j_num, a_win_b_num;
        a_win_c_num = a_win_j_num = a_win_b_num = 0;
        int b_win_c_num, b_win_j_num, b_win_b_num;
        b_win_c_num = b_win_j_num = b_win_b_num = 0;

        for(int i = 1; i <= n; i++)
        {
            cin>>a>>b;
            if(a == b)
                p++;
            else
            {
                if(a == 'C')
                {
                    if(b == 'J')
                    {
                        a_win++;
                        a_win_c_num++;
                    }
                    else
                    {
                        b_win++;
                        b_win_b_num++;
                    }
                }
                else if(a == 'J')
                {
                    if(b == 'B')
                    {
                        a_win++;
                        a_win_j_num++;
                    }
                    else
                    {
                        b_win++;
                        b_win_c_num++;
                    }
                }
                else
                {
                    if(b == 'C')
                    {
                        a_win++;
                        a_win_b_num++;
                    }
                    else
                    {
                        b_win++;
                        b_win_j_num++;
                    }
                }
            }
        }

        cout<<a_win<<" "<<p<<" "<<b_win<<endl;
        cout<<b_win<<" "<<p<<" "<<a_win<<endl;

        int a_win_max_sign = max(a_win_b_num, a_win_c_num, a_win_j_num);
        int b_win_max_sign = max(b_win_b_num, b_win_c_num, b_win_j_num);
        if(a_win_max_sign == 1) cout<<"B ";
        if(a_win_max_sign == 2) cout<<"C ";
        if(a_win_max_sign == 3) cout<<"J ";
        if(b_win_max_sign == 1) cout<<"B"<<endl;
        if(b_win_max_sign == 2) cout<<"C"<<endl;
        if(b_win_max_sign == 3) cout<<"J"<<endl;
    }
    return 0;
}

1019 数字黑洞

给定任一个各位数字不完全相同的 4 位正整数，如果我们先把 4 个数字按非递增排序，再按非递减排序，然后用第 1 个数字减第 2 个数字，将得到一个新的数字。一直重复这样做，我们很快会停在有“数字黑洞”之称的 6174，这个神奇的数字也叫 Kaprekar 常数。

不需要想太复杂，输入用整数就好了，然后把这个整数转化成数组，然后对这个数组两次排序即可求得最大和最小的值。不得不吐槽一下，这个非递增和非递减几个意思，还有乱序不成？你直接写递增就递增不就好了。然后把最大值和最小值转化成数值，然后求得差值又要把这个数转化成数组，如此循环，直到差值等于0或者6174。

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
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
using namespace std;

bool cmp(int a, int b)
{
    return a > b;
}

int num(int arr[])
{
    int p = 1, sum = 0;
    for(int i = 0; i < 4; i++)
        sum = sum*10 + arr[i];
    return sum;
}

int to_arr(int arr[], int n)
{
    for(int i = 0; i <= 3; i++)
    {
        arr[i] = n % 10;
        n /= 10;
    }
}

int main()
{
    int n, arr[5];
    while(cin>>n)
    {
        while(true)
        {
            to_arr(arr, n);
            sort(arr, arr + 4);
            int min_n = num(arr);
            sort(arr, arr + 4, cmp);
            int max_n = num(arr);

            n = max_n - min_n;
            printf("%04d - %04d = %04d\n", max_n, min_n, n);

            if(n == 6174 || n == 0)
                break;
        }
    }
    return 0;
}

1020 月饼

时间过得真快，转眼间已经有四个多月了，我的typecho博客第一篇文章就是这样子的一道题目，可惜原本的数据库被我删了，现在啥也没有了。这题换了一个说法，本质上也就是一个排序加贪心的东西，进步还是有点的，看到这种题目直接上手就干了，只是要注意段错误这点…也就是数组下标溢出。

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
#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;

struct node {
    double kc, sj;
}yb[1005];

bool cmp(struct node a, struct node b)
{
    return (a.sj / a.kc) > (b.sj / b.kc);
}

int main()
{
    int n, m;
    while(cin>>n>>m)
    {
        for(int i = 0; i < n; i++)
            cin>>yb[i].kc;

        for(int i = 0; i < n; i++)
            cin>>yb[i].sj;

        sort(yb, yb + n, cmp);

        double sum = 0;
        int i = -1;
        while(m && i++ < n)
        {
            if(yb[i].kc >= m)
            {
                sum += m / yb[i].kc * yb[i].sj;
                m -= m;
            }
            else
            {
                sum += yb[i].sj;
                m -= yb[i].kc;
            }
        }
        printf("%.2lf\n", sum);
    }
    return 0;
}

1021 个位数统计

我摸清楚了一个规律，那就是每5道之后的一题都是比较简单的，我觉PAT得这一点做的很好，哈哈。
这题思路很清晰，输入数据之后用另外一个数组把出现的数字的次数记录下来，最后输出次数不为0的结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <cstring>
using namespace std;

int main()
{
    char str[1005];
    while(cin>>str)
    {
        int len = strlen(str);
        int arr[15] = {0};
        for(int i = 0; i < len; i++)
            arr[str[i] - '0']++;

        for(int i = 0; i < 10; i++)
        {
            if(arr[i] != 0)
                cout<<i<<":"<<arr[i]<<endl;
        }
    }
    return 0;
}

1022 D进制的A+B

输入两个非负 10 进制整数 A 和 B (≤2^30−1)，输出 A+B 的 D (1<D≤10)进制数。

进制转化，前几天还做过类似的题目，但是这题却没有一发A…首先注意特例0直接输出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
#include <iostream>
using namespace std;

int main()
{
    int a, b, d;
    while(cin>>a>>b>>d)
    {
        long long sum = a + b;
        int ans[50], i = 0;

        if(sum == 0)
        {
            cout<<0<<endl;
            continue;
        }
        
        while(sum)
        {
            ans[i++] = sum % d;
            sum /= d;
        }

        while(--i >= 0)
            cout<<ans[i];
        cout<<endl;
    }
    return 0;
}

1023 组个最小数

给定数字 0-9 各若干个。你可以以任意顺序排列这些数字，但必须全部使用。目标是使得最后得到的数尽可能小（注意 0 不能做首位）。例如：给定两个 0，两个 1，三个 5，一个 8，我们得到的最小的数就是 10015558。

现给定数字，请编写程序输出能够组成的最小的数。

这道题比较简单，如果我思路没有错的话，输入数据之后算出实际的数组和数据总数，然后用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
#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
    int x, num = 0, min_n = 11, arr[55] = {0};
    for(int i = 0; i < 10; i++)
    {
        cin>>x;
        for(int j = num; j < x + num; j++)
            arr[j] = i;
        num += x;
        if(x != 0 && i != 0)
            min_n = min_n < i ? min_n : i;
    }


    sort(arr, arr + num);
    for(int i = 0; i < num; i++)
    {
        if(arr[i] == min_n)
        {
            for(int j = i; j > 0; j--)
                arr[i] = arr[i-1];
            break;
        }
    }
    arr[0] = min_n;
    for(int i = 0; i < num; i++)
        cout<<arr[i];
    cout<<endl;
    return 0;
}

1024 科学计数法

现以科学计数法的格式给出实数 A，请编写程序按普通数字表示法输出 A，并保证所有有效位都被保留。

我认为这道题就算是复杂的题目了，给出科学计数法然后写成普通的，这道题告诉我们怎么化简单为复杂…
首先有负号先输出负号，然后判断指数正负大小，注释写了。

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
#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
    string s;
    while(cin>>s)
    {
        int len = s.length();

        if(s[0] == '-')
            cout<<"-";
        //有负号先输出

        int pos = 0;
        while(s[pos] != 'E')
            pos++;
        //找到‘E’所在的位置

        int exp = 0;
        for(int i = pos + 2; i < len; i++)
            exp = exp*10 + (s[i] - '0');
        //计算得到指数exp

        //如果指数为0直接输出‘E’前面的数
        if(exp == 0)
        {
            for(int i = 1; i < pos; i++)
                cout<<s[i];
        }
        else if(s[pos+1] == '-')
        {
            //判断指数不为0时E后面的符号，如果为负，先输出'0.'
            cout<<"0.";
            for(int i = 0; i < exp - 1; i++)
                cout<<"0";
            //紧接着输出exp - 1个'0'
            for(int i = 1; i < pos; i++)
                if(s[i] != '.')
                    cout<<s[i];
            //最后输出从第一个字符到’E'之间的除'.'之外的字符
        }
        else
        {
            //指数非0且E后面的符号为正时
            for(int i = 1; i < pos; i++)
            {
                if(s[i] != '.')
                    cout<<s[i];
                //输出从第一个字符到’E'之间的除'.'之外的字符
                if(i == exp + 2 && i != (pos - 1))
                    cout<<".";
                //如果字符串的长度大于指数+2需要输出'.'
            }

            //最后补零，零的个数是指数减去'.'到'E'的位数，也就是pos - 3
            for(int i = 0; i < exp - (pos - 3); i++)
                cout<<"0";
        }
        cout<<endl;
    }
    return 0;
}

1025 反转链表

给定一个常数 K 以及一个单链表 L，请编写程序将 L 中每 K 个结点反转。例如：给定 L 为 1→2→3→4→5→6，K 为 3，则输出应该为 3→2→1→6→5→4；如果 K 为 4，则输出应该为 4→3→2→1→5→6，即最后不到 K 个元素不反转。

哎，你说反转链表就反转呗，为何要把题目搞这么复杂，如果普通的反转链表我肯定会老老实实去写。这道题最开始我压根就没想要用链表写，我想直接水过去…然而我想多了，最后还是老老实实来了，不过其实最关键的部分还是用的reverse函数…其他部分要注意的输入的时候，用地址来作为标准存储数据，然后用另外一个结构体指针数组来指向本来的结构体数组以方便reverse，最后输出的时候下一个地址应该是用下一个结构体指针数组的地址，以及最后一个数的next地址用-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
43
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

const int maxn = 100005;
struct list {
    int data;
    int address, next_address;
}a[maxn], *b[maxn];

int main()
{
    int begin_address, n, m;
    while(cin>>begin_address>>n>>m)
    {
        int data, address, next_address;
        for(int i = 0; i < n; i++)
        {
            cin>>address>>data>>next_address;
            a[address].address = address;
            a[address].data = data;
            a[address].next_address = next_address;
        }

        int j = 0;
        for(int i = begin_address; i != -1; i = a[i].next_address)
            b[j++] = &a[i];

        for(int i = 0; i <= j - m; i += m)
            reverse(b + i, b + i + m);

        for(int i = 0; i < j; i++)
        {
            if(i != j - 1)
                printf("%05d %d %05d\n", b[i]->address, b[i]->data, b[i + 1]->address);
            else
                printf("%05d %d -1\n", b[i]->address, b[i]->data);
        }

    }
    return 0;
}

1026 程序运行时间

这道题不难，需要注意的一点是差值/100不足1需要四舍五入，也就是后两位数和50相比较判断是否+1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <cstdio>
#include <iostream>
using namespace std;

int main()
{
    int a, b;
    while(cin>>a>>b)
    {
        int c = b - a;
        if(c % 100 >= 50)
            c = c / 100 + 1;
        else
            c = c / 100;
        printf("%02d:%02d:%02d\n", c / 3600, c % 3600 / 60, c % 60);
    }
    return 0;
}

1027 打印沙漏

这道题应该是去年天梯赛的第二题，也算是初学者要写的题目，也就不知道我这个代码像不像初学者，嘿嘿…

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
#include <iostream>
using namespace std;

int main()
{
    int a;
    char c;
    while(cin>>a>>c)
    {
        int n, sum = 0;
        for(n = 1; ; n += 2)
        {
            n == 1 ? sum += n : sum += n*2;
            if(sum > a)
            {
                sum -= n*2;
                n -= 2;
                break;
            }
        }

        int z = 0;
        for(int i = n; i >= 1; i -= 2)
        {
            for(int j = 1; j <= z; j++)
                cout<<" ";
            z++;

            for(int k = 1; k <= i; k++)
                cout<<c;
            cout<<endl;
        }

        z--;
        for(int i = 3; i <= n; i += 2)
        {
            z--;
            for(int j = 1; j <= z; j++)
                cout<<" ";

            for(int k = 1; k <= i; k++)
                cout<<c;
            cout<<endl;
        }
        cout<<(a - sum)<<endl;
    }
    return 0;
}

1028 人口普查

某城镇进行人口普查，得到了全体居民的生日。现请你写个程序，找出镇上最年长和最年轻的人。

这里确保每个输入的日期都是合法的，但不一定是合理的——假设已知镇上没有超过 200 岁的老人，而今天是 2014 年 9 月 6 日，所以超过 200 岁的生日和未出生的生日都是不合理的，应该被过滤掉。

我想问谁活了200年…此题不是太难，思路参考了一个CSDN博主，也就是年月日用一个数来表示，之后的判断什么的都很简单。

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
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;

const int maxn = 100005;
struct node {
    char name[10];
    int yy, mm, dd;
}temp, temp_max, temp_min;

int main()
{
    int n;
    while(cin>>n)
    {
        long long max_yyr = 18140906, min_yyr = 20140906;
        long long temp_min_yyr = max_yyr, temp_max_yyr = min_yyr;
        int x = 0, max_i = 0, min_i = 0;

        for(int i = 0; i < n; i++)
        {
            scanf("%s %d/%d/%d", temp.name, &temp.yy, &temp.mm, &temp.dd);
            long long sum = temp.yy*10000 + temp.mm*100 + temp.dd;

            if(sum >= max_yyr && sum <= min_yyr)
            {
                x++;
                if(sum < temp_max_yyr)
                {
                    temp_max_yyr = sum;
                    strcpy(temp_max.name, temp.name);
                }

                if(sum > temp_min_yyr)
                {
                    temp_min_yyr = sum;
                    strcpy(temp_min.name, temp.name);
                }
            }
        }

        if(x != 0)
            cout<<x<<" "<<temp_max.name<<" "<<temp_min.name<<endl;
        else
            cout<<x<<endl;
    }
    return 0;
}

1029 旧键盘

旧键盘上坏了几个键，于是在敲一段文字的时候，对应的字符就不会出现。现在给出应该输入的一段文字、以及实际被输入的文字，请你列出肯定坏掉的那些键。

先把两个字符串所有的小写字母转化成大写字母，分别用两个数组统计输入的两个字符串出现的字符，最后比较两个统计数组，输出差异字符。

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
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;

void to_big(char str[], int n)
{
    for(int i = 0; i < n; i++)
        if(str[i] >= 'a' && str[i] <= 'z')
            str[i] = str[i] - 'a' + 'A';
}

int main()
{
    char a[100], b[100], vis_a[100], vis_b[100];
    while(cin>>a>>b)
    {
        int len_a = strlen(a);
        int len_b = strlen(b);
        int k_a = 0, k_b = 0;

        to_big(a, len_a);
        to_big(b, len_b);

        for(int i = 0; i < len_a; i++)
        {
            bool flag = true;
            for(int j = 0; j < k_a; j++)
            {
                if(a[i] == vis_a[j])
                {
                    flag = false;
                    break;
                }
            }
            if(flag)
                vis_a[k_a++] = a[i];
        }

        for(int i = 0; i < len_b; i++)
        {
            bool flag = true;
            for(int j = 0; j < k_b; j++)
            {
                if(b[i] == vis_b[j])
                {
                    flag = false;
                    break;
                }
            }
            if(flag)
                vis_b[k_b++] = b[i];
        }

        for(int i = 0; i < k_a; i++)
        {
            bool flag = true;
            for(int j = 0; j < k_b; j++)
            {
                if(vis_b[j] == vis_a[i])
                {
                    flag = false;
                    break;
                }
            }

            if(flag)
                cout<<vis_a[i];
        }
    }
    return 0;
}

1030 完美数列

这道题的所谓完美数列就是数列中的最大值小于或等于最小值乘一个常数。
输入数组之后排序，统计数组中每一个数作为最大数的时候出现完美数列的数列个数。

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
#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
    int n, p;
    while(cin>>n>>p)
    {
        int a[100005];
        for(int i = 0; i < n; i++)
            cin>>a[i];

        sort(a, a + n);

        int i = 0, j = 0, ans = 0;
        while(i < n && j < n)
        {
            while(j < n && a[j] <= (long long)a[i]*p)   //a[i]*p会溢出
                j++;
            ans = max(ans, j - i);
            i++;
        }

        cout<<ans<<endl;
    }
    return 0;
}

1031 查验身份证

一个合法的身份证号码由17位地区、日期编号和顺序编号加1位校验码组成。校验码的计算规则如下：

首先对前17位数字加权求和，权重分配为{7，9，10，5，8，4，2，1，6，3，7，9，10，5，8，4，2}
然后将计算的和对11取模得到值Z；最后按照以下关系对应Z值与校验码M的值：

1
2
Z：0 1 2 3 4 5 6 7 8 9 10
M：1 0 X 9 8 7 6 5 4 3 2

现在给定一些身份证号码，请你验证校验码的有效性，并输出有问题的号码。

此题简单，输出’X’不是在最后一个以及Z值和校验码M不匹配的例子就好了。

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
#include <iostream>
#include <cstring>
using namespace std;

bool check(string s) {
    int i= -1, len = s.length();
    while(i++ < len - 2) {
        if(s[i] < '0' || s[i] > '9')
            return false;
    }
    return true;
}

int sum_id(string s) {
    int quan[18] = {7, 9, 10, 5, 8, 4, 2, 1, 6, 3, 7, 9, 10, 5, 8, 4, 2};
    int sum = 0, len = s.length();
    for(int i = 0; i < len; i++)
        sum += (s[i] - '0') * quan[i];
    return sum % 11;
}

int main() {
    int n;
    while(cin >> n) {
        string id[105];
        for(int i = 0; i < n; i++)
            cin >> id[i];

        int z[12] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        int m[12] = {1, 0, 24, 9, 8, 7, 6, 5, 4, 3, 2};

        int x = 0;
        for(int i = 0; i < n; i++) {
            int nm, nz = sum_id(id[i]);
            if(id[i][34] == 'X')
                nm = 24;
            else
                nm = id[i][35] - '0';
            
            for(int j = 0; j < 11; j++) {
                if(nz == z[j] && nm != m[j] || !check(id[i]))
                {
                    cout << id[i] << endl;
                    x++;
                    break;
                }
            }
        }

        if(x == 0)
            cout << "All passed" << endl;
    }
    return 0;
}

1032 挖掘机技术哪家强

输入的时候求和然后迭代找出和的最大值即可

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 <iostream>
#include <cstring>
using namespace std;

int main()
{
    int n;
    while(cin >> n)
    {
        int school[100005], id, score, max_id = 0;
        memset(school, 0, sizeof school);
        for(int i = 0; i < n; i++)
        {
            cin >> id >> score;
            school[id] += score;
            max_id = max_id > id ? max_id : id;
        }

        int max_sum = 0, max_sum_id = 0;
        for(int i = 1; i <= max_id; i++)
        {
            if(max_sum < school[i])
            {
                max_sum = school[i];
                max_sum_id = i;
            }
        }
        cout<< max_sum_id << " " << max_sum << endl;
    }
    return 0;
}

1033 旧键盘打字

旧键盘上坏了几个键，于是在敲一段文字的时候，对应的字符就不会出现。现在给出应该输入的一段文字、以及坏掉的那些键，打出的结果文字会是怎样？

我的写法是直接数组和tag统计坏的按键，然后迭代输出第二个字符串没有坏的字符即可，非常low的写法，不过就是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
54
55
56
#include <iostream>
#include <cstring>
using namespace std;

int main()
{
    string a, b;
    getline(cin, a);
    cin >> b;

    bool number[10], english[27];
    memset(number, 1, sizeof number);
    memset(english, 1, sizeof english);

    bool tag1, tag2, tag3, tag4, tag5;
    tag1 = tag2 = tag3 = tag4 = tag5 = true;
    
    for(int i = 0; i < a.size(); i++)
    {
        if(a[i] >= 'A' && a[i] <= 'Z')
            english[a[i] - 'A' + 1] = false;
        else if(a[i] >= '0' && a[i] <= '9')
            number[a[i] - '0'] = false;
        else if(a[i] == '_')
            tag1 = false;
        else if(a[i] == ',')
            tag2 = false;
        else if(a[i] == '.')
            tag3 = false;
        else if(a[i] == '-')
            tag4 = false;
        else if(a[i] == '+')
            tag5 = false;
    }

    for(int i = 0; i < b.size(); i++)
    {
        if(b[i] >= 'a' && b[i] <= 'z' && english[b[i] - 'a' + 1])
            cout << b[i];
        else if(b[i] >= 'A' && b[i] <= 'Z' && english[b[i] - 'A' + 1] && tag5)
            cout << b[i];
        else if(b[i] >= '0' && b[i] <= '9' && number[b[i] - '0'])
            cout << b[i];
        else if(b[i] == '_' && tag1)
            cout << b[i];
        else if(b[i] == ',' && tag2)
            cout << b[i];
        else if(b[i] == '.' && tag3)
            cout << b[i];
        else if(b[i] == '-' && tag4)
            cout << b[i];
        else if(b[i] == '+' && tag5)
            cout << b[i];
    }
    return 0;
}

1035 插入与归并

这题本来应该是考察这两个算法，但是我的归并排序好像有点不一样，所以归并排序是用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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 300005;

int n;
int a[105], b[105];

void insert_sort(int n)
{
    bool flag = false;
    for(int i = 1; i < n; i++) {
        if(a[i] < a[i - 1]) {
            int j = i - 1;
            int x = a[i];

            while(j >= 0 && x < a[j]) {
                a[j + 1] = a[j];
                j--;
            }
            a[j + 1] = x;
        }

        if (flag == true) {
            cout << "Insertion Sort" << endl;
            for(int i = 0; i < n; i++) {
                if(i == n - 1)
                    cout << a[i] << endl;
                else
                    cout << a[i] << " ";
            }
            return;
        }

        if (equal(a, a + n, b)) {
            flag = true; 
        }
    }
}
    
void merge_sort(int left, int right) {
    int key = 0;
	for (int i = 2; ; i *= 2) {
		for (int j = 0; j < n; j += i) {
			sort(a + j, a + (j + i < n ? j + i : n));
		}
		if (key) {
			cout << "Merge Sort" << endl;
			for (int j = 0; j < n; j++) {
                if(j == n - 1)
                    cout << a[j] << endl;
                else
                    cout << a[j] << " ";
            }
			return;
		}
		if (equal(a, a + n, b))
			key = 1;
		if (i > n)
			break;
 
	}
}

int main()
{
    while(cin >> n) {

        for(int i = 0; i < n; i++) {
            cin >> a[i];
        }
        for(int i = 0; i < n; i++) {
            cin >> b[i];
        }
        int c[105];
        for(int i = 0; i < n; i++) {
            c[i] = a[i];
        }

        insert_sort(n);
        for(int i = 0; i < n; i++) {
            a[i] = c[i];
        }
        merge_sort(0, n - 1);
    }
    return 0;
}

1036 跟奥巴马一起编程

很简单的一个题目，列是行数的一半且取四舍五入，两个for循环就好了，第一行和最后一行输出n个a字符，其他行输出a空格a

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
#include <iostream>
using namespace std;

int main() {
    int n;
    char c;
    while(cin >> n >> c) {
        double m = (double)n / 2 + 0.5;
        for(int i = 1; i <= (int)m; i++) {
            if(i == 1 || i == (int)m) {
                for(int i = 1; i <= n; i++) {
                    cout << c;
                }
                cout << endl;
            }
            else {
                for(int i = 1; i <= n; i++) {
                    if(i == 1 || i == n)
                        cout << c;
                    else
                        cout << " ";
                }
                cout << endl;
            }
        }
    }

}

1037 在霍格沃茨找零钱

没啥好说的，我不明白为什么这道题有20分…

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

int main() {
    int g1, s1, k1;
    scanf("%d.%d.%d", &g1, &s1, &k1);
    int sum1 = g1*17*29 + s1*29 + k1;

    int g2, s2, k2;
    scanf("%d.%d.%d", &g2, &s2, &k2);
    int sum2 = g2*17*29 + s2*29 + k2;

    int cha = sum2 - sum1;
    if(cha >= 0)
        printf("%d.%d.%d", cha / 17 / 29, cha / 29 % 17, cha % 29);
    else {
        cha = -cha;
        printf("-%d.%d.%d", cha / 17 / 29, cha / 29 % 17, cha % 29);
    }
    return 0;
}

1038 统计同成绩学生

每次输入一个成绩就把这个成绩的次数加一，然后输出就完事了

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 <iostream>
using namespace std;

int main() {
    int n;
    while (cin >> n) {

        int a[100005], b[100005] = {0};
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
            b[a[i]] ++;
        }

        int k, x, sum;
        cin >> k;

        for (int i = 1; i <= k; i++) {
            cin >> x;
            if(i == k)
                cout << b[x] << endl;
            else
                cout << b[x] << " ";
        }
    }
    return 0;
}

1039 到底买不买

日常暴力求解，判断b字符串出现的字符在a字符串有没有出现，出现了b字符串的大小n减1，同时标记a字符访问了。最后如果N是零的话就输出剩余的，不为0就输出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
#include <iostream>
#include <cstring>
using namespace std;

int main() {
    string a, b;
    while (cin >> a >> b) {
        int n = b.size();
        int m = a.size();
        bool vis[1005];
        memset(vis, 0, sizeof vis);
        for(int i = 0; i < b.size(); i++) {
            for(int j = 0; j < a.size(); j++) {
                if(b[i] == a[j] && vis[j] == false) {
                    n--;
                    vis[j] = true;
                    break;
                }
            }
        }
        if(n == 0)
            cout << "Yes " << m - b.size() << endl;
        else
            cout << "No " << n << endl;
    }
    return 0;
}

1040 有几个PAT

这道题让我想起了最起初校赛的时候，没做出来，今天还是没有做出来，我直接三个循环肯定是超时的，再我去看了其他人的题解之后感觉恍然大悟，但是又感觉这东西太难想到了，具体的操作见代码的注释

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
#include <iostream>
#include <cstring>
using namespace std;

int main() {
    string a;
    while (cin >> a) {
        int i = a.size();
        int numT = 0, numAT = 0, numPAT = 0;
        while (i --) {
            if (a[i] == 'T')
                numT ++;
            else if (a[i] == 'A')
                numAT += numT;
            else
                numPAT += numAT;
            if (numPAT > 1000000007)
                numPAT %= 1000000007;
        }
        cout << numPAT << endl;
    }
    return 0;
}

/*
    栗子:
    PATTATAATT
    0123456789

    i = 9: numT ++;         numT = 1
    i = 8: numT ++;         numT = 2
    i = 7: numAT += numT;   numAT = 2
    i = 6: numAT += numT;   numAT = 4
    1.'AT'序列数目增加到了4种

    i = 5: numT ++;         numT = 3
    i = 4: numAT += numT;   numAT = 7
    2.'AT'序列数目增加到了7种

    i = 3: numT++;          numT = 4
    i = 2: numT++;          numT = 5
    3.'AT'序列数目增加到了12种
    i = 1: numAT += numT;   numAT = 12
    i = 0: numPAT += numAT; numPAT = 12
    这是特例,只有一个'P'在最前面,只有一个'P'来整合'AT’序列,总计12种'PAT'
*/