Intro

PTA基础编程题目集好歹算是写完了，买了紫书，多多少少算是休息了三四天吧，现在也该重新开始新的旅程(受虐😤)了。
PTA基础编程题目集因为按照PTA网站的格式，在Blog中给出了题目的内容、输入输出样例、要求等信息，嗯，写的十分详细(水文)，洋洋洒洒的好几万字呢(凑字数)，哈哈。
说到底是自己整理的累，别人看的也累。
所以，在本篇Blog中就不在给出其他信息了，只给出代码和分析吧。
题目信息，请点击：PAT (Basic Level) Practice。不过，想来各位看官应该也只有在看到题目摸头、挠头的时候，才会来看这里的内容吧，这也就更加没有显示题目信息的必要了。
嗯，就按照这样的想法来做吧。

话说，在Basic Level内好像只有编程题哦。

Classification

这部分内容是自己做完题目之后，回过头再来看这些题目时做的，所以也算是总结性的内容，建议刷题的时候，一次性将一个类型的题目全部做完。

模拟

题号	名称	分值	备注
1001	害死人不偿命的(3n+1)猜想	15	-
1008	数组元素循环右移问题	20	-
1011	A+B 和 C	15	-
1012	数字分类	20	-
1016	部分A+B	15	-
1018	锤子剪刀布	20	-
1019	数字黑洞	20	-
1026	程序运行时间	15	四舍五入
1031	查验身份证	15	-
1035	插入与归并	25	-
1045	快速排序	25	-
1046	划拳	15	-
1053	住房空置率	20	-
1055	集体照	25	-
1061	判断题	15	-
1066	图像过滤	15	-
1067	试密码	20	-
1068	万绿丛中一点红	20	-
1069	微博转发抽奖	20	-
1071	小赌怡情	15	-
1077	互评成绩计算	20	四舍五入
1086	就不告诉你	15	-
1089	狼人杀-简单版	20	-
1091	N-自守数	15	-
1096	大美数	15	求因数
1097	矩阵行平移	20	-
1101	B是A的多少倍	15	-
1103	缘分数	20	-
1106	2019数列	15	-

字符串处理

题号	名称	分值	备注
1002	写出这个数	20	-
1006	换个格式输出整数	15	-
1009	说反话	20	-
1014	福尔摩斯的约会	20	-
1021	个位数统计	15	-
1024	科学计数法	20	-
1048	数字加密	20	-
1052	卖个萌	20	-
1054	求平均值	20	sscanf
1057	数零壹	20	2 进制转换
1058	选择题	20	1073
1073	多选题常见计分法	20	1058
1076	Wifi密码	15	-
1078	字符串压缩与解压	20	-
1081	检查密码	15	-
1084	外观数列	20	-
1093	字符串A+B	20	字符串的并集
1094	谷歌的招聘	20	素数判断
1109	擅长C	20	-

数学

题号	名称	分值	备注
1003	我要通过！	20	找规律
1007	素数对猜想	20	素数
1010	一元多项式求导	25	求导
1013	数素数	20	素数
1017	A除以B	20	大数除法
1034	有理数四则运算	20	分数运算
1040	有几个PAT	25	找规律
1049	数列的片段和	20	注意误差
1051	复数乘法	15	注意误差
1056	组合数的和	15	模拟也可以
1060	爱丁顿数	25	-
1062	最简分数	20	分数运算
1063	计算谱半径	20	复数求模
1079	延迟的回文数	20	大数加法、回文数判断
1082	射击比赛	20	点的距离公式、查找最值
1088	三人行	20	多元方程求可能解
1099	性感素数	20	素数
1104	天长地久	20	素数、最大公约数、排序

查找

题号	名称	分值	备注
1004	成绩排名	20	-
1028	人口普查	20	string
1030	完美数列	25	binary search or two pointer
1032	挖掘机技术哪家强	20	-
1041	考试座位号	20	-
1059	C语言竞赛	20	-
1065	单身狗	25	set & map
1072	开学寄语	20	-
1090	危险品装箱	set	-
1092	最好吃的月饼	20	find max
1100	校庆	25	find & sort
1102	教超冠军卷	20	find max
1107	老鼠爱大米	20	find max

散列

题号	名称	分值	备注
1005	继续(3n+1)猜想	25	-
1029	旧键盘	20	string
1033	旧键盘打字	20	string
1038	统计同成绩学生	20	-
1039	到底买不买	20	-
1042	字符统计	20	-
1043	输出PATest	20	-
1047	编程团体赛	20	查找最大值
1064	朋友数	20	-
1083	是否存在相等的差	20	-
1087	有多少不同的值	20	数学
1108	String复读机	20	-

排序

题号	名称	分值	备注
1015	德才论	25	-
1080	MOOC期终成绩	25	注意计算
1085	PAT单位排行	25	-
1095	解码PAT准考证	25	-

贪心

题号	名称	分值	备注
1020	月饼	25	-
1023	组个最小数	20	-
1070	结绳	25	排名的处理
1098	岩洞施工	20	-

进制转换

题号	名称	分值	备注
1022	D进制的A+B	20	-
1037	在霍格沃茨找零钱	20	-
1044	火星数字	20	map
1074	宇宙无敌加法器	20	字符串处理

链表

题号	名称	分值	备注
1025	反转链表	25	-
1075	链表元素分类	25	-
1105	链表合并	25	-
1110	区块反转	25	-

图形输出

题号	名称	分值	备注
1027	打印沙漏	20	-
1036	跟奥巴马一起编程	15	-
1050	螺旋矩阵	25	-

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

Analysis

题目比较简单，按照题目给出的算法去构造计算过程即可，count++其实只在最后写一句就可以了。

Code

#include <iostream>
using namespace std;
int main() {
    int n, count = 0;
    cin >> n;
    while(n != 1) {
        if(n % 2 == 1) n = 3 * n + 1;
        n /= 2;
        count++;
    }
    cout << count;
    return 0;
}

1002 写出这个数

Analysis

这个题目20分呢，不过不难，嘻嘻，就是比较麻烦，看着题目中的话：这里保证$n$小于$10^{100}$，好像看到了出题人“善意”的微笑一样呢(wo zhen xiang da si ni~)。大致思路，先要算出每个数位上数字的总和，然后再将结果进行数位拆分输出一位一位的数字就好了。对于输入的数字串，可以用单字符的形式来处理，也可以从字符串的角度去处理，另外注意做数位拆分时的个位数，注意0的拼音是ling不是lin。

继续分析一下题目条件，“保证$n$小于$10^{100}$这个条件好像还有点猫腻？小于$10^{100}$那能取到的最大的数不就是$10^{100} - 1$了？而且这个数的每一位都是 9，总共 99 位，也就是说，最后得到的各位数字之和肯定不会大于$9 \times 100 = 900$，最多也不会超过三位数了，这是个好消息！明确了这点后，数位拆分的过程就简单了；另外，需要输出的字符串，可以单独放在二维数组内，利用能到的数位代替下标，来输出就很方便了！

Code

version 1

按照上述的两种思路得到的 AC 分别代码如下：

#include <cstdio>

int main(int argc, char const *argv[]) {
    char c;
    int num, sum=0;
    while((c=getchar()) != '\n') {
        if('0' <= c && c <= '9') {
            num = c - '0';
            sum+=num;
        } else continue;
    }
    /* method 1: 
	int digit, temp=sum, mask=1;
	while(temp > 9) {
		temp/=10;
		mask*=10;
	}
	temp=sum;
	do {
		digit = temp / mask;
		temp %= mask;
		mask /= 10;
		switch(digit) {
			case 0:printf("ling");break;
			case 1:printf("yi");break;
			case 2:printf("er");break;
			case 3:printf("san");break;
			case 4:printf("si");break;
			case 5:printf("wu");break;
			case 6:printf("liu");break;
			case 7:printf("qi");break;
			case 8:printf("ba");break;
			case 9:printf("jiu");break;
		}
		if(mask == 0) printf("\n");
		else printf(" ");
	} while(mask > 0);
	*/ 
    /*method 2:*/
    char num2chi[][6] = {"ling", "yi", "er", "san", "si",
     "wu", "liu", "qi", "ba", "jiu"};
    int unit, tens, hundred;
    unit = sum % 10;
    tens = sum / 10 % 10;
    hundred = sum / 100;
    if(sum > 100) printf("%s %s %s\n", num2chi[hundred], num2chi[tens], num2chi[unit]);
    else if (10 < sum && sum < 100) printf("%s %s\n", num2chi[tens], num2chi[unit]);
    else printf("%s\n", num2chi[unit]);
    return 0;
}

version 2

这个题还可以借助 C++ 自带的一些工具函数。

#include <iostream>
using namespace std;

int main() {
    string s;
    cin >> s;
    int sum = 0;
    string num[10] = {"ling", "yi", "er", "san", "si", "wu", "liu", "qi", "ba", "jiu"};
    for(int i = 0; i < s.length(); i++) {
        sum += (s[i] - '0');
    }
    s = to_string(sum);
    for(int i = 0; i < s.length(); i++) {
        if(i != 0) cout << ' ';
        cout << num[s[i] - '0'];
    }
    return 0;
}

1003 我要通过！

Analysis

这个题目是真的坑，光是理解题意就得花不少时间，第一眼看到条件 3 估计会把人给弄懵逼。
但实际上，这个题目其实算是个找规律的题目，先理解一下这 3 个条件：

条件 1 很直接
xPATx这类字符串都是答案正确
aPbTc正确，那么aPbATca也是正确的。就样例而言，AAPATAA是正确的，原因是符合xPATx；而AAPAATAAAA正确是因为AAPATAA正确且也符合aPbATca，此时有a = AA, b = A, c = AA。同理，APAAATAA中a = A, b = AA, c = A，那么aPbTc就是APAATA，这个字符串是不符合xPATx的，所以错误。

理解题意之后，就可以进一步找规律了。首先，可以发现xPATx是所有正确答案的根源，因为它可以通过变换成为其他字符串。假设 x 是 P 左边的 A 的个数， y 是 P 和 T 中间 A 的个数，z 是 T 右边 A 的个数。那么，可以得到以下规律：

P 和 T 的个数一定是 1，A 的个数不定，但其他字符个数一定是 0
y >= 1
为了确保aPbTca经过变换后符合xPATx，b每次只能增加 1 个 A，也即，y 每次只能增加 1，c中 A 的个数则一定是 x 的倍数。同样地，不管如何变换，x 是不变的，每次 y 增加 1，就会让 z 增加 x（可以结合上面条件 3 中的例子分析）。按照这样的规律，可以利用循环判断当y = 1时，z 和 x 是否相等来确定答案是否正确。若以aPbATca为模板，可以得到z = x + x * (y - 1)这个一般性的式子，这样就可以省去循环。

发现这些规律后，这个题目基本上就清晰了。

Code

#include <cstdio>
#include <cstring>

int main(int argc, char const *argv[]) {
    int n;
    scanf("%d", &n);
    while(n--) {
        char str[105];
        scanf("%s", str);
        int len = strlen(str);
        int num_p = 0, num_t = 0, other = 0;
        int pos_p = -1, pos_t = -1;
        for(int i = 0; i < len; i++) {
            if(str[i] == 'P') {
                num_p++;
                pos_p = i;
            } else if(str[i] == 'T') {
                num_t++;
                pos_t = i;
            } else if(str[i] != 'A') other++;
        }
        if(num_p != 1 || num_t != 1 || other != 0 || pos_t - pos_p <= 1) {
            printf("NO\n");
            continue;
        }
        int x = pos_p, y = pos_t - pos_p - 1, z = len - pos_t - 1;
        if(z - x * (y - 1) == x) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

1004 成绩排名

Analysis

这道题比较简单，算是查找吧，定义好结构体进行处理就好，注意最大、最小值得分开判断，而不是只用if-else就完事大吉。

Code

#include <stdio.h>

typedef struct Stu {
    char name[12];
    char number[12];
    int grade;
} students;

int main(int argc, char const *argv[]) {
    int n;
    scanf("%d", &n);
    int i=0;
    students stu, max, min;
    scanf("%s %s %d", stu.name, stu.number, &stu.grade);
    max = min = stu;
    for(i=1; i<n; i++) {
        scanf("%s %s %d", stu.name, stu.number, &stu.grade);
        /*online processing, find the minimum and maximum when inputing. */ 
        if(stu.grade < min.grade) min = stu;
        if(stu.grade > max.grade) max = stu;
    } 
    printf("%s %s\n%s %s\n", max.name, max.number, min.name, min.number);
    return 0;
}

1005 继续(3n+1)猜想

Analysis

按照1001的思路，对输入的每个数进行模拟，开辟一个bool数组来记录某个数字是否出现，出现则将下标为其值的bool量置为true，由于每个数在模拟中可能会出现不同的数字，最好还是每个数字都模拟一下。另外，由于最后需要从小到大输出，所以将输入数字序列按从大到小排序后，在进行输出。
特别要注意，数组的大小一定要开到 10000，可能出现的最大数是会超过 1000 的，不然测试点 4 会出现溢出的错误。

Code

#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN = 10000 + 10;

int main(int argc, char const *argv[]) {
    int K, Num[105] = {0}, temp;
    bool times[MAXN] = {false};
    scanf("%d", &K);
    for(int i = 0; i < K; i++) {
        scanf("%d", &Num[i]);
        temp = Num[i];
        while(temp != 1) {
            if(temp % 2 == 1) {
                temp = 3 * temp + 1;
            }
            temp /= 2;
            times[temp] = true;
        }
    }
    sort(Num, Num + K);
    bool flag = true;
    for(int i = K - 1; i >= 0; i--) {
        if(!times[Num[i]]) {
            if(flag) {
                printf("%d", Num[i]);
                flag = false;
            } else {
                printf(" %d", Num[i]);
            }
        }
    }
    return 0;
}

1006 换个格式输出整数

Analysis

水题一道，题目已经说了~~给一个不超过3位的正整数~~ n < 1000，做好数位拆分后，挨个输出即可。

Code

#include <stdio.h>

int main(int argc, char const *argv[]) {
    int i, num, unit, tens, hundred;
    scanf("%d", &num);
    unit = num % 10;
    tens = num / 10 % 10;
    hundred = num / 100;
    for(i=0; i<hundred; i++) {
        printf("B");
    }
    for(i=0; i<tens; i++) {
        printf("S");
    }
    for(i=1; i<=unit; i++) {
        printf("%d", i);
    }
    printf("\n");
    return 0;
}

1007 素数对猜想

Analysis

这道题要稍微理解一下题目意思，乍一看，可能会没明白题目的意思。关键的条件：存在无穷多对相邻且差为2的素数，也即是说，对于题目给定的$N = 20$而言，在$2 - 20$之间，必然存在相邻且差为2的素数对！而题目的问题是：计算不超过$N$的满足猜想的素数对的个数，那么直接进行计算就好了。至于如何判断素数，这就是老生常谈的问题了，方法很多。

这个题目没有超时的测试点，不用想的太复杂。

Code

#include <stdio.h>
#include <math.h>
typedef enum{ false, true} bool;

bool IsPrime(int n);

int main(int argc, char const *argv[]) {
    int i, N, count = 0;
    scanf("%d", &N);
    for(i = 2; i <= N - 2; i++) {
        if(IsPrime(i) && IsPrime(i + 2)) {
            count++;
        }
    }
    printf("%d\n", count);
    return 0;
}

bool IsPrime(int n) {
    bool flag = true;
    if(n <= 1 || n % 2 == 0) {
        flag = false;
    } else {
        int i;
        for(i = 3; i <= (int)sqrt(n); i+=2) {
            if(n % i == 0) {
                flag = false;
                break;
            }
        }
    } 
    return flag;
}

1008 数组元素循环右移问题

Analysis

本题的解答方法较多，首先需要对移动次数$M$进行处理，分别对应两种情况，$M >= N$和$M < N$，使用取余运算即可。
下面介绍一下各种方法：

不移动，先输出指定位置，再输出余下位置即可
利用队列，移动的过程正好对应队列出一次队，再入一次队
采用~~移位算法~~reverse 函数，大致过程（以样例为例）：

n = 6, m = 2, move 3 turns
-> 1 2 3 4 5 6 - start
-> 6 5 4 3 2 1
-> 5 6 4 3 2 1
-> 5 6 1 2 3 4 - end

~~移位算法~~reverse 函数的大致代码：

void reverse(int *array, int start, int end) {
    for(int i = start; i <= (start + end) / 2; i++) {
        int temp = array[i];
        array[i] = array[start + end - i];
        array[start + end - i] = temp;
    }
}

Code

direct output

#include <iostream>
using namespace std;
const int maxn = 110;
int main() {
    int n, m, a[maxn];
    cin >> n >> m;
    for(int i = 0; i < n; i++) {
        cin >> a[i];
    }
    m %= n;
    for(int i = n - m; i < n; i++) {
        cout << a[i] << ' ';
    }
    for(int i = 0; i < n - m; i++) {
        cout << a[i];
        if(i != n - m - 1) cout << ' ';
    }
    return 0;
}

use queue

#include <iostream>
#include <queue>
using namespace std;

int main() {
    queue<int> q;
    int n, m, temp;
    cin >> n >> m;
    m %= n;
    for(int i = 0; i < n; i++) {
        cin >> temp;
        q.push(temp);
    }
    for(int i = 0; i < n - m; i++) {
        temp = q.front();
        q.pop();
        q.push(temp);
    }
    while(!q.empty()) {
        cout << q.front();
        q.pop();
        if(q.size() != 0) cout << ' ';
    }
    return 0;
}

reverse function

#include <iostream>
using namespace std;
const int maxn = 110;
void Reverse(int a[], int start, int end) {
    for(int i = start; i <= (start + end) / 2; i++) {
        int temp = a[i];
        a[i] = a[end + start - i];
        a[end + start - i] = temp;
    }
}
int main() {
    int n, m, a[maxn];
    cin >> n >> m;
    for(int i = 0; i < n; i++) {
        cin >> a[i];
    }
    m %= n;
    Reverse(a, 0, n - m - 1);
    Reverse(a, n - m, n - 1);
    Reverse(a, 0, n - 1);
    for(int i = 0; i < n; i++) {
        cout << a[i];
        if(i != n - 1) cout << ' ';
    }
    return 0;
}

使用 C++ 就不用自己实现 reverse 函数了，这里先逆置前面的元素，再逆置后面的元素，最后整体逆置，具体如下：

#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 110;

int main() {
    int n, m, a[maxn];
    cin >> n >> m;
    for(int i = 0; i < n; i++) {
        cin >> a[i];
    }
    m %= n;
    reverse(a, a + n - m);
    reverse(a + n - m, a + n);
    reverse(a, a + n);
    for(int i = 0; i < n; i++) {
        cout << a[i];
        if(i != n - 1) cout << ' ';
    }
    return 0;
}

1009 说反话

Analysis

这个题如果单纯的处理字符串的话，会比较麻烦。不过若是使用二维数组（字符串数组）就很简单了，利用的是scanf无法读入带空格的字符串的特性。
同理，使用 cin 也可以做到同样的事情，输出的时候实际上是栈的思想。

Code

version 1

#include <stdio.h>

int main(int argc, char const *argv[]) {
    int count = 0;
    char Str[85][85], c;
    while(1) {
        scanf("%s", Str[++count]);
        c = getchar();
        if(c == '\n') {
            break;
        }
    }
    for(; count > 1; count--) {
        printf("%s ", Str[count]);
    }
    puts(Str[count]);
    return 0;
}

version 2

原来没有从字符串的角度来做，现在再来从字符串处理的角度来做一下：

#include <iostream>
using namespace std;

int main() {
    string str, res;
    getline(cin, str);
    for(int i = str.length() - 1; i >= 0; i--) {
        int j = i - 1;
        for(; j > 0; j--) {
            if(str[j] == ' ') break;
        }
        if(j >= 0 && str[j] == ' ') res += str.substr(j + 1, i - j) + ' ';
        else res += str.substr(0, i + 1); 
        i = j;
    }
    cout << res;
    return 0;
}

要注意的点就是可能会存在字符串前面有多个空格的情况。

1010 一元多项式求导

Analys

题目大意较为明确，但感觉有些东西没说明白...
注意的地方大致如下：

因为没说输入什么时候结束，所以只能手动使用 Windows 下的Ctrl + Z来结束输入，判题系统建在 Linux 上，应该自动使用的Ctrl + D，这两个操作都表示EOF，所以得使用!= EOF来作为输入结束的标志
常数项求导后为0，需要输出为0 0，这应该是题目最后一个条件的提示了
可能出现指数为负的项，输出顺序是指数递降的，这里用链表就很无脑，因为输入绝对是指数递降的，那么求导完后，也绝对是指数递降的，直接输出即可

这道题也可以用链表来做，求导的过程会复杂一些。

Code

use linked list

#include <stdio.h>
#include <stdlib.h>

typedef struct node* List;
typedef struct node{
    int coef, expo;
    List next;
} Node;

List CreateList(void);
void Derivation(List L);
void Print(List L);

int main(int argc, char const *argv[]) {
    List L = CreateList();
    Derivation(L);
    Print(L);
    return 0;
} 

List CreateList(void) {
    List L = (List)malloc(sizeof(Node)), rear;
    L->next = NULL;
    rear = L;
    int c, e;
    while(scanf("%d %d", &c, &e) != EOF) {
        List temp_node = (List)malloc(sizeof(Node));
        temp_node->next = NULL;
        rear->next = temp_node;
        rear = temp_node;
        temp_node->coef = c;
        temp_node->expo = e;
    }
    return L;
}

void Print(List L) {
    List Temp = L->next;
    int flag = 1;
    while(Temp) {
        if(flag) {
            printf("%d %d", Temp->coef, Temp->expo);
            flag = 0;
        } else {
            if(Temp->coef != 0) {
                printf(" %d %d", Temp->coef, Temp->expo);
            }
        }
        Temp = Temp->next;
    }
    putchar('\n');
}

void Derivation(List L) {
    List p = L->next;
    while(p) {
        if(p->expo) {
            p->coef = p->coef * p->expo;
            p->expo--;
        } else {
            p->coef = 0;
        }
        p = p->next;
    }
}

use array

#include <stdio.h>

int main(int argc, char const *argv[]) {
    int i, items[1005] = {0}, c, e, count = 0;
    while(scanf("%d %d", &c, &e) != EOF) {
        items[e] = c;
    }
    items[0] = 0;
    for(i = 1; i <= 1000; i++) {
        items[i - 1] = items[i] * i;
        items[i] = 0;
        if(items[i - 1] != 0) {
            count++;
        }
    }
    if(count == 0) printf("0 0\n");
    else {
        for(i = 1000; i >= 0; i--) {
            if(items[i]) {
                printf("%d %d", items[i], i);
                count--;
                if(count != 0) {
                    putchar(' ');
                }
            }
        }
        putchar('\n');
    }
    return 0;
}

1011 A+B和C

Analysis

由于题目限定了输入数据范围为$[-2^{31}, 2^{31}]$，本题可以有两种解法：

直接使用long long，避免使用int带来的溢出
依旧使用int，但是需要做溢出处理，包括正溢出和负溢出两种情况

Code

use long long

#include <iostream>
using namespace std;

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

use int

#include <iostream>
using namespace std;

int main() {
    int t, a, b, c;
    cin >> t;
    for(int i = 1; i <= t; i++) {
        cin >> a >> b >> c;
        cout << "Case #" << i << ": ";
        if(a + b < 0 && a > 0 && b > 0) cout << "true"; //positive overflow
        else if(a + b >= 0 && a < 0 && b < 0) cout << "false";   //negative overflow
        else if(a + b > c) cout << "true";	//normal
        else cout << "false";
        cout << endl;
    }
    return 0;
}

1012 数字分类

Analysis

按照题目要求，依次求出所有数字，但在输出的时候要注意，$A_2$的结果可能是 0 ，此时$A_2$是存在的，要输出0，而不是N，类似的有$A_4$。

Code

#include <cstdio>
int main() {
    int n, temp, a[6] = {0}, sign = 1, count = 0, flag = 0;
    scanf("%d", &n);
    while(n--) {
        scanf("%d", &temp);
        int remain = temp % 5;
        if(remain == 0 && temp % 2 == 0) a[1] += temp;
        if(remain == 1) {
            a[2] += sign * temp;
            sign = -sign;
            flag = 1;
        }
        if(remain == 2) a[3]++;
        if(remain == 3) {
            a[4] += temp;
            count++;
        }
        if(remain == 4 && temp > a[5]) {
            a[5] = temp;
        }
    }
    if(a[1]) printf("%d ", a[1]);
    else printf("N ");
    if(flag) printf("%d ", a[2]);
    else printf("N ");
    if(a[3]) printf("%d ", a[3]);
    else printf("N ");
    if(a[4]) printf("%.1lf ", (double)a[4] / count);
    else printf("N ");
    if(a[5]) printf("%d", a[5]);
    else printf("N");
    return 0;
}

1013 数素数

Analysis

素数相关的题目好像已经是老生常谈的题型了，注意不要超时。
关于素数的求法，可以看这里：素数的求法

Code

非筛法

#include <cstdio>
#include <cmath>
#define MAX 15000

bool IsPrime(int number);

int main(int argc, char const *argv[]) {
    int M, N, Prime[MAX];
    scanf("%d %d", &M, &N);
    int i, count = 2;
    Prime[1] = 2;
    for(i = 3; i <= 105000; i++) {
        if( IsPrime(i) ) {
            Prime[count++] = i;
        }
    }
    count = 0;
    for(; M < N; M++) {
        printf("%d", Prime[M]);
        count++;
        if(count % 10 == 0) {
            putchar('\n');
        } else {
            putchar(' ');
        }
    }
    printf("%d\n", Prime[M]);
    return 0;
} 

bool IsPrime(int number) {
    bool flag = true;
    if(number <= 1 || number % 2 == 0) {
        flag = false;
    } else {
        int i;
        for(i = 3; i <= (int)sqrt(number); i+=2) {
            if(number % i == 0) {
                flag = false;
                break;
            }
        }
    }
    return flag;
}

筛法

#include <cstdio>
const int MAXN = 1000001;
int prime[MAXN], pNum = 0;
bool p[MAXN] = {false};

void filterPrime(int n) {
    for(int i = 2; i < MAXN; i++) {
        if(p[i] == false) {
            prime[pNum++] = i;
            if(pNum >= n) break;
            for(int j = i + i; j < MAXN; j += i) {
                p[j] = true;
            }
        }
    }
}

int main(int argc, char const *argv[]) {
    int m, n, count = 0;
    scanf("%d %d", &m, &n);
    filterPrime(n);
    for(int i = m; i <= n; i++) {
        printf("%d", prime[i - 1]);
        count++;
        if(count % 10 != 0 && i < n) putchar(' ');
        else putchar('\n');
    }
    return 0;
}

1014 福尔摩斯的约会

Analysis

这个题目的细节处理，真是...太太太麻烦啦~
大致分析一下：

字符相同的时候才能判断是否输出
星期判断必须是大写字母，且必须属于 $[A, G]$ 这个范围内（测试点4），用取余不是更好么？
时间单位需要用0来补全2位

特别要注意的就这些，其他的再仔细读读题目就OK了~

Code

#include <cstdio>
#include <cstring>
#include <cctype>

char Week[7][5] = {
    "MON", "TUE", "WED", "THU", "FRI", "SAT", "SUN",
};

int Hours[31] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
0, 0, 0, 0, 0, 0, 0,
10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23};

int main(int argc, char const *argv[]) {
    char Str[5][65];
    scanf("%s\n%s\n%s\n%s", Str[1], Str[2], Str[3], Str[4]);
    int i, len1 = strlen(Str[1]), len2 = strlen(Str[2]), flag = 0, j;
    for(i = 0; ; i++) {
        if(!flag && Str[1][i] == Str[2][i] && ('A' <= Str[1][i] && Str[1][i] <= 'G')) {
            printf("%s ", Week[Str[1][i] - 'A']);
            flag = 1;
            continue;
        }
        if(flag && Str[1][i] == Str[2][i] && \
         (isdigit(Str[1][i]) || ('A' <= Str[1][i] && Str[1][i] <= 'N')) ) {
            printf("%02d:", Hours[Str[1][i] - '0']);
            break;
        }
    }
    len1 = strlen(Str[3]), len2 = strlen(Str[4]);
    for(j = 0; ; j++) {
        if(Str[3][j] == Str[4][j] && isalpha(Str[3][j])) {
            printf("%02d\n", j);
            break;
        }
    }
    return 0;
}

1015 德才论

Analysis

这道题一开始做的时候还想了挺久的，而且还没想出来，下面来分析一下。

使用库函数sort来完成排序的基本操作就不说了，大概得注意两个点：

总分需要计算出来作为排序的依据，这个是题目明确说明的
题目给的考生种类很多，为了排序方便可以给这些考生分类，数字越大等级越低（或反之）

能注意到这两个点，题目基本就可以完成了。所以，以后在遇到类似的题目，就提前分好类吧。

Code

#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN = 100000 + 5;
struct student{
    int id, scoreD, scoreC, sumCD, flag;
} stu[MAXN];
bool cmp(student a, student b) {
    if(a.flag != b.flag) return a.flag < b.flag;
    else if(a.sumCD != b.sumCD) return a.sumCD > b.sumCD;
    else if(a.scoreD != b.scoreD) return a.scoreD > b.scoreD;
    else return a.id < b.id;
}
int N, L, H, M = 0;

int main(int argc, char const *argv[]) {
    scanf("%d %d %d", &N, &L, &H);
    for(int i = 0; i < N; i++) {
        scanf("%d %d %d", &stu[i].id, &stu[i].scoreD, &stu[i].scoreC);
        stu[i].sumCD = stu[i].scoreC + stu[i].scoreD;
        if(stu[i].scoreD >= L && stu[i].scoreC >= L) {
            M++;
            if(stu[i].scoreD >= H && stu[i].scoreC >= H) {
                stu[i].flag = 1;
            } else if(stu[i].scoreD >= H && stu[i].scoreC < H) {
                stu[i].flag = 2;
            } else if(stu[i].scoreD < H && stu[i].scoreD < H && stu[i].scoreD >= stu[i].scoreC) {
                stu[i].flag = 3;
            } else stu[i].flag = 4;
        } else {
            stu[i].flag = 5;
        }
    }
    sort(stu, stu + N, cmp);
    printf("%d\n", M);
    for(int i = 0; i < M; i++) {
        printf("%d %d %d\n", stu[i].id, stu[i].scoreD, stu[i].scoreC);
    }
    return 0;
}

1016 部分A+B

Analysis

根据题目的要求进行计算即可，从字符串或者数字的角度都可以得到解决方法。

Code

use string

#include <iostream>
using namespace std;
int getnum(char *str, char D) {
    int ret = 0;
    char *p = str;
    for(; *p != '\0'; p++) {    //loop condition also can use str[i] != '\0'
        if(*p == D) {
            ret = ret * 10 + (*p - '0');
        }
    }
    return ret;
}
int main() {
    char A[12], B[12], a, b;
    scanf("%s %c %s %c", A, &a, B, &b);
    printf("%d", getnum(A, a) + getnum(B, b));
    return 0;
}

use int

#include <iostream>
using namespace std;
int getnum(int A, int a) {
    int ret = 0;
    do{
        if(A % 10 == a) ret = ret * 10 + a;
        A /= 10;
    } while(A > 0);
    return ret;
}
int main() {
    int A, B, a, b;
    scanf("%d %d %d %d", &A, &a, &B, &b);
    printf("%d", getnum(A, a) + getnum(B, b));
    return 0;
}

1017 A除以B

Analysis

此题考察大整数运算，其中A为大整数，B为int类型的整数，计算这两个数的商和余数。
此类型的题目，需要使用数组来保存大整数，并用数组来模拟题目要求做的运算。

Code

#include <iostream>
#include <cstring>
using namespace std;
struct bign{
    int d[1005], len;
    bign() {
        memset(d, 0, sizeof(d));
        len = 0;
    }
};

bign change(char *str) {
    bign a;
    a.len = strlen(str);
    for(int i = 0; i < a.len; i++) {
        a.d[i] = str[a.len - i - 1] - '0';
    }
    return a;
}

bign divide(bign a, int b, int &r) {
    bign c;
    c.len = a.len;
    for(int i = a.len - 1; i >= 0; i--) {
        r = r * 10 + a.d[i];
        if(r < b) c.d[i] = 0;
        else {
            c.d[i] = r / b;
            r %= b;
        }
    }
    while(c.len - 1 >= 1 && c.d[c.len - 1] == 0) {
        c.len--;
    }
    return c;
}

int main(int argc, char const *argv[]) {
    char str[1005];
    int b, r = 0;
    cin >> str >> b;
    bign a = change(str), c;
    c = divide(a, b, r);
    for(int i = c.len - 1; i >= 0; i--) {
        cout << c.d[i];
    }
    cout << ' ' << r ;;
    return 0;
}

1018 锤子剪刀布

Analysis

题目大意就是剪刀石头布的游戏规则，对应 9 种情况，进行模拟即可，注意输出赢的次数最多且字典序最小的解。

Code

#include <iostream>
using namespace std;
char gesture(int *a) {
    int index = 1;
    char ges = '\0';
    for(int i = 1; i <= 3; i++) {
        if(a[i] > a[index]) index = i;
    }
    switch(index) {
        case 1: ges = 'B'; break;
        case 2: ges = 'C'; break;
        case 3: ges = 'J'; break;
    }
    return ges;
}
int main() {
    int n, tie = 0, win = 0, ar[4] = {0}, br[4] = {0};
    cin >> n;
    char a, b;
    for(int i = 1; i <= n; i++) {
        cin >> a >> b;
        if(a == b) tie++;
        else if(a == 'C' && b == 'J') {
            win++;
            ar[2]++;
        }
        else if(a == 'J' && b == 'B') {
            win++;
            ar[3]++;
        }
        else if(a == 'B' && b == 'C') {
            win++;
            ar[1]++;
        }
        else if(b == 'C' && a == 'J') {
            br[2]++;
        }
        else if(b == 'J' && a == 'B') {
            br[3]++;
        }
        else if(b == 'B' && a == 'C') {
            br[1]++;
        }
    }
    cout << win << ' ' << tie << ' ' << n - tie - win << endl;
    cout << n - tie - win << ' ' << tie << ' ' << win << endl;
    cout << gesture(ar) << ' ' << gesture(br);
    return 0;
}

1019 数字黑洞

Analysis

题目大意是给定一个四位数字，拆分出其各位数后，能得到一个最大值和最小值，二者相减后，会得到一个新数字。重复这个过程，最后差会一直等于6174。所以，当差为6174时，就停止循环。

按照下面的代码思路，每次必须要将保存各位数字的数组初始化为0，否则会有错误（因为数组有四个元素参与了运算）。另外，需要输出前导 0。

Code

#include <cstdio>
#include <algorithm>
using namespace std;

void toArray(int n, int *array) {
    int temp = n, i = 0, ret = 0;
    while(temp) {
        array[i++] = temp % 10;
        temp /= 10;
    }
}

int main(int argc, char const *argv[]) {
    int n, min, max, diff;
    scanf("%d", &n);
    while(1) {
        int num[5] = {0};
        toArray(n, num);
        sort(num, num + 4); 
        max = num[0] + num[1] * 10 + num[2] * 100 + num[3] * 1000;
        min = num[3] + num[2] * 10 + num[1] * 100 + num[0] * 1000;
        diff = max - min;
        if(!diff) {
            printf("%04d - %04d = 0000\n", max, min);
            break;
        } else {
            printf("%04d - %04d = %04d\n", max, min, diff);
            if(diff == 6174) break;
            n = diff;
        }
    }
    return 0;
}

1020 月饼

Analysis

这是道考察贪心算法的题目，题目要求输出的最大收益，实际上就是对应单价最高的月饼卖出后的总收益。若单价最高的月饼的贮存量不满足市场需求，按照剩余的市场需求量继续卖单价第二高的月饼。所以，需要计算出每种月饼的单价，再对其进行排序，接着按照题目要求计算总收益，最后在输出。

Code

#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN = 1000 + 5;
struct mooncake{
    double store, sell, price;
} cake[MAXN];
bool cmp(mooncake a, mooncake b) {
    return a.price > b.price;
}

int main(int argc, char const *argv[]) {
    int N;
    double D;
    scanf("%d %lf", &N, &D);
    for(int i = 0; i < N; i++) {
        scanf("%lf", &cake[i].store);
    }
    for(int i = 0; i < N; i++) {
        scanf("%lf", &cake[i].sell);
        cake[i].price = cake[i].sell / cake[i].store;
    }
    sort(cake, cake + N, cmp);
    double ans = 0;
    for(int i = 0; i < N; i++) {
        if(cake[i].store <= D) {
            D -= cake[i].store;
            ans += cake[i].sell;
        } else {
            ans += cake[i].price * D;
            break;
        }
    }
    printf("%.2lf\n", ans);
    return 0;
}

1021 个位数统计

Analysis

以字符串的形式读入题目给定的数字，再利用散列的思想，统计各个数字出现的次数，继而输出。

Code

#include <stdio.h>
#define MAXN 1005

int main(int argc, char const *argv[]) {
    char num[MAXN];
    int i, digit[10]={0};
    scanf("%s", num);
    char *p;
    p = num;
    while(*p) {
        digit[*p - '0']++;
        p++;
    }
    for(i=0; i<10; i++) {
        if(digit[i] != 0) printf("%d:%d\n", i, digit[i]);
    }
    return 0;
}

1022 D进制的A+B

Analysis

进制转换的常规题型，利用取余运算获取到转换进制的每一位，然后从高位往地位输出即可，注意输入0 0 8时特判，输出为0。

Code

#include <cstdio>

int main(int argc, char const *argv[]) {
    long long A, B, D, digit[50] = {0}, count = 0;
    scanf("%lld %lld %lld", &A, &B, &D);
    A += B;
    while(A) {
        digit[count++] = A % D;
        A /= D;
    }
    if(count) {
        for(count--; count >= 0; count--) {
            printf("%d", digit[count]);
        }
    } else {
        printf("0");
    }
    putchar('\n');
    return 0;
}

1023 组个最小数

Analysis

输出第一个数字时，不能输出0，所以直接从数字1开始遍历，存在则输出，然后个数减1，并跳出循环；接着在输出剩下的数字，此时0是可以被直接输出的，所以从数字0开始遍历（也是从小到大的规律），将每一个数字全部输出完后，再开始输出下一个数字。

Code

#include <cstdio>

int main(int argc, char const *argv[]) {
    int count[10] = {0};
    for(int i = 0; i < 10; i++) {
        scanf("%d", &count[i]);
    }
    //print the first number
    for(int i = 1; i < 10; i++) {
        if(count[i]) {
            printf("%d", i);
            count[i]--;
            break;
        }
    }
    //print the rest of numbers
    for(int i = 0; i < 10; i++) {
        while(count[i]) {
            printf("%d", i);
            count[i]--;
        }
    }
    return 0;
}

1024 科学计数法

Analysis

题目意思比较明确，科学记数法转换成正常的数字，要把指数提取出来，在指数为正、负或零时，分别对应不同的情况。

Code

version 1

#include <cstdio>
#include <cstring>
#define MAXN 10005

int Getexpon(char *s, int Epos);

int main(int argc, char const *argv[]) {
    char Num[MAXN];
    scanf("%s", Num);
    int count = 0, expo, Epos = 0, len = strlen(Num);
    for(; Num[Epos] != 'E'; Epos++);
    if(Num[0] == '-') putchar(Num[0]);
    expo = Getexpon(Num, Epos);
    if(expo > 0) {
        for(int i = 1; i < Epos; i++) {
            if(Num[i] == '.') continue;
            putchar(Num[i]);
            if(i == expo + 2 && Epos - 3 != expo) {
                putchar('.');
            }
        }
        for(int i = 0; i < expo - (Epos - 3); i++) {
            putchar('0');
        }
    } else if(expo == 0) {
        Num[Epos] = '\0';
        puts(Num + 1);
    } else {
        expo = -expo;
        printf("0.");
        for(int i = 0; i < expo - 1; i++) {
            putchar('0');
        }
        putchar(Num[1]);
        for(int i = 3; i < Epos; i++) {
            putchar(Num[i]);
        }
    }
    putchar('\n');
    return 0;
}

int Getexpon(char *s, int Epos) {
    int ret = 0, flag = 1, i = Epos + 1;
    if(s[i] == '-') {
        flag = -1;
    }
    i++;
    for(; s[i] != '\0'; i++) {
        ret = ret * 10 + s[i] - '0';
    }
    return ret * flag;
}

version 2

这个题如果利用了 scanf 的格式化串就会有奇效，使用%[^E]E%d可以直接将指数读出来，%[^E]与%s是类似的，但是会一直读取，直到读到E这个字符。如果要用 scanf 读取一行，那么就是%[^'\n']了。
scanf 还有很多其他的用法，参考链接：scanf 格式化字符串详解。
回到这道题，这样上面的代码就可以简单一点了。

#include <cstdio>
#include <cstring>
#define MAXN 10005

int main(int argc, char const *argv[]) {
    char Num[MAXN];
    int count = 0, expo, len;
    scanf("%[^E]E%d", Num, &expo);
    len = strlen(Num);
    if(Num[0] == '-') putchar(Num[0]);
    if(expo > 0) {
        for(int i = 1; i < len; i++) {
            if(Num[i] == '.') continue;
            putchar(Num[i]);
            if(i == expo + 2 && len - 3 != expo) {
                putchar('.');
            }
        }
        for(int i = 0; i < expo - (len - 3); i++) {
            putchar('0');
        }
    } else if(expo == 0) {
        puts(Num + 1);
    } else {
        expo = -expo;
        printf("0.");
        for(int i = 0; i < expo - 1; i++) {
            putchar('0');
        }
        putchar(Num[1]);
        for(int i = 3; i < len; i++) {
            putchar(Num[i]);
        }
    }
    putchar('\n');
    return 0;
}

1025 反转链表

Analysis

题目大意：给定一个单链表，每 k 个结点进行逆置，若最后剩下小于 k 个结点，则不需逆置，输出逆置后的链表。

对待此类题目，还是使用静态链表的思路来处理。先默认结构数组内的结点全部为无效结点，再按照地址逐个输入每个结点。然后，利用第一个结点的地址遍历链表，将合法结点的order改为链表结点的顺序，再利用sort函数将合法结点全部排在结构数组的左端，非法结点则在右端。

接着，再开始逆置输出。对于具有 n 个合法结点的链表，按照 k 来逆置，则其必可被分为 n/k 个子块来分别逆置。由于是逆置，所以需要将每一个子块倒着输出。但这一块的最后一个需要输出的结点需要分开考虑，因为其next已经变成了下一个块的最后一个结点（这里说的是初始顺序）的地址了。针对每次输出的最后这个结点的位置有三种情况：

若当前输出的块不是最后一个整块，那么其next就是(i + 2) * K - 1结点（也就是下一个整块的最后一个结点）的地址
若当前输出的块是最后一个整块，且是最后一个整块的最后一个结点，那么其next即为-1
若当前输出的块是最后一个整块，但其后面还有小于K的结点个数，所以其next最后“尾巴”的第一个结点的地址，即(i + 1) * K号结点，然后再将剩余结点输出即可。

Code

#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 100005;
struct node {
    int address, data, next;
    int order;
} Node[maxn];

void init() {
    for(int i = 0; i < maxn; i++) {
        Node[i].order = maxn;
    }
}

bool cmp(node a, node b) {
    return a.order < b.order;
}

int main(int argc, char const *argv[]) {
    init();
    int n, k, head, address;
    cin >> head >> n >> k;
    for(int i = 0; i < n ; i++) {
        cin >> address;
        cin >> Node[address].data >> Node[address].next;
        Node[address].address = address;
    }
    int count = 0, p = head;
    while(p != -1) {
        Node[p].order = count++;
        p = Node[p].next;
    }
    sort(Node, Node + maxn, cmp);
    n = count;
    for(int i = 0; i < n / k; i++) {
        for(int j = (i + 1) * k - 1; j > i * k; j--) {
            printf("%05d %d %05d\n", Node[j].address, Node[j].data,
                   Node[j - 1].address);
        }
        printf("%05d %d ", Node[i * k].address, Node[i * k].data);
        if(i < n / k - 1) {
            printf("%05d\n", Node[(i + 2) * k - 1].address);
        } else {
            if(n % k == 0) printf("-1\n");
            else {
                printf("%05d\n", Node[(i + 1) * k].address);
                for(int i = n / k * k; i < n; i++) {
                    printf("%05d %d ", Node[i].address, Node[i].data);
                    if(i < n - 1) {
                        printf("%05d\n", Node[i + 1].address);
                    } else {
                        printf("-1\n");
                    }
                }
            }
        }
    }
    return 0;
}

1026 程序运行时间

Analysis

给定的是整数，但是要求四舍五入，又知题目给定的除数是 100 ，给被除数加上 50 后，就可以模拟出四舍五入的效果。

Code

#include <iostream>
using namespace std;
int main() {
    int c1, c2, c;
    scanf("%d %d", &c1, &c2);
    c = (c2 - c1 + 50) / 100;
    printf("%02d:%02d:%02d", c / 3600, c / 60 % 60, c % 60);
    return 0;
}

1027 打印沙漏

Analysis

这种打印图像的题目，需要找找规律。

以样例为例，只看图像一半，从中心开始出发，就是$a_1 = 1, a_2 = 3, a_3 = 5$的等差数列，按照这种思路的话，需要打印的图像其实就是两个等差数列，只不过第二个等差数列没有首项，只有两项$a_1 = 3, a_2 = 5$，但这并不影响计算，当作两个相同的等差数列计算好后，减去多余的部分即可。

从而有：$2S_n - 1= 2 \times \frac{3 \times (1 + 5)}2 = 17$，这就是需要打印出来的符号数量，而此时的层数为3（其实也是等差数列的项数）。

下面再来进行输出，注意每行要先输出空格，在输出字符，最后一行输出未使用的字符数。使用绝对值，能简化一半的代码量，看着很清爽~

Code

#include <cstdio>
#define ABS(x) ((x) >= 0 ? (x) : -(x))

int main(int argc, char const *argv[]) {
    int N, layers;
    char c;
    scanf("%d %c", &N, &c);
    for(layers = 1; 2 * layers * layers - 1 <= N; layers++);
    layers--;
    for(int i = 0; i < 2 * layers - 1; i++) {
        for(int j = 0; j < layers - ABS(layers - i - 1) - 1; j++) {
            putchar(' ');
        }
        for(int k = 0; k < 2 * ABS(layers - i - 1) + 1; k++) {
            putchar(c);
        }
        putchar('\n');
    }
    printf("%d\n", N - 2 * layers * layers + 1);
    return 0;
}

1028 人口普查

Analysis

这道题如果在处理日期上面没有经验的话，就很难受...
一开始在判断日期合法性的时候，想到了全部转化为天数，光是转换天数，还有平闰年的区分，感觉又是一道题了🤔，这应该不是姥姥想让答题者干的活。
事实证明，确实想歪了😂，对于这类日期的判断，从年这个数字开始逐个进行比较即可（参考下面的代码），同时注意不要用if-else来得到最年长和年轻的人就好，要分开判断。

Code

use sort

#include <cstdio>

struct citizen{
    int year, month, day;
    char name[7];
} youngest, oldest, left, right, temp;

void Init();
bool Less(citizen a, citizen b);
bool More(citizen a, citizen b);

int main(int argc, char const *argv[]) {
    Init();
    int N, valid = 0;
    scanf("%d", &N);
    while(N--) {
        scanf("%s %d/%d/%d", temp.name, &temp.year, &temp.month, &temp.day);
        if(Less(temp, right) && More(temp, left)) {
            valid++;
            if(More(temp, youngest)) {
                youngest = temp;
            }
            if(Less(temp, oldest)) {
                oldest = temp;
            }
        }
    }
    if(valid) {
        printf("%d %s %s\n", valid, oldest.name, youngest.name);
    } else {
        printf("0\n");
    }
    return 0;
}

void Init() {
    left.year = youngest.year = 1814;
    right.year = oldest.year = 2014;
    youngest.month = oldest.month = left.month = right.month = 9;
    youngest.day = oldest.day = left.day = right.day = 6;
}

bool Less(citizen a, citizen b) {
    if(a.year != b.year) return a.year <= b.year;
    else if(a.month != b.month) return a.month <= b.month;
    else return a.day <= b.day;
}

bool More(citizen a, citizen b) {
    if(a.year != b.year) return a.year >= b.year;
    else if(a.month != b.month) return a.month >= b.month;
    else return a.day >= b.day;
}

use string

这个题，一旦用 string 容器来处理，就非常简单。

#include <iostream>
using namespace std;
int main() {
    int n, cnt = 0;
    cin >> n;
    string name, birth, maxname, minname, maxbirth = "1814/09/06", minbirth = "2014/09/06";
    for(int i = 0; i < n; i++) {
        cin >> name >> birth;
        if("1814/09/06" <= birth && birth <= "2014/09/06") {
            cnt++;
            if(maxbirth <= birth) {
                maxbirth = birth;
                maxname = name;
            }
            if(minbirth >= birth) {
                minbirth = birth;
                minname = name;
            }
        }
    }
    cout << cnt;
    if(cnt) cout << ' ' << minname << ' ' << maxname;
    return 0;
}

实际上，用 strcmp 函数也能完成这样的功能。

1029 旧键盘

Analysis

遍历字符串，找出第一个字符串中出现过，但第二个字符串中未出现的字符即可，字母不区分大小写，但字符串内有空格和数字，用_表示空格（也就是说，可能坏掉的键盘一共有 37 个），注意不能输出小写字母，且重复的字符只输出一次。
这个题还可以用散列的思想来做，会更加简单直接。

Code

traverse string

#include <cstdio>
#include <cctype>

void levelup(char *str);

int main(int argc, char const *argv[]) {
    char str1[85], str2[85], Result[40];
    scanf("%s %s", str1, str2);
    levelup(str1);
    levelup(str2);
    int count = 0;
    for(int i = 0; str1[i] != '\0'; i++) {
        char temp = str1[i];
        bool flag = true;
        for(int j = 0; str2[j] != '\0'; j++) {
            if(temp == str2[j]) {
                flag = false;
                break;
            }
        }
        if(flag) {
            int k = 0;
            for(k = 0; k < 40; k++) {
                if(temp == Result[k]) {
                    break;
                }
            }
            if(k == 40) {
                Result[count++] = temp;
            }
        }
    }
    Result[count] = '\0';
    puts(Result);
    return 0;
}

void levelup(char *str) {
    char *p = str;
    while(*p != '\0') {
        if(islower(*p)) {
            *p = toupper(*p);
        }
        p++;
    }
}

use string.find()

上面代码做的事情，完全可以用 find 函数替代，如下：

#include <iostream>
#include <cctype>
using namespace std;
int main() {
    string s1, s2, ans;
    cin >> s1 >> s2;
    for(int i = 0; i < s1.length(); i++) {
        if(s2.find(s1[i]) == string::npos && ans.find(toupper(s1[i])) == string::npos) {
            ans += toupper(s1[i]);
        }
    }
    cout << ans;
    return 0;
}

实际上，strstr 函数也可以完成同样的功能。

hash

#include <cstdio>
#include <cstring>
#define maxn 85
char A[maxn], B[maxn];
int hashtable[128] = {0};

int main() {
    scanf("%s %s", A, B);
    for(int i = 0; i < strlen(B); i++) {
        if('a' <= B[i] && B[i] <= 'z') hashtable[B[i] - 32]++;
        else hashtable[B[i]]++;
    }
    for(int i = 0; i < strlen(A); i++) {
        if('a' <= A[i] && A[i] <= 'z') {
            if(!hashtable[A[i] - 32]) {
                printf("%c", A[i] - 32);
                hashtable[A[i] - 32]++;
            }
        } else if(!hashtable[A[i]]) {
            printf("%c", A[i]);
            hashtable[A[i]]++;
        }
    } 
    return 0;
}

1030 完美数列

Analysis

题目大意是给一堆数字，这些数字以任意个数和顺序组成序列，使得这个数列的最大、最小值存在这样的关系：$M\ \le\ m \times p$，并要求这个数列包含的数字数量要尽可能的多。

看到题目一般会想到先将序列排序，然后找出其中的最大值，再从小到大枚举每一个数字，直到不满足关系时，退出循环，下标之差即是结果，但这这种思路实际上只把题目的输入数据当作了一个数列来处理（此时提交可得 20 分）。若这个数列还存在比$m \times p$小的数，按照这样的思路就无法让数字数量增加了（因为最大值已经限定了）。举个与样例相同的例子，唯一不同是总数字有 20 个，前 10 个数字与样例一样，后 10 个全是 1，这种思路得到的结果还是 8。但实际上，那 10 个 1 可以跟别的数字构成$M \le m \times p$的关系。

继续深入思考，对有序序列而言，按照题目要求，就需要以当前数字为左端点，然后找到符合要求的最大的右端点值（此时这个右端点值的下标最大，因为下标差越大，数字数量就越多）。按照这样的思路依次枚举每个数字就可以得到最终结果，此算法的时间复杂度为$O(n^2)$。

如何能将查找右端点值过程缩短一点呢？注意到数组已经被排好序了，所以可以使用二分查找来做这件事。此时，问题就演变为：从一个数的后面所有数中，找出刚好满足 $M\ \le\ m \times p$ 这个条件的数字，其中$M$和$m$分别为第一个数字与查找到的数字组成的数列的最大和最小值，这样时间复杂度就是$O(nlogn)$了。
注意，由于 p 与数字都是不超过$10^9$的数，但相乘就溢出了，所以需要转换成 long long。

Code

use binarysearch

#include <cstdio>
#include <algorithm>
using namespace std; 
const int MAXN = 100000 + 10;
int n, p, Num[MAXN];
int BinarySearch(int i, long long x);

int main(int argc, char const *argv[]) {
    scanf("%d %d", &n, &p);
    for(int i = 0; i < n; i++) {
        scanf("%d", &Num[i]);
    }
    sort(Num, Num + n);
    int ans = 1;
    for(int i = 0; i < n; i++) {
        // you can also use upper_bound function
        // int j = upper_bound(Num + i + 1, Num + n, (long long)Num[i] * p) - Num;
        int j = BinarySearch(i, (long long)Num[i] * p);
        ans = max(ans, j - i);
    }
    printf("%d", ans);
    return 0;
}

int BinarySearch(int i, long long x) {
    if(Num[n - 1] <= x) {
        return n;
    }
    int left = i + 1, right = n - 1, mid;
    while(left < right) {
        mid = (left + right) / 2;
        if(Num[mid] <= x) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return left;
}

use two pointer

实际上，这个题还可以用双指针的思想来找右端点的下标，如下：

#include <cstdio>
#include <algorithm>
using namespace std; 
const int MAXN = 100000 + 10;
int n, p, Num[MAXN];
int BinarySearch(int i, long long x);

int main(int argc, char const *argv[]) {
    scanf("%d %d", &n, &p);
    for(int i = 0; i < n; i++) {
        scanf("%d", &Num[i]);
    }
    sort(Num, Num + n);
    int i = 0, j = 0, ans = 1;
    while(i < n && j < n) {
        while(j < n && Num[j] <= (long long)Num[i] * p) {
            ans = max(ans, j - i + 1);
            j++;
        }
        i++;
    }
    printf("%d", ans);
    return 0;
}

1031 查验身份证

Analysis

题目不难，就是要认真读题，根据题目要求进行计算即可，略微有点麻烦，别马虎。

Code

#include <cstdio>
#include <cstring>
char idnum[20];
int weight[17] = {7, 9, 10, 5, 8, 4, 2, 1, 6, 3, 7, 9, 10, 5, 8, 4, 2};
char check[12] = {'1', '0', 'X', '9', '8', '7', '6', '5', '4', '3', '2'};
int main() {
    int n, invalid = 0;
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        scanf("%s", idnum);
        int z = 0, flag = 1;
        for(int i = 0; i < 17; i++) {
            if(!('0' <= idnum[i] && idnum[i] <= '9')) {
                printf("%s\n", idnum);
                invalid++; 
                flag = 0;
                break;
            }
            z = z + (idnum[i] - '0') * weight[i];
        }
        if(flag) {
            z %= 11;
            if(check[z] != idnum[17]) {
                printf("%s\n", idnum);
                invalid++;
            }
        }
    }
    if(!invalid) printf("All passed\n");
    return 0;
}

1032 挖掘机技术哪家强

Analysis

这道题很简单，用数组~~简单模拟一下~~处理数据，然后查找最大值就好了，注意最后一个大数据的测试点。

Code

#include <stdio.h>
#define MAXN 100005

int main(int argc, char const *argv[]) {
    int i, Num, Max = 0, N, School_Num[MAXN] = {0}, temp;
    scanf("%d", &N);
    while(N--) {
        scanf("%d %d", &Num, &temp);
        School_Num[Num] += temp;
    }
    for(i = 0; i < MAXN; i++) {
        if(Max < School_Num[i]) {
            Num = i;
            Max = School_Num[i];
        }
    }
    printf("%d %d\n", Num, Max);
    return 0;
}

1033 旧键盘打字

Analysis

与 1029 正好相反的一道题目，要注意的点：

不区分大小写，只要是第一个字符串出现过的字母，第二个字符串在输出时，无论大小写，都不能输出。
上档键坏了，尽管某个字母按键没坏，但是也不能输出这个字母的大写了。
第一个字符串可能是空串。
strlen可能会超时。
scanf无法读入测试点 2 的空串，所以要用fgets。

Code

hash

#include <cstdio>
#include <cctype>
const int MAXN = 100000 + 5;

int main(int argc, char const *argv[]) {
    char str1[MAXN], str2[MAXN]; 
    bool brokenkey[128] = {false};
    fgets(str2, MAXN, stdin);
    fgets(str1, MAXN, stdin);
    for(int i = 0; str2[i] != '\0'; i++) {
        brokenkey[str2[i]] = true;
        if(isupper(str2[i])) brokenkey[str2[i] + 32] = true;
    }
    for(int i = 0; str1[i] != '\0'; i++) {
        if(!brokenkey[str1[i]]) {
            if(isupper(str1[i]) && brokenkey['+']) continue;
            printf("%c", str1[i]);
        }
    }
    return 0;
}

use string.find()

这个题一样可以用 find 函数来完成，如下：

#include <iostream>
#include <cctype>
using namespace std;
int main() {
    string s1, s2, ans;
    getline(cin, s1);
    getline(cin, s2);
    for(int i = 0; i < s1.length(); i++) {
    	s1[i] = tolower(s1[i]);
    }
    for(int i = 0; i < s2.length(); i++) {
    	if(s1.find(s2[i]) == string::npos) {
    		if(!isupper(s2[i])) cout << s2[i];
    		else if(s1.find('+') == string::npos && s1.find(tolower(s2[i])) == string::npos) cout << s2[i];
        }
    }
    return 0;
}

1034 有理数运算

Analysis

题目大意是给定2个a/b形式的分数，a为分子，b为分母，求这2个分数的和、差、积、商，再输出。

给定的分数只有两种情况（形式上）：真分数和假分数，不存在带分数，但输出要输出带分数，并且是最简形式。化简的目的其实是题目在考察求最大公约数，利用欧几里得算法即可求得两个数的最大公约数。

注意：

除数为0时，需要输出Inf
负数需要使用()括起来

这种题，建议都用这种模板做。

Code

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;

struct Fraction {
    ll up, down;
} f1, f2;

ll gcd(ll a, ll b) {
    return b == 0 ? a : gcd(b, a % b);
}

Fraction Reduction(Fraction result) {
    if(result.down < 0) {
        result.up = -result.up;
        result.down = -result.down;
    }
    if(result.up == 0) {
        result.down = 1;
    } else {
        int d = gcd(abs(result.up), abs(result.down));
        result.up /= d;
        result.down /= d;
    }
    return result;
}

Fraction Add(Fraction f1, Fraction f2) {
    Fraction result;
    result.up = f1.up * f2.down + f2.up * f1.down;
    result.down = f1.down * f2.down;
    return Reduction(result);
}

Fraction Minu(Fraction f1, Fraction f2) {
    Fraction result;
    result.up = f1.up * f2.down - f2.up * f1.down;
    result.down = f1.down * f2.down;
    return Reduction(result);
}

Fraction Mult(Fraction f1, Fraction f2) {
    Fraction result;
    result.up = f1.up * f2.up;
    result.down = f1.down * f2.down;
    return Reduction(result);
}

Fraction Divide(Fraction f1, Fraction f2) {
    Fraction result;
    result.up = f1.up * f2.down;
    result.down = f1.down * f2.up;
    return Reduction(result);
}

void printResult(Fraction r) {
    r = Reduction(r);
    if(r.up < 0) printf("(");
    if(r.down == 1) printf("%lld", r.up);
    else if(abs(r.up) > r.down) {
        printf("%lld %lld/%lld", r.up / r.down, abs(r.up) % r.down, r.down);
    } else {
        printf("%lld/%lld", r.up, r.down);
    }
    if(r.up < 0) printf(")");
}

int main(int argc, char const *argv[]) {
    scanf("%lld/%lld %lld/%lld", &f1.up, &f1.down, &f2.up, &f2.down);
    //add
    printResult(f1);
    printf(" + ");
    printResult(f2);
    printf(" = ");
    printResult(Add(f1, f2));
    putchar('\n');
    
    //minu
    printResult(f1);
    printf(" - ");
    printResult(f2);
    printf(" = ");
    printResult(Minu(f1, f2));
    putchar('\n');

    //mult
    printResult(f1);
    printf(" * ");
    printResult(f2);
    printf(" = ");
    printResult(Mult(f1, f2));
    putchar('\n');
    
    //divide
    printResult(f1);
    printf(" / ");
    printResult(f2);
    printf(" = ");
    if(f2.up == 0) printf("Inf");
    else printResult(Divide(f1, f2));
    return 0;
}

1035 插入与归并

Analysis

题目的意思比较明确，给定两个序列，判断属于哪一种排序，然后输出这个序列在这种排序下的下一轮排序结果。

对给定的初始序列，按照插入排序的过程进行模拟，每轮排序都与给定的中间序列进行比较，如果相同就属于Insertion Sort，否则就是Merge Sort了。

在整个排序和比较的过程中，先进行比较，在需要输出的时候就不需要再进行依次排序操作，可以减少一部分的代码量。另外，重新写归并排序比较麻烦，直接使用sort函数来模拟归并排序的过程就比较方便，要注意sort函数每次只能排指定间隔内的数字。所以采用min(i + step, n)的写法避免最后一次排序时元素个数低于归并间隔的情况，即再最后一次排序过程中，只排剩下的元素。

Code

#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN = 100 + 5;
int origin[MAXN], tempOri[MAXN], changed[MAXN];
int n;

bool isSame(int A[], int B[]) {
    for(int i = 0; i < n; i++) {
        if(A[i] != B[i]) return false;
    }
    return true;
}

void showArray(int A[]) {
    for(int i = 0; i < n; i++) {
        printf("%d", A[i]);
        if(i < n - 1) putchar(' ');
    }
    putchar('\n');
}

bool InsertSort() {
    bool flag = false;
    for(int i = 1; i < n; i++) {
        if(i != 1 && isSame(tempOri, changed)) {
            flag = true;
        }
        int temp = tempOri[i], j = i;
        while(j > 0 && tempOri[j - 1] > temp) {
            tempOri[j] = tempOri[j - 1];
            j--; 
        }
        tempOri[j] = temp;
        if(flag == true) {
            return true;
        }
    }
    return false;
}

void MergeSort() {
    bool flag = false;
    for(int step = 2; step / 2 <= n; step *= 2) {
        if(step != 2 && isSame(tempOri, changed)) {
            flag = true;
        }
        for(int i = 0; i < n; i += step) {
            sort(tempOri + i, tempOri + min(i + step, n));
        }
        if(flag == true) {
            showArray(tempOri);
            return;
        }
    }
}

int main(int argc, char const *argv[]) {
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        scanf("%d", &origin[i]);
        tempOri[i] = origin[i];
    }
    for(int i = 0; i < n; i++) {
        scanf("%d", &changed[i]);
    }
    if(InsertSort()) {
        printf("Insertion Sort\n");
        showArray(tempOri);
    } else {
        printf("Merge Sort\n");
        for(int i = 0; i < n; i++) {
            tempOri[i] = origin[i];
        }
        MergeSort();
    }
    return 0;
}

1036 跟奥巴马一起编程

Analysis

这种打印图形类的题目主要是在找输出的位置，注意题目给定的是字符变量C，而不是C字符。

Code

#include <stdio.h>

int main(int argc, char const *argv[]) {
    int N, i, j;
    char C;
    scanf("%d %c", &N, &C);
    /*actually, you just need to find the place you want print */
    for(i = 0; i < (N + 1) / 2; i++) {
        for(j = 0; j < N; j++) {
            if(i == 0 || i == (N - 1) / 2 || j == 0 || j == N - 1) putchar(C);
            else putchar(' ');
        }
        putchar('\n');
    }
    return 0;
}

1037 在霍格沃茨找零钱

Analysis

题目意思很直观就是找零钱了，只不过度量单位不一样，在计算的时候，按照给定的量进行计算即可。
注意由于，本题中钱的形式有三样，所以在计算前得先判断大小，然后让大的减小的，这样计算起来就很简单了；另外，相等的时候要特判输出0.0.0。

这个题目直接先全部转换成 Knut 然后再进行计算，得到结果后再转换回来会更简单一些。

Code

version 1

#include <cstdio>

struct money {
    int g, s, k;
} P, A, Result;

bool Bigger(money a, money b);
money Substract(money big, money small);

int main(int argc, char const *argv[]) {
    scanf("%d.%d.%d %d.%d.%d", &P.g, &P.k, &P.s, &A.g, &A.k, &A.s);
    if(Bigger(P, A)) {
        Result = Substract(P, A);
        if(!Result.g && !Result.k && !Result.s) printf("0.0.0\n");
        else printf("-%d.%d.%d\n", Result.g, Result.k, Result.s);
    } else {
        Result = Substract(A, P);
        printf("%d.%d.%d\n", Result.g, Result.k, Result.s);
    }
    return 0;
}

bool Bigger(money a, money b) {
    if(a.g != b.g) return a.g >= b.g;
    else if(a.k != b.k) return a.k >= b.k;
    else return a.s >= b.s;
}

money Substract(money big, money small) {
    money ret;
    if(big.s >= small.s) {
        ret.s = big.s - small.s;
    } else {
        ret.s = big.s + 29 - small.s;
        big.k--;
    }
    if(big.k >= small.k) {
        ret.k = big.k - small.k;
    } else {
        ret.k = big.k + 17 - small.k;
        big.g--;
    }
    ret.g = big.g - small.g;
    return ret;
}

version 2

#include <cstdio>
int change2knut(int g, int s, int k) {
    int res = k;
    s = s + g * 17;
    res = res + s * 29;
    return res;
}

int main() {
    int g, s, k, p, a;
    scanf("%d.%d.%d", &g, &s, &k);
    p = change2knut(g, s, k);
    scanf("%d.%d.%d", &g, &s, &k);
    a = change2knut(g, s, k);
    int ans = a - p;
    if(ans == 0) printf("0.0.0\n");
    else {
        int flag = 1;
        if(ans < 0) {
            ans = -ans;
            flag = 0;
        }
        k = ans % 29;
        s = (ans / 29) % 17;
        g = ans / 29 / 17;
        if(!flag) printf("-");
        printf("%d.%d.%d\n", g, s, k);
    }
    return 0;
}

1038 统计同成绩学生

Analysis

考察基本散列的思想，将输入的分数值作为数组下标，每次查找的时间复杂度就变为了：$O(1)$。

Code

#include <cstdio>
int grade[101] = {0};

int main(int argc, char const *argv[]) {
    int N, K, temp;
    scanf("%d", &N);
    for(int i = 0; i < N; i++) {
        scanf("%d", &temp);
        grade[temp]++;
    }
    scanf("%d", &K);
    while(K--) {
        scanf("%d", &temp);
        printf("%d", grade[temp]);
        if(K > 0) putchar(' ');
    }
    return 0;
}

1039 到底买不买

Analysis

将字符常量作为下标散列在统计次数的数组中，就可以很方便的统计珠子的个数了。买与不买对应两种情况：

买，多余的珠子数目就是两个字符串的长度之差
不买，遍历统计次数的数组，找到第二个字符串中出现次数比第一个字符串中出现次数多的字符，并记录下其差值。

Code

version 1

#include <cstdio>
#include <cstring>
const int MAXN = 1000 + 5;

void get_count(int *a, char *s);

int main(int argc, char const *argv[]) {
    char str1[MAXN], str2[MAXN];
    fgets(str1, MAXN, stdin);
    fgets(str2, MAXN, stdin);
    int count1[90] = {0}, count2[90] = {0};
    get_count(count1, str1);
    get_count(count2, str2);
    int temp, less = 0, len1 = strlen(str1), len2 = strlen(str2);
    bool enough = true;
    for(int i = 0; i < 90; i++) {
        temp = count2[i] - count1[i];
        if(temp > 0) {
            less += temp;
            enough = false;
        }
    }
    if(enough) {
        printf("Yes %d\n", len1 - len2);
    } else {
        printf("No %d\n", less);
    }
    return 0;
}

void get_count(int *a, char *s) {
    char *p = s;
    while(*p != '\0') {
        a[*p - '0']++;
        p++;
    }
}

version 2

其实这个题，完全可以只用一个 hash 数组来完成，如下：

#include <iostream>
using namespace std;
int hashtb[256] = {0};

int main() {
    string a, b;
    cin >> a >> b;
    for(int i = 0; i < a.length(); i++) {
        hashtb[a[i]]++;
    }
    int less = 0;
    for(int i = 0; i < b.length(); i++) {
        if(hashtb[b[i]] > 0) hashtb[b[i]]--;
        else less++;
    }
    if(less) cout << "No " << less;
    else cout << "Yes " << a.length() - b.length(); 
    return 0;
}

1040 有几个PAT

Analysis

题目大意是给定一个只含P、A、T三个字母的字符串，按照PAT的顺序，在不改变字符串内字符排列顺序的前提下，最多能有几个PAT这样的子串。

按照题目要求，最容易想到的思路就是利用三个循环暴力枚举所有可能的出现情况，然后统计符合要求的情况，最后在输出。但这样会超时，所以需要换个思路。

对于字符串中确定位置的每一个A而言，其能够与P、T组成PAT的个数，等于其左边P的个数乘以其右边T的个数。那么，这个问题就变成了，遍历字符串时，累加每一个A的左边P的个数与右边T的个数的乘积。

那么，如何才能较快的获得P的个数呢？可以使用一个数组一次性计算出字符串中每一个字符串左边P的个数。直接从左至右遍历字符串，如果当前位是P，那么此位置的数目就是前一位的数目加1；如果当前位不是P，那么此位置的数目就是前一位的数目。

解决了P的问题，T怎么办呢？定义一个变量，从右往左遍历字符串，现在只考虑两种情况：

当前字符为T，变量加 1。
当前字符为A，统计此位置A能组成的子串PAT的数目（计算时别忘了取余），再累加。

遍历结束后，就可以直接输出总数目了。

Code

version 1

#include <cstdio>
#include <cstring> 
const int MAXN = 100000 + 10;
const int MOD = 1000000007;
char str[MAXN];
int leftNumP[MAXN] = {0};

int main(int argc, char const *argv[]) {
    scanf("%s", str);
    int len = strlen(str);
    for(int i = 0; i < len; i++) {
        if(i > 0) {
            leftNumP[i] = leftNumP[i - 1];
        }
        if(str[i] == 'P') {
            leftNumP[i]++;
        }
    }
    int ans = 0, rightNumT = 0;
    for(int i = len - 1; i >= 0; i--) {
        if(str[i] == 'T') {
            rightNumT++;
        } else if(str[i] == 'A') {
            ans = (ans + leftNumP[i] * rightNumT) % MOD;
        }
    }
    printf("%d", ans);
    return 0;
}

version 2

实际上，要求 A 左边 P 的个数其实完全可以不用数组，如果不用数组，那么如何计算 PAT 的个数呢？答案就是，先把 T 的个数求出来。按照上面的思路，把 T 的个数求出来后，每遇到 P 就记录 P 的个数，遇到 T 也记录 T 的个数，遇到 A 就计算 PAT 的个数，但是要减去记录的 T 的个数，因为这个 T 的个数是当前 A 前面的 T 的个数，二者的差才是当前 A 后面的个数，最后别忘了取余。

#include <cstdio>
#include <cstring>
#define MOD 1000000007
const int maxn = 100000 + 10;
char str[maxn];

int main() {
    scanf("%s", str);
    int len = strlen(str), P_cnt = 0, t_cnt = 0, T_cnt = 0;
    long long sum = 0;
    for(int i = 0; i < len; i++) {
        if(str[i] == 'T') T_cnt++;
    }
    for(int i = 0; i < len; i++) {
        if(str[i] == 'P') P_cnt++;
        else if(str[i] == 'T') t_cnt++;
        else if(str[i] == 'A') {
            T_cnt -= t_cnt;
            t_cnt = 0;
            sum = (sum + (P_cnt * T_cnt)) % MOD;
        }
    }
    printf("%d", sum);
    return 0;
}

参考链接：1040. 有几个PAT（25）-PAT乙级真题

version 3

这个题其实还有更直观的思路：

每个 A 对应的 PA 组合是 A 之前 P 的数量。
每个 T 对应的 PAT 组合是 T 之前所有 A 对应的 PA 组合数量的累加。
所有 PAT 组合数量是所有 T 对应的 PAT 组合数量的累加。

从而，就可以得到：

#include <iostream>
#define mod 1000000007
using namespace std;

int main() {
    int p = 0, pa = 0, pat = 0;
    char c;
    while((c = getchar()) != EOF && c != '\n') {
        if(c == 'P') p++;
        if(c == 'A') pa = (pa + p) % mod;
        if(c == 'T') pat = (pat + pa) % mod;
    }
    cout << pat;
    return 0;
}

参考链接：PAT Basic 1040. 有几个PAT (25) (C语言实现)

1041 考试座位号

Analysis

由于最后要输出准考证号，所以每次输入都必须保存输入的准考证号等信息。这样的话，使用结构体数组无疑是一种很方便的选择，之后再遍历结构体数组输出符合条件的信息即可，

Code

#include <stdio.h>

struct examinee_info{
    char number[17];
    int test_seat;
    int exam_seat;
} Examinee_Info[1005];

int main(int argc, char const *argv[]) {
    int N, M, i, temp;
    scanf("%d", &N);
    for(i = 0; i < N; i++) {
        scanf("%s %d %d", Examinee_Info[i].number, &Examinee_Info[i].test_seat, &Examinee_Info[i].exam_seat);
    }
    scanf("%d", &M);
    while(M--) {
        scanf("%d", &temp);
        for(i = 0; i < N; i++) {
            if(temp == Examinee_Info[i].test_seat) {
                printf("%s %d\n", Examinee_Info[i].number, Examinee_Info[i].exam_seat);
            }
        }
    }
    return 0;
}

1042 字符统计

Analysis

利用数组统计每个英文字符（不区分大小写）的出现次数，直接使用字符变量（ASCII 码值）作为下标会很方便，同时得到出现的最大次数。输出时，遍历统计次数的数组，只输出字典序最小的字母即可。

Code

#include <cstdio>
#include <cctype>

const int MAXN = 1000 + 5;
int main(int argc, char const *argv[]) {
    char str[MAXN];
    fgets(str, MAXN, stdin);
    int times[27] = {0}, maxtimes = -1;
    for(int i = 0; str[i] != '\0'; i++) {
        char c1 = str[i];
        if(isalpha(c1)) {
            if(isupper(c1)) c1 = tolower(c1);
            times[c1 - 'a']++;
            if(times[c1 - 'a'] > maxtimes) {
                maxtimes = times[c1 - 'a'];
            }
        }
    }
    for(int i = 0; i < 27; i++) {
        if(maxtimes == times[i]) {
            printf("%c %d\n", i + 'a', times[i]);
            break;
        }
    }
    return 0;
}

1043 输出PATest

Analysis

先统计字符串中PATest这六个字符的出现次数，然后依次输出PATest，注意当其中某个字符输出完后，仍然要保持PATest这个顺序来输出字符。

Code

#include <cstdio>
const int MAXN = 10000 + 5;
char PATest[10] = "PATest";

int main(int argc, char const *argv[]) {
    char str[MAXN];
    fgets(str, MAXN, stdin);
    char *p = str;
    int times[128] = {0};
    while(*p != '\0') {
        times[*p]++;
        p++;
    }
    while(times['P'] || times['A'] || times['T'] || times['e'] || 
        times['s'] || times['t']) {
        for(p = PATest; *p != '\0'; p++) {
            if(times[*p]) {
                putchar(*p);
                times[*p]--;
            }
        }
    }
    return 0;
}

1044 火星数字

Analysis

题目给出了火星上的数位规则，要求将十进制数转换为火星数字并输出。尽管火星上每一位数输出的形式不一样，但其本质是13进制的，所以按照这个规则进行即可。

由于整个范围的数字有169个，所以提前将所有需要输出的数字全部打印好，之后直接输出比较好。为此，需要借助 C++ 的string和map，来分别建立数字对应字符串、字符串对应数字的映射数组。

注意：输入13时，需要输出tam，而不是tam tret。

Code

#include <iostream>
#include <string>
#include <map>
using namespace std;
string unitDigit[13] = {"tret", "jan", "feb", "mar", "apr", "may", "jun",
                        "jly", "aug", "sep", "oct", "nov", "dec",
                       };
string tenDigit[13] = {"tret", "tam", "hel", "maa", "huh", "tou", "kes",
                       "hei", "elo", "syy", "lok", "mer", "jou",
                      };
string numToStr[170];
map<string, int> strToNum;
void init();
int main(int argc, char const *argv[]) {
    init();
    int n;
    cin >> n;
    getchar();	//get the extra ' ' from stdin
    while(n--) {
        string s;
        getline(cin, s);
        if('0' <= s[0] && s[0] <= '9') {
            int num = 0;
            for(int i = 0; i < s.length(); i++) {
                num = num * 10 + s[i] - '0';
            }
            cout << numToStr[num] << endl;
        } else {
            cout << strToNum[s] << endl;
        }
    }
    return 0;
}

void init() {
    for(int i = 0; i < 13; i++) {
        numToStr[i] = unitDigit[i];
        strToNum[unitDigit[i]] = i;
        numToStr[i * 13] = tenDigit[i];
        strToNum[tenDigit[i]] = i * 13;
    }
    for(int i = 1; i < 13; i++) {
        for(int j = 1; j < 13; j++) {
            //string concatenation
            string str = tenDigit[i] + ' ' + unitDigit[j];
            numToStr[i * 13 + j] = str;
            strToNum[str] = i * 13 + j;
        }
    }
}

1045 快速排序

Analysis

题目的背景是快速排序算法内的一些概念，已经给出了描述，所以但不影响读题。依据题目的例子，可以得到主元的特点：

主元左边的数字全部比它小，即最大值小于它
主元右边的数字全部比它大，即最小值大于它

按照上述分析，依次枚举数组内每一个元素，如果每次都去查找当前元素的最值，会很耗时间。所以，要换一个角度去思考问题。

定义一个数组，一次性将所有数字左边的最小值全部计算出来，每次枚举时，就只用和前一个数字最左边的最小值进行比较，找最大值时同理。

最后在遍历一次数组，找出符合条件的数后直接输出即可。

Code

version 1

这种记录“状态”的写法，很有用。

#include <cstdio>
#include <algorithm>
using namespace std; 
const int MAXN = 100000 + 10;
const int INF = 0x3fffffff;
int array[MAXN], leftMax[MAXN], rightMin[MAXN];
int ans[MAXN], num = 0;

int main(int argc, char const *argv[]) {
    int N;
    scanf("%d", &N);
    for(int i = 0; i < N; i++) {
        scanf("%d", &array[i]);
    }
    leftMax[0] = 0;
    for(int i = 1; i < N; i++) {
        leftMax[i] = max(leftMax[i - 1], array[i - 1]);
    }
    rightMin[N - 1] = INF;
    for(int i = N - 2; i >= 0; i--) {
        rightMin[i] = min(rightMin[i + 1], array[i + 1]);
    }
    for(int i = 0; i < N; i++) {
        if(leftMax[i] < array[i] && rightMin[i] > array[i]) {
            ans[num++] = array[i];
        }
    }
    printf("%d\n", num);
    for(int i = 0; i < num; i++) {
        printf("%d", ans[i]);
        if(i < num - 1) putchar(' ');
    }
    putchar('\n');
    return 0;
}

version 2

一般而言，这个题最容易想到的思路应该就是排序，排序之后，如果元素位置没有改变就可以确定这个元素是主元。但实际上，这种思路其实只确定了一个条件，那就是这个元素右边必然没有元素小于它，换句话讲，就是这个元素右边最小值大于它，这可以从反证法的角度来证明。那么，剩下要解决的问题就是，这个元素的左边的最大值是否小于它，这个判断也很简单。具体如下：

#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 100000 + 5;
int n, arr[maxn] = {0}, tmp[maxn], ans[maxn] = {0};

int main() {
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> arr[i];
        tmp[i] = arr[i];
    } 
    sort(tmp, tmp + n);
    int cnt = 0, max = 0;
    for(int i = 1; i <= n; i++) {
        if(arr[i] == tmp[i] && max < arr[i]) ans[cnt++] = arr[i];
        if(arr[i] > max) max = arr[i];
    }
    cout << cnt << endl;
    if(cnt) {
        for(int i = 0; i < cnt; i++) {
            cout << ans[i];
            if(i != cnt - 1) cout << ' ';
        }
    }
    cout << endl;
    return 0;
}

1046 划拳

Analysis

注意读题，理解题目意思后就好办了。另外注意，输家罚一杯酒，甲若输了，甲喝一杯，乙不喝；同赢或同输都不喝。

Code

#include <iostream>
using namespace std;

int main() {
    int n, a, b, c, d, countA = 0, countB = 0;
    cin >> n;
    while(n--) {
        cin >> a >> b >> c >> d;
        if(a + c == b && a + c == d) continue;	// all win
        else if(a + c != b && a + c != d) continue;	// all lose
        else if(a + c == b) countB++;	// A win
        else countA++;	// B win
    }
    cout << countA << ' ' << countB;
    return 0;
}

1047 编程团体赛

Analysis

统计每支队伍的总分，然后找出总分的最大值，即可得到冠军队的编号。然后，输出冠军队的编号和总成绩。

Code

#include <cstdio>

int main(int argc, char const *argv[]) {
    int N, team, score[1010] = {0}, eachScore, maxteam = 0;
    scanf("%d", &N);
    while(N--) {
        scanf("%d-%*d %d", &team, &eachScore);
        score[team] += eachScore;
        if(team > maxteam) {
            maxteam = team;
        }
    }
    int maxscore = -1, index = 0;
    for(int i = 1; i <= maxteam; i++) {
        if(score[i] > maxscore) {
            maxscore = score[i];
            index = i;
        }
    }
    printf("%d %d", index, maxscore);
    return 0;
}

1048 数字加密

Analysis

题目意思简单，做法也不难，就是有陷阱🤩，即：若是B的位数少于加密密钥的位数，需要假设B的当前位上的数字是0然后参与计算（注意奇偶位不同）即可。

一开始偷懒，以为短就短吧，只加密到需要加密的位数就行了，结果有两个测试点无法通过，看来还是题意理解的不够深入。

另外，由于输入后，数字的个位在字符串最后一位，所以需要逆置一下。

Code

#include <cstdio>
#include <cstring>
const int MAXN = 100 + 5;
char change[14] = "0123456789JQK";

void Reverse(char *s);

int main(int argc, char const *argv[]) {
    char A[MAXN], B[MAXN], Result[MAXN];
    scanf("%s %s", A, B);
    Reverse(A);
    Reverse(B);
    int i, lenA = strlen(A), lenB = strlen(B), len; 
    len = lenA > lenB ? lenA : lenB;
    for(i = 0; i < len; i++) {
        int numA = i < lenA ? A[i] - '0' : 0;
        int numB = i < lenB ? B[i] - '0' : 0;
        if(i % 2 == 0) {
            int sum = numA + numB;
            Result[i] = change[sum % 13];
        } else {
            int diff = numB - numA;
            if(diff < 0) {
                diff += 10;
            }
            Result[i] = change[diff];
        }
    }
    Result[i] = '\0';
    Reverse(Result);
    puts(Result);
    return 0;
}

void Reverse(char *s) {
    char temp;
    int len = strlen(s);
    for(int i = 0; i < len / 2; i++) {
        temp = s[i];
        s[i] = s[len - i - 1];
        s[len - i - 1] = temp;
    }
}

1049 数列的片段和

Analysis

题目大意是给定一个数列，计算其所有按序排列的子列和，直接做会超时，需要找规律。
列举出$N$分别取3、4、5时，其和（$Sum$）情况如下：

$N$	$Sum$
3	$3 \times a_1 + 4 \times a_2 + 3 \times a_3$
4	$4 \times a_1 + 6 \times a_2 + 6 \times a_3 + 4 \times a_4$
5	$5 \times a_1 + 8 \times a_2 + 9 \times a_3 + 8 \times a_4 + 5 \times a_5$

于是可以推出规律为：首项和尾项乘以项数相加，中间每项其左、右两边项数之积（包含它自身）。

修正测试数据后，在系数相乘的过程中，会出现溢出的情况，解决办法是用long long来代替double，再除以 1000 来得到最后的结果。

Code

version 1.0

#include <cstdio>
const int MAXN = 100000 + 10;
double seq[MAXN] = {0};

int main(int argc, char const *argv[]) {
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        scanf("%lf", &seq[i]);
    }
    double ans = 0;
    ans = seq[0] * n;
    if(n > 1) {
        for(int i = 1; i < n - 1; i++) {
            ans += (seq[i] * (i + 1) * (n - i));
        }
        ans += seq[n - 1] * n;
    }
    printf("%.2lf\n", ans);
    return 0;
}

version 2.0

#include <cstdio>
const int maxn = 100000 + 5;
int n;
 
int main() {
    scanf("%d", &n);
    double tmp;
    long long ans = 0;
    for(int i = 1; i <= n; i++) {
        scanf("%lf", &tmp);
        ans += (long long)(tmp * 1000) * (long long)i * (long long)(n - i + 1);
    }
    printf("%.2lf\n", ans/1000.0);
    return 0;
}

1050 螺旋矩阵

Analysis

这个题是个比较中等的模拟题，类似的题目其实有很多，难点在于输出顺序的确定，也就是数组的下标对应关系。
先将给定的数字降序排列，然后一个一个读到矩阵中。此时，设置 4 个变量，分别代表上边界、下边界、左边界和右边界，这样就可以用 4 个循环按照题目要求的顺序放入对应的数字了。注意，最后一个数字要单独处理。单独处理并不是说每种情况最后一个数字都是这样处理，而是为了避免某些情况会陷入死循环中。比如当 n 取 9 时，最后一个数字如果不单独处理就会死循环。

Code

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const int MAXN = 10000 + 5;
int N, num[MAXN], m, n, matrix[MAXN][MAXN];

bool cmp(int a, int b) {
    return a > b;
}
int main() {
    scanf("%d", &N);
    for(int i = 0; i < N; i++) {
        scanf("%d", &num[i]);
    }
    if(N == 1) {
        printf("%d", num[0]);
        return 0;
    }
    sort(num, num + N, cmp);
    m = (int)ceil(sqrt(N * 1.0));
    while(N % m != 0) m++;
    n = N / m;
    int i = 1, j = 1, now = 0;
    int U = 1, D = m, L = 1, R = n;
    while(now < N) {
        while(now < N && j < R) {
            matrix[i][j] = num[now++];
            j++;
        }
        while(now < N && i < D) {
            matrix[i][j] = num[now++];
            i++;
        }
        while(now < N && j > L) {
            matrix[i][j] = num[now++];
            j--;
        }
        while(now < N && i > U) {
            matrix[i][j] = num[now++];
            i--;
        }
        U++, D--, L++, R--;
        i++, j++;
        if(now == N - 1) {
            matrix[i][j] = num[now++];
        }
    }
    for(int i = 1; i <= m; i++) {
        for(int j = 1; j <= n; j++) {
            printf("%d", matrix[i][j]);
            if(j < n) printf(" ");
            else printf("\n");
        }
    }
    return 0;
}

1051 复数乘法

Analysis

此题不难，属于“纸老虎”，不过找特殊情况很是烦人的😅~
注意计算得到的小于 -0.01 的会被保留 2 位有效数字的printf输出成-0.00。

Code

#include <stdio.h>
#include <math.h>

int main(int argc, char const *argv[]) {
    double R1, P1, R2, P2, R, P;
    scanf("%lf %lf %lf %lf", &R1, &P1, &R2, &P2);
    R = R1 * R2 * (cos(P1) * cos(P2) - sin(P1) * sin(P2));
    P = R1 * R2 * (cos(P1) * sin(P2) + sin(P1) * cos(P2));
    //prevent to print "-0.00"
    if(-0.01 < R && R < 0) R = 0.0;
    if(-0.01 < P && P < 0) P = 0.0;
    printf("%.2lf", R);
    if(P >= 0) {
        printf("+%.2lfi\n", P);
    } else {
        printf("-%.2lfi\n", fabs(P));
    }
    return 0;
}

1052 卖个萌

Analysis

这个题有点坑爹，题意也不算难理解，就是按照给定的输入样例，可能无法得到给定的输出样例，总是给人感觉好像做错了。实际上，样例内有些字符的不是 ASCII 编码，所以没法正常的输出。所以，真要是在考试的时候遇到这样的情况，只能通过字符的个数来猜，有没有获得需要的字符。

明白了以上情况后，再回到这道题上，可以发现，题目想让我们做的事情，本质上就是将字符拼在一起，然后输出就行了。要输出的字符是题目给定的，可能会给不存在的字符，这时输出Are you kidding me? @\/@即可。另外，还有几个注意点：

要输出\必须使用"\\"，也就是转义。
不存在某种字符时，直接输出Are you kidding me? @\/@。
由于给定的字符串有空格的存在，所以使用getline来直接读取一行字符串。
别忘记了还要给最终结果加括号：(和)。

Code

version 1

这个版本是自己写的，利用vector<char>来储存处理字符，代码写的比较繁琐，很多其实都是重复的部分。写的时候，想的是能 AC 就行了，之后再改，结果现在也懒得改了，奏这样吧。

#include <iostream>
#include <vector>
using namespace std;
vector<char> hands[11], eyes[11], mouth[11], emo;
string temp;
int arr[6];
int main() {
    for(int i = 1; i <= 3; i++) {
        getline(cin, temp);
        int j, k, cnt = 1;
        if(i == 1) {
            for(j = 0; j < temp.length(); j++) {
                if(temp[j] == '[') {
                    for(k = j + 1; temp[k] != ']'; k++) {
                        hands[cnt].push_back(temp[k]);
                    }
                    cnt++;
                    j = k;
                }
            }
        } else if(i == 2) {
            for(j = 0; j < temp.length(); j++) {
                if(temp[j] == '[') {
                    for(k = j + 1; temp[k] != ']'; k++) {
                        eyes[cnt].push_back(temp[k]);
                    }
                    cnt++;
                    j = k;
                }
            }
        } else {
            for(j = 0; j < temp.length(); j++) {
                if(temp[j] == '[') {
                    for(k = j + 1; temp[k] != ']'; k++) {
                        mouth[cnt].push_back(temp[k]);
                    }
                    cnt++;
                    j = k;
                }
            }
        }
    }
    int k, tmp;
    cin >> k;
    while(k--) {
        bool flag = true;
        emo.clear();
        for(int i = 0; i < 5; i++) {
            cin >> arr[i];
        }
        if(hands[arr[0]].size() == 0 || eyes[arr[1]].size() == 0 || mouth[arr[2]].size() == 0 \
            || eyes[arr[3]].size() == 0 || hands[arr[4]].size() == 0) {
            printf("Are you kidding me? @\\/@\n");
            continue;
        } 
        for(vector<char>::iterator it = hands[arr[0]].begin(); it != hands[arr[0]].end(); it++) {
            emo.push_back(*it);
        }
        emo.push_back('(');
        for(vector<char>::iterator it = eyes[arr[1]].begin(); it != eyes[arr[1]].end(); it++) {
            emo.push_back(*it);
        }
        for(vector<char>::iterator it = mouth[arr[2]].begin(); it != mouth[arr[2]].end(); it++) {
            emo.push_back(*it);
        }
        for(vector<char>::iterator it = eyes[arr[3]].begin(); it != eyes[arr[3]].end(); it++) {
            emo.push_back(*it);
        }
        emo.push_back(')');
        for(vector<char>::iterator it = hands[arr[4]].begin(); it != hands[arr[4]].end(); it++) {
            emo.push_back(*it);
        }
        for(int i = 0; i < emo.size(); i++) {
            cout << emo[i];
        }
        cout << endl;
    }
    return 0;
}

version 2

这个版本来自：1052. 卖个萌 (20)-PAT乙级真题，用的是vector<string>，本质上与自己的思路是一样的，不过代码清爽了许多。

#include <iostream>
#include <vector>
using namespace std;
int main() {
    vector<vector<string> > v;
    for(int i = 0; i < 3; i++) {
        string s;
        getline(cin, s);
        vector<string> row;
        int j = 0, k = 0;
        while(j < s.length()) {
            if(s[j] == '[') {
                while(k++ < s.length()) {
                    if(s[k] == ']') {
                        row.push_back(s.substr(j+1, k-j-1));
                        break;
                    }
                }
            }
            j++;
        }
        v.push_back(row);
    }
    int n;
    cin >> n;
    for(int i = 0; i < n; i++) {
        int a, b, c, d, e;
        cin >> a >> b >> c >> d >> e;
        if(a > v[0].size() || b > v[1].size() || c > v[2].size() || d > v[1].size() || e > v[0].size() || a < 1 || b < 1 || c < 1 || d < 1 || e < 1) {
            cout << "Are you kidding me? @\\/@" << endl;
            continue;
        }
        cout << v[0][a-1] << "(" << v[1][b-1] << v[2][c-1] << v[1][d-1] << ")" << v[0][e-1] << endl;
    }
    return 0;
}

version 3

这个版本来自：PAT Basic 1052. 卖个萌 (20)（C语言实现），利用scanf的特性来直接得到想要的东西，这个操作很精彩，还有 3 维数组的使用，也需要学习一下。就根本来讲，用 3 维的vector<char>应该也可以得到这样的效果。

#include <stdio.h>
int main() {
    int N, m[5];
    char c, symbols[3][10][5] = {0};

    for(int symbol = 0; symbol < 3; symbol++)
        for(int index = 0; (c = getchar()) != '\n'; )
            if(c == '[') scanf("%[^]]", symbols[symbol][index++]);
    scanf("%d", &N);
    for(int i = 0; i < N; i++) {
        for(int i = 0; i < 5; i++)  scanf("%d", m + i);
        if(m[0] > 0 && m[0] <= 10 && *symbols[0][--m[0]]
        && m[1] > 0 && m[1] <= 10 && *symbols[1][--m[1]]
        && m[2] > 0 && m[2] <= 10 && *symbols[2][--m[2]]
        && m[3] > 0 && m[3] <= 10 && *symbols[1][--m[3]]
        && m[4] > 0 && m[4] <= 10 && *symbols[0][--m[4]])
            printf("%s(%s%s%s)%s\n", symbols[0][m[0]], symbols[1][m[1]],
                   symbols[2][m[2]], symbols[1][m[3]], symbols[0][m[4]]);
        else
            puts("Are you kidding me? @\\/@");
    }
    return 0;
}

1053 住房空置率

Analysis

按照题目给定的条件进行计算即可，但要注意第二个条件需要观察期 K 大于给定阈值 D。另外，还需注意浮点数的计算和百分号的输出。

Code

#include <cstdio>
int N, D;
double e;

int main() {
    scanf("%d %lf %d", &N, &e, &D);
    int empty = 0, possible = 0, tmp = N;
    while(tmp--) {
        int k, half = 0;
        scanf("%d", &k);
        double days[k];
        for(int i = 0; i < k; i++) {
            scanf("%lf", &days[i]);
            if(days[i] < e) half++;
        }
        if(half > k / 2) {
            if(k > D) empty++;
            else possible++;
        }
    }
    printf("%.1lf%% %.1lf%%\n", possible * 100.0 / N, empty * 100.0 / N);
    return 0;
} 

/*
in:
5 0.5 10
6 0.3 0.4 0.5 0.2 0.8 0.6
10 0.0 0.1 0.2 0.3 0.0 0.8 0.6 0.7 0.0 0.5
5 0.4 0.3 0.5 0.1 0.7
11 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1
11 2 2 2 1 1 0.1 1 0.1 0.1 0.1 0.1
out:
40.0% 20.0%

in:
3 0.5 10
10 0.0 0.1 0.2 0.3 0.0 0.8 0.6 0.7 0.0 0.5
5 0.4 0.3 0.5 0.1 0.7
11 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1
out:
66.7% 33.3%

in:
1 0.5 10
11 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1
out:
0.0% 100.0%

in:
1 0.5 10
6 0.3 0.4 0.5 0.2 0.8 0.6
out:
0.0% 0.0%

in:
2 0.5 10
10 0.0 0.1 0.2 0.3 0.0 0.8 0.6 0.7 0.0 0.5
5 0.4 0.3 0.5 0.1 0.7
out:
100.0% 0.0%

*/

1054 求平均值

Analysis

这是一道字符串处理题，首先是对数字合法的判断，非法的输入包含下面几点：

数值范围超过了$[-1000, 1000]$。
输入中含有非数字或小数点字符。
输入中含有多个小数点字符。
有效数字超过了 2 位。

按照上面的标准判断是否合法即可，提取出数值也比较容易，负号一定出现在str[0]；计算小数，只需记录好小数点后数字的个数，最终结果在除以pow(10, dec)即可。另外还需要注意一下题目中的陷阱，如果只有一个有效数字，得输出The average of 1 number is Y，里面的number没有s。

Code

version 1

#include <cstdio>
#include <cstring>
#include <cmath>
char str[100];
double num;
bool getnum(char *str) {
    num = 0.0;
    bool flag = false;
    int i = 0, dec = 0, pnum = 0;
    if(str[i] == '-') {
        for(i++; str[i] != '\0'; i++) {
            if(flag) dec++;
            if(str[i] == '.') {
                pnum++;
                flag = true;
            } else if(pnum > 1 || '9' < str[i] || str[i] < '0' || dec > 2) return false;
            if('0' <= str[i] && str[i] <= '9') num = num * 10 + str[i] - '0';
        }
        num = num / pow(10, dec) * -1;
    } else {
        for(; str[i] != '\0'; i++) {
            if(flag) dec++;
            if(str[i] == '.') {
                pnum++;
                flag = true;
            } else if(pnum > 1 || '9' < str[i] || str[i] < '0' || dec > 2) return false;
            if('0' <= str[i] && str[i] <= '9') num = num * 10 + str[i] - '0';
        }
        num = num / pow(10, dec);
    }
    if(-1000.0 <= num && num <= 1000.0) return true;
    else return false;
}

int main() {
    int n, valid = 0;
    double sum = 0.0;
    scanf("%d", &n);
    while(n--) {
        scanf("%s", str);
        if(getnum(str)) {
            sum += num;
            valid++;
        } else {
            printf("ERROR: %s is not a legal number\n", str);
        }
    }
    if(valid > 1) printf("The average of %d numbers is %.2lf\n", valid, sum / valid);
    else if(valid == 1) printf("The average of %d number is %.2lf\n", valid, sum / valid);
    else printf("The average of 0 numbers is Undefined\n");
    return 0;
} 

/*
in:
7
5 -3.2 aaa 9999 2.3.4 7.123 2.35
out:
ERROR: aaa is not a legal number
ERROR: 9999 is not a legal number
ERROR: 2.3.4 is not a legal number
ERROR: 7.123 is not a legal number
The average of 3 numbers is 1.38

in:
2
aaa -9999
out:
ERROR: aaa is not a legal number
ERROR: -9999 is not a legal number
The average of 0 numbers is Undefined

in:
1
1000
out:
The average of 2 number is 1000.00
*/

version 2

这个题一旦用 sscanf 和 sprintf 来处理输出的字符串，就会非常简单，sscanf 是从字符串中读入指定格式的数据放到变量中，sprintf 是将变量中的数据按照指定的格式放到字符串中，如下：

#include <cstdio>
#include <cstring>

int main() {
    int n, valid = 0;
    double sum = 0.0, tmp = 0.0;
    scanf("%d", &n);
    char a[50], b[50];
    while(n--) {
        scanf("%s", a);
        sscanf(a, "%lf", &tmp);
        sprintf(b, "%.2lf", tmp);
        int flag = 0;
        for(int j = 0; j < strlen(a); j++) {
            if(a[j] != b[j]) flag = 1;
        }
        if(flag || tmp < -1000 || tmp > 1000) {
            printf("ERROR: %s is not a legal number\n", a);
            continue;
        } else {
            sum += tmp;
            valid++;
        }
    }
    if(valid == 1) printf("The average of 1 number is %.2lf\n", sum);
    else if(valid > 1) printf("The average of %d numbers is %.2lf\n", valid, sum / valid);
    else printf("The average of 0 numbers is Undefined\n");
    return 0;
}

1055 集体照

Analysis

这个题参考了1055. 集体照 (25)-PAT乙级真题的思路。
主要有两个难点：

题意的理解
排队过程的模拟

分开来看：

首先要明确题目是站在拍照者（就是排队的人）的角度来描述的，排多少排，每排多少人数，这些题目都交代的很清晰，多出来的人全部排在最后一排。显然，如果每排$N/K$个人，那么，最后一排的人数就是$N/K + N\%K$，这样就可以把多出来的人全部排下。如果下标从 1 开始，那么中间位置（最高的人）就是$m/2 + 1$，下标从 0 开始，就是$m/2$。中间人选好后，接着以其为轴开始交替排其他人。就描述中的例子而言，5人身高为 190、188、186、175、170，首先得到的序列是x x 190 x x，按照身高非增序（降序）先右边（假设你是最高的人）排一个可以得到x 188 190 x x，再按照身高顺序左边排一个可以得到x 188 190 186 x，然后再排右边，就是175 188 190 186 x，最后再排左边就可以得到175 188 190 186 170了。

按照上面的分析要模拟排队的过程，首先就需要将身高与人名（字典序升序）进行排序，这个问题很容易解决，构造结构体，然后排序即可。然后再来排队，首先从输出样例可以看出，输出的第一排实际上是整个队伍的最后一排。换句话说，第一行输出的是人数最多，身高最高的一排，那么这一排的人数就是$N/K + N\%K$，其他排的人数就是$N/K$。people 数组和 queue 数组的下标都是从 0 开始的，身高最高的人就排在m/2。接着站在拿相机的人的视角，再来排中间人的左边，queue 这个数组就得从j = m/2 - 1开始，people 数组的下标就要从i = t + 1，因为要还要排右边所以不要改动t的值，再排下一个人，queue 数组的下标就是j--，people 数组的下标就是i = i + 2，因为另一个人要排在右边，所以要跳一个人。同理，排右边的时候，queue 数组从j = m/2 + 1开始，people 数组的下标从i = t + 2开始，再排下一个人时，queue 数组下标就变为j++，people 数组下标就变为i = i + 2。每次循环，只排了当前排的人的数目。

Code

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 10000 + 10;
struct human{
    char name[10];
    int height;
} people[maxn], queue[maxn];
int n, k, m;
bool cmp(human a, human b){
    if(a.height != b.height) return a.height > b.height;
    else return strcmp(a.name, b.name) < 0;
}
int main() {
    cin >> n >> k;
    for(int i = 0; i < n; i++) {
        cin >> people[i].name >> people[i].height;
    }
    sort(people, people + n, cmp);
    int t = 0, row = k;
    while(row) {
        if(row == k) m = n / k + n % k;
        else m = n / k;
        queue[m / 2] = people[t];
        // left
        int j = m / 2 - 1;
        for(int i = t + 1; i < t + m; i = i + 2) {
            queue[j--] = people[i];
        }
        // right
        j = m / 2 + 1;
        for(int i = t + 2; i < t + m; i = i + 2) {
            queue[j++] = people[i];
        } 
        // print
        cout << queue[0].name;
        for(int i = 1; i < m; i++) {
            cout << ' ' << queue[i].name;
        }
        cout << endl;
        t = t + m;
        row--;
    }
    return 0;
}

1056 组合数的和

Analysis

题目不难，读懂题目之后直接做就可以了，也没有设置超时数据。不过，仔细观察一下可以发现，每个数都被当做n-1次十位，这样得话，就可以直接计算了。

Code

version 1

#include <cstdio>

int main() {
    int n, arr[15], sum = 0;
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        scanf("%d", &arr[i]); 
    } 
    for(int i = 0; i < n; i++) {
        sum = sum + (arr[i] * 10 * (n - 1));
        for(int j = 0; j < n; j++) {
            if(j != i) sum += arr[i]; 
        }
    }
    printf("%d", sum);
    return 0;	                 	
}

version 2

再深入思考一下，假设一共 3 项为 a、b、和 c，就有：
$(a + b + c) \times 10 \times (3 - 1) + (b + c + a + c + a + b) = (a + b + c) \times (3 - 1) \times 11$，把其中的项数换成 n 就可以得到一般化公式：$sum = 11(N - 1)\sum_{i=1}^Na_i$。那么，就可以得到下面的代码：

#include <cstdio>

int main() {
    int n, arr, sum = 0;
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        scanf("%d", &arr);
        sum += arr;
    } 
    printf("%d", sum * (n - 1) * 11);
    return 0;	                 	
}

1057 数零壹

Analysis

先得到整数 N，然后再做进制转换，分别记录下 0 和 1 的个数。

Code

#include <cstdio>
const int maxn = 100000 + 5;
char str[maxn];
long long sum = 0;

int main() {
    fgets(str, maxn, stdin);
    for(int i = 0; str[i] != '\0'; i++) {
        if('A' <= str[i] && str[i] <= 'Z') sum = sum + str[i] - 'A' + 1;
        if('a' <= str[i] && str[i] <= 'z') sum = sum + str[i] - 'a' + 1;
    }
    long long tmp = sum;
    int one = 0, zero = 0;
    while(tmp != 0){
        int i = tmp % 2;
        if(i) one++;
        else zero++;
        tmp /= 2; 
    }
    printf("%d %d", zero, one);
    return 0;
}

这个题如果对数在计算机内的存储形式比较了解的话，完全可以不用取余来做，直接利用位运算得到结果，如下：

for(; tmp; tmp >>= 1) {
        if(tmp & 1) one++;
        else zero++;
}

1058 选择题

Analysis

题目意思比较直观，根据题目的描述可以判断出这是一道字符串处理相关的题目。题目描述的内容比较多，为了储存数据方便，构造一个新的结构体比较好。另外，strcmp这个函数只有字符串相同的时候才会输出 0；利用scanf输入时，需要用getchar来接受末尾的回车符或者是空格，当然，scanf的格式化串%*c也可以直接吞掉后面的一个字符。

Code

#include <cstdio>
#include <cstring>
const int maxn = 1000 + 5;
const int maxm = 100 + 5;
struct question {
    char answer[6];
    int score, c1, c2;
} que[maxm];
char str[1005];
int n, m, times[maxm] = {0};

int main() {
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= m; i++) {
        scanf("%d %d %d", &que[i].score, &que[i].c1, &que[i].c2);
        char c;
        getchar();
        int j;
        for(j = 0; j < que[i].c2; j++) {
            scanf("%c%*c", &que[i].answer[j]);
        }
        que[i].answer[j] = '\0';
    }
    for(int i = 1; i <= n; i++) {
        fgets(str, 1005, stdin);
        char ans[6];
        int score = 0, ti, qnum = 1;
        for(int j = 0; str[j] != '\0'; j++) {
            if(str[j] == '(') {
                int k, tmp = 0;
                for(k = j + 1; str[k] != ')'; k++) {
                    if('0' <= str[k] && str[k] <= '9') {
                        ti = str[k] - '0';
                    }
                    if('a' <= str[k] && str[k] <= 'z') {
                        ans[tmp++] = str[k];
                    }
                }
                ans[tmp] = '\0';
                j = k + 1;
                if(ti != que[qnum].c2 || strcmp(que[qnum].answer, ans) != 0) times[qnum]++;
                else score += que[qnum].score;
                qnum++;
            }
        }
        printf("%d\n", score);
    }
    int max = times[0];
    for(int i = 1; i <= m; i++) {
        if(max < times[i]) max = times[i];
    }
    if(max) {
        printf("%d", max);
        for(int i = 1; i <= m; i++) {
            if(max == times[i]) printf(" %d", i);
        }
    } else printf("Too simple");
    return 0;
}

1059 C语言竞赛

Analysis

参赛者的 ID 跟排名是一次性给出的，可以直接用排名当作下标来保存 ID。要区分是否查询过了，可以设置一个 bool 数组，查询过的元素就标记为true。这个题有 2 个测试点是卡时间的，C 语言的strcmp和 C++ 的string可能无法通过，所以直接使用 map 就行了。

Code

use char[]

#include <cstdio>
#include <cstring>
#include <cmath>
const int maxn = 10000 + 5;
char stu[maxn][6];
int n, k;
bool check[maxn] = {false};
bool isprime(int a) {
    if(a <= 1) return false;
    else {
        for(int i = 2; i <= sqrt(a); i++) {
            if(a % i == 0) return false;
        }
    }
    return true;
}
int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        scanf("%s", stu[i]);
    }
    scanf("%d", &k);
    char str[6];
    while(k--) {
        scanf("%s", str);
        int rank = 1;
        bool flag1 = false;
        for(; rank <= n; rank++) {
            if(strcmp(str, stu[rank]) == 0) {
                flag1 = true;
                break;
            }
        }
        printf("%s: ", str);
        if(flag1) {
            if(!check[rank]) {
                if(rank == 1) printf("Mystery Award\n");
                else if(isprime(rank)) printf("Minion\n");
                else printf("Chocolate\n");
                check[rank] = true;
            } else printf("Checked\n");
        } else printf("Are you kidding?\n");
    }
    return 0;
}

use string

#include <iostream>
#include <string>
#include <cmath>
using namespace std;
const int maxn = 10000 + 5;
bool check[maxn] = {false};
int n, k;
string str[maxn];
bool isprime(int a) {
    if(a <= 1) return false;
    else {
        for(int i = 2; i <= sqrt(a); i++) {
            if(a % i == 0) return false;
        }
    }
    return true;
}
int main() {
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> str[i];
    }
    cin >> k;
    string s;
    while(k--){
        cin >> s;
        int rank = 1;
        bool flag = false;
        for(; rank <= n; rank++) {
            if(s == str[rank]) {
                flag = true;
                break;
            }
        }
        cout << s << ": ";
        if(flag) {
            if(!check[rank]) {
                if(rank == 1) cout << "Mystery Award";
                else if(isprime(rank)) cout << "Minion";
                else cout << "Chocolate";
                check[rank] = true;
            } else cout << "Checked";
        } else cout << "Are you kidding?";
        cout << endl;
    }
    return 0;
}

use map

#include <iostream>
#include <map>
#include <cmath>
using namespace std;
const int maxn = 10000 + 5;
map<string, int> stu;
int n, k;
bool check[maxn] = {false};
bool isprime(int a) {
    if(a <= 1) return false;
    else {
        for(int i = 2; i <= sqrt(a); i++) {
            if(a % i == 0) return false;
        }
    }
    return true;
}
int main() {
    cin >> n;
    string str;
    for(int i = 1; i <= n; i++) {
        cin >> str;
        stu[str] = i;
    }
    cin >> k;
    while(k--) {
        cin >> str;
        cout << str << ": ";
        map<string, int>::iterator it = stu.find(str); 
        if(it == stu.end()) cout << "Are you kidding?";
        else {
            if(!check[it->second]) {
                if(it->second == 1) cout << "Mystery Award";
                else if(isprime(it->second)) cout<< "Minion";
                else cout<< "Chocolate";
                check[it->second] = true;
            } else cout << "Checked";
        }
        cout << endl;
    }
    return 0;
}

1060 爱丁顿数

Analysis

这道题参考了1060. 爱丁顿数(25)-PAT乙级真题。
总感觉这个题有点像脑筋急转弯😓...
首先要明确的是，E 可能并不是给出来的数，能确定的就是 E 肯定要小于天数。以6 7 6 9 3这组数据为例，这组数据的 E 应该等于 4，也即连续 4 天骑车超过 4 英里（6、7、6、9）。理解这个点了后，设置数组下标从 1 开始（假设是第一天）。先将所给序列降序排序，然后让ans = 0，遍历数组，每存在一个num[p] > p的数（就是骑车的公里数大于天数的这类数），就让ans++，最后结果就是所求 E。
PS：自己做的时候，排完序，拿到 13 分，就没思路了，主要是不明白 E 可能并不是数组中的数，应该多思考一下。

Code

#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 100000 + 5;
int n, num[maxn] = {0};
bool cmp(int a, int b) {
    return a > b;
}
int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &num[i]);
    }
    sort(num + 1, num + n + 1, cmp);
    int ans = 0, p = 1;
    while(ans <= n && num[p] > p) {
        ans++;
        p++;
    }
    printf("%d", ans);
    return 0;
}

1061 判断题

Analysis

题目稍微有点绕，大致意思就像老师改卷一样，正确打勾，错误打叉，然后把对的题目的分数加到一起，从而得到每位学生的总分。

Code

#include <cstdio>
const int maxn = 100 + 5;
const int maxm = 100 + 5;
int scores[maxm] = {0}, ans[maxm] = {0};

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= m; i++) {
        scanf("%d", &scores[i]);
    }
    for(int i = 1; i <= m; i++) {
        scanf("%d", &ans[i]);
    }
    while(n--) {
        int gre = 0, tmp;
        for(int i = 1; i <= m; i++) {
            scanf("%d", &tmp);
            if(tmp == ans[i]) gre += scores[i];
        }
        printf("%d\n", gre);
    }
    return 0;
}

1062 最简分数

Analysis

这个题有两个思路，一种是直接从分数的角度思考，另外一种是从小数的角度思考，分开来看：

从分数的角度思考，那么就要求出两个分母和题目给定的分母，这 3 个数的最小公倍数。以这个数作为公共分母，然后再从小的分子开始遍历，找出分母为 k 的最简分数即可。从分数的角度思考，一定要明确思路，不然容易被绕糊涂。
从小数的角度思考就简单一点了，先将给定的分数转化为小数，然后从 1 到 k 遍历所有分数（题目给定的数据肯定没有大于 1 的假分数，这个其实很容易猜到），满足不能与 k 约分（即没有最小公约数）并在给定范围内的数即为所求的解。

Code

use fraction

#include <cstdio>
int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}
int lcm(int a, int b) {
    int tmp = gcd(a, b);
    return a * b / tmp;
}

int main() {
    int n1, m1, n2, m2, k;
    scanf("%d/%d %d/%d %d", &n1, &m1, &n2, &m2, &k);
    int t1 = lcm(m1, m2);
    int t2 = lcm(t1, k);
    if(n1 > n2) {
        int tmp = n1;
        n1 = n2;
        n2 = tmp;
    }
    int left = n1 * t2 / m1, right = n2 * t2 / m2, tmp = t2 / k;
    bool flag = true;
    for(int i = left + 1; i < right; i++) {
        if(i % tmp == 0 && gcd(i / tmp, k) == 1) {
            if(flag) {
                printf("%d/%d", i / tmp, k);
                flag = false;
            } else {
                printf(" %d/%d", i / tmp, k);
            }
        }
    }
    return 0;
}

/*
in:
7/18 13/20 12
out:
5/12 7/12

in:
7/18 19/20 12
out:
5/12 7/12 11/12

in:
1/8 7/8 8
out:
3/8 5/8

in:
1/8 7/8 2
out:
1/2

in:
1/18 13/20 12
out:
1/12 5/12 7/12

in:
1/2 3/4 8
out:
5/8

in:
1/10 1/2 5
out:
1/5 2/5
*/

use decimals

参考：PAT乙级练习题 1062 最简分数 (20 point(s))

#include <stdio.h>

int hasCommonDivisor(int i, int k) {
    for (int j = 2; j <= i; ++j) {
        if (i % j == 0 && k % j == 0) {
            return 1;
        }
    }
    return 0;
}

int main() {
    int N1, M1, N2, M2, K;
    scanf("%d/%d %d/%d %d", &N1, &M1, &N2, &M2, &K);
    double d1 = N1 * 1.0 / M1;
    double d2 = N2 * 1.0 / M2;
    if (d1 > d2) {
        double tmp = d1;
        d1 = d2;
        d2 = tmp;
    }

    int isFirst = 1;
    for (int i = 1; i <= K; i++) {
        if (!hasCommonDivisor(i, K)) {
            double di = i * 1.0 / K;
            if (di > d1 && di < d2) {
                if(isFirst){
                    printf("%d/%d", i, K);
                    isFirst = 0;
                }else{
                    printf(" %d/%d", i, K);
                }

            }
        }
    }
    return 0;
}

1063 计算谱半径

Analysis

输出结果是浮点数，那么直接用浮点数就好了，避免可能会出现的误差，~~也可以直接用pow函数，就可以省去判断正负了~~直接乘就行。

Code

#include <cstdio>
#include <cmath>

int main() {
    int n;
    scanf("%d", &n);
    double rep, imp, pradius = 0.0, tmp;
    while(n--) {
        scanf("%lf %lf", &rep, &imp);
        tmp = sqrt(rep * rep + imp * imp);
        if(tmp > pradius) pradius = tmp;
    }
    printf("%.2lf", pradius);
    return 0;
}

1064 朋友数

Analysis

这个题只需要统计可能的“朋友数”即可，利用散列，统计“朋友数”出现的次数即可。

Code

#include <cstdio>
#include <cctype>
#include <cstring>
int times[40] = {0};
int main() {
    int n;
    scanf("%d", &n);
    char num[6];
    while(n--) {
        scanf("%s", num);
        int tmp = 0, digit = 0, len = strlen(num);
        for(int i = len - 1; i >= 0; i--) {
            if(isdigit(num[i])) tmp += num[i] - '0';	
        }
        times[tmp]++;
    }
    int cnt = 0;
    for(int i = 0; i < 40; i++) {
        if(times[i] > 0) cnt++;
    }
    printf("%d\n", cnt);
    bool flag = true;
    for(int i = 0; i < 40; i++) {
        if(times[i] > 0) {
            if(flag) {
                printf("%d", i);
                flag = false;
            } else printf(" %d", i);
        }
    }
    return 0;
} 

/*
in:
10
123 899 51 998 27 33 36 12 0 0
out:
5
0 3 6 9 26

*/

1065 单身狗

Analysis

利用 map 建立夫妻关系的映射，同时利用 set，保存这些非单身狗（莫名戳中笑点😂）和派对总人数。然后利用夫妻关系，找出派对中夫妻双方只出席了一方的单身狗；接着再利用保存的非单身狗信息，确定剩下本来就是单身狗的人。
PS：直接用 map 和 set 也能过

Code

#include <iostream>
#include <set>
#include <unordered_map>
using namespace std;
unordered_map<string, string> couples;
set<string> peo, sdog, notdog;
int n, m;

int main() {
    cin >> n;
    string hs_tmp, wi_tmp, people;
    while(n--) {
        cin >> hs_tmp >> wi_tmp;
        couples[hs_tmp] = wi_tmp;
        notdog.insert(hs_tmp), notdog.insert(wi_tmp);
    }
    cin >> m;
    for(int i = 0; i < m; i++) {
        cin >> people;
        peo.insert(people);
    }
    for(unordered_map<string, string>::iterator it = couples.begin(); it != couples.end(); it++) {
        hs_tmp = it->first, wi_tmp = it->second;
        if(peo.find(hs_tmp) != peo.end() && peo.find(wi_tmp) == peo.end()) sdog.insert(hs_tmp);
        else if(peo.find(hs_tmp) == peo.end() && peo.find(wi_tmp) != peo.end()) sdog.insert(wi_tmp);
    }
    for(set<string>::iterator it = peo.begin(); it != peo.end(); it++) {
        if(notdog.find(*it) != notdog.end()) continue;
        else sdog.insert(*it);
    }
    cout << sdog.size() << endl;
    set<string>::iterator it = sdog.begin();
    for(int i = 0; i < sdog.size(); i++) {
        cout << *it;
        if(i < sdog.size() - 1) cout << ' ';
        it++;
    }
    return 0;
}

1066 图像过滤

Analysis

这道题的意思，其实就是图像的灰度化处理（当然这里的比较简单）。Matlab 内有直接进行此种操作的图像处理函数，可以直接调用。注意 N 和 M 的最大值，最后一个测试点是最大值测试。

这个题其实开不开数组都可以。

Code

#include <stdio.h>
#define MAXN 500
#define MAXM 500

int main(int argc, char const *argv[]) {
    int r, c, M, N, A, B, gray_value;
    scanf("%d %d %d %d %d", &M, &N, &A, &B, &gray_value);
    int image_array[MAXM][MAXN];
    for(r = 0; r < M; r++) {
        for(c = 0; c < N; c++) {
            scanf("%d", &image_array[r][c]);
            if(A <= image_array[r][c] && image_array[r][c] <= B) {
                image_array[r][c] = gray_value;
            }
        }
    }
    for(r = 0; r < M; r++) {
        for(c = 0; c < N; c++) {
            printf("%03d", image_array[r][c]);
            if(c == N-1) {
                putchar('\n');
            } else {
                putchar(' ');
            }
        }
    }
    return 0;
}

1067 试密码

Analysis

这个题看着简单，其实有一点细节信息：

正确的密码不包含空格，错误的密码就会包含了，这是 AC 这道题目的关键。
#不被认为输入，~~#...#也不被认为是输入~~。

Code

#include <iostream>
using namespace std;

int main() {
    string password, str;
    int N;
    cin >> password >> N;
    int attempt = 1;
    bool flag = false;
    getchar();
    while(1) {
        getline(cin, str);
        if(str == "#") break;
        if(str == password && attempt <= N) {
            cout << "Welcome in" << endl;
            break;
        }
        if(str != password && attempt <= N) {
            cout << "Wrong password: " << str << endl;
            if(attempt == N){
                cout << "Account locked" << endl;
                break;
            }
        }
        attempt++;
    }
    return 0;
}

1068 万绿丛中一点红

Analysis

题意不难理解，但是有点细节需要注意：

选出来的点一定要是唯一存在的。
选出来的点与其相邻的八个点的色差的绝对值一定要大于 TOL。
输入是列、行，输出也是。

Code

version 1

这段代码是自己写的，一开始没想到竟然能开这么大的数组，之所以下标从 1 开始是为了与题目保持一致，也可以避免判断时越界访问。实际上，数组下标是可以为负的，下标从 0 开始也能 AC ，但这段代码就不那么严谨了，题目的测试数据可能也不是那么严谨。

#include <cstdio>
#include <cmath>
typedef long long LL;
const int maxn = 1000 + 5;
const int maxm = 1000 + 5;
LL M, N, TOL, image[maxm][maxn] = {0};
int times[18000000] = {0};

int main() {
    scanf("%lld %lld %lld", &M, &N, &TOL);
    for(int i = 1; i <= N; i++) {
        for(int j = 1; j <= M; j++) {
            scanf("%lld", &image[i][j]);
            times[image[i][j]]++;
        }
    }
    LL x, y, cnt = 0;
    x = y = 1;
    for(int i = 1; i <= N; i++) {
        for(int j = 1; j <= M; j++) {
            LL t = image[i][j];
            if(times[image[i][j]] == 1 
                && abs(t - image[i - 1][j - 1]) > TOL && abs(t - image[i - 1][j]) > TOL
                && abs(t - image[i - 1][j + 1]) > TOL && abs(t - image[i][j - 1]) > TOL
                && abs(t - image[i][j + 1]) > TOL && abs(t - image[i + 1][j - 1]) > TOL
                && abs(t - image[i + 1][j]) > TOL && abs(t - image[i + 1][j + 1]) > TOL  ) {
                x = j, y = i;
                cnt++;
            }
        }
    }
    if(cnt == 1)  printf("(%lld, %lld): %lld", x, y, image[y][x]);
    else if(cnt > 1) printf("Not Unique");
    else printf("Not Exist");
    return 0;
}

version 2

这段代码参考：1068 万绿丛中一点红（20 分），其中判断是否唯一的函数做了限定，这样进行判断的点一定是数组内的点。

#include <iostream>
#include <map>
using namespace std;
int image[1005][1005];
map<int, int> isappear; 
int dd[8][2] = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};
int m, n, tol;
bool isonly(int x, int y) {
    for(int i = 0; i < 8; i++) {
        int xx = x + dd[i][0];
        int yy = y + dd[i][1];
        if(xx >= 0 && xx < n && yy >= 0 && yy < m && image[x][y] - image[xx][yy] >= -tol
            && image[x][y] - image[xx][yy] <= tol) return false;
    }
    return true;
}
int main() {
    cin >> m >> n >> tol;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            cin >> image[i][j];
            isappear[image[i][j]]++;
        }
    }
    int cnt = 0, x = 0, y = 0;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if(isappear[image[i][j]] == 1 && isonly(i, j)) {
                cnt++;
                x = j + 1, y = i + 1;
            }
        }
    }
    if(cnt == 1) cout << "(" << x << ", " << y << "): " << image[y - 1][x - 1];
    else if(cnt > 1) cout << "Not Unique";
    else cout << "Not Exist";
    return 0;
}

1069 微博转发抽奖

Analysis

用 map 来表示是否中过奖，只要没有人中奖就输出Keep going...，如果不用vector<string>也可以用char str[][]。

Code

#include <iostream>
#include <vector>
#include <map>
using namespace std;
vector<string> acc;
map<string, int> done;
int main() {
    int m, n, s;
    cin >> m >> n >> s;
    string str;
    for(int i = 0; i < m; i++) {
        cin >> str;
        acc.push_back(str);
    }
    vector<string>::iterator it = acc.begin();
    if(s > m) {
        cout << "Keep going...";
    } else {
        for(int i = s - 1; i < m; i += n) {
            str = *(it + i);
            if(done[str] == 0) {
                cout << str << endl;
                done[str]++;
            } else {
                for(i++; i < m; i++) {
                    str = *(it + i);
                    if(done[str] == 0) {
                        done[str]++;
                        cout << str << endl;
                        break;
                    }
                }
            }
        }
    }
    return 0;
}

1070 结绳

Analysis

这是道考察贪心的题目，明确了思想之后就比较简单，没明确就有点折磨人。从题目的来看，无法看出需要使用每一根绳子，按照样例，容易让人想到的直接选取两个最长的绳子结成一个就好了。实际上，这也是自己一开始想到的贪心思想，认为头两次分别找当前备选绳段中的最长段，结成一段就完事了。事实上需要将每根绳段都用上，并且结绳次数越多，绳段就会被对折的越短。换句话说，需要先对折短绳段，然后再对折长绳段。按照这样的思路，要求每次挑选的绳段尽可能短，这就是这个题的贪心思想。

Code

#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 10000 + 5;
int num[maxn] = {0};
int main() {
    int n;
    cin >> n;
    for(int i = 0; i < n; i++) {
        cin >> num[i];
    }
    sort(num, num + n);
    int res = num[0]; 
    for(int i = 1; i < n; i++) {
        res = (res + num[i]) / 2;
    }
    cout << res;
    return 0;
}

1071 小赌怡情

Analysis

这道题的题目比较长，耐心一点，仔细读完，按照题目给定的四种情况的处理方式来写代码，应该就 OK 了，注意输光后（筹码x <= 0），就可以直接退出了。还有一点，题目给的输出中 total 前要有 1 个空格，但是样例是 2 个空格。

Code

#include <cstdio>

int main(int argc, char const *argv[]) {
    int T, K, n1, b, t, n2, remains;
    scanf("%d %d", &T, &K);
    remains = T;
    while(K--) {
        scanf("%d %d %d %d", &n1, &b, &t, &n2);
        if(remains <= 0) {
            printf("Game Over.\n");
            break;
        }
        if(t > remains) {
            printf("Not enough tokens.  Total = %d.\n", remains);
            continue;
        }
        if((n1 > n2 && b == 0) || (n1 < n2 && b == 1)) {
            remains += t;
            printf("Win %d!  ", t);
        } else {
            remains -= t;
            printf("Lose %d.  ", t);
        }
        printf("Total = %d.\n", remains);
    }
    return 0;
}

1072 开学寄语

Analysis

用set来保存被缴物品信息，用vector<string>来保存含有被缴物品的学生物品信息，重复遍历一次就可以输出被缴物品信息了。

Code

#include <iostream>
#include <vector>
#include <set>
using namespace std;
int n, m;
const int maxn = 1000 + 5;
vector<string> stu[maxn];
set<string> ban;

int main() {
    cin >> n >> m;
    string str, name;
    for(int i = 0; i < m; i++) {
        cin >> str;
        ban.insert(str);
    }
    int snum = 0, bnum = 0, tmp;
    for(int i = 0; i < n; i++) {
        cin >> name >> tmp;
        for(int j = 0; j < tmp; j++) {
            cin >> str;
            if(ban.find(str) != ban.end()) {
                stu[i].push_back(str);
                bnum++;
            }
        }
        if(stu[i].size() != 0) {
            cout << name << ":";
            snum++;
            for(vector<string>::iterator it = stu[i].begin(); it != stu[i].end(); it++) {
                cout << " " << *it;
            }
            cout << endl;
        }
    }
    cout << snum << ' ' << bnum << endl;
    return 0;
}

1073 多选题常见计分法

Analysis

这个题相当坑，很费时间，本质上是跟 1058 一样的题目，但是处理起来要麻烦的多。因为最终要输出选项的错误次数，很直接就会想到逐个比较，所以用 set 来保存正确答案。至于选项的错误次数，就交给一个二维数组来保存。题目所给的每个选择题的选项个数这个信息，基本上无用。接着就是一些细节了：

非正确选项选了算错误，漏选的正确选项也算在错误选项内
题目最后要求输出的错误次数，不是题目的错误次数，而是这个选项的错误次数
由于有()、空格的存在，字符串的空间最好开大一点

自己在第二个细节的地方卡了很久，后来终于反应过来是自己题意理解错了。

Code

#include <cstdio>
#include <set>
using namespace std;
const int maxm = 100 + 5;
set<char> answer[maxm];
int que[maxm] = {0}, wrong_opt[maxm][6] = {0};
double scores[maxm] = {0.0};
char stu[10005];

int main() {
    int n, m, tmp;
    char ctmp;
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= m; i++) {
        scanf("%lf %d %d%*c", &scores[i], &que[i], &tmp);
        for(int j = 0; j < tmp; j++) {
            scanf("%c%*c", &ctmp);
            answer[i].insert(ctmp);
        }
    }
    for(int i = 1; i <= n; i++) {
        int qnum = 1;
        double sum = 0.0;
        fgets(stu, 10005, stdin);
        for(int j = 0; stu[j] != '\0'; j++) {
            if(stu[j] == '(') {
                bool isappear[6] = {false}, flag = true;
                tmp = stu[++j] - '0';
                if(tmp > answer[qnum].size()) flag = false;
                for(j++; stu[j] != ')'; j++) {
                    if(stu[j] == ' ') continue;
                    else {
                        ctmp = stu[j];
                        if(answer[qnum].find(ctmp) == answer[qnum].end()) {
                            flag = false;
                            wrong_opt[qnum][ctmp - 'a']++;
                        }
                        isappear[ctmp - 'a'] = true;
                    }
                }
                set<char>::iterator it = answer[qnum].begin();
                for(; it != answer[qnum].end(); it++) {
                    if(!isappear[*it - 'a']) wrong_opt[qnum][*it - 'a']++;
                }
                if(flag && tmp == answer[qnum].size()) sum += scores[qnum];
                else if(flag && tmp < answer[qnum].size()) sum += (scores[qnum] / 2.0);
                qnum++;
            }
        }
        printf("%.1lf\n", sum);
    }
    int max = wrong_opt[1][0];
    for(int i = 1; i <= m; i++) {
        for(int j = 0; j < 5; j++) {
            max = max > wrong_opt[i][j] ? max : wrong_opt[i][j];
        }
    }
    if(max == 0) {
        printf("Too simple\n");
    } else {
        for(int i = 1; i <= m; i++) {
            for(int j = 0; j < 5; j++) {
                if(max == wrong_opt[i][j]) {
                    printf("%d %d-%c\n", max, i, j + 'a');
                }
            }
        }
    }
    return 0;
}

1074 宇宙无敌加法器

Analysis

这个题目，自己的思路比较复杂，需要注意两个特殊点：

结果是 0 时，也要输出 0。
超过 20 位后的计算按十进制进行计算，要判断 20 位之后的计算是否存在进位。

Code

version 1

#include <cstdio>
#include <cstring>
const int maxn = 20 + 5;
char tab[maxn], num1[maxn], num2[maxn];
int ans[maxn] = {0}, digit[10] = {10, 0, 2, 3, 4, 5, 6, 7, 8, 9};
void sreverse(char *str) {
    int len = strlen(str);
    for(int i = 0; i < len / 2; i++) {
        char tmp = str[i];
        str[i] = str[len - i - 1];
        str[len - i - 1] = tmp;
    }
}
int main() {
    scanf("%s\n%s\n%s", tab, num1, num2);
    sreverse(num1), sreverse(num2), sreverse(tab);
    int tmp, carry = 0, i;
    for(i = 0; num1[i] != '\0' && num2[i] != '\0'; i++) {
        tmp = num1[i] + num2[i] - 2 * '0' + carry;
        if(i < 20 && tmp >= digit[tab[i] - '0']) {
            tmp = tmp - digit[tab[i] - '0'];
            carry = 1;
        } else if(i >= 20 && tmp >= 10) {
            tmp = tmp - 10;
            carry = 1;
        } else carry = 0;
        ans[i] = tmp;
    }
    while(num1[i] != '\0') {
        tmp = num1[i] - '0' + carry;
        if(i < 20 && tmp >= digit[tab[i] - '0']) {
            tmp = tmp - digit[tab[i] - '0'];
            carry = 1;
        } else if(i >= 20 && tmp >= 10) {
            tmp = tmp - 10;
            carry = 1;
        } else carry = 0;
        ans[i++] = tmp;
    }
    while(num2[i] != '\0') {
        tmp = num2[i] - '0' + carry;
        if(i < 20 && tmp >= digit[tab[i] - '0']) {
            tmp = tmp - digit[tab[i] - '0'];
            carry = 1;
        } else if(i >= 20 && tmp >= 10) {
            tmp = tmp - 10;
            carry = 1;
        } else carry = 0;
        ans[i++] = tmp;
    }
    if(carry != 0) ans[i] = carry;
    while(ans[i] == 0) i--;
    if(i < 0) printf("0");
    else {
        for(int j = i; j >= 0; j--) {
            printf("%d", ans[j]);
        }
    }
    return 0;
}

/*
in:
30527
06203
415
out:
7201

in:
22
11
11
out:
110

in:
08
77
17
out:
96

in:
22222222222222222222
11111111111111111111
00000000000000000001
out:
100000000000000000000

in:
22222222222222222222
11111111111111111111
10000000000000000001
out:
110000000000000000000

in:
22222222222222222222
211111111111111111111
110000000000000000001
out:
410000000000000000000

in:
22222222222222222222
8800000000000000000000
8800000000000000000000
out:
17600000000000000000000
*/

version 2

这个思路参考：1074. 宇宙无敌加法器(20)-PAT乙级真题
从这个思路可以获得一点收获：

这类题目，都可以先扩展成最长的字符串后再进行计算
与其分情况判断 carry 是否为 0，不如直接用除法来获得
string 类的初始化用法，以及其运算符的用法

#include <iostream>
using namespace std;

int main() {
    string s, s1, s2, ans;
    int carry = 0, flag = 0;
    cin >> s >> s1 >> s2;
    ans = s;
    string ss1(s.length() - s1.length(), '0');
    s1 = ss1 + s1;
    string ss2(s.length() - s2.length(), '0');
    s2 = ss2 + s2;
    for(int i = s.length() - 1; i >= 0; i--) {
        int mod = s[i] == '0' ? 10 : (s[i] - '0');
        ans[i] = (s1[i] + s2[i] - 2 * '0' + carry) % mod + '0';
        carry = (s1[i] + s2[i] - 2 * '0' + carry) / mod;
    }
    if(carry != 0) ans = '1' + ans;
    for(int i = 0; i < ans.size(); i++) {
        if(ans[i] != '0' || flag == 1) {
            flag = 1;
            cout << ans[i];
        }
    }
    if(flag == 0) cout << 0;
    return 0;
}

1075 链表元素分类

Analysis

按照题目意思，从最后输出的结果上来看，特定区间内的结点的相对位置实际上并没有发生改变，就是一开始输入的顺序，所以给每个结点设置一个 order 来记录位置。除此之外，这个 order 还可以用来去除无效结点。然后，用 sort 排序除去无效的结点，再挑出符合条件的结点，输出就行了，注意一下最后一个结点的 next 是 -1。

老实说，这个题用排序做，感觉有点投机取巧，因为压根就没有做题目要求的事情，但依然可以 AC 。

如果一本正经的从链表的角度思考，那么需要遍历链表，然后挑出符合条件的结点，同样需要 3 个循环来完成。挑出结点的步骤，建议重新弄一个结构体数组来完成，同样的，仅仅挑出结点就行了，不需要再修改next和address了。

Code

#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 100000 + 5;
struct Node {
    int address, data, next;
    int order;
} node[maxn], nod[maxn];
bool cmp(Node a, Node b) {
    return a.order < b.order;
}
int main() {
    for(int i = 0; i < maxn; i++) {
        node[i].order = maxn;
    }
    int begin, n, k, address;
    scanf("%d %d %d", &begin, &n, &k);
    for(int i = 0; i < n; i++) {
        scanf("%d", &address);
        scanf("%d %d", &node[address].data, &node[address].next);
        node[address].address = address;
    }
    int p = begin, count = 0;
    while(p != -1) {
        node[p].order = count++;
        p = node[p].next;
    }
    sort(node, node + maxn, cmp);
    n = count;
    count = 0;
    for(int i = 0; i < n; i++) {
        if(node[i].data < 0) nod[count++] = node[i];
    }
    for(int i = 0; i < n; i++) {
        if(0 <= node[i].data && node[i].data <= k) nod[count++] = node[i];
    }
    for(int i = 0; i < n; i++) {
        if(node[i].data > k) nod[count++] = node[i];
    }
    for(int i = 0; i < count; i++) {
        if(i != count - 1) printf("%05d %d %05d\n", nod[i].address, nod[i].data, nod[i + 1].address);
        else printf("%05d %d -1\n", nod[i].address, nod[i].data);
    }
    return 0;
}

1076 Wifi密码

Analysis

为了促进学生学习，这题也真是难为老师了，哈哈~
此题不难，不过需要细心一点，输入的格式是确定好了的。如果每次输入利用字符来做处理，则需要注意回车符\n不要被输入函数获取到了（测试点2就是这样）。
可以按照字符串的思路去处理，并且循环进行的次数可能会少一些。
这个题发现了一个有点意思的思路：PAT Basic 1076. Wifi密码 (15) (C语言实现)。

Code

#include <stdio.h>
#define MAXN 105
int Wifi_Password[4] = {1, 2, 3, 4};

int main(int argc, char const *argv[]) {
    int i, N, count = 0;
    scanf("%d%*c", &N);
    char Answers[MAXN], temp, flag;
    for(i = 0; i < 4 * N; i++) {
        scanf("%c-%c%*c", &temp, &flag);
        if(flag == 'T') {
            Answers[count++] = temp;
        }
    }
    for(i = 0; i < count; i++) {
        printf("%d", Wifi_Password[Answers[i] - 'A']);
    }
    putchar('\n');
    return 0;
}

1077 互评成绩计算

Analysis

题意很明确，唯一的坑点在四舍五入上。

Code

#include <cstdio>

int main() {
    int n, m, tea_score;
    scanf("%d %d", &n, &m);
    for(int i = 0; i < n; i++) {
        scanf("%d", &tea_score);
        int sum = 0, valid = 0, tmp, max = -1, min = m + 1;
        for(int j = 0; j < n - 1; j++) {
            scanf("%d", &tmp);
            if(0 <= tmp && tmp <= m) {
                sum += tmp;
                valid++;
                if(tmp > max) max = tmp;
                if(tmp < min) min = tmp;
            }
        }
        double ans = (double)(sum - max - min) / (valid - 2);
        printf("%d\n", (int)((ans + tea_score) / 2 + 0.5));
    }
    return 0;
}

1078 字符串压缩与解压

Analysis

C、D 分别对应压缩与解压两种模式，分开进行就可以了，空格与字母的处理方式是一样的。

Code

#include <cstdio>
#include <cctype>
char str[2005], mode;

int main() {
    scanf("%c%*c", &mode);
    fgets(str, 2005, stdin);
    if(mode == 'C') {
        for(int i = 0; str[i] != '\0'; i++) {
            char tmp = str[i];
            int count = 1, j;
            for(j = i + 1; str[j] == tmp; j++) {
                count++;
            }
            if(count == 1) printf("%c", tmp);
            else printf("%d%c", count, tmp);
            i = --j;
        }
    } else if(mode == 'D') {
        for(int i = 0; str[i] != '\0'; i++) {
            int count = 0, j;
            if(isdigit(str[i])) {
                count = str[i] - '0';
                for(j = i + 1; isdigit(str[j]); j++) {
                    count = count * 10 + str[j] - '0';
                }
                for(int k = 0; k < count; k++) {
                    printf("%c", str[j]);
                }
                i = j;
            } else printf("%c", str[i]);
        }
    }
    return 0;
}

1079 延迟的回文数

Analysis

这个题主要在考察回文数的判断和大数加法，从数组下标 0 开始保存数的低位。这样会好算一点。另外，注意个位数也是回文数。

数组逆置的函数可以借助 C++ 的 reverse 函数完成。

Code

#include <cstdio>
#include <cctype>
const int maxn = 1000 + 5;
int num[maxn] = {0}, temp[maxn] = {0};
bool ispalindromic(int *a, int count) {
    if(count == 1) return true;
    for(int i = 0; i < count / 2; i++) {
        if(a[i] != a[count - i - 1]) return false;
    }
    return true;
}
void shownum(int *a, int count) {
    for(int i = count - 1; i >= 0; i--) {
        printf("%d", a[i]);
    }
}
void arr_reverse(int *a, int *b, int count) {
    for(int i = 0; i < count; i++) {
        a[i] = b[count - i - 1];
    }
}
int main() {
    char c;
    int count = 0;
    while((c = getchar()) != '\n') {
        temp[count++] = c - '0';
    }
    arr_reverse(num, temp, count);
    int times = 0;
    while(times++ < 10) {
        if(ispalindromic(num, count)) {
            shownum(num, count);
            printf(" is a palindromic number.\n");
            break;
        } else {
            shownum(num, count);
            printf(" + ");
            shownum(temp, count);
            int carry = 0, tmp;
            for(int i = 0; i < count; i++) {
                tmp = num[i];
                num[i] = (tmp + temp[i] + carry) % 10;
                carry = (tmp + temp[i] + carry) / 10;
            }
            if(carry) num[count++] = carry;
            printf(" = ");
            shownum(num, count);
            printf("\n");
            arr_reverse(temp, num, count);
        }
    }
    if(times >= 10) printf("Not found in 10 iterations.\n");
    return 0;
}

1080 MOOC期终成绩

Analysis

需要处理的数据太多，直接构造一个新的结构体。开始读入数据之前，全部默认为没有考试的状态（全部置为 -1，输出的时候就可以直接输出了），然后读入数据，计算最终成绩，第一顺序是成绩递减，第二顺序是学号递增。
因为每次考试的成绩是分别给出的，所以为了在处理下一次考试的数据时找到对应的学生，所以需要用 map 建立学生学号与下标的对应关系。
另外，计算最终成绩需要四舍五入。

Code

#include <iostream>
#include <algorithm>
#include <map>
using namespace std;
const int maxn = 100000 + 5;
struct student {
    string name;
    int gp, gmt, gf, g;
} stu[maxn];
map<string, int> name2num;
void init() {
    for(int i = 0; i < maxn; i++) {
        stu[i].g = stu[i].gf = stu[i].gmt = stu[i].gp = -1;
    }
}
bool cmp(student a, student b) {
    if(a.g != b.g) return a.g > b.g;
    else return a.name < b.name;
}
int main() {
    init();
    int p, m, n, count = 0, tmp;
    cin >> p >> m >> n;
    string str;
    for(int i = 0; i < p; i++) {
        cin >> str >> tmp;
        stu[count].name = str;
        stu[count].gp = tmp;
        name2num[str] = count++;
    }
    map<string, int>::iterator it;
    for(int i = 0; i < m; i++) {
        cin >> str >> tmp;
        it = name2num.find(str);
        if(it == name2num.end()) {
            stu[count].gmt = tmp;
            stu[count].name = str;
            name2num[str] = count++;
        } else stu[it->second].gmt = tmp;
    }
    for(int i = 0; i < n; i++) {
        cin >> str >> tmp;
        it = name2num.find(str);
        if(it == name2num.end()) {
            stu[count].gf = tmp;
            stu[count].name = str;
            name2num[str] = count++;
        } else stu[it->second].gf = tmp;
    }
    int a, b;
    for(int i = 0; i < count; i++) {
        if(stu[i].gp < 200) continue;
        else {
            a = stu[i].gmt, b = stu[i].gf;
            if(a <= b) stu[i].g = b;
            else stu[i].g = (int)((a * 0.4 + b * 0.6) + 0.5);
        }
    }
    sort(stu, stu + count, cmp);
    for(int i = 0; i < count; i++) {
        if(stu[i].g >= 60) {
            cout << stu[i].name << ' ' << stu[i].gp << ' ' << stu[i].gmt \
                 << ' ' << stu[i].gf  << ' ' << stu[i].g << endl;
        }
    }
    return 0;
}

1081 检查密码

Analysis

此题的难点在于情况的分类，无论输入的“密码”是否合法，首先判断长度是否不小于6，紧接着，判断是否有非法字符，继而确认有无数字，最后确认有无字母。注意可能会输入带空格的字符串（测试点2）。
因为gets函数无法在用了，可以使用fgets来读入一行，或者 C++ 的getline。如果用fgets，要注意它会把最后的回车也读到字符串内，所以长度要减一。

Code

version 1

这是原来写的版本。

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#define MaxLength 85

int Validity_Check(char *password);
char Result[5][100] = {
    "Your password is tai duan le.",
    "Your password is tai luan le.",
    "Your password needs shu zi.",
    "Your password needs zi mu.",
    "Your password is wan mei.",
};

int main(int argc, char const *argv[]) {
    int flag, N;
    char Password[MaxLength];
    scanf("%d%*c", &N);
    while(N--) {
        gets(Password);	//notice the space
        flag = Validity_Check(Password);
        puts(Result[flag]);
    }
    return 0;
}

int Validity_Check(char *password) {
    int ret = 4, len = strlen(password), i;
    int num_flag, alpha_flag, invalid_flag;
    num_flag = alpha_flag = invalid_flag = 0;
    if(len >= 6) {
        for(i = 0; i < len; i++) {
            if( isdigit(password[i]) ) {
                num_flag = 1;
            } else if( isalpha(password[i]) ) {
                alpha_flag = 1;
            } else if(password[i] == '.') {
                continue;
            } else {
                invalid_flag = 1;
            }
        }
        if(invalid_flag) {
            ret = 1;
        } else if(!num_flag) {
            ret = 2;
        } else if(!alpha_flag) {
            ret = 3;
        }
    } else {
        ret = 0;
    }
    return ret;
}

version 2

这是后来写的版本。

#include <cstdio>
#include <cstring>
#include <cctype>
char str[85];
int n;

int main() {
    scanf("%d%*c", &n);
    while(n--) {
        fgets(str, 85, stdin);
        if(strlen(str) - 1 < 6) {
            printf("Your password is tai duan le.\n");
            continue;
        }
        bool flag1, flag2, flag3;
        flag1 = flag2 = flag3 = false;
        for(int i = 0; str[i] != '\0'; i++) {
            if(isalpha(str[i])) flag2 = true;
            else if(isdigit(str[i])) flag3 = true;
            else if(str[i] == '.' || str[i] == '\n') continue;
            else flag1 = true;
        }
        if(flag1) printf("Your password is tai luan le.\n");
        else if(flag2 && !flag3) printf("Your password needs shu zi.\n");
        else if(!flag2 && flag3) printf("Your password needs zi mu.\n");
        else printf("Your password is wan mei.\n");
    }
    return 0;
}

1082 射击比赛

Analysis

因为最终要输出的是编号，所以需要保存编号信息，这样的话，不如用一个新的结构体来保存需要的信息。另外，在计算离靶心的距离的时候，不需要四舍五入。

其实这个题，即便没有用 sqrt 将真正的距离算出来，也是可以 AC 的。如果设置非常相近的两组解（大概只有小数部分有几位差），可能就能卡掉很多代码了。

Code

#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxn = 10000 + 5;
struct athlete{
    char id[5];
    int x, y, dis;	
} ath[maxn];
bool cmp(athlete a, athlete b) {
    return a.dis < b.dis;
}
int main() {
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        scanf("%s %d %d", ath[i].id, &ath[i].x, &ath[i].y);
        ath[i].dis = sqrt(ath[i].x * ath[i].x + ath[i].y * ath[i].y);
    }
    sort(ath, ath + n, cmp);
    printf("%s %s", ath[0].id, ath[n - 1].id);
    return 0;
}

1083 是否存在相等的差

Analysis

这个题比较简单，借着这个题，想了想 map 能不能从大到小排列，查了下资料还真的可以。需要注意的点就是，只有重复的数才输出，换句话说，就是出现次数大于等于 2。
不过，这个题，其实直接开一个很大的数组就可以了。

Code

use map

#include <cstdio>
#include <map>
#include <algorithm>
using namespace std;
struct cmp {
    bool operator()(const int k1, const int k2) {
        return k1 > k2;
    }
};
map<int, int, cmp> mp;

int main() {
    int n, tmp;
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &tmp);
        mp[abs(tmp - i)]++;
    }
    for(map<int, int>::iterator it = mp.begin(); it != mp.end(); it++) {
        if(it->second >= 2) printf("%d %d\n", it->first, it->second);
    }
    return 0;
}

use array

#include <iostream>
#include <cmath>
using namespace std;
const int maxn = 10000 + 5;
int n, appear[maxn] = {0}, tmp;

int main() {
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> tmp;
        appear[abs(tmp - i)]++;
    }
    for(int i = 9999; i >= 0; i--) {
        if(appear[i] > 1) cout << i << ' ' << appear[i] << endl;
    }
    return 0;
}

1084 外观数列

Analysis

按照题目给的过程模拟，字符串数组一定要开大一点。

Code

#include <cstdio>
char str1[100005], str2[100005];
int n;

int main() {
    scanf("%s %d", str1, &n);
    for(int i = 1; i < n; i++) {
        int len = 0;
        for(int j = 0; str1[j] != '\0'; j++) {
            str2[len++] = str1[j];
            int count = 1, k;
            for(k = j + 1; str1[k] == str1[j]; k++) count++;
            str2[len++] = count + '0';
            j = --k;
        }
        str2[len] = '\0';
        for(int j = 0; j <= len; j++) {
            str1[j] = str2[j];
        }
    }
    printf("%s", str1);
    return 0;
}

1085 PAT单位排行

Analysis

很常规的排序题，用 map 建立学校名字与数组下标的对应关系，每读入一个分数就统计一个考生。计算学校排名时，要注意先按照学校总分排序后，再进行排名。

Code

#include <iostream>
#include <algorithm>
#include <map>
#include <string>
#include <cctype>
using namespace std;
const int maxn = 100000 + 5;
struct school{
    string name;
    int sum_score, A, B, T, rank, men;
} sch[maxn];
map<string, int> sch_name2num;
bool cmp(school a, school b) {
    if(a.sum_score != b.sum_score) return a.sum_score > b.sum_score;
    else if(a.men != b.men) return a.men < b.men;
    else return a.name < b.name;
}
void Init() {
    for(int i = 0; i < maxn; i++) {
        sch[i].sum_score = sch[i].A = sch[i].B = sch[i].T = sch[i].men =  0;
        sch[i].rank = maxn; 
    }
}
int main() {
    Init();
    int n, score, count = 0;
    cin >> n;
    string stu_name, sch_name;
    while(n--) {
        cin >> stu_name >> score >> sch_name;
        for(int i = 0; i < sch_name.length(); i++) {
            sch_name[i] = tolower(sch_name[i]);
        }
        if(sch_name2num.find(sch_name) == sch_name2num.end()) {
            sch[count].name = sch_name;
            sch_name2num[sch_name] = count++;
        }
        if(stu_name[0] == 'B') {
            sch[sch_name2num[sch_name]].B += score;
        } else if(stu_name[0] == 'A') {
            sch[sch_name2num[sch_name]].A += score;
        } else if(stu_name[0] == 'T') {
            sch[sch_name2num[sch_name]].T += score;
        }
        sch[sch_name2num[sch_name]].men++;
    }
    for(int i = 0; i < count; i++) {
        sch[i].sum_score = (int)(sch[i].B / 1.5 + sch[i].A + sch[i].T * 1.5);
    }
    sort(sch, sch + count, cmp);
    sch[0].rank = 1;
    cout << count << endl;
    cout << sch[0].rank << ' ' << sch[0].name << ' ' << sch[0].sum_score << ' ' << sch[0].men << endl; 
    for(int i = 1; i < count; i++) {
        if(sch[i].sum_score == sch[i - 1].sum_score) sch[i].rank = sch[i - 1].rank;
        else sch[i].rank = i + 1;
        cout << sch[i].rank << ' ' << sch[i].name << ' ' << sch[i].sum_score << ' ' << sch[i].men << endl; 
    }
    return 0;
}

1086 就不告诉你

Analysis

水题一道，注意$700$，不要倒着输出为$007$了。

Code

version 1

#include <stdio.h>

int main(int argc, char const *argv[]) {
    int A, B, Product, temp, digit, result = 0;
    scanf("%d %d", &A, &B);
    Product = A * B;
    temp = Product;
    while(temp) {
        digit = temp % 10;
        temp /= 10;
        result = result * 10 + digit;
    }
    printf("%d\n", result);
    return 0;
}

version 2

#include <cstdio>
char ans[10];

int main() {
    int A, B, C, len = 0;
    scanf("%d %d", &A, &B);
    C = A * B;
    do{
        ans[len++] = C % 10 + '0';
        C /= 10;
    } while(C != 0);
    ans[len] = '\0';
    char *p = ans;
    while(*p == '0') p++;
    puts(p);
    return 0;
}

1087 有多少不同的值

Analysis

出现过的数，只统计一次。

Code

version 1

#include <cstdio>
const int maxn = 20000 + 5;
int appear[maxn] = {0};
int main() {
    int N, n, ans = 0;
    scanf("%d", &N);
    for(n = 1; n <= N; n++) {
        appear[n / 2 + n / 3 + n / 5]++;
    }
    for(n = 0; n <= maxn; n++) {
        if(appear[n]) ans++;
    }
    printf("%d", ans);
    return 0;
}

version 2

如果从数学的角度思考，随着 N 的增大，计算结果也会依次增大，所以一开始的值是最小的，这样就可以不用散列，只用变量记录当前计算的值，如果比之前的小，就算是不同的值了，如下：

#include <cstdio>
int main() {
    int N, n, ans = 0, m = -1;
    scanf("%d", &N);
    for(int i = 1; i <= N; i++) {
        n = i / 2 + i / 3 + i / 5;
        if(n > m) ans++;
        m = n;
    }
    printf("%d", ans);
    return 0;
}

1088 三人行

Analysis

这个题有点像鸡兔同笼的问题，实际上就是多元方程求可能解。唯一的坑点在于，丙的值可能是个小数。另外，要以甲的最大解为准，可以从大到小进行枚举。

Code

#include <cstdio>
#include <cmath>
int m, x, y, a, b, tmp, i, j;
double c, k;
void print(double t) {
    if(m < t) printf(" Cong");
    else if(m == t) printf(" Ping");
    else printf(" Gai");
}
int main() {
    scanf("%d %d %d", &m, &x, &y);
    bool flag = false;
    for(i = 10; i <= 99; i++) {
        tmp = i;
        j = tmp % 10 * 10 + tmp / 10;
        k = abs(i - j) * 1.0 / x;
        if(j == y * k) {
            flag = true;
            a = i, b = j, c = k;
        }
    }
    if(flag) {
        printf("%d", a);
        print(a), print(b), print(c);
    } else printf("No Solution");
    return 0;
}

1089 狼人杀-简单版

Analysis

这个题想了很久，没什么思路，感觉很怪，后来看了一下别人的代码，发现是一道模拟题（其实跟上一题的模拟思路很像）。做法就是按照序号从小到大不断的假设 2 个人是狼人，判断是否符合条件。如果符合，那就输出这个解后直接退出程序；如果没找到，就输出 No Solution 。
参考：
1089 狼人杀-简单版 (20 分)
PAT 1089 狼人杀-简单版（20 分）- 乙级

PS：这个题的难点不在于问题的复杂性，在于对实际问题的抽象能力。

Code

#include <cstdio>
#include <cmath>
const int maxn = 100 + 5;
int fact[maxn] = {0}, iswolf[maxn], lie[maxn];

int main() {
    int n;
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &fact[i]);
    }
    for(int i = 1; i <= n; i++) {
        for(int j = i + 1; j <= n; j++) {
            for(int i = 1; i <= n; i++) {
                iswolf[i] = 1;
            }
            iswolf[i] = iswolf[j] = -1;
            int index = 0;
            for(int k = 1; k <= n; k++) {
                if(fact[k] * iswolf[abs(fact[k])] < 0) lie[index++] = k;
            }
            if(index == 2 && iswolf[lie[0]] + iswolf[lie[1]] == 0) {
                printf("%d %d\n", i, j);
                return 0;
            }
        }
    }
    printf("No Solution");
    return 0;
}

1090 危险品装箱

Analysis

这个题如果不用 STL 的话，确实有点麻烦，一旦用了 STL 就很简单了。先将危险品信息统计好，然后在遍历货物清单上的每一件物品，判断货物清单上是否有不相容的物品即可。考虑到题目可能会给重复的数据，所以用 SET 来处理数据就可以自动去重了。

Code

#include <iostream>
#include <set>
using namespace std;
const int maxn = 100000 + 5;
set<int> pairs[maxn], stuff;
int n, m, k;

int main() {
    cin >> n >> m;
    for(int i = 0; i < n; i++) {
        int tmp_a, tmp_b;
        cin >> tmp_a >> tmp_b;
        pairs[tmp_a].insert(tmp_b), pairs[tmp_b].insert(tmp_a);
    }
    while(m--) {
        cin >> k;
        stuff.clear();
        for(int i = 0; i < k; i++) {
            int tmp;
            cin >> tmp;
            stuff.insert(tmp);
        }
        bool flag = false;
        for(set<int>::iterator it1 = stuff.begin(); it1 != stuff.end(); it1++) {
            int tmp1 = *it1;
            if(pairs[tmp1].size() == 0) continue;
            else {
                for(set<int>::iterator it2 = pairs[tmp1].begin(); it2 != pairs[tmp1].end(); it2++) {
                    int tmp2 = *it2;
                    if(stuff.find(tmp2) != stuff.end()) {
                        flag = true;
                        break;
                    }
                }
            }
            if(flag) break;
        }
        if(flag) cout << "No\n";
        else cout << "Yes\n";
    }
    return 0;
}

1091 N-自守数

Analysis

注意读题，判断一个数是否自守，就是用这个数的最后几位构成的数字与原数字比较是否相等即可，~~而“最后几位”就是原数字的位数了，能得到这个细节（题目中的这些细节，真是叫人又爱又恨）后，这个题目就很简单了。~~
要得到最后几位构成的数字，直接用这个数对应的整数取余即可（比如，8 对应 10，88 对应 100，依次类推）。
本来以为，使用int可能会有测试点不过，结果没有，没设置大数的测试点么？嘿嘿，逃过一劫~

Code

version 1

#include <stdio.h>
#include <stdbool.h>

bool Judge_Automorphic(int test_number, int original_number);

int main(int argc, char const *argv[]) {
    int M, N, K, each_item;
    bool flag;
    scanf("%d", &M);
    while(M--) {
        scanf("%d", &K);
        flag = false;
        for(N = 1; N < 10; N++) {
            each_item = N * K * K;
            if( Judge_Automorphic(each_item, K) ) {
                flag = true;
                break;
            }
        }
        if(flag) {
            printf("%d %d\n", N, each_item);
        } else {
            puts("No");
        }
    }
    return 0;
}

bool Judge_Automorphic(int test_number, int original_number) {
    bool flag = false;
    int mask = 1, temp;
    temp = original_number;
    while(temp) {
        temp /= 10;
        mask *= 10;
    }
    temp = test_number;
    temp %= mask;
    if(temp == original_number) {
        flag = true;
    }
    return flag;
}

version 2

#include <cstdio>

int main() {
    int n, k, m, digit, tmp;
    scanf("%d", &m);
    while(m--) {
        scanf("%d", &k);
        tmp = k, digit = 1;
        while(tmp != 0) {
            tmp /= 10;
            digit *= 10;
        }
        bool flag = false;
        for(n = 1; n < 10; n++) {
            tmp = n * k * k;
            if(tmp % digit == k) {
                flag = true;
                break;
            }
        }
        if(flag) printf("%d %d\n", n, tmp);
        else printf("No\n");
    }
    return 0;
}

1092 最好吃的月饼

Analysis

统计所有月饼的销量，找到最大值输出即可。

Code

#include <cstdio>
const int maxn = 1000 + 5;
int sales[maxn] = {0};

int main() {
    int n, m, tmp;
    scanf("%d %d", &n, &m);
    for(int i = 0; i < m; i++) {
        for(int j = 1; j <= n; j++) {
            scanf("%d", &tmp);
            sales[j] += tmp;
        }
    }
    int max = sales[1];
    for(int i = 2; i <= n; i++) {
        if(max < sales[i]) max = sales[i];
    }
    printf("%d\n", max);
    bool flag = true;
    for(int i = 1; i <= n; i++) {
        if(max == sales[i]) {
            if(flag) {
                printf("%d", i);
                flag = false;
            } else printf(" %d", i);
        }
    }
    return 0;
}

1093 字符串A+B

Analysis

分别遍历两个字符串，每输出一个字符，就将这个字符标记为已出现，下次就不在输出了。

Code

#include <iostream>
using namespace std;
bool isappear[256] = {false};
int main() {
    string a, b;
    getline(cin, a);
    getline(cin, b);
    for(int i = 0; i < a.length(); i++) {
        if(!isappear[a[i]]) {
            cout << a[i];
            isappear[a[i]] = true;
        }
    }
    for(int i = 0; i < b.length(); i++) {
        if(!isappear[b[i]]) {
            cout << b[i];
            isappear[b[i]] = true;
        }
    }
    return 0;
}

1094 谷歌的招聘

Analysis

唯一要注意的点就是，最终要输出的不是数，而是字符串。

Code

#include <cstdio>
#include <cmath>
bool isprime(int a) {
    if(a <= 1) return false;
    for(int i = 2; i <= sqrt(a); i++) {
        if(a % i == 0) return false;
    }
    return true;
}
char num[1005];

int main() {
    int l, k;
    scanf("%d %d%*c", &l, &k);
    scanf("%s", num);
    bool flag = false;
    for(int i = 0; i + k <= l; i++) {
        int number = 0;
        for(int j = i; j < i + k; j++) {
            number = number * 10 + num[j] - '0';
        }
        if(isprime(number)) {
            for(int j = i; j < i + k; j++) {
                printf("%c", num[j]);
            }
            flag = true;
            break;
        }
    }
    if(!flag) printf("404");
    return 0;
}

1095 解码PAT准考证

Analysis

这个题给的信息很多，按照不同的统计要求，分别利用对应的信息来处理，本质上还是排序题，所以处理的方法基本上是差不多的，只是有些地方要注意一下：

测试点 3 是卡时间的，要用 unordered_map，并且排序函数要使用引用的写法，这样更快。
指令 3，每次不同考场的人数统计完成后要重置为 0，以免又有指令 3 查询导致叠加。
指令 2 存在总分为 0 的情况，所以不要用分数来当作判断条件，这也是自己犯的错误。

Code

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <unordered_map>
using namespace std;
const int maxn = 10000 +5;
struct student {
    char level;
    string id, exam_room, exam_date;
    int score;
} stu[maxn];
struct examroom {
    string roomid;
    int men;
} examro[maxn];
bool cmp1(student &a, student &b) {
    if(a.level != b.level) return a.level < b.level;
    else if(a.score != b.score) return a.score > b.score;
    else return a.id < b.id;
}
bool cmp2(examroom &a, examroom &b) {
    if(a.men != b.men) return a.men > b.men;
    else return a.roomid < b.roomid;
}
void Init_examro() {
    for(int i = 0; i < maxn; i++) {
        examro[i].roomid.resize(10);
        examro[i].men = 0;
    }
}
int main() {
    int n, m, mode;
    string md, tmp;
    tmp.resize(15);
    scanf("%d %d%*c", &n, &m);
    for(int i = 0; i < n; i++) {
        scanf("%c%s %d%*c", &stu[i].level, tmp.c_str(), &stu[i].score);
        stu[i].exam_room = tmp.substr(0, 3);
        stu[i].exam_date = tmp.substr(3, 6);
        stu[i].id = tmp;
    }
    for(int i = 1; i <= m; i++) {
        cin >> mode >> md;
        bool flag = false;
        printf("Case %d: %d %s\n", i, mode, md.c_str());
        if(mode == 1) {
            sort(stu, stu + n, cmp1);
            for(int i = 0; i < n; i++) {
                if(md[0] == stu[i].level) {
                    printf("%c%s %d\n", stu[i].level, stu[i].id.c_str(), stu[i].score);
                    flag = true;
                }
            }
        } else if(mode == 2) {
            int sum = 0, men = 0;
            for(int i = 0; i < n; i++) {
                if(md == stu[i].exam_room) {
                    sum += stu[i].score;
                    men++;
                }
            }
            if(men) {
                printf("%d %d\n", men, sum);
                flag = true;
            }
        } else if(mode == 3) {
            int count = 0;
            unordered_map<string, int> room2num;
            Init_examro();
            for(int i = 0; i < n; i++) {
                if(md == stu[i].exam_date) {
                    if(room2num.find(stu[i].exam_room) == room2num.end()) {
                        room2num[stu[i].exam_room] = count++;
                        examro[room2num[stu[i].exam_room]].roomid = stu[i].exam_room;
                    }
                    examro[room2num[stu[i].exam_room]].men++;
                }
            }
            sort(examro, examro + count, cmp2);
            for(int i = 0; i < count; i++) {
                printf("%s %d\n", examro[i].roomid.c_str(), examro[i].men);
                flag = true;
            }
        }
        if(!flag) cout << "NA" << endl;
    }
    return 0;
}

1096 大美数

Analysis

这个题刚开始读的时候，感觉有点怪，仔细一想，15 分的题，应该不会设置一些难过的测试点。事实也是这样，直接用暴力枚举就可以了。
注意：

N 是除数，4 个因数之和是被除数。
1 与 N 本身也是因数。

Code

多写判断语句和缩短循环条件是为了减少执行次数，加快运行时间，就本题而言，实际提升了 1 ms😂。

#include <cstdio>
const int maxn = 10000 + 5;
int factor[maxn] = {1};
 
int main() {
    int k, n;
    scanf("%d", &k);
    while(k--) {
        int cnt = 1;
        scanf("%d", &n);
        for(int i = 2; i <= n; i++) {
            if(n % i == 0) factor[cnt++] = i;
        }
        if(cnt < 4) printf("No\n");
        else {
            bool flag = false;
            for(int i = 0; i < cnt - 3; i++) {
                for(int j = i + 1; j < cnt - 2; j++) {
                    for(int k = j + 1; k < cnt - 1; k++) {
                        for(int l = k + 1; l < cnt; l++) {
                            if((factor[i] + factor[j] + factor[k] + factor[l]) % n == 0) {
                                printf("Yes\n");
                                flag = true;
                                goto out;
                            }
                        }
                    }
                }
            }
            out: 
                if(!flag) printf("No\n");
        }
    }
    return 0;
}

1097 矩阵行平移

Analysis

考察二维数组的概念和一维数组元素后移的操作，注意要先后移在改值。

Code

#include <cstdio>
int matrix[105][105] = {0}, n, k, x;;

int main() {
    scanf("%d %d %d", &n, &k, &x);
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            scanf("%d", &matrix[i][j]);
        }
    }
    int s = 1;
    for(int i = 1; i <= n; i+=2) {
        for(int j = n - s; j >= 1; j--) {
            matrix[i][j + s] = matrix[i][j];
        }
        for(int j = 1; j <= s; j++) {
            matrix[i][j] = x;
        }
        if(s == k) s = 1;
        else s++;
    }
    for(int i = 1; i <= n; i++) {
        int sum = 0;
        for(int j = 1; j <= n; j++) {
            sum += matrix[j][i];
        }
        printf("%d", sum);
        if(i != n) printf(" ");
    }
    return 0;
}

1098 岩洞施工

Analysis

这个题自己一开始想歪了，总是把注意力集中在相同横坐标的点的纵坐标之差得大于 1，才能放入管道。然后又考虑不同横坐标下的点的纵坐标之差要达到多少才合适。实际上，只需要考虑顶部点的最低点与底部点的最高点的纵坐标之差就可以了。

Code

#include <cstdio>

int main() {
    int n, tmp, up_low = 1005, down_high = 0;
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        scanf("%d", &tmp);
        if(up_low > tmp) up_low = tmp;
    }
    for(int i = 0; i < n; i++) {
        scanf("%d", &tmp);
        if(down_high < tmp) down_high = tmp;
    }
    tmp = up_low - down_high;
    if(tmp > 0) printf("Yes %d", tmp);
    else printf("No %d", 1 - tmp);
    return 0;
}

/*
in:
11
7 6 5 5 6 5 4 5 5 4 4
3 2 2 2 2 3 3 2 1 2 3
out:
Yes 1

in:
11
7 6 5 5 6 5 4 5 5 4 4
3 2 2 2 3 4 3 2 1 2 3
out:
No 1

in:
11
7 6 5 5 6 5 4 5 5 4 4
3 2 2 2 3 5 3 2 1 2 3
out:
No 2

in:
11
7 6 5 5 6 5 4 5 5 4 4
3 2 2 2 3 6 3 2 1 2 3
out:
No 3
*/

1099 性感素数

Analysis

注意：性感素数是一对一对存在的，测试点 3 就给的是不符合条件的 n，但是与 n-6 构成了一对性感素数。那么，按照要求输出的就是大于 n 的最小性感素数。

Code

#include <cstdio>
#include <cmath>
bool isprime(int a) {
    if(a <= 1) return false;
    else {
        for(int i = 2; i <= sqrt(a); i++) {
            if(a % i == 0) return false;
        }
    }
    return true;
}
int main() {
    int n;
    scanf("%d", &n);
    if(isprime(n) && isprime(n - 6)) printf("Yes\n%d", n - 6);
    else if(isprime(n) && isprime(n + 6)) printf("Yes\n%d", n);
    else {
        while(n++) {
            if(isprime(n) && isprime(n - 6) || isprime(n) && isprime(n + 6)) break;
        }
        printf("No\n%d", n);
    }
    return 0;
}

1100 校庆

Analysis

利用 set 存储校友信息，读入参加校庆的人员信息后，在 set 中查找，是否是校友，统计校友个数。因为最终要输出的结果是最年长的人，所以需要按照出生日期进行分类排序（校友与非校友），默认将校友放在前面，输出会方便一些。

Code

#include <iostream>
#include <set>
#include <algorithm>
using namespace std;
const int maxn = 100000 + 5;
set<string> xiaoyou;
struct guest{
    string id, birth;
    int flag;
} g[maxn];
bool cmp(guest a, guest b) {
    if(a.flag != b.flag) return a.flag > b.flag;
    else return a.birth < b.birth;
}
int main() {
    string tmp;
    int n, m;
    cin >> n;
    for(int i = 0; i < n; i++) {
        cin >> tmp;
        xiaoyou.insert(tmp);
    }
    int count = 0;
    cin >> m;
    for(int i = 0; i < m; i++) {
        cin >> g[i].id;
        g[i].birth = g[i].id.substr(6, 8);
        if(xiaoyou.find(g[i].id) != xiaoyou.end()) {
            count++;
            g[i].flag = 1;
        }
    }
    sort(g, g + m, cmp);
    cout << count << endl << g[0].id;
    return 0;
}

1101 B是A的多少倍

Analysis

这个题差点想歪了从字符串的角度做，实际上直接从数的角度做更简单，因为位数 d 是给定的。

Code

#include <cstdio>
#include <cmath>

int main() {
    int a, d, tmp, digit = 0, b;
    scanf("%d %d", &a, &d);
    tmp = a;
    while(tmp != 0) {
        tmp /= 10;
        digit++;
    }
    tmp = a % (int)pow(10, d);
    b = tmp * pow(10, digit - d) + a / pow(10, d);
    printf("%.2lf", b * 1.0 / a);
}

1102 教超冠军卷

Analysis

结构体存储信息，找出符合条件的最大值即可。

Code

#include <cstdio>
const int maxn = 10000 + 5;
struct test{
    char id[9];
    int price, amount, sum;
} te[maxn]; 

int main() {
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        scanf("%s %d %d", te[i].id, &te[i].price, &te[i].amount);
        te[i].sum = te[i].price * te[i].amount;
    }
    int max_amount = te[0].amount, max_sum = te[0].sum, index1 = 0, index2 = 0;
    for(int i = 1; i < n; i++) {
        if(max_amount < te[i].amount) {
            max_amount = te[i].amount;
            index1 = i;
        }
        if(max_sum < te[i].sum) {
            max_sum = te[i].sum;
            index2 = i;
        }
    }
    printf("%s %d\n%s %d\n", te[index1].id, max_amount, te[index2].id, max_sum);
    return 0;
}

1103 缘分数

Analysis

按照题目要求模拟即可，注意 2 个地方：

多数相乘的过程中可能会溢出，所以直接使用long long比较好。
sqrt的返回值强转后会丢掉小数，只取整数部分，所以需要判断平方相等是否成立。

Code

#include <cstdio>
#include <cmath>
typedef long long LL;
int main() {
    LL m, n, a, b, c, tmp;
    scanf("%lld %lld", &m, &n);
    bool flag = false;
    for(; m <= n; m++) {
        a = m;
        tmp = a * a * a - (a - 1) * (a - 1) * (a - 1);
        c = sqrt(tmp);
        if(c * c != tmp) continue;
        else {
            for(b = 1; b < c; b++) {
                if(c == b * b + (b - 1) * (b - 1)) {
                    flag = true;
                    printf("%lld %lld\n", a, b);
                }
            }
        }
    }
    if(!flag) printf("No Solution\n");
    return 0;
}

1104 天长地久

Analysis

这个题需要一定的数学能力，不然拿不到满分，注意以下几点：

最终输出的结果需要按照 n 或 A 的递增顺序输出，所以需要排序，使用 set 是最方便的。
直接暴力枚举会超时，需要排除掉一些特殊情况，分 3 种情况考虑：

A 的个位数是 1-8，此时 $gcd(m, n)$ 就只可能是 1，不满足条件。
A 的个位数是 9，以 1009 为例，其各位数字之和为 10，加 1 后是 1010，各位数字之和为 2，相差 8，而 $gcd(11, 2$ 就是 1 了。实际上可以发现，$m = n + 9 - 1 = n + 8$，从而可以得到，$gcd(m, n) = gcd(n + 8, n) = gcd(n, (n + 8) \% n) = gcd(n, 8)$，所以，这种情况下，公约数只可能取 1、2、4、8，也不满足条件。
A 的十位数和个位数都是 9，那么按照上面的思路就有 $m = n + 9 + 9 - 1$（当然也可以理解成 $n = m - 9 - 9 + 1$，因为再多的 9 也只有 1 个进位，这样解释可能更易于理解），从而 $gcd(m, n) = gcd(n, 17)$，公约数可能取 1、17，17 是满足条件的。现在就知道了，A 的尾数必须至少有 2 位 9 才满足条件，那就直接从尾数为 99 的数开始遍历，每次加 100 即可。

这个题需要动点脑筋才能拿满分，算是有点难但又不是太难的那种题，最主要的是怎么把思路往数学上想。另外，素数的判定，数位求和，公约数求法，这些小考点也要会才行，还有 set 和 pair 的用法也得会，不然再来排序的话，可能又会产生其他的问题。

Code

#include <cstdio>
#include <cmath>
#include <set>
using namespace std;
set<pair<int, int>> res;
bool isprime(int a) {
    if(a <= 1) return false;
    else {
        for(int i = 2; i <= sqrt(a); i++) {
            if(a % i == 0) return false;
        }
    }
    return true;
}
int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b); 
}
int digitsum(int a) {
    int res = 0;
    while(a != 0) {
        res = res + a % 10;
        a /= 10;
    }
    return res;
}
int main() {
    int N, n, k, m, tmp, g;
    scanf("%d", &N);
    for(int i = 1; i <= N; i++) {
        printf("Case %d\n", i);
        scanf("%d %d", &k, &m);
        tmp = pow(10, k);
        bool flag = false;
        for(int j = 99 + pow(10, k - 1); j < tmp; j += 100) {
            if(digitsum(j) == m) {
                n = digitsum(j + 1);
                g = gcd(m, n);
                if(g > 2 && isprime(g)) {
                    res.insert(make_pair(n, j));
                    flag = true;
                }
            } 
        }
        if(!flag) printf("No Solution\n");
        else {
            set<pair<int, int>>::iterator it = res.begin();
            for(; it != res.end(); it++) {
                printf("%d %d\n", it->first, it->second);
            }
            res.clear();
        }
    }
    return 0;
}

1105 链表合并

Analysis

题目保证没有空链表，但是没保证一定没有无效结点，所以直接将需要处理的链表放到新链表里面，并记录好有效结点的个数。虽然题目要求短的链表进行逆序，但实际上，也不是非得逆序，用栈存一下，再输出就行。按照长链表输出 2 个，短链表输出 1 个的过程交替输出，此时要考虑 3 种情况：

输出长链表要求输出的第一个结点，这个结点可能是长链表的最后一个结点，也可能不是。
输出长链表要求输出的第二个结点，这个结点可能是要输出的最后一个结点，也可能不是。如果不是，那么这个结点的 next 需要输出短链表下一个要输出的结点的地址。
输出短链表的结点，这个结点可能是短链表的最后一个结点但不是要输出结点的最后一个结点。如果不是，那就意味着长链表还有结点没有输出完，i 就要减 1。

PS：下面这段代码的很多地方的判断条件其实可以换成其他的，比如i != n - 1可以换成lrev.size() != 0。

Code

#include <cstdio>
#include <stack>
using namespace std;
const int maxn = 100000 + 5;
struct node {
    int address, data, next;
} L[maxn], L1[maxn], L2[maxn];
stack<node> lrev;
int newlist(int head, node *l) {
    int p = head, count = 0;
    while(p != -1) {
        l[p].address = p, l[p].data = L[p].data, l[p].next = L[p].next;
        p = L[p].next;
        count++;
    }
    return count;
}
void printlist(int head1, int head2, int n1, int n2, node *l1, node *l2) {
    int p = head1, n = n1 + n2, count = 0;
    while(p != -1) {
        lrev.push(l1[p]);
        p = l1[p].next;
    }
    p = head2;
    node tmp;
    for(int i = 0; i < n; i++) {
        if(count == 0) {
            if(l2[p].next != -1) printf("%05d %d %05d\n", l2[p].address, l2[p].data, l2[p].next);
            else printf("%05d %d -1\n", l2[p].address, l2[p].data);
            p = l2[p].next;
            count++;
        } else if(count == 1) {
            if(i == n - 1) printf("%05d %d -1\n", l2[p].address, l2[p].data);
            else {
                if(!lrev.empty()) {
                    tmp = lrev.top();
                    printf("%05d %d %05d\n", l2[p].address, l2[p].data, tmp.address);
                } else {
                    printf("%05d %d %05d\n", l2[p].address, l2[p].data, l2[p].next);
                }
            }
            p = l2[p].next;
            count++;
        } else if(count == 2) {
            if(!lrev.empty()) {
                tmp = lrev.top();
                lrev.pop();
                if(i != n - 1) printf("%05d %d %05d\n", tmp.address, tmp.data, l2[p].address);
                else printf("%05d %d -1\n", tmp.address, tmp.data);
            } else i--;
            count = 0;
        }
    }
}
int main() {
    int p, head1, head2, n, n1, n2;
    scanf("%d %d %d", &head1, &head2, &n);
    for(int i = 0; i < n; i++) {
        scanf("%d", &p);
        scanf("%d %d", &L[p].data, &L[p].next);
        L[p].address = p;
    }
    n1 = newlist(head1, L1);
    n2 = newlist(head2, L2);
    if(n1 < n2) printlist(head1, head2, n1, n2, L1, L2);
    else printlist(head2, head1, n2, n1, L2, L1);
    return 0;
}
/*
in:
00100 01000 7
02233 2 34891
00100 6 00001
34891 3 10086
01000 1 02233
00033 5 -1
10086 4 00033
00001 7 -1
out:
01000 1 02233
02233 2 00001
00001 7 34891
34891 3 10086
10086 4 00100
00100 6 00033
00033 5 -1

in:
01000 00100 7
02233 2 34891
00100 6 00001
34891 3 10086
01000 1 02233
00033 5 -1
10086 4 00033
00001 7 -1
out:
01000 1 02233
02233 2 00001
00001 7 34891
34891 3 10086
10086 4 00100
00100 6 00033
00033 5 -1

in:
00100 01000 6
02233 2 34891
00100 6 -1
34891 3 10086
01000 1 02233
00033 5 -1
10086 4 00033
out:
01000 1 02233
02233 2 00100
00100 6 34891
34891 3 10086
10086 4 00033
00033 5 -1

*/

1106 2019数列

Analysis

这个题有点像斐波那契数列，不过比较简单。
另外，写代码的时候没看到“题外话”（神经太大条了），总结的时候看到了，勾起了好奇心，试着用反证法尝试了一下，未得解。百度了一下，发现是这样的规律：
以前 20 项为例，最终得到的数列是：

2 0 1 9 2 2 4 7 5 8 4 4 1 7 6 8 2 3 9 2
从奇偶性的角度来看就是：

偶偶奇奇偶偶偶奇奇偶偶偶奇奇偶偶偶奇奇偶
就可以发现，奇偶性的排列是按照“偶偶偶奇奇”的顺序不断重复的，而对比 2018，1 这个数字的两侧都是偶数，所以它就不可能出现在这个数列中，但这好像并不是在证明，而是在验证😂。

Code

#include <cstdio>
const int maxn = 1000 + 5;
int arr[maxn] = {0, 2, 0, 1, 9};
int main() {
    int n, tmp;
    scanf("%d", &n);
    for(int i = 5; i <= n;i++) {
        tmp = arr[i - 1] + arr[i - 2] + arr[i - 3] + arr[i - 4];
        arr[i] = tmp % 10;
    }
    for(int i = 1; i <= n; i++) {
        printf("%d", arr[i]);
    }
    return 0;
}

1107 老鼠爱大米

Analysis

这个题没什么说的，可以读入所有数据后在输出，也可以边读入边输出，只要测试的结果与样例一致就行，可以使用 PTA 自带的自定义测试功能进行测试。

Code

#include <cstdio>

int main() {
    int n, m, tmp, max2 = -1;
    scanf("%d %d", &n, &m);
    for(int i = 0; i < n; i++) {
        int max1 = -1;
        for(int j = 0; j < m; j++) {
            scanf("%d", &tmp);
            if(max1 < tmp) max1 = tmp;
        }
        printf("%d", max1);
        if(i != n - 1) printf(" ");
        if(max1 > max2) max2 = max1;
    }
    printf("\n%d", max2);
    return 0;
}

1108 String复读机

Analysis

这个题也比较直观，想着是不是能把代码写的简单一点，结果发现，好像这样就已经很简单、直观、易于理解了。

好吧，确实可以改短一点，不过，version 1 确实是最直观且易于理解的。

Code

version 1

#include <cstdio>
char str[10005];
int times[6] = {0};
int main() {
    scanf("%s", str);
    for(int i = 0; str[i] != '\0'; i++) {
        if(str[i] == 'S') times[0]++;
        else if(str[i] == 't') times[1]++;
        else if(str[i] == 'r') times[2]++;
        else if(str[i] == 'i') times[3]++;
        else if(str[i] == 'n') times[4]++;
        else if(str[i] == 'g') times[5]++;
    } 
    while(times[0] || times[1] || times[2] || times[3] || times[4] || times[5]) {
        if(times[0]) {
            printf("S");
            times[0]--;
        }
        if(times[1]) {
            printf("t");
            times[1]--;
        }
        if(times[2]) {
            printf("r");
            times[2]--;
        }
        if(times[3]) {
            printf("i");
            times[3]--;
        }
        if(times[4]) {
            printf("n");
            times[4]--;
        }
        if(times[5]) {
            printf("g");
            times[5]--;
        }
    }
    return 0;
}

version 2

这个题其实与 1043 一样，所以可以按照同样的思路改写一下，如下：

#include <cstdio>
char str[10005];
int times[128] = {0};
char String[10] = "String";
int main() {
    scanf("%s", str);
    char *p = str;
    int times[128] = {0};
    while(*p != '\0') {
        times[*p]++;
        p++;
    }
    while(times['S'] || times['t'] || times['r'] || times['i'] || 
        times['n'] || times['g']) {
        for(p = String; *p != '\0'; p++) {
            if(times[*p]) {
                putchar(*p);
                times[*p]--;
            }
        }
    }
    return 0;
}

1109 擅长C

Analysis

这个题有点麻烦，写完之后，感觉用 3 维数组好像比 2 维数组麻烦。整个模拟过程不是很难，难的是保持题目要求的格式，要注意以下几个地方：

除了大写英文字符外，其他的字符都是“分隔符”。
多余字符可能出现在开头（测试点 1）。
多余字符可能出现在结尾。
多余字符可能出现在中间。
多余字符可能会连续出现多个。

PS：这个题的输出太长了，自己编测试样例都不是很好编，不得不吐槽下。

Code

#include <cstdio>
#include <cctype>
char words[26][7][7], str[10000];
int word_index[10000] = {0};

int main() {
    for(int i = 0; i < 26; i++) {
        for(int j = 0; j < 7; j++) {
            scanf("%s", words[i][j]);
        }
    }
    getchar();
    fgets(str, 10000, stdin);
    int count = 0;
    for(int i = 0; str[i] != '\0'; i++) {
        if(isupper(str[i])) {
            word_index[count++] = str[i] - 'A';
        } else {
            word_index[count++] = -1;
            while(!isupper(str[i]) && str[i] != '\0') i++;
            i--;
        }
    }
    int i, j, k;
    while(word_index[i] == -1) i++;
    for(; i < count; i++) {
        for(j = 0; j < 7; j++) {
            printf("%s", words[word_index[i]][j]);
            for(k = i + 1; word_index[k] != -1; k++) {
                printf(" %s", words[word_index[k]][j]);
            }
            printf("\n");
        }
        i = k;
        if(i < count - 1) printf("\n");
    }
    return 0;
}

1110 区块反转

Analysis

这个题跟B1025是一样的题，唯一的差别就是输出要求不太相同，大致思路基本一致。注意以下几个地方：

可能会有无效结点，读入数据后，需要先遍历链表，排序剔除掉无效结点，并保存有效结点的个数。
输出末尾结点数小于 k 的块时，如果要输出链表最后一个结点，其 next 需要输出第 (i - 1) * k 个结点的地址（也就是下一个要输出的块的第一个结点的地址）。
输出结点数等于 k 且不是最后一块时，如果要输出当前块的最后一个结点，其 next 需要输出第 (i - 1) * k 个结点的地址（也就是下一个要输出的块的第一个结点的地址）。
输出结点数等于 k 且是最后一块时，如果输出的是最后一个结点，其 next 需要输出 -1。

Code

#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 100000 + 5;
struct node {
    int addr, data, next;
    int order;
} L[maxn];
void Init() {
    for(int i = 0; i < maxn; i++) {
        L[i].order = maxn;
    }
}
bool cmp(node a, node b) {
    return a.order < b.order;
}

int main() {
    Init();
    int head, n, k, tmp;
    scanf("%d %d %d", &head, &n, &k);
    for(int i = 0; i < n; i++) {
        scanf("%d", &tmp);
        scanf("%d %d", &L[tmp].data, &L[tmp].next);
        L[tmp].addr = tmp;
    }
    int p = head, count = 0;
    while(p != -1) {
        L[p].order = count++;
        p = L[p].next;
    }
    sort(L, L + maxn, cmp);
    n = count;
    for(int i = n / k; i >= 0; i--) {
        int j = i * k;
        if(i == n / k) {
            for(; j < n; j++) {
                if(j == n - 1) printf("%05d %d %05d\n", L[j].addr, L[j].data, L[(i - 1) * k].addr);
                else printf("%05d %d %05d\n", L[j].addr, L[j].data, L[j].next);
            }
        } else {
            if(i != 0) {
                for(; j < (i + 1) * k; j++) {
                    if(j == (i + 1) * k - 1) printf("%05d %d %05d\n", L[j].addr, L[j].data, L[(i - 1) * k].addr);
                    else printf("%05d %d %05d\n", L[j].addr, L[j].data, L[j].next);
                }
            } else {
                for(; j < k; j++) {
                    if(j == k - 1) printf("%05d %d -1\n", L[j].addr, L[j].data);
                    else printf("%05d %d %05d\n", L[j].addr, L[j].data, L[j].next);
                }
            }
        }
    }
    return 0;
}

Summary

算上今天，一共大概花了大约 80 个小时的时间，把原来做过的和没做过的题都做了一遍。感觉乙级的题目还是比较基础的，有些题目设置的卡点，其实没有太多的必要？不过，尽可能的减少自己写的程序的 bug 也是应该的。

有时候一道题有思路，但却没拿到满分是件很痛苦的事情。不过，感觉花时间 debug 带来的提升，可能会比花时间学习别人的思路带来的提升更大。当然，成就感也会更大，这就好比玩游戏刷副本被人带和自己单刷的感觉吧。

接下来该做的事情，就是再回过头看看这些题目蕴含的思想了。还有就是，有没有什么更快捷、方便、简单且易于理解的其他解法了。

总之，要做且能做事情还有很多...