# PAT算法笔记

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

```
卡拉兹(Callatz)猜想：

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

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

输入格式：
每个测试输入包含 1 个测试用例，即给出正整数 n 的值。

输出格式：
输出从 n 计算到 1 需要的步数。

输入样例：
3
结尾无空行
输出样例：
5
```

```
#include<bits/stdc++.h>
using namespace std;

int main() {
    int num;
    cin >> num;
    int cnt = 0;
    while(num != 1) {
        if(num % 2 != 0) num = 3 * num + 1;
        num /= 2;
        cnt++; 
    }
    cout << cnt;
}
```

## **1002 写出这个数 (20 分)**

```
读入一个正整数 n，计算其各位数字之和，用汉语拼音写出和的每一位数字。

输入格式：
每个测试输入包含 1 个测试用例，即给出自然数 n 的值。这里保证 n 小于 10 
100
 。

输出格式：
在一行内输出 n 的各位数字之和的每一位，拼音数字间有 1 空格，但一行中最后一个拼音数字后没有空格。

输入样例：
1234567890987654321123456789
结尾无空行
输出样例：
yi san wu
结尾无空行
```

```
#include<bits/stdc++.h>
using namespace std;

int main() {
    int flag = 1;
    char a[11][10] = {"ling","yi","er","san","si","wu","liu","qi","ba","jiu"};
    string s;//输入数字 
    int sum = 0;//
    cin >> s;
    for(int i = 0; i < s.size(); i++) {
        int temp = s[i] - '0';
        sum += temp;//字符转数字相加 
    }
    string s1 = to_string(sum);//和转字符串 
    for(int i = 0; i < s1.size(); i++) {
        int temp = s1[i] - '0';
        if(flag) {
            cout << a[temp];//输出 
            flag = 0;
        } else cout << " " << a[temp];

    }
}
```

## **1003 我要通过！ (20 分)**

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

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

字符串中必须仅有 P、 A、 T这三种字符，不可以包含其它字符；
任意形如 xPATx 的字符串都可以获得“答案正确”，其中 x 或者是空字符串，或者是仅由字母 A 组成的字符串；
如果 aPbTc 是正确的，那么 aPbATca 也是正确的，其中 a、 b、 c 均或者是空字符串，或者是仅由字母 A 组成的字符串。
现在就请你为 PAT 写一个自动裁判程序，判定哪些字符串是可以获得“答案正确”的。

输入格式：
每个测试输入包含 1 个测试用例。第 1 行给出一个正整数 n (≤10)，是需要检测的字符串个数。接下来每个字符串占一行，字符串长度不超过 100，且不包含空格。

输出格式：
每个字符串的检测结果占一行，如果该字符串可以获得“答案正确”，则输出 YES，否则输出 NO。

输入样例：
10
PAT
PAAT
AAPATAA
AAPAATAAAA
xPATx
PT
Whatever
APAAATAA
APT
APATTAA
结尾无空行
输出样例：
YES
YES
YES
YES
NO
NO
NO
NO
NO
NO
```

```
#include<bits/stdc++.h>
using namespace std;

int main() {
    int n;//待测组数 
    cin >> n;
    int p,t;//P T出现的位置 
    for(int i = 0; i < n; i++) {
        string s;
        cin >> s;//输入待测字符串 
        map<char,int> m;//map对应字母出现的次数 
        for(int j = 0; j < s.size(); j++) {
            m[s[j]]++;//每次对应的字母出现次数+1 
            if(s[j] == 'P') p = j;
            if(s[j] == 'T') t = j;
        }
        if(m['P'] == 1 && m['A'] >= 1 && m['T'] == 1 && m.size() 
        == 3 && t - p > 1 && p*(t-p-1) == s.size() - 1 -t)
        //P T仅出现1次 A大于等于1次 不包括其他字符 P和T中间存在字符（A） P前的字符
        //乘P T中间字符的个数等于结尾字符的个数 
            cout << "YES\n";
        else cout << "NO\n";
    }
}
```

## 1004 成绩排名 (20)

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

输入格式

每个测试输入包含1个测试用例，格式为
第1行：正整数n
第2行：第1个学生的姓名 学号 成绩
第3行：第2个学生的姓名 学号 成绩
… … …
第n+1行：第n个学生的姓名 学号 成绩
其中姓名和学号均为不超过10个字符的字符串，成绩为0到100之间的一个整数，这里保证在一组测试用例中没有两个学生的成绩是相同的。

输出格式

对每个测试用例输出2行，第1行是成绩最高学生的姓名和学号，第2行是成绩最低学生的姓名和学号，字符串间有1空格。

输入样例

3
Joe Math990112 89
Mike CS991301 100
Mary EE990830 95

输出样例

Mike CS991301
Joe Math990112

分析：
maxname和maxnum保存成绩最高的学生的姓名和学号，minname和minnum保存成绩最低的学生的姓名和学号，max和min保存当前的最高分和最低分，因为成绩区间为0-100，所以初始化时先令max = -1，min = 101。遍历所有数据，如果当前学生数据的分数比最大值大，那么更新max的值，并将他的姓名学号保存在maxname和maxnum中；如果当前学生数据的分数比最小值小，那么更新min的值，并将他的姓名学号保存在minname和minnum中。最后输出maxname、maxnum、minname和minnum～
```

```
#include<bits/stdc++.h>
using namespace std;

struct{
    char name[11];
    char num[11];
    int grade;
}stu[100],max1,min1;

int main(){
    int N;
    cin >> N;
    

    for(int i = 0;i < N;i++){
        scanf("%s %s %d",stu[i].name,stu[i].num,&stu[i].grade);    
    }
    max1 = stu[0];
    min1 = stu[0];
    
    for(int i = 0;i < N;i++){
        if(stu[i].grade > max1.grade){
            max1 = stu[i];
        }
        if(stu[i].grade < min1.grade){
            min1 = stu[i];
        }
    }
    printf("%s %s\n",max1.name,max1.num);
    printf("%s %s",min1.name,min1.num);

}
```

### sort方法使用

```
如果对数组进⾏sort排序： sort(a, a + n, cmp1);
如果对vector v或者字符串v进⾏sort排序： sort(v.begin(), v.end(), cmp1);
```

### ★辗转相除求最大公约数

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

### ☆素数判断

```
bool isprime(int n) {
     if (n <= 1) return false;
     int sqr = int(sqrt(n * 1.0));
     for (int i = 2; i <= sqr; i++)
     if (n % i == 0) return false;
     return true; 
 }
```

## **1005 继续(3*n+1)猜想 (25 分)**

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

当我们验证卡拉兹猜想的时候，为了避免重复计算，可以记录下递推过程中遇到的每一个数。例如对 n=3 进行验证的时候，我们需要计算 3、5、8、4、2、1，则当我们对 n=5、8、4、2 进行验证的时候，就可以直接判定卡拉兹猜想的真伪，而不需要重复计算，因为这 4 个数已经在验证3的时候遇到过了，我们称 5、8、4、2 是被 3“覆盖”的数。我们称一个数列中的某个数 n 为“关键数”，如果 n 不能被数列中的其他数字所覆盖。

现在给定一系列待验证的数字，我们只需要验证其中的几个关键数，就可以不必再重复验证余下的数字。你的任务就是找出这些关键数字，并按从大到小的顺序输出它们。

输入格式：
每个测试输入包含 1 个测试用例，第 1 行给出一个正整数 K (<100)，第 2 行给出 K 个互不相同的待验证的正整数 n (1<n≤100)的值，数字间用空格隔开。

输出格式：
每个测试用例的输出占一行，按从大到小的顺序输出关键数字。数字间用 1 个空格隔开，但一行中最后一个数字后没有空格。

输入样例：
6
3 5 6 7 8 11
结尾无空行
输出样例：
7 6
结尾无空行
```

```
#include<bits/stdc++.h>
using namespace std;

bool cmp(int a,int b) {//从大到小排序 
    return a > b;
}

int main() {
    int a[100001] = {0};//数组存放验证过的数，出现过为1 
    int n;//n个测试样例 
    cin >> n;
    vector<int> v(n);//可变数组存放数据 
    for(int i = 0; i < n; i++) {
        int m;
        cin >> m;
        v[i] = m;
        while(m != 1) {//3n+1猜想 
            if(m % 2 != 0) m = 3 * m + 1;//若奇 num*3+1
            m /= 2;//除半
            if(a[m] == 1) break;//若出现过，则终止跳出 
            a[m] = 1;//若没出现过，对应为位置+1 
        }
    }
    sort(v.begin(),v.end(),cmp);//排序 
    int flag = 0;
    for(int i = 0; i < v.size(); i++) {//规范输出 
        if(a[v[i]] == 0) {
            if(flag) cout << " ";
            cout << v[i];
            flag = 1;
        }
    }
}
```

## **1006 换个格式输出整数 (15 分)**

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

输入格式：
每个测试输入包含 1 个测试用例，给出正整数 n（<1000）。

输出格式：
每个测试用例的输出占一行，用规定的格式输出 n。

输入样例 1：
234
结尾无空行
输出样例 1：
BBSSS1234
结尾无空行
输入样例 2：
23
结尾无空行
输出样例 2：
SS123
结尾无空行
```

```
解法1:
#include<bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    int b = n / 100;
    int s = n % 100 / 10;
    int g = n % 10;
    
    if(b != 0){
        while(b--) cout << "B";
    }
    if(s != 0){
        while(s--) cout << "S";
    }
    if(g != 0){
        for(int i = 1;i <= g;i++){
            cout << i;
        }
    }
}
```

```
解法2：
#include<bits/stdc++.h>
using namespace std;

int main() {
    int n;//待测数字 
    cin >> n;
    int i = 0;
    
    int b[3] = {0};
    
    while (n != 0) {//循环求各位上的数 
        b[i++] = n % 10;
        n = n / 10;
    }    
    if(b[2] != 0){
        while(b[2]--) cout << "B";
    }
    if(b[1] != 0){
        while(b[1]--) cout << "S";
    }
    if(b[0] != 0){
        for(int i = 1;i <= b[0];i++){
            cout << i;
        }
    }
}
```

### 取数字的个十百各位

```
int i = 0;
int b[3] = {0};
while (n != 0) {//循环求各位上的数 
    b[i++] = n % 10;
    n = n / 10;
}    
```

## **1007 素数对猜想 (20 分)**

```
让我们定义 dn 为：dn = pn+1 – pn，其中 pi 是第i个素数。显然有 d1=1 且对于n>1有 dn 是偶数。“素数对猜想”认为“存在无穷多对相邻且差为2的素数”。
现给定任意正整数N (< 105)，请计算不超过N的满足猜想的素数对的个数。

输入格式

每个测试输入包含1个测试用例，给出正整数N。

输出格式

每个测试用例的输出占一行，不超过N的满足猜想的素数对的个数。

输入样例

20

输出样例

4

分析：判断素数的函数isprime这样写：对于数字a，i从2到根号a，如果a能够被其中一个i整除，说明i不是素数，return false，否则说明a是素数return true；对于输入数据N，for循环中的i从5到N依次判断i-2和i是否是素数，如果都是素数，则统计个数的cnt++，最后输出cnt即可～
```

```
#include<bits/stdc++.h>
using namespace std;

int isprime(int a) {//素数判断 
    if(a <= 1)return 0;
    for(int i = 2; i * i <= a; i++)
        if(a % i == 0) return 0;
    return 1;
}

int main() {
    int n;
    cin >> n;
    int cnt = 0;
    for(int i = 5;i <= n;i++){//从5开始，若i和i-2都是素数，都+1素数对 
        if((isprime(i - 2) && isprime(i))) cnt++;
    }
    cout << cnt;
}
```

## **1008 数组元素循环右移问题 (20 分)**

```
一个数组A中存有N（N>0）个整数，在不允许使用另外数组的前提下，将每个整数循环向右移M（M>=0）个位置，即将A中的数据由（A0 A1……AN-1）变换为（AN-M …… AN-1 A0 A1……AN-M-1）（最后M个数循环移至最前面的M个位置）。如果需要考虑程序移动数据的次数尽量少，要如何设计移动
的方法？

输入格式

每个输入包含一个测试用例，第1行输入N ( 1<=N<=100)、M（M>=0）；第2行输入N个整数，之间用空格分隔。

输出格式

在一行中输出循环右移M位以后的整数序列，之间用空格分隔，序列结尾不能有多余空格。

输入样例

6 2
1 2 3 4 5 6

输出样例

5 6 1 2 3 4

分析：数组长度为n，要想把数组循环右移m位，只需要先将整个数组a倒置，再将数组前m位倒置，最后将数组后n-m位倒置即可完成循环右移m位～reverse函数可以实现将一个数组或者vector中元素倒置，这个函数在algorithm头文件中～（如果m大于n，那么循环右移m位相当于循环右移m%n位，因为那些n倍数位的移动是多余的，所以在使用m之前，先将m = m%n）
```

```c++
#include<bits/stdc++.h>
using namespace std;

int main() {
    int n,m;//数组长度 后移长度 
    cin >> n >> m;
    m = m % n;//成倍的右移无意义 取余数 
    vector<int> v(n);//输入数组 
    for(int i = 0; i < n; i++) {
        cin >> v[i];
    }
    while(m) {//先整个数组翻转 在前m位翻转 再后n-m位翻转 
        reverse(begin(v),begin(v) + n);
        reverse(begin(v),begin(v) + m);
        reverse(begin(v) + m,begin(v) + n);
        break;
    }
    for(int i = 0;i < n - 1;i++){//规范输出 
        cout << v[i] << " ";
    }
    cout << v[n - 1];
}
```

### vector数组翻转

```c++
reverse(begin(v),begin(v) + n);//从begin指向的元素到begin+n指向的元素翻转
reverse(begin(v),begin(v) + m);
reverse(begin(v) + m,begin(v) + n);
```

## **1009 说反话 (20 分)**

```
题目描述

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

输入格式

测试输入包含一个测试用例，在一行内给出总长度不超过80的字符串。字符串由若干单词和若干空格组成，其中单词是由英文字母（大小写有区分）组成的字符串，单词之间用1个空格分开，输入保证句子末尾没有多余的空格。

输出格式

每个测试用例的输出占一行，输出倒序后的句子。

输入样例

Hello World Here I Come

输出样例

Come I Here World Hello
分析：将输入的每个单词s都分别v.push(s)压入栈中，再输出栈顶v.top()，然后将栈顶元素弹出v.pop()，直到栈空为止～
```

```
#include<bits/stdc++.h>
using namespace std;

int main() {
    stack<string> v;//新建stack 
    string s; 
    while(cin >> s){//将输入的每个单词s都分别v.push(s)压入栈中
        v.push(s);
    }
    cout << v.top();//输出栈顶v.top()
    v.pop();
    while(!v.empty()){//将栈顶元素弹出v.pop()，直到栈空为止～
        cout << " " << v.top();
        v.pop();
    }
}
```

### stack栈的基本用法

```
stack<int> s; // 定义⼀个空栈s
for (int i = 0; i < 6; i++) {
    s.push(i); // 将元素i压⼊栈s中
}
cout << s.top() << endl; // 访问s的栈顶元素
cout << s.size() << endl; // 输出s的元素个数
s.pop(); // 移除栈顶元素
```

## **1010 一元多项式求导 (25 分)**

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

输入格式:
以指数递降方式输入多项式非零项系数和指数（绝对值均为不超过 1000 的整数）。数字间以空格分隔。

输出格式:
以与输入相同的格式输出导数多项式非零项的系数和指数。数字间以空格分隔，但结尾不能有多余空格。注意“零多项式”的指数和系数都是 0，但是表示为 0 0。

输入样例:
3 4 -5 2 6 1 -2 0
结尾无空行
输出样例:
12 3 -10 1 6 0
结尾无空行
```

```
#include<bits/stdc++.h>
using namespace std;

int main() {
    int a,b;//输入 
    int flag = 1;
    while(cin >> a >> b) {//循环处理2个数 
        //scanf("%d %d",&a,&b) != EOF
        if(a * b != 0 && flag == 1) {
            cout << a * b << " " << (b - 1);
            flag = 0;
        } else if(a * b != 0 && flag == 0)
            cout << " "  << a * b << " " << (b - 1);
        if(flag == 1)cout << "0 0";//若未进入上循环，则输出0 0 
    }
}
```

## **1011 A+B 和 C (15 分)**

```
题目描述：
给定区间[-2^31, 2^31]内的3个整数A、B和C，请判断A+B是否大于C。
输入格式：
输入第1行给出正整数T(<=10)，是测试用例的个数。随后给出T组测试用例，每组占一行，顺序给出A、B和C。整数间以空格分隔。
输出格式：
对每组测试用例，在一行中输出“Case #X: true”如果A+B>C，否则输出“Case #X: false”，其中X是测试用例的编号（从1开始）。
输入样例：
4
1 2 3
2 3 4
2147483647 0 2147483646
0 -2147483648 -2147483647
输出样例：
Case #1: false
Case #2: true
Case #3: true

Case #4: false

分析：使用long long int存储a、b和c，当a + b > c的时候输出true，否则输出false～
```

```
#include<bits/stdc++.h>
using namespace std;

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

## 1012 数字分类 (20)

```
给定一系列正整数，请按要求对数字进行分类，并输出以下5个数字：
A1 = 能被5整除的数字中所有偶数的和；
A2 = 将被5除后余1的数字按给出顺序进行交错求和，即计算n1-n2+n3-n4…；
A3 = 被5除后余2的数字的个数；
A4 = 被5除后余3的数字的平均数，精确到小数点后1位；
A5 = 被5除后余4的数字中最大数字。

输入格式

每个输入包含1个测试用例。每个测试用例先给出一个不超过1000的正整数N，
随后给出N个不超过1000的待分类的正整数。数字间以空格分隔。

输出格式

对给定的N个正整数，按题目要求计算A1~A5并在一行中顺序输出。
数字间以空格分隔，但行末不得有多余空格。
若其中某一类数字不存在，则在相应位置输出“N”。

输入样例1

13 1 2 3 4 5 6 7 8 9 10 20 16 18

输出样例1

30 11 2 9.7 9

输入样例2

8 1 2 4 5 6 7 9 16

输出样例2

N 11 2 N 9
```

```
#include<bits/stdc++.h>
using namespace std;

int main(){
    int N;//输入数字的个数 
    cin >> N;
    int m;//临时输入的数字 
    
    int a1=0,a2=0,a3=0,a5=0;
    double a4=0;
    double sum = 0;
    int temp = 0;
    int flag = -1;
    for(int i = 0;i < N;i++){
        cin >> m;//输入的数字 
        
        switch(m % 5){
            case 0:
                if(m % 2 == 0){
                    a1 += m;//偶数 
                }break;
            case 1:
                flag = (-1)*flag;
                a2 += flag*m;//n1-n2+n3... 
                temp = 1;
                break;
            case 2:
                a3++;break;//统计个数 
            case 3:
                sum += m;
                a4++;//总和 平均数 
                break;
            case 4:
                if(a5 < m){
                    a5 = m;//最大数 
                }
                break;
        }        
    }
    if(a1 != 0)cout << a1 << " ";
        else cout << "N ";
        
        if(a2 == 0 && temp == 0)cout << "N ";
        else cout << a2 << " ";
        
        if(a3 != 0)cout << a3 << " ";
        else cout << "N ";
        
        if(a4 != 0)printf("%.1f ",sum/a4);
        else cout << "N ";
        
        if(a5 != 0)cout << a5;
        else cout << "N";
}
```

## **1013 数素数 (20 分)**

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

输入格式：

输入在一行中给出M和N，其间以空格分隔。

输出格式：

输出从PM到PN的所有素数，每10个数字占1行，其间以空格分隔，但行末不得有多余空格。

输入样例：

5 27

输出样例：

11 13 17 19 23 29 31 37 41 43
47 53 59 61 67 71 73 79 83 89
97 101 103

分析：vector中保存第M到第N个素数，用cnt标记输出了多少个，如果当前已经输出的个数为10的倍数，则输出一个空行～
```

```
#include<bits/stdc++.h>
using namespace std;

int isprime(int a) {// 素数判断 
    if(a <= 1) return 0;
    for(int i = 2; i * i <= a; i++)
        if(a % i == 0) return 0;
    return 1;
}

int main() {
    int a,b;//两个正整数a，b 
    cin >> a >> b;
    int cnt = 0;//当前输出的素数次序 
    int temp = 0;//若能整除10 输出换行 
    for(int i = 2;i < 1000001;i++){
        if(isprime(i)){
            cnt++;
            if(cnt >= a && cnt < b){//规范输出 
                temp++;
                if(temp % 10 == 0) cout << i << endl;
                else cout << i << " ";
            }
            if(cnt == b) {
                cout << i;
                break;
            }
        }
    }
}
```

## **1014 福尔摩斯的约会 (20 分)**

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

输入格式

输入在4行中分别给出4个非空、不包含空格、且长度不超过60的字符串。

输出格式

在一行中输出约会的时间，格式为“DAY HH:MM”，其中“DAY”是某星期的3字符缩写,即MON表示星期一，TUE表示星期二，WED表示星期三，THU表示星期四，FRI表示星期五，SAT表示星期六，SUN表示星期日。题目输入保证每个测试存在唯一解。

输入样例

3485djDkxh4hhGE
2984akDfkkkkggEdsb
s&hgsfdk
d&Hyscvnm

输出样例

THU 14:04

分析：按照题目所给的方法找到相等的字符后判断即可，如果输出的时间不足2位数要在前面添0，即用%02d输出～
```

```
#include<bits/stdc++.h>
using namespace std;

int main() {
    string s1,s2,s3,s4;
    cin >> s1 >> s2 >> s3 >> s4;
    int j = 0;//保存第一次比较完的位置 
    char week[8][10] = {"MON","TUE","WED","THU","FRI","SAT","SUN"};

    for(int i = 0; i < s1.size() && i < s2.size(); i++) {//首次出现A-G间的字母 
        if(s1[i] >= 'A' && s1[i] <= 'G' && s1[i] == s2[i]) {
            printf("%s ",week[s1[i] - 'A']);
            j = i;
            break;
        }
    }

    for(int i = j + 1; i < s1.size() && i < s2.size(); i++) {//第二次出现0-9或者A-N 
        if((s1[i] >= '0' && s1[i] <= '9') &&  (s1[i] == s2[i])) {
            printf("%02d:",s1[i] - '0');
            break;
        } else if ((s1[i] >= 'A' && s1[i] <= 'N') &&  (s1[i] == s2[i])) {
            printf("%02d:",s1[i] - 'A' + 10);
            break;
        }
    }
    for(int i = 0; i < s3.size() && i < s4.size(); i++) {//出现首次相等的字母的位置i 
        if((s3[i] >= 'a' && s3[i] <= 'z') ||  (s3[i] >= 'A' && s3[i] <= 'Z')) {
            if (s3[i] == s4[i]) {
                printf("%02d",i);
                return 0;
            }
            
        }
    }
}
```

## **1015 德才论 (25 分)**

```
题目描述：

宋代史学家司马光在《资治通鉴》中有一段著名的“德才论”：“是故才德全尽谓之圣人，才德兼亡谓之愚人，德胜才谓之君子，才胜德谓之小人。凡取人之术，苟不得圣人，君子而与之，与其得小人，不若得愚人。”
现给出一批考生的德才分数，请根据司马光的理论给出录取排名。

输入格式：

输入第1行给出3个正整数，分别为：N（<=105），即考生总数；L（>=60），为录取最低分数线，即德分和才分均不低于L的考生才有资格被考虑录取；H（<100），为优先录取线——德分和才分均不低于此线的被定义为“才德全尽”，此类考生按德才总分从高到低排序；才分不到但德分到线的一类考生属于“德胜才”，也按总分排序，但排在第一类考生之后；德才分均低于H，但是德分不低于才分的考生属于“才德兼亡”但尚有“德胜才”者，按总分排序，但排在第二类考生之后；其他达到最低线L的考生也按总分排序，但排在第三类考生之后。
随后N行，每行给出一位考生的信息，包括：准考证号、德分、才分，其中准考证号为8位整数，德才分为区间[0, 100]内的整数。数字间以空格分隔。

输出格式：

输出第1行首先给出达到最低分数线的考生人数M，随后M行，每行按照输入格式输出一位考生的信息，考生按输入中说明的规则从高到低排序。当某类考生中有多人总分相同时，按其德分降序排列；若德分也并列，则按准考证号的升序输出。

输入样例：

14 60 80
10000001 64 90
10000002 90 60
10000011 85 80
10000003 85 80
10000004 80 85
10000005 82 77
10000006 83 76
10000007 90 78
10000008 75 79
10000009 59 90
10000010 88 45
10000012 80 100
10000013 90 99
10000014 66 60

输出样例：

12
10000013 90 99
10000012 80 100
10000003 85 80
10000011 85 80
10000004 80 85
10000007 90 78
10000006 83 76
10000005 82 77
10000002 90 60
10000014 66 60
10000008 75 79
10000001 64 90

分析：用结构体存储。写好cmp函数~结构体数组vector v[4]中v[0]保存第一类考生，v[1]保存第二类考生…以此类推。写好cmp函数很重要，cmp函数中，排序先按照总分排序，然后按照德分排序，最后按照准考证号排序…最后输出符合条件的结果～
```

```
#include<bits/stdc++.h>
using namespace std;

struct stu {//学生结构体 学号 德 才 
    int num,de,cai;
};
int cmp(stu a,stu b) {
    if(a.de + a.cai != b.de + b.cai) return a.de + a.cai > b.de + b.cai;//总分降序 
    if(a.de != b.de) return a.de > b.de;//德分降序 
    else return a.num < b.num;//学号升序 
}

int main() {
    int n,l,h;//学生数 最低分 优秀分 
    cin >> n >> l >> h;
    stu st;//临时学生 
    vector<stu> v[4];//划分4类学生 
    int cnt = n;//学生总数 
    for(int i = 0; i < n; i++) {
        cin >> st.num >> st.de >> st.cai;
        if(st.de < l || st.cai < l) {//不及格学生，过线人数-1 
            cnt--;
        } else if(st.de >= h && st.cai >= h) { //德才皆备 1类学生 
            v[0].push_back(st);
        } else if(st.de >= h && st.cai < h) {//德大于才 2类学生 
            v[1].push_back(st);
        } else if(st.de < h && st.cai < h && st.de >= st.cai) {//德才小于优秀但德大于才 3类 
            v[2].push_back(st);
        } else v[3].push_back(st);//过线但无优点 4类 
    }

    cout << cnt << endl;
    for(int i = 0; i < 4; i++) {
        sort(v[i].begin(),v[i].end(),cmp);//每类学生内部按规则排序 
        for(int j = 0; j < v[i].size(); j++) {//规范输出 
            cout << v[i][j].num << " " << v[i][j].de << " " << v[i][j].cai << endl;
        }
    }
}
```

### vector存放结构体

```
vector<stu> v[4];//划分4类学生
stu st;//定义类
v[0].push_back(st);//存放学生

```

## 1016  部分A+B(15)

```
正整数A的“DA（为1位整数）部分”定义为由A中所有DA组成的新整数PA。例如：给定A = 3862767，DA = 6，则A的“6部分”PA是66，因为A中有2个6。
现给定A、DA、B、DB，请编写程序计算PA + PB。

输入格式

输入在一行中依次给出A、DA、B、DB，中间以空格分隔，其中0 < A, B < 10^10。

输出格式

在一行中输出PA + PB的值。

输入样例1

3862767 6 13530293 3

输出样例1

399

输入样例2

3862767 1 13530293 8

输出样例2

0

分析：将A和B保存在string a和b中，将DA和DB保存在da和db中，因为A为字符串，所以对于它的每一位a[i]，当da == (a[i]- '0')时候表示da和a[i]相等，则pa = pa * 10 + da；B同理，当db == (b[i]- '0')时候表示db和b[i]相等，则pb = pb * 10 + db；最后输出pa+pb的值～
```

```
#include<bits/stdc++.h>
using namespace std;

int main(){
    string s1,s2;
    int n,m;
    int num1 = 0,num2 = 0;
    int a = 0,b = 0;
    
    cin >> s1 >> n >> s2 >> m;
    
    for(int i = 0;i < s1.size();i++){
        if(n == (s1.at(i)-'0')){
            num1++;
        }
    }
    
    for(int i = 0;i < num1;i++){
        a += n * pow(10,i);
    }
    
    
    for(int i = 0;i < s2.size();i++){
        if(m == (s2.at(i)-'0')){
            num2++;
        }
    }
    for(int i = 0;i < num2;i++){
        b += m * pow(10,i);
    }
    cout << a + b;    
}
```

### 未知循环次数

```
while(a!=0)
```

## **1017 A除以B (20 分)**

```
本题要求计算A/B，其中A是不超过1000位的正整数，B是1位正整数。你需要输出商数Q和余数R，
使得A = B * Q + R成立。

输入格式

输入在1行中依次给出A和B，中间以1空格分隔。

输出格式

在1行中依次输出Q和R，中间以1空格分隔。

输入样例

123456789050987654321 7

输出样例

17636684150141093474 3

分析：模拟手动除法的过程，每次用第一位去除以B，如果得到的商不是0就输出，否则就*10+下一位，直到最后的数为余数～
```

```
#include<bits/stdc++.h>
using namespace std;

int main() {
    int b;//除数 
    string s,s1;//被除数 输出结果 
    cin >> s >> b;
    int temp = 0;//商 
    int temp1 = 0;//余数 
    for(int i = 0; i < s.size();i++){
        int a = s[i] - '0';//单个字符变数字 
        a = 10 * temp1 + a;//取余数的10倍+商 
        temp = a / b;
        temp1 = a % b;
        s1 += temp + '0';//数字变字符 
    } 
    if(s1[0] == '0' && s1.size() > 1) s1 = s1.substr(1);//当s1长度大于1且首字符为0时 忽略首0 
    cout << s1 << " " << temp1;
}
```

## 1018 锤子剪刀布 (20)

```
大家应该都会玩“锤子剪刀布”的游戏：两人同时给出手势，胜负规则如图所示：现给出两人的交锋记录，请统计双方的胜、平、负次数，并且给出双方分别出什么手势的胜算最大。

输入格式

输入第1行给出正整数N（<=105），即双方交锋的次数。随后N行，每行给出一次交锋的信息，即甲、乙双方同时给出的的手势。C代表“锤子”、J代表“剪刀”、B代表“布”，第1个字母代表甲方，第2个代表乙方，中间有1个空格。

输出格式

输出第1、2行分别给出甲、乙的胜、平、负次数，数字间以1个空格分隔。第3行给出两个字母，分别代表甲、乙获胜次数最多的手势，中间有1个空格。如果解不唯一，则输出按字母序最小的解。

输入样例

10
C J
J B
C B
B B
B C
C C
C B
J B
B C
J J

输出样例

5 3 2
2 3 5
B B

分析：jiawin、yiwin分别表示甲乙赢的次数，s和t分别表示每一次甲乙给出的手势，maxjia和maxyi分别表示甲乙获胜次数最多的手势所对应的下标（012分别表示BCJ），枚举每一次甲乙手势的胜负结果并累加到jiawin和yiwin中，最后根据题目要求输出结果～
```

```
#include<bits/stdc++.h>
using namespace std;

int main(){
    int n;//交锋次数 
    cin >> n;
    int jiawin = 0;//甲win次数 
    int yiwin = 0;//乙win次数 
    int jia[3] = {0};//甲赢的方式 
    int yi[3] = {0};//乙赢的方式 
    for(int i = 0; i < n; i++){
        char s,t;
        cin >> s >> t;
        if(s == 'C' && t == 'J'){
            jiawin++;
            jia[1]++;
        }else if(s == 'B' && t == 'C'){
            jiawin++;
            jia[0]++;
        }else if(s == 'J' && t == 'B'){
            jiawin++;
            jia[2]++;
        }else if(s == 'C' && t == 'B'){
            yiwin++;
            yi[0]++;
        }else if(s == 'J' && t == 'C'){
            yiwin++;
            yi[1]++;
        }else if(s == 'B' && t == 'J'){
            yiwin++;
            yi[2]++;
        }
    }
    cout << jiawin << " "<< (n - jiawin - yiwin) << " "<< yiwin << endl;
    cout << yiwin << " "<< (n - jiawin - yiwin) << " "<< jiawin << endl;
    
    int maxjia = jia[0] >= jia[1] ? 0 : 1;//0，1,2判断哪种赢得次数最大 
    maxjia = jia[2] > jia[maxjia] ? 2 : maxjia;
    int maxyi = yi[0] >= yi[1] ? 0 : 1;
    maxyi = yi[2] > yi[maxyi] ? 2 : maxyi;
    
    char str[4] = {"BCJ"};//4位数组存放BCJ 
    cout << str[maxjia] << " " << str[maxyi];
} 
```

## **1019 数字黑洞 (20 分)**

```
给定任一个各位数字不完全相同的4位正整数，如果我们先把4个数字按非递增排序，再按非递减排序，然后用第1个数字减第2个数字，将得到一个新的数字。一直重复这样做，我们很快会停在有“数字黑洞”之称的6174，这个神奇的数字也叫Kaprekar常数。
例如，我们从6767开始，将得到
7766 – 6677 = 1089
9810 – 0189 = 9621
9621 – 1269 = 8352
8532 – 2358 = 6174
7641 – 1467 = 6174
… …
现给定任意4位正整数，请编写程序演示到达黑洞的过程。

输入格式

输入给出一个(0, 10000)区间内的正整数N。

输出格式

如果N的4位数字全相等，则在一行内输出“N – N = 0000”；否则将计算的每一步在一行内输出，直到6174作为差出现，输出格式见样例。注意每个数字按4位数格式输出。

输入样例1

6767

输出样例1

7766 – 6677 = 1089
9810 – 0189 = 9621
9621 – 1269 = 8352
8532 – 2358 = 6174

输入样例2

2222

输出样例2

2222 – 2222 = 0000

分析：有一个测试用例注意点，如果当输入N值为6174的时候，依旧要进行下面的步骤，直到差值为6174才可以～所以用do while语句，无论是什么值总是要执行一遍while语句，直到遇到差值是0000或6174～

s.insert(0, 4 – s.length(), ‘0’);用来给不足4位的时候前面补0～
```

```
#include<bits/stdc++.h>
using namespace std;

int cmp(char a,char b){// 从大到小 
    return a > b;
}

int main() {
    string s;
    cin >> s;
    s.insert(0,4 - s.size(),'0');//不足4位前面补0 
    int result;
    do{
        string s1 = s,s2 = s ;
        sort(s1.begin(),s1.end(),cmp);//从大到小 
        sort(s2.begin(),s2.end());//从小到大（默认） 
        result = stoi(s1) - stoi(s2);//字符串转数字求差 
        string s3 = to_string(result);
        s3.insert(0,4 - s3.size(),'0');//差转字符串再补0 
        cout << s1 << " - " << s2 << " = " << s3 << endl;//输出 
        s = s3;
    }while(result != 6174 && result != 0);//结果不为6174或0时 继续循环 
}
```

## **1020 月饼 (25 分)**

```
月饼是中国人在中秋佳节时吃的一种传统食品，不同地区有许多不同风味的月饼。现给定所有种类月饼的库存量、总售价、以及市场的最大需求量，请你计算可以获得的最大收益是多少。

注意：

销售时允许取出一部分库存。样例给出的情形是这样的：假如我们有3种月饼，其库存量分别为18、15、10万吨，总售价分别为75、72、45亿元。如果市场的最大需求量只有20万吨，那么我们最大收益策略应该是卖出全部15万吨第2种月饼、以及5万吨第3种月饼，获得 72 + 45/2 = 94.5（亿元）。

输入格式

每个输入包含1个测试用例。每个测试用例先给出一个不超过1000的正整数N表示月饼的种类数、以及不超过500（以万吨为单位）的正整数D表示市场最大需求量。随后一行给出N个正数表示每种月饼的库存量（以万吨为单位）；最后一行给出N个正数表示每种月饼的总售价（以亿元为单位）。数字间以空格分隔。

输出格式

对每组测试用例，在一行中输出最大收益，以亿元为单位并精确到小数点后2位。

输入样例

3 20
18 15 10
75 72 45

输出样例

94.50

分析：首先根据月饼的总价和数量计算出每一种月饼的单价，然后将月饼数组按照单价从大到小排序，根据需求量need的大小，从单价最大的月饼开始售卖，将销售掉这种月饼的价格累加到result中，最后输出result即可～
```

```c++
#include<bits/stdc++.h>
using namespace std;

struct node {//结构体 数量 总价 单价 
    double num,price,unit;
};

int cmp(node a,node b) {//按单价降序排列 
    return a.unit > b.unit;
}

int main() {
    int n,m;//月饼种类数 需求量 
    cin >> n >> m;
    double sum = 0.0;//需求的总价 
    vector<node> v(n);//容器装月饼 
    for(int i = 0; i < n; i++)    cin >> v[i].num;
    for(int i = 0; i < n; i++)    cin >> v[i].price;
    for(int i = 0; i < n; i++)  v[i].unit = v[i].price / v[i].num;
    sort(v.begin(),v.end(),cmp);//排序 
    for(int i = 0; i < n && m >= 0; i++) {
        if(m >= v[i].num) {//当需求量大于该类月饼 
            sum += v[i].price;
            m -= v[i].num;
        } else {//需求量小于月饼数 
            sum += m * v[i].unit;
            break;
        }
    }
    printf("%.2f",sum);
}
```

## **1021 个位数统计 (15 分)**

给定一个 *k* 位整数 *N*=*d**k*−110*k*−1+⋯+*d*1101+*d*0 (0≤*d**i*≤9, *i*=0,⋯,*k*−1, *d**k*−1>0)，请编写程序统计每种不同的个位数字出现的次数。例如：给定 *N*=100311，则有 2 个 0，3 个 1，和 1 个 3。

输入格式：

每个输入包含 1 个测试用例，即一个不超过 1000 位的正整数 *N*。

输出格式：

对 *N* 中每一种不同的个位数字，以 `D:M` 的格式在一行中输出该位数字 `D` 及其在 *N* 中出现的次数 `M`。要求按 `D` 的升序输出。

输入样例：

```in
100311
```

输出样例：

```out
0:2
1:3
3:1
```

```
#include<bits/stdc++.h>
using namespace std;

int main(){
    string s;
    cin >> s;
    int num[11] = {0};
    
    for(int i = 0;i < s.size();i++){
        int n;
        n = s.at(i)-'0';
        num[n]++;
    }
    
    for(int i = 0;i < 10;i++){
        if(num[i] != 0){
            cout << i << ":" << num[i] <<endl;
        }
    }
}
```

### string字符串/char数组/数字转换

```
char[] -> string：str=c；
string -> char[] ：strcpy(c,s.c_str())

char[] -> num：sscanf(c,"%d",&n);
num -> char[]：sprintf(c,"%d",n);

string -> num：n=stoi(str);
num -> string：str=to_string(n);
```

### 输出字符所代表的十进制

```
char str=‘b’;
cout<<str-‘0’+‘0’;
cout<<'1'-'0'+'0'<<endl;：49
cout<<'b'-'0'+'0';：98
```

## 1022. D进制的A+B (20)

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

输入格式

输入在一行中依次给出3个整数A、B和D。

输出格式

输出A+B的D进制数。

输入样例

123 456 8

输出样例

1103

分析：设t = A + B，将每一次t % d的结果保存在int类型的数组s中，然后将t / d，直到 t 等于 0为止，此时s中保存的就是 t 在 D 进制下每一位的结果的倒序，最后倒序输出s数组即可～
```

```
#include<bits/stdc++.h>
using namespace std;

int main() {
    long long a,b,d;//数a b 进制D 
    cin >> a >> b >> d;
    long long sum = a + b;//求和 
    vector<int> v;
    if(sum == 0) cout << 0;//若和为0 输出0 
    int result = sum,carry;
    while(result){//模拟手动进制运算 
        carry = result % d;//余数，即结果 
        result = result / d;//商，不为0继续循环 
        v.push_back(carry);
    }
    for(int i = v.size() - 1;i >= 0;i--) cout << v[i];//倒序输出 
}
```

## **1023 组个最小数(20 分)**

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

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

输入格式：
输入在一行中给出 10 个非负整数，顺序表示我们拥有数字 0、数字 1、……数字 9 的个数。整数间用一个空格分隔。10 个数字的总个数不超过 50，且至少拥有 1 个非 0 的数字。

输出格式：
在一行中输出能够组成的最小的数。

输入样例：
2 2 0 0 0 3 0 0 1 0
结尾无空行
输出样例：
10015558
结尾无空行
```

```
#include<bits/stdc++.h> 
using namespace std;

int main(){
    int a[10],t;//10位数字
    for(int i = 0;i < 10;i++){
        cin >> a[i];
    }
    
    for(int i = 1;i < 10;i++){//除0外的最小数放在第一个
        if(a[i] != 0){
            cout << i;
            t = i;
            break;
        }
    }
    
    for(int i = 0;i < a[0];i++) cout << 0;//输出0
    for(int i = 0;i < a[t] - 1;i++) cout << t;//输出除0外的最小数
    for(int i = t + 1;i < 10;i++){//后续的数依次输出
        for(int j = 0;j < a[i];j++){
            cout << i;
        }
    }    
} 
```

## 1024. 科学计数法 (20)

```
科学计数法是科学家用来表示很大或很小的数字的一种方便的方法，其满足正则表达式[+-][1-9]”.”[0-9]+E[+-][0-9]+，即数字的整数部分只有1位，小数部分至少有1位，该数字及其指数部分的正负号即使对正数也必定明确给出。
现以科学计数法的格式给出实数A，请编写程序按普通数字表示法输出A，并保证所有有效位都被保留。

输入格式

每个输入包含1个测试用例，即一个以科学计数法表示的实数A。该数字的存储长度不超过9999字节，且其指数的绝对值不超过9999。

输出格式

对每个测试用例，在一行中按普通数字表示法输出A，并保证所有有效位都被保留，包括末尾的0。

输入样例1

+1.23400E-03

输出样例1

0.00123400

输入样例2

-1.2E+10

输出样例2

-12000000000

分析：n保存E后面的字符串所对应的数字，t保存E前面的字符串，不包括符号位。当n<0时表示向前移动，那么先输出0. 然后输出abs(n)-1个0，然后继续输出t中的所有数字；当n>0时候表示向后移动，那么先输出第一个字符，然后将t中尽可能输出n个字符，如果t已经输出到最后一个字符(j == t.length())那么就在后面补n-cnt个0，否则就补充一个小数点. 然后继续输出t剩余的没有输出的字符～
```

```
#include<bits/stdc++.h>
using namespace std;

int main() {
    string s;// 输入科学计数字符串
    cin >> s;
    int i;
    while(s[i] != 'E') i++;//找到E对应的下标
    string t = s.substr(1,i - 1);//提取数字的前面部分
    int n = stoi(s.substr(i + 1));//提取指数部分
    if(s[0] == '-') cout << "-";//若是负数 输出负号
    if(n < 0) {//当指数小于0
        cout << "0.";
        n = abs(n) - 1;
        while(n--) cout << "0";//输出0.000。。。 小数点后n-1个0
        for(i = 0; i < t.size(); i++) {
            if(t[i] != '.') cout << t[i];
        }
    } else {//当指数大于0
        cout << t[0];//输出首位
        int cnt,i;
        for(i = 2,cnt = 0; i < t.size() && cnt < n; i++,cnt++) {
            //从小数点后1位开始输出，直到输出结束或截止到n 记录此时位置i
            cout << t[i];
        }
        if(i == t.size()) {//若i等于t长度 说明有剩余的0没输出
            for(int j = 0; j < n - cnt; j++) cout << "0";
        } else {//若i不等于t长度 说明仍为小数
            cout << '.';
            for(int j = i; j < t.size(); j++) {
                cout << t[j];
            }
        }
    }
}
```

## **1025 反转链表 (25 分)**

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

输入格式：

每个输入包含1个测试用例。每个测试用例第1行给出第1个结点的地址、结点总个数正整数N(<= 10^5)、以及正整数K(<=N)，即要求反转的子链结点的个数。结点的地址是5位非负整数，NULL地址用-1表示。
接下来有N行，每行格式为：Address Data Next
其中Address是结点地址，Data是该结点保存的整数数据，Next是下一结点的地址。

输出格式：

对每个测试用例，顺序输出反转后的链表，其上每个结点占一行，格式与输入相同。

输入样例：

00100 6 4
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 00000
99999 5 68237
12309 2 33218

输出样例：

00000 4 33218
33218 3 12309
12309 2 00100
00100 1 99999
99999 5 68237
68237 6 -1

分析：输入样例正确连接顺序应该是：
/*
00100 1 12309
12309 2 33218
33218 3 00000
00000 4 99999
99999 5 68237
68237 6 -1
*/
还应该考虑输入样例中有不在链表中的结点的情况。所以用个sum计数~

而且，algorithm头文件里面有reverse函数可以直接调用～
```

```
#include<bits/stdc++.h>
using namespace std;

struct node{// 结构体 存放链表 
    int add,data,next;
};

int cmp(node a,node b){// 结构体按data升序 
    return a.data < b.data;
}

int main() {
    int first,n,k;//首地址 数据 下一节点地址 
    cin >> first >> n >> k;
    vector<node> v(n);// 数组存放节点 
    for(int i = 0; i < n;i++){//输入 
        cin >> v[i].add >> v[i].data >> v[i].next;
    }
    sort(v.begin(),v.end(),cmp);//排序 
    int temp = n;
    for(int i = 0; i < n;i += k){//翻转 
        if(k <= temp) reverse(v.begin() + i,v.begin() + i + k);
        temp -= k;
    }
    for(int i = 0; i < n - 1;i++) {//规范输出 
        printf("%05d %d %05d\n",v[i].add,v[i].data,v[i + 1].add);
    }
    printf("%05d %d -1",v[n-1].add,v[n-1].data);
}
```

## **1026 程序运行时间 (15 分)**

```
要获得一个 C 语言程序的运行时间，常用的方法是调用头文件 time.h，其中提供了 clock() 函数，可以捕捉从程序开始运行到 clock() 被调用时所耗费的时间。这个时间单位是 clock tick，即“时钟打点”。同时还有一个常数 CLK_TCK，给出了机器时钟每秒所走的时钟打点数。于是为了获得一个函数 f 的运行时间，我们只要在调用 f 之前先调用 clock()，获得一个时钟打点数 C1；在 f 执行完成后再调用 clock()，获得另一个时钟打点数 C2；两次获得的时钟打点数之差 (C2-C1) 就是 f 运行所消耗的时钟打点数，再除以常数 CLK_TCK，就得到了以秒为单位的运行时间。

这里不妨简单假设常数 CLK_TCK 为 100。现给定被测函数前后两次获得的时钟打点数，请你给出被测函数运行的时间。

输入格式：
输入在一行中顺序给出 2 个整数 C1 和 C2。注意两次获得的时钟打点数肯定不相同，即 C1 < C2，并且取值在 [0,10 7]。

输出格式：
在一行中输出被测函数运行的时间。运行时间必须按照 hh:mm:ss（即2位的 时:分:秒）格式输出；不足 1 秒的时间四舍五入到秒。

输入样例：
123 4577973

输出样例：
12:42:59
```

```
#include<bits/stdc++.h>
using namespace std;

int main() {
    int c1,c2;
    cin >> c1 >> c2;
    
    int num = (c2 - c1 + 50) / 100;//四舍五入 
    int h = num / 3600;
    int m = num % 3600 / 60;
    int s = num % 60;
    
    printf("%02d:%02d:%02d",h,m,s);
}
```

### 整数相除的四舍五入

1.整数除法用 “/”的话得到的是一个整数（得到小数的话自动去掉小数位只保留整数位）
2.先将两个数转化为double类型，再进行“/”除法。

```
double c1,c2;
    scanf("%lf%lf",&c1,&c2);
    double c = c2-c1;
    double time = c/100;
    printf("%f",time);

输出：
123 4577973
45778.500000
```

```
四舍五入：
    1.round（）
    2."/100"之后要判断四舍五入，所以判断后两位 >=50与否！ 
    if(time%100>=50){
        time=time/100+1;
    }
    else{
        time=time/100;
    }
```

    保留小数：
    1.cout<<setprecision(2)<<fixed<<...
    2.cout<<setiosflags(ios::fixed)<<setprecision(2)<<...

```
cout<<setprecision(2)<<fixed<< round(c/100)<<endl;
cout<<setiosflags(ios::fixed)<<setprecision(2)<<round(c/100);
45779.00
45779.00

cout<<setprecision(2)<<fixed<<1.235;//1.24
```

## **1027 打印沙漏 (20 分)**

```
本题要求你写个程序把给定的符号打印成沙漏的形状。例如给定17个“*”，要求按下列格式打印
*****
***
*
***
*****
所谓“沙漏形状”，是指每行输出奇数个符号；各行符号中心对齐；相邻两行符号数差2；符号数先从大到小顺序递减到1，再从小到大
顺序递增；首尾符号数相等。给定任意N个符号，不一定能正好组成一个沙漏。要求打印出的沙漏能用掉尽可能多的符号。

输入格式

输入在一行给出1个正整数N（<=1000）和一个符号，中间以空格分隔。

输出格式

首先打印出由给定符号组成的最大的沙漏形状，最后在一行中输出剩下没用掉的符号数。

输入样例：

19 *

输出样例：

*****
***
*
***
*****
2

分析：每个沙漏都是从最中间一行行向上下分别扩展一行，每次扩展行都要比之前一层多2个符号，最中间一行只有 1 个符号，假设扩展的层数为 i，则扩展出去的上边需要的所有符号个数为3 + 5 + 7 + … + (2i+1) = (3 + 2i + 1) * i / 2 = i * (i + 2)，扩展出去的下边与上边同样多所以乘以2，加上最重要那一行1个符号，所以 总共需要2 * i * (i + 2) + 1个符号，所以i从0到N，找满足(2 * i * (i + 2) + 1) > N的最小的 i，因为符号不能超过N，所以只能扩展出去 i-1 行，用变量row表示从最中间一行需要扩展出去的行数，row = i – 1，接下来开始输出，上面的每一行，对于扩展出去的第 i 层需要输出row – i个空格，接着输出i * 2 + 1个符号c和换行符；对于最中间一行，需要输出row – 1个空格、符号c和换行符；对于下面的每一行，对于扩展出去的第i层，需要输出row-i个空格，接着输出i * 2 + 1个符号c和换行符，因为用掉的符号数为2 * row * (row + 2) + 1，所以最后输出剩下没用掉的符号数为N – (2 * row * (row + 2) + 1)～
```

```
#include <iostream>
using namespace std;
int main() {
    int N, row = 0;
    char c;
    cin >> N >> c;
    for (int i = 0; i < N; i++) {
        if ((2 * i * (i + 2) + 1) > N) {
            row = i - 1;
            break;
        }
    }
    for (int i = row; i >= 1; i--) {
        for (int k = row - i; k >= 1; k--) cout << " ";
        for (int j = i * 2 + 1; j >= 1; j--) cout << c;
        cout << endl;
    }
    for (int i = 0; i < row; i++) cout << " ";
    cout << c << endl;
    for (int i = 1; i <= row; i++) {
        for (int k = row - i; k >= 1; k--) cout << " ";
        for (int j = i * 2 + 1; j >= 1; j--) cout << c;
        cout << endl;
    }
    cout << (N - (2 * row * (row + 2) + 1));
    return 0;
}
```

## **1030 完美数列 (25 分)**

```
给定一个正整数数列，和正整数 p，设这个数列中的最大值是 M，最小值是 m，如果 M≤mp，则称这个数列是完美数列。

现在给定参数 p 和一些正整数，请你从中选择尽可能多的数构成一个完美数列。

输入格式：
输入第一行给出两个正整数 N 和 p，其中 N（≤10 
5
 ）是输入的正整数的个数，p（≤10 
9
 ）是给定的参数。第二行给出 N 个正整数，每个数不超过 10 
9
 。

输出格式：
在一行中输出最多可以选择多少个数可以用它们组成一个完美数列。

输入样例：
10 8
2 3 20 4 5 1 6 7 8 9
结尾无空行
输出样例：
8
结尾无空行
```

```
#include<bits/stdc++.h>
using namespace std;

int main() {
    int N;//整数的个数 
    long long p;//参数p 
    scanf("%d%lld",&N,&p);
    
    vector<int> v(N);//可变数组 
    for(int i = 0; i < N;i++){
        cin >> v[i];
    }
    
    sort(v.begin(),v.end());//从小到大排序 
    
    int result = 0;//最长的数组 
    int tmp = 0;//临时数 
    
    for(int i = 0;i < N;i++){
        for(int j = i + result;j < N;j++){
            if(v[j] <= v[i] * p){
                tmp = j - i + 1;
                if(tmp > result) result = tmp;
            }else {
                break;
            }
        }
    }
    cout << result;
}
```

### vector的排序

```
sort(v.begin(),v.end());//从小到大排序 
sort(v.begin(),v.end(),cmp);//按比较器的顺序排序
```

## **1032 挖掘机技术哪家强 (20 分)**

```
为了用事实说明挖掘机技术到底哪家强，PAT 组织了一场挖掘机技能大赛。现请你根据比赛结果统计出技术最强的那个学校。

输入格式：
输入在第 1 行给出不超过 10 
5
  的正整数 N，即参赛人数。随后 N 行，每行给出一位参赛者的信息和成绩，包括其所代表的学校的编号（从 1 开始连续编号）、及其比赛成绩（百分制），中间以空格分隔。

输出格式：
在一行中给出总得分最高的学校的编号、及其总分，中间以空格分隔。题目保证答案唯一，没有并列。

输入样例：
6
3 65
2 80
1 100
2 70
3 40
3 0
输出样例：
2 150
```

```
#include<bits/stdc++.h>
using namespace std;

int main() {
    int N;//参赛者认识 
    cin >> N;
    int a[100001] = {0};

    int id;//代表学校 
    int score;//个人成绩 
    for(int i = 0; i < N; i++) {//输入每个人的成绩和学校 
        cin >> id >> score;
        a[id] += score;//在数组中对应的学校编号增加成绩 
    }

    int t = 0;//临时数，记录成绩最大的学校 
    int max = -1;//最大值 
    for(int i = 0; i < 100001; i++) {//
        if(max < a[i]) {
            max = a[i];
            t = i;
        }
    }
    if(max) cout << t << " " << max;
    else cout << id << " " << max;
}
```

## **1042 字符统计 (20 分)**

```
请编写程序，找出一段给定文字中出现最频繁的那个英文字母。

输入格式：
输入在一行中给出一个长度不超过 1000 的字符串。字符串由 ASCII 码表中任意可见字符及空格组成，至少包含 1 个英文字母，以回车结束（回车不算在内）。

输出格式：
在一行中输出出现频率最高的那个英文字母及其出现次数，其间以空格分隔。如果有并列，则输出按字母序最小的那个字母。统计时不区分大小写，输出小写字母。

输入样例：
This is a simple TEST.  There ARE numbers and other symbols 1&2&3...........
结尾无空行
输出样例：
e 7
结尾无空行
```

```
#include<bits/stdc++.h>
using namespace std;

int main(){
    string s;
    getline(cin,s);//读取整行字符 
    
    int tmp[128] = {0};//128长度的数组记录ASCII码 
    int len = s.size();//记录数组的长度 
    
    for(int i = 0;i < len;i++){
        if(s[i] >= 'A' && s[i] <= 'Z'){
            s[i] =s[i] -  'A' + 'a';//大小写转换 
        }
        if(s[i] >= 'a' && s[i] <= 'z'){
            tmp[s[i]]++;//对应ASCII码的数量+1 
        }
    }
    
    char p = 'a';//最小字母a 
    for(char i = 'b';i < 'z';i++){
        if(tmp[i] > tmp[p]){
            p = i;
        }
    }
    
    cout << p << " " << tmp[p];
}
```

## **1053 住房空置率 (20 分)**

```
在不打扰居民的前提下，统计住房空置率的一种方法是根据每户用电量的连续变化规律进行判断。判断方法如下：

在观察期内，若存在超过一半的日子用电量低于某给定的阈值 e，则该住房为“可能空置”；

若观察期超过某给定阈值 D 天，且满足上一个条件，则该住房为“空置”。

现给定某居民区的住户用电量数据，请你统计“可能空置”的比率和“空置”比率，即以上两种状态的住房占居民区住房总套数的百分比。

输入格式：
输入第一行给出正整数 N（≤1000），为居民区住房总套数；正实数 e，即低电量阈值；正整数 D，即观察期阈值。随后 N 行，每行按以下格式给出一套住房的用电量数据：

其中 K 为观察的天数，Ei为第 i 天的用电量。

输出格式：
在一行中输出“可能空置”的比率和“空置”比率的百分比值，其间以一个空格分隔，保留小数点后 1 位。

输入样例：
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
结尾无空行
输出样例：
40.0% 20.0%
结尾无空行
```

```
#include<bits/stdc++.h>
using namespace std;

int main(){
    int N,D,k;//N 住房数 D 观察阈值 k 观察的天数 
    int maybe = 0,must=0;//可能为空和一定为空 
    double e,temp;//低电量阈值 临时数 
    
    cin >> N >> e >> D;
    for(int i = 0;i < N;i++){
        cin >> k;
        int sum = 0;//记录低于阈值的天数 
        for(int j = 0;j < k;j++){
            cin >> temp;
            if(temp < e)sum++;//若低于e 则天数+1 
        }
        if(sum > (k/2)){//若满足低电量天数大于观察天数的一半 则为可能空置或空置 
            k > D ? maybe++:must++;//满足观察天数大于k/2 则一定空置 
        }
    }
    
    double mayberesult = (double)maybe/N*100;//转化为百分比 
    double mustresult = (double)must/N*100;//转化为百分比 
    
    printf("%.1f%% %.1f%%",mustresult,mayberesult);//%%表示输出一个%
}
```

## 1055 集体照 (25 分)

```
拍集体照时队形很重要，这里对给定的 N 个人 K 排的队形设计排队规则如下：

每排人数为 N/K（向下取整），多出来的人全部站在最后一排；

后排所有人的个子都不比前排任何人矮；

每排中最高者站中间（中间位置为 m/2+1，其中 m 为该排人数，除法向下取整）；

每排其他人以中间人为轴，按身高非增序，先右后左交替入队站在中间人的两侧（例如5人身高为190、188、186、175、170，则队形为175、188、190、186、170。这里假设你面对拍照者，所以你的左边是中间人的右边）；

若多人身高相同，则按名字的字典序升序排列。这里保证无重名。

现给定一组拍照人，请编写程序输出他们的队形。

输入格式：
每个输入包含 1 个测试用例。每个测试用例第 1 行给出两个正整数 N（≤10 
4
 ，总人数）和 K（≤10，总排数）。随后 N 行，每行给出一个人的名字（不包含空格、长度不超过 8 个英文字母）和身高（[30, 300] 区间内的整数）。

输出格式：
输出拍照的队形。即K排人名，其间以空格分隔，行末不得有多余空格。注意：假设你面对拍照者，后排的人输出在上方，前排输出在下方。

输入样例：
10 3
Tom 188
Mike 170
Eva 168
Tim 160
Joe 190
Ann 168
Bob 175
Nick 186
Amy 160
John 159
结尾无空行
输出样例：
Bob Tom Joe Nick
Ann Mike Eva
Tim Amy John
结尾无空行
```

```
#include<bits/stdc++.h>
using namespace std;

struct stu { //结构体创建
    string name;
    int h;
} st[10001];

bool cmp(stu a,stu b) { //比较方法
    return a.h != b.h ? a.h > b.h : a.name < b.name;
}
int main() {
    int N,K;//学生数and每列学生数
    cin >> N >> K;
    for(int i = 0; i < N; i++) { //输入学生信息
        cin >> st[i].name >> st[i].h;
    }

    sort(st,st+N,cmp);//排序

    int row = K;//行数
    int t = 0;//st[t]初始化下标
    while(row) {
        int m;//每行的人数
        if(row == K) { //初始行
            m = N/K + N%K;
        } else //普通行
            m = N/K;

        vector<string> ans(m);//人名数组
        ans[m/2] = st[t].name;//四舍五入 身高最高者

        int j = m/2 - 1;//左边 身高2-4-6...
        for(int i = t + 1; i < t + m; i += 2) {
            ans[j--] = st[i].name;
        }

        int k = m/2 + 1;//右边 身高3-5-7...
        for(int i = t + 2; i < t + m; i += 2) {
            ans[k++] = st[i].name;
        }

        cout << ans[0];//输出
        for(int i = 1; i < m; i++) {
            cout << " " << ans[i];
        }
        cout << endl;
        t = t + m;//st[t]下标递进
        row--;//下一行
    }
}
```

## **1060 爱丁顿数 (25 分)**

```
英国天文学家爱丁顿很喜欢骑车。据说他为了炫耀自己的骑车功力，还定义了一个“爱丁顿数” E ，即满足有 E 天骑车超过 E 英里的最大整数 E。据说爱丁顿自己的 E 等于87。

现给定某人 N 天的骑车距离，请你算出对应的爱丁顿数 E（≤N）。

输入格式：
输入第一行给出一个正整数 N (≤10 5)，即连续骑车的天数；第二行给出 N 个非负整数，代表每天的骑车距离。

输出格式：
在一行中给出 N 天的爱丁顿数。

输入样例：
10
6 7 6 9 3 10 8 2 7 8
结尾无空行
输出样例：
6
结尾无空行

分析：从下标1开始存储n天的公里数在数组a中，对n个数据从大到小排序，i表示了骑车的天数，那么满足a[i] > i的最大值即为所求
```

## **1062 最简分数 (20 分)**

```
一个分数一般写成两个整数相除的形式：N/M，其中 M 不为0。最简分数是指分子和分母没有公约数的分数表示形式。

现给定两个不相等的正分数 N 
要求你按从小到大的顺序列出它们之间分母为 K 的最简分数。

输入格式：
输入在一行中按 N/M 的格式给出两个正分数，随后是一个正整数分母 K，其间以空格分隔。题目保证给出的所有整数都不超过 1000。

输出格式：
在一行中按 N/M 的格式列出两个给定分数之间分母为 K 的所有最简分数，按从小到大的顺序，其间以 1 个空格分隔。行首尾不得有多余空格。题目保证至少有 1 个输出。

输入样例：
7/18 13/20 12
结尾无空行
输出样例：
5/12 7/12
结尾无空行
```

```
#include<bits/stdc++.h>
using namespace std;

int gcd(int n,int m){
    return (!m)?n:gcd(m,n%m);//辗转相除求公约数 
}

int main(){
    int n1,n2,m1,m2,k;
    double e1,e2;
    scanf("%d/%d %d/%d %d",&n1,&n2,&m1,&m2,&k);
    e1 = n1 * 1.0 / n2;//整数先乘1.0 
    e2 = m1 * 1.0 / m2;
    int flag = 1;
    
    for(int i = 1;i < k;i++){
        double temp;
        if(gcd(i,k) == 1){
            temp = i * 1.0 / k;
            if((temp> e1 && temp < e2) ||
            (temp > e2 && temp < e1)){
                if(flag == 1){
                printf("%d/%d",i,k);flag++;}
                else printf(" %d/%d",i,k);    
            }
        }
    }
}
```

## **1067 试密码 (20 分)**

```
当你试图登录某个系统却忘了密码时，系统一般只会允许你尝试有限多次，当超出允许次数时，账号就会被锁死。本题就请你实现这个小功能。

输入格式：
输入在第一行给出一个密码（长度不超过 20 的、不包含空格、Tab、回车的非空字符串）和一个正整数 N（≤ 10），分别是正确的密码和系统允许尝试的次数。随后每行给出一个以回车结束的非空字符串，是用户尝试输入的密码。输入保证至少有一次尝试。当读到一行只有单个 # 字符时，输入结束，并且这一行不是用户的输入。

输出格式：
对用户的每个输入，如果是正确的密码且尝试次数不超过 N，则在一行中输出 Welcome in，并结束程序；如果是错误的，则在一行中按格式输出 Wrong password: 用户输入的错误密码；当错误尝试达到 N 次时，再输出一行 Account locked，并结束程序。

输入样例 1：
Correct%pw 3
correct%pw
Correct@PW
whatisthepassword!
Correct%pw
#
结尾无空行
输出样例 1：
Wrong password: correct%pw
Wrong password: Correct@PW
Wrong password: whatisthepassword!
Account locked
结尾无空行
输入样例 2：
cool@gplt 3
coolman@gplt
coollady@gplt
cool@gplt
try again
#
结尾无空行
输出样例 2：
Wrong password: coolman@gplt
Wrong password: coollady@gplt
Welcome in
结尾无空行
```

```
#include<bits/stdc++.h>
using namespace std;

int main() {
    int N;//允许尝试的最大次数 
    string s;//密码 
    cin >> s >> N;
    int cnt = 0;//尝试次数 
    getchar();//换行符 
    string test;//尝试密码 
    while(1) {
        getline(cin,test);//读取整行 
        if(test == "#") break;//读取到#结束 
        cnt++;//尝试次数+1 
        if(cnt <= N && test == s) {//密码正确 
            cout << "Welcome in";
            break;
        } else if(cnt <= N && test != s) {//密码错误 
            cout << "Wrong password: " << test << endl;
            if(cnt == N) {
                cout << "Account locked";
                break;
            }
        }
    }
}
```

## **1068 万绿丛中一点红 (20 分)**

```
对于计算机而言，颜色不过是像素点对应的一个 24 位的数值。现给定一幅分辨率为 M×N 的画，要求你找出万绿丛中的一点红，即有独一无二颜色的那个像素点，并且该点的颜色与其周围 8 个相邻像素的颜色差充分大。

输入格式：
输入第一行给出三个正整数，分别是 M 和 N（≤ 1000），即图像的分辨率；以及 TOL，是所求像素点与相邻点的颜色差阈值，色差超过 TOL 的点才被考虑。随后 N 行，每行给出 M 个像素的颜色值，范围在 [0,2 
24
 ) 内。所有同行数字间用空格或 TAB 分开。

输出格式：
在一行中按照 (x, y): color 的格式输出所求像素点的位置以及颜色值，其中位置 x 和 y 分别是该像素在图像矩阵中的列、行编号（从 1 开始编号）。如果这样的点不唯一，则输出 Not Unique；如果这样的点不存在，则输出 Not Exist。

输入样例 1：
8 6 200
0      0       0        0        0          0           0        0
65280      65280    65280    16711479 65280    65280    65280    65280
16711479 65280    65280    65280    16711680 65280    65280    65280
65280      65280    65280    65280    65280    65280    165280   165280
65280      65280       16777015 65280    65280    165280   65480    165280
16777215 16777215 16777215 16777215 16777215 16777215 16777215 16777215
结尾无空行
输出样例 1：
(5, 3): 16711680
结尾无空行
输入样例 2：
4 5 2
0 0 0 0
0 0 3 0
0 0 0 0
0 5 0 0
0 0 0 0
结尾无空行
输出样例 2：
Not Unique
结尾无空行
输入样例 3：
3 3 5
1 2 3
3 4 5
5 6 7
结尾无空行
输出样例 3：
Not Exist
结尾无空行
```

```
#include<bits/stdc++.h>
using namespace std;

int main() {
    int m,n,tol;//行 列 阈值 
    cin >> m >> n >> tol;
    int color[n][m];//像素 
    map<int,int> mp;//判断是否唯一 

    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            cin >> color[i][j];
            mp[color[i][j]]++;
        }
    }
    int k = 0;
    int h,l;

    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if(mp[color[i][j]] == 1) { //判断是否唯一 
                if(fabs(color[i][j]-color[i-1][j-1]>tol&&fabs(color[i][j]-color[i-1][j])>tol&&fabs(color[i][j]-color[i][j-1])>tol&&fabs(color[i][j]-color[i+1][j-1])>tol&&fabs(color[i][j]-color[i-1][j+1])>tol&&fabs(color[i][j]-color[i+1][j])>tol&&fabs(color[i][j]-color[i][j+1])>tol&&fabs(color[i][j]-color[i+1][j+1])>tol))
                    //判断与周围像素差值与阈值的大小 
                    {
                        k++;//若满足，数量++ 
                        h = i + 1; 
                        l = j + 1;
                    }
                }
        }
    }
    
    if(k == 0) cout << "Not Exist";
    if(k > 1)  cout << "Not Unique";
    if(k == 1) printf("(%d,%d): %d",l,h,color[h-1][l-1]);
}
```

## **1071 小赌怡情 (15 分)**

```
常言道“小赌怡情”。这是一个很简单的小游戏：首先由计算机给出第一个整数；然后玩家下注赌第二个整数将会比第一个数大还是小；玩家下注 t 个筹码后，计算机给出第二个数。若玩家猜对了，则系统奖励玩家 t 个筹码；否则扣除玩家 t 个筹码。

注意：玩家下注的筹码数不能超过自己帐户上拥有的筹码数。当玩家输光了全部筹码后，游戏就结束。

输入格式：
输入在第一行给出 2 个正整数 T 和 K（≤ 100），分别是系统在初始状态下赠送给玩家的筹码数、以及需要处理的游戏次数。随后 K 行，每行对应一次游戏，顺序给出 4 个数字：

n1 b t n2
其中 n1 和 n2 是计算机先后给出的两个[0, 9]内的整数，保证两个数字不相等。b 为 0 表示玩家赌小，为 1 表示玩家赌大。t 表示玩家下注的筹码数，保证在整型范围内。

输出格式：
对每一次游戏，根据下列情况对应输出（其中 t 是玩家下注量，x 是玩家当前持有的筹码量）：

玩家赢，输出 Win t! Total = x.；
玩家输，输出 Lose t. Total = x.；
玩家下注超过持有的筹码量，输出 Not enough tokens. Total = x.；
玩家输光后，输出 Game Over. 并结束程序。
输入样例 1：
100 4
8 0 100 2
3 1 50 1
5 1 200 6
7 0 200 8
结尾无空行
输出样例 1：
Win 100!  Total = 200.
Lose 50.  Total = 150.
Not enough tokens.  Total = 150.
Not enough tokens.  Total = 150.
结尾无空行
输入样例 2：
100 4
8 0 100 2
3 1 200 1
5 1 200 6
7 0 200 8
结尾无空行
输出样例 2：
Win 100!  Total = 200.
Lose 200.  Total = 0.
Game Over.
```

```
#include<bits/stdc++.h>
using namespace std;

int main() {
    int T,K;//T 初始筹码  K 游戏的次数
    cin >> T >> K;
    getchar();//读取换行
    int num = T;//初始筹码数

    for(int i = 0; i < K; i++) {
        int n1,n2,t,b;//n1 n2比大小 b=0为小b=1为大 t为下注数
        scanf("%d %d %d %d",&n1,&b,&t,&n2);
        if(t <= num) { //下注数小于筹码数，允许游戏
            if((n1 > n2 && b == 0) ||(n1 < n2 && b == 1) ) { //猜对
                num += t;//赢筹码
                printf("Win %d!  Total = %d.\n",t,num);
            } else { //
                num -= t;
                printf("Lose %d.  Total = %d.\n",t,num);
            }
        } else if(t > num && num > 0){ //下注数大于筹码数，不允许游戏
            printf("Not enough tokens.  Total = %d.\n",num);
        }
        if(num <= 0) {
            cout << "Game Over.";//
            return 0;
        }
    }
}
```

## **1072 开学寄语 (20 分)**

```
本题要求你写个程序帮助这所学校的老师检查所有学生的物品，以助其成大器。

输入格式：
输入第一行给出两个正整数 N（≤ 1000）和 M（≤ 6），分别是学生人数和需要被查缴的物品种类数。第二行给出 M 个需要被查缴的物品编号，其中编号为 4 位数字。随后 N 行，每行给出一位学生的姓名缩写（由 1-4 个大写英文字母组成）、个人物品数量 K（0 ≤ K ≤ 10）、以及 K 个物品的编号。

输出格式：
顺次检查每个学生携带的物品，如果有需要被查缴的物品存在，则按以下格式输出该生的信息和其需要被查缴的物品的信息（注意行末不得有多余空格）：

姓名缩写: 物品编号1 物品编号2 ……
最后一行输出存在问题的学生的总人数和被查缴物品的总数。

输入样例：
4 2
2333 6666
CYLL 3 1234 2345 3456
U 4 9966 6666 8888 6666
GG 2 2333 7777
JJ 3 0012 6666 2333
结尾无空行
输出样例：
U: 6666 6666
GG: 2333
JJ: 6666 2333
3 5
结尾无空行
```

```
#include<bits/stdc++.h>
using namespace std;

int main() {
    int N,M;//N 学生人数 M 待查物品种类数 
    cin >> N >> M;
    int forbid[10001] = {0};//10000种物品 
    int tmp;

    for(int i = 0; i < M; i++) {
        scanf("%4d",&tmp);
        forbid[tmp] = 1;//物品id==1 代表违禁
    }

    string name;
    int k;//物品件数 
    int goods;//物品id 
    int cnt1 = 0;//违规学生数 
    int cnt2 = 0;//违规物品数 

    for(int i = 0; i < N; i++) {
        cin >> name >> k;
        int flag = 0;
        for(int j = 0; j < k; j++) {
            cin >> goods;
            if(forbid[goods]) {//若该物品违规 
                if(flag == 0) {//首次查到违规物品，违规学生+1 输出违规学生名 
                    cout << name << ":";
                    cnt1++;
                }
                printf(" %04d",goods);//输出违规物品id 
                flag = 1;//重置flag 
                cnt2++;//违规物品数+1 
            }
        }
        if(flag == 1) cout << endl;//
    }
    cout << cnt1 << " " << cnt2;//
}
```

## **1074 宇宙无敌加法器 (20 分)**

```
地球人习惯使用十进制数，并且默认一个数字的每一位都是十进制的。而在 PAT 星人开挂的世界里，每个数字的每一位都是不同进制的，这种神奇的数字称为“PAT数”。每个 PAT 星人都必须熟记各位数字的进制表，例如“……0527”就表示最低位是 7 进制数、第 2 位是 2 进制数、第 3 位是 5 进制数、第 4 位是 10 进制数，等等。每一位的进制 d 或者是 0（表示十进制）、或者是 [2，9] 区间内的整数。理论上这个进制表应该包含无穷多位数字，但从实际应用出发，PAT 星人通常只需要记住前 20 位就够用了，以后各位默认为 10 进制。

在这样的数字系统中，即使是简单的加法运算也变得不简单。例如对应进制表“0527”，该如何计算“6203 + 415”呢？我们得首先计算最低位：3 + 5 = 8；因为最低位是 7 进制的，所以我们得到 1 和 1 个进位。第 2 位是：0 + 1 + 1（进位）= 2；因为此位是 2 进制的，所以我们得到 0 和 1 个进位。第 3 位是：2 + 4 + 1（进位）= 7；因为此位是 5 进制的，所以我们得到 2 和 1 个进位。第 4 位是：6 + 1（进位）= 7；因为此位是 10 进制的，所以我们就得到 7。最后我们得到：6203 + 415 = 7201。

输入格式：
输入首先在第一行给出一个 N 位的进制表（0 < N ≤ 20），以回车结束。 随后两行，每行给出一个不超过 N 位的非负的 PAT 数。

输出格式：
在一行中输出两个 PAT 数之和。

输入样例：
30527
06203
415
结尾无空行
输出样例：
7201
结尾无空行
```

```
#include<bits/stdc++.h>
using namespace std;

int main(){
    string s1,s2,s,ans;//s N位的进制表 s1 s2 两个待求和PAT数  
    int flag = 0;//
    int carry = 0;//临时数 加法的进位 
    cin >> s >> s1 >> s2;
    ans = s;//
    
    string ss1(s.size()-s1.size(),'0');//将ss1赋值为s-s1长度的'0' 
    s1 = ss1 + s1;//s1转化为和s等长的字符串 
    string ss2(s.size()-s2.size(),'0');//
    s2 = ss2 + s2;//s2转化为和s等长的字符串 
    
    for(int i = s.size() - 1;i >=0;i--){//从后往前运算 
        int mod = s[i] == '0' ? 10:(s[i] - '0');//若余数为0 则为10 若为其他 则-'0' 
        ans[i] = (s1[i] - '0' + s2[i] - '0' + carry) % mod + '0';//ans为求和所得数 
        carry = (s1[i] - '0' + s2[i] - '0' + carry) / mod;//进位 
    }
    
    if(carry != 0)ans = '1' + ans;//若进位不为0 则在ans之前加个1 
    for(int i = 0;i < ans.size();i++){
        if(ans[i] != '0' || flag == 1){//不为首位的0都需要输出 
            cout << ans[i];//
            flag = 1;//
        }
    }    
    if(flag == 0)cout << 0;//若ans全为0 则输出0 
    
}
```

## **1076 Wifi密码 (15 分)**

```
输入格式：
输入第一行给出一个正整数 N（≤ 100），随后 N 行，每行按照 编号-答案 的格式给出一道题的 4 个选项，T 表示正确选项，F 表示错误选项。选项间用空格分隔。

输出格式：
在一行中输出 wifi 密码。

输入样例：
8
A-T B-F C-F D-F
C-T B-F A-F D-F
A-F D-F C-F B-T
B-T A-F C-F D-F
B-F D-T A-F C-F
A-T C-F B-F D-F
D-T B-F C-F A-F
C-T A-F B-F D-F
结尾无空行
输出样例：
13224143
结尾无空行
```

```
#include<bits/stdc++.h>
using namespace std;

int main() {
    int N;//待处理行数 
    cin >> N;
    string s1;//WiFi密码 
    getchar();//换行 为代码getline准备 
    for(int i = 0; i < N; i++) {
        string s; 
        getline(cin,s);//读取整行（带空格 
        for(int i = 0; i < s.size(); i++) {
            if(s.at(i) == 'T') {//若遇到T 
                s1 += (s.at(i-2) - 'A' + 1 + '0');//T的前两位的字母+1并转为char 存放s1 
            }
        }
    }
    cout << s1;//输出数WiFi密码 
}
```

## **1078 字符串压缩与解压 (20 分)**

```
文本压缩有很多种方法，这里我们只考虑最简单的一种：把由相同字符组成的一个连续的片段用这个字符和片段中含有这个字符的个数来表示。例如 ccccc 就用 5c 来表示。如果字符没有重复，就原样输出。例如 aba 压缩后仍然是 aba。

解压方法就是反过来，把形如 5c 这样的表示恢复为 ccccc。

本题需要你根据压缩或解压的要求，对给定字符串进行处理。这里我们简单地假设原始字符串是完全由英文字母和空格组成的非空字符串。

输入格式：
输入第一行给出一个字符，如果是 C 就表示下面的字符串需要被压缩；如果是 D 就表示下面的字符串需要被解压。第二行给出需要被压缩或解压的不超过 1000 个字符的字符串，以回车结尾。题目保证字符重复个数在整型范围内，且输出文件不超过 1MB。

输出格式：
根据要求压缩或解压字符串，并在一行中输出结果。

输入样例 1：
C
TTTTThhiiiis isssss a   tesssst CAaaa as
结尾无空行
输出样例 1：
5T2h4is i5s a3 te4st CA3a as
结尾无空行
输入样例 2：
D
5T2h4is i5s a3 te4st CA3a as10Z
结尾无空行
输出样例 2：
TTTTThhiiiis isssss a   tesssst CAaaa asZZZZZZZZZZ
结尾无空行
```

```
#include<bits/stdc++.h>
using namespace std;

int main() {
    char t;//输入字符（模式）
    cin >> t;//C or D
    getchar();//换行
    string s,num;//S:待处理字符串 num：字符串个数
    getline(cin,s);//输入

    char pre;//压缩记录
    int cnt = 1;//连续字符个数

    int tmp = 1;
    if(t == 'D') {
        for(int i = 0; i < s.size(); i++) {
            if(s[i] >= '0' && s[i] <= '9') {
                num += s[i];//数字读取到num中
            } else {
                if(num.size() > 0)  tmp = stoi(num);//字符串转数字
                while(tmp--) {
                    cout << s[i];//输入num个字符s[i]
                }
                tmp = 1;//重新初始化
                num="";
            }
        }
    }

    else {
        pre = s[0];
        for(int i = 1; i < s.size(); i++) {
            if(s[i] == pre) { //相同则+1
                cnt++;
            } else {
                if(cnt >= 2) cout << cnt;//大于2 则输出数字
                cout << pre;//输出数字
                cnt = 1;//重新初始化
                pre = s[i];
            }
        }
        if(cnt >= 2) cout << cnt;
        cout << pre;
    }

}
```

## **1086 就不告诉你 (15 分)**

```
输入格式：
输入在第一行给出两个不超过 1000 的正整数 A 和 B，其间以空格分隔。

输出格式：
在一行中倒着输出 A 和 B 的乘积。

输入样例：
5 7
结尾无空行
输出样例：
53
结尾无空行
```

```
#include<bits/stdc++.h> 
using namespace std;

int main(){
    int n,m;
    cin >> n >> m;//输入n m待乘 
    
    int num = n * m;
    string s;
    s = to_string(num);//数字转字符串 
    reverse(s.begin(),s.end());// 字符串翻转 
    
    int d;
    d = stoi(s);//字符串转数字 
    cout << d;
    
}
```

## **1090 危险品装箱 (25 分)**

```
集装箱运输货物时，我们必须特别小心，不能把不相容的货物装在一只箱子里。比如氧化剂绝对不能跟易燃液体同箱，否则很容易造成爆炸。

本题给定一张不相容物品的清单，需要你检查每一张集装箱货品清单，判断它们是否能装在同一只箱子里。

输入格式：
输入第一行给出两个正整数：N (≤10 4是成对的不相容物品的对数；M (≤100) 是集装箱货品清单的单数。

随后数据分两大块给出。第一块有 N 行，每行给出一对不相容的物品。第二块有 M 行，每行给出一箱货物的清单，格式如下：

K G[1] G[2] ... G[K]
其中 K (≤1000) 是物品件数，G[i] 是物品的编号。简单起见，每件物品用一个 5 位数的编号代表。两个数字之间用空格分隔。

输出格式：
对每箱货物清单，判断是否可以安全运输。如果没有不相容物品，则在一行中输出 Yes，否则输出 No。

输入样例：
6 3
20001 20002
20003 20004
20005 20006
20003 20001
20005 20004
20004 20006
4 00001 20004 00002 20003
5 98823 20002 20003 20006 10010
3 12345 67890 23333
结尾无空行
输出样例：
No
Yes
Yes
结尾无空行
```

```
#include<bits/stdc++.h>
using namespace std;

int main() {
    int N,M;//N 成对的危险品数 M待查的货数
    int t1,t2;//成对的危险品id
    cin >> N >> M;
    map<int,vector<int>> m;//map存放成对的危险品
    for(int i = 0; i < N; i++) {
        scanf("%d%d",&t1,&t2);
        m[t1].push_back(t2);//将t1放进t2  互斥
        m[t2].push_back(t1);//将t2放进t1  互斥
    }

    while(M--) {
        int k,flag = 0,a[100001] = {0};        //k 货品件数  数组a存放100000个id
        scanf("%d",&k);
        vector<int> v(k);//vector存放物品id
        for(int i = 0; i < k; i++) {
            scanf("%d",&v[i]);
            a[v[i]] = 1;//货品对应的件数为1 代表存在该物品
        }

        for(int i = 0; i < v.size(); i++) { //从0到k件物品
            for(int j = 0; j < m[v[i]].size(); j++) { //从0到物品id对应map的长度
                if(a[m[v[i]][j]] == 1) flag = 1;//若数组对应的物品id，则危险 不能输出
            }
        }
        printf("%s\n",flag == 1? "No":"Yes");//flag为1则NO 为0则Yes
    }
}
```

## **1091 N-自守数 (15 分)**

```
如果某个数 K 的平方乘以 N 以后，结果的末尾几位数等于 K，那么就称这个数为“N-自守数”。例如 3×92 2=25392，而 25392 的末尾两位正好是 92，所以 92 是一个 3-自守数。

本题就请你编写程序判断一个给定的数字是否关于某个 N 是 N-自守数。

输入格式：
输入在第一行中给出正整数 M（≤20），随后一行给出 M 个待检测的、不超过 1000 的正整数。

输出格式：
对每个需要检测的数字，如果它是 N-自守数就在一行中输出最小的 N 和 NK 
2 的值，以一个空格隔开；否则输出 No。注意题目保证 N<10。

输入样例：
3
92 5 233
结尾无空行
输出样例：
3 25392
1 25
No
```

```
#include<bits/stdc++.h>
using namespace std;

int main() {
    int N;//输入待检测数量
    cin >> N;
    int m;//临时待测数据
    int num;//j*m*m
    int num1 = 0;//自守数

    for(int i = 0; i < N; i++) {
        int flag = 0;//判断是否进入循环
        cin >> m;
        for(int j = 1; j < 10; j++) { //自守数<10
            num = j * m * m;//判断条件
            string s1,s2;
            s1 = to_string(num);//数字->字符串
            s2 = to_string(m);//
            if(s1.substr(s1.size() - s2.size()) == s2) { //对比
                flag = 1;//进入循环 为自守数
                num1 = j;//N-自守数
                break;
            }
        }
        if(flag == 1) { //为自守数的情况
            printf("%d %d",num1,num);
            if(i != N - 1)  cout << endl;
        } else {
            cout << "No";
            if(i != N - 1)  cout << endl;
        }
    }
}
```

## **1094 谷歌的招聘 (20 分)**

```
自然常数 e 是一个著名的超越数，前面若干位写出来是这样的：e = 2.718281828459045235360287471352662497757247093699959574966967627724076630353547594571382178525166427427466391932003059921... 其中粗体标出的 10 位数就是答案。

本题要求你编程解决一个更通用的问题：从任一给定的长度为 L 的数字中，找出最早出现的 K 位连续数字所组成的素数。

输入格式：
输入在第一行给出 2 个正整数，分别是 L（不超过 1000 的正整数，为数字长度）和 K（小于 10 的正整数）。接下来一行给出一个长度为 L 的正整数 N。

输出格式：
在一行中输出 N 中最早出现的 K 位连续数字所组成的素数。如果这样的素数不存在，则输出 404。注意，原始数字中的前导零也计算在位数之内。例如在 200236 中找 4 位素数，0023 算是解；但第一位 2 不能被当成 0002 输出，因为在原始数字中不存在这个 2 的前导零。

输入样例 1：
20 5
23654987725541023819
结尾无空行
输出样例 1：
49877
结尾无空行
输入样例 2：
10 3
2468001680
结尾无空行
输出样例 2：
404
结尾无空行
```

```
#include<bits/stdc++.h>
using namespace std;

int isprime(int num){//判断素数 
    if(num == 1 || num == 0) return 0;
    for(int i = 2;i <= sqrt(num);i++){
        if(num % i == 0) return 0;
    }
    return 1;
}

int main(){
    int L,K;//数字长度L 连续长度K 
    cin >> L >> K;
    
    string s;//输入长度为L的字符串 
    cin >> s;
    
    string s2;//长度为5的字符串 
    if(L < K){
        cout << "404";
        return 0;
    }
    
    for(int i = 0;i <= s.size() - K;i++){
        int num;
        s2 = s.substr(i,K);//从i开始取K位数 
        num = stoi(s2);//字符串->数字 
        if(isprime(num)){ //若素数，输出 
            cout << s2;
            return 0;
        }
      
    }
    cout << "404";//
    return 0;
}
```

# 2021PAT秋季乙级

## 7-1 好数 (15 分)

```
好数是指由一对正整数 a<b 按照 a 2 a ^ 2a 
2
  + ab + b 2 b ^ 2b 
2
 这个规则生成的数，a 和 b 就称为这个好数的源头。例如 91 就是一个好数，
因为 5 2 5 ^ 25 
2
  + 5 × 6 + 6 2 6 ^ 26 
2
  = 91，于是数对（5，6）就是 91 的源头。而对于一个好数，其源头并不一定唯一，例如（1，9）就是 91 的另一个源头。

本题就要求你编写程序，判断一个给定的数字是否好，并且输出好数的所有源头。

输入格式：
输入在第一行给出一个不超过 100 的正整数 N，随后 N 行，每行给出一个不超过 1 0 4 10 ^ 410 
4
 的正整数。

输出格式：
对于每一个输入的数字，如果其是好数，则首先在一行中输出 Yes，然后每行输出它的一个源头，格式为 a b，按 a 的递增顺序输出；否则在一行中输出 No和比该数大的最小的好数，其间以空格分隔，然后每行输出这个好数的一个源头，格式同上。

输入样例
3
1
91
50

输出样例
No 7
1 2
Yes
1 9
5 6
No 52
2 6
```

```
#include<bits/stdc++.h>
using namespace std;

int main() {
    int n;// 待测数字个数 
    cin >> n;
    int m;//每次输入的数 
    int flag = 1;
    for(int i = 0; i < n; i++) {
        cin >> m;
        flag = 1;//找到好数的标志 
        int flag1 = 1;//输入的数就是好数的标志 
        int temp = m;//临时数 当temp不等于m时，找到的好数不是输入的数 
        while(flag) {
            for(int i = 1; i <= temp - 1; i++) {
                for(int j = i + 1; j <= temp; j++) {
                    if(i * i + i * j + j * j == temp) {//好数判断 
                        if(temp == m && flag1 == 1) {//输入的数为好数 输出一次Yes 
                            cout << "Yes" << endl;
                            flag1 = 0;
                        } else if(temp != m && flag1 == 1)cout << "No" << " " << temp << endl;
                        //输入的数非好数 输出一次No 并找到下一个好数 
                        cout << i << " " << j << endl;
                        flag = 0;
                    }
                }
            }
            temp++;//
        }
    }
}
```

## 7-2 数以类聚 (20 分)

```
我们把所有各位数字的乘积相同的数归为一类。例如 1362 和 2332 就是同一类，因为 1×3×6×2=2×3×3×2。给定 N 个正整数，请你判断它们可以被归成多少不同的类？

输入格式：
输入在第一行给出一个正整数 N（≤ 1 0 5 10 ^ 510 
5
 ），第二行给出 N 个不超过 1 0 7 10 ^ 710 
7
 的正整数，数字间以空格分隔。

输出格式：
在一行中输出 N 个给定的整数可以归类的数量、以及规模最大的类中最小的乘积。数字间以一个空格分隔。

输入样例：
10
1234 98 329 9552 47621 8862 5539 2333 5365 463

输出样例：
7 54

样例说明：
10 个给定数字对应的各位数字乘积依次为：24、72、54、450、336、768、675、54、450、72。所以一共有 7 个不同的种类，即：24、72、54、450、336、768、675。
其中规模最大的有 2 个 54、2 个 72、2 个 450。即这 3 个种类都分别对应了 2 个数字，在规模相等、都是最大的情况下，我们输出最小的乘积 54。

解题思路
简单排序题：抠出数位->计算乘积->数据分组->数据排序->输出答案
```

```
#include<bits/stdc++.h>
using namespace std;

int main() {
    int a[100001] = {0};//创建大数组 对应位置存放乘积出现的次数
    string s;//输入的数
    int n;//输入个数
    cin >> n;

    for(int i = 0; i < n; i++) {
        cin >> s;//输入数
        int sum = 1;
        for(int i = 0; i < s.size(); i++) {//提取每位数 相乘 到sum上
            sum *= s[i] - '0';
        }
        a[sum]++;//对应位置的数目+1
    }

    int cnt = 0;//种类数
    int maxId = 0;//最大的类出现的id
    int max = 0;//最大的类出现的次数
    for(int i = 10001; i >= 0; i--) {//求最小的乘积 降序遍历
        if(a[i] >= 1) {//若种类出现次数>=1 种类数+1
            cnt++;
        }
        if(a[i] >= max) { //若此种类处出现的次数大于之前出现的最大次数 该处为找到的结果
            max = a[i];
            maxId = i;
        }
    }
    cout << cnt << " " << maxId;//输出结果

}
```

```
map做：
#include<bits/stdc++.h>
using namespace std;

int main() {
    map<int,int> mp;//创建map映射 对应位置存放乘积出现的次数
    string s;//输入的数
    int n;//输入个数
    cin >> n;

    for(int i = 0; i < n; i++) {
        cin >> s;//输入数
        int sum = 1;
        for(int i = 0; i < s.size(); i++) {//提取每位数 相乘 到sum上
            sum *= s[i] - '0';
        }
        mp[sum]++;//对应位置的数目+1
    }

    int cnt = 0;//种类数
    int maxId = 0;//最大的类出现的id
    int max = 0;//最大的类出现的次数
    for (auto it = mp.end(); it != mp.begin(); it--) {
        cnt++;
        if(it->second >= max) {
            max = it->second;
            maxId = it->first;
        }
    }
    cout << cnt << " " << maxId;//输出结果
}
```

## 7-3 自定义判题程序 (20 分)

```
在每次允许插入、删除、修改一个字符的前提下，用最少的动作把一个字符串变成另一个字符串，是一道著名的可以用动态规划解决的问题。但判题的麻烦之处在于，虽然最小代价是唯一的，但变换方法却是不唯一的。例如把 PAT 变成 PTA 最少需要 2 步，可以保持第 1 个字母不变，修改后面 2 个字母，也可以保持第 1、2 个字母不变，在 A 前面插入 T，后面删除 T。由于拼题 A 系统的默认判题程序只能通过比对输出文件来判断对错，对这种正确答案输出不唯一的题目就不能处理了，需要出题者额外编写一个自定义判题程序来解决问题。

本题就请你编写这个自定义判题程序，读入两个字符串和用户程序产生的输出结果，判断他们的程序输出是否正确。

输入格式：
输入首先在前两行分别给出两个不超过 1000 个字符、以回车结束的非空字符串，第 1 行对应初始字符串，第 2 行对应目标字符串。

随后一行给出一个正整数 N（≤ 100），为需要判断的提交数。

接下来是 N 个提交的输出结果，每个结果占 2 行：第 1 行给出一个整数 K（不超出 32 位 int 的范围），为用户输出的动作数；第 2 行顺次描述对初始字符串的每个字符所做的操作：

如果这个字符不变，则在对应位置输出 0
如果这个字符被删除，则在对应位置输出 1
如果这个字符被改变，则在对应位置输出 2
如果这个字符前面或者后面插入了一个字符，则在插入的位置输出 3
注意我们要求用户提交的行首尾和数字间均无空格，所以如果有多余空格应判为错误。

题目保证这个操作序列不为空。

输出格式：
对每个正确的提交，在一行中输出 AC；否则输出 WA。

注意：这里并不要求你会用动态规划求出最优解。所以对“正确提交”的判断，并不以动态规划求出的最优解为根据！ 对于用户输出的 K，如果其操作序列的确给出了 K 步操作并可以完成字符串的变换，则称为一个“可行解”。所谓“正确提交”，是指所有提交的可行解中的最优解。

输入样例：
This is a test.
Tom is a cat.
6
8
02330001100022100
8
11113330000001113300
6
022100000012200
5
033310000000200
6
0 2 2 1 000000 1 2 2 00
6
012200000022100

输出样例：
WA
WA
AC
WA
WA
AC
```

```
#include<bits/stdc++.h>
using namespace std;

int main() {
    string s1,s2;// 输入处理前后的字符串
    getline(cin,s1);
    getline(cin,s2);
    int n;//待处理的操作
    cin >> n;
    for(int i = 0; i < n; i++) {
        int m;//操作字符的次数
        string s3;//进行操作的字符串
        cin >> m;
        getchar();//读换行
        getline(cin,s3);
        int cnt = 0;//操作次数计数器
        int flag = 0;//若flag改变 说明进行了错误的操作 输出WA
        for(int j = 0,k = 0,l = 0; j < s3.size(); j++,k++,l++) {//k和l分别为s1和s2对比的位置
            if(flag) {//若flag为1 说明进行了错误的操作 输出WA
                cout << "WA\n";
                break;
            }
            switch(s3[j]) {
                case '0':
                    if(s1[k] != s2[l]) flag = 1;//0-无操作 若发生改变 说明出错
                    break;
                case '1':
                    cnt++;
                    if(s1[k] == s2[l]) flag = 1;//1-删除操作 若删除后仍相等 说明出错
                    l--;//s1进行了删除 s2对比的位置应-1
                    break;
                case '2':
                    cnt++;
                    if(s1[k] == s2[l]) flag = 1;//2-更换操作 与0类似 若更换后仍相等 说明出错
                    break;
                case '3':
                    cnt++;
                    if(s1[k] == s2[l]) flag = 1;//3-插入操作 与1类似 若插入后仍相等 说明出错
                    k--;//插入后s1的长度+1 应+1再做运算
                    break;
                default://若输入的操作非0123 说明出错
                    flag = 1;
                    break;
            }
        }
        if(!flag && cnt == m) cout << "AC\n";//若没出现上述错误 且 操作的次数和输入m一致 则对
    }
}
```

## 7-4 数组与链表 (20 分)

```
让我们来设计这样一种数组与链表结合的整数存储的结构 A：
这种结构首先初始化一个长度为 L0
的整型数组 A0，返回给用户使用。当用户访问第 i 个元素 A[i] 的时候，如果 0 ≤ i < L0，则 A[i] 对应 A0[i]，
系统就返回 h0​ + i × sizeof(int) 作为要访问的地址，其中 h0是数组 A0的起始位置，sizeof(int) 是数组元素的大小，这里元素就是 int 型，占 4 个字节。
当用户访问越界时（即 i ≥ L0），系统将另外开辟一个长度为 L1的数组 A1。此时 A[i] 对应 A1[j]（这里 i 和 j 之间的映射关系留给你去推导）。如果 0≤j<L1，
则返回 h1+j × sizeof(int) 作为要访问的地址，其中 h1是数组 A1的起始位置。当 A1[j] 继续越界时，系统就按照上述规则继续开辟另一个长度为 L2​ 的数组 A2，并以此类推。

本题就请你实现这个系统功能，为用户的任何一次访问返回对应元素的地址。

输入格式：
输入第一行给出两个正整数 N（≤ 1 0 4 10 ^ 410 
4
 ）和 K（≤ $10 ^ 3%），分别为最多允许开出的数组个数、以及用户访问的次数。

此后 N 行，每行给出两个正整数，分别是一个数组的初始地址（≤1 0 7 10 ^ 710 
7
 ）和长度（≤ 100），其间以空格分隔。题目保证这些数组占据的空间无重叠。

最后一行顺序给出 K 个用户访问的数组下标，为区间 [0, 2 ^ 20] 内的整数。

输出格式：
对每个用户访问，在一行中输出对应的地址。但如果用户的访问超出了 N 个数组的存储范围，则这个访问是非法的，要输出 Illegal Access，并且对这个访问不采取任何处理。

最后一行请输出上述过程中一共创建了多少个数组。

输入样例：
6 7
2048 5
128 6
4016 10
1024 7
3072 12
9332 10
2 12 25 50 28 8 39

输出样例：
2056
4020
1040
Illegal Access
3072
140
3116
5
```

```
#include<bits/stdc++.h>
using namespace std;

struct node {// 结构体 存放初始地址和长度 
    int id,num;
};

int main() {
    int n,m;//允许数组总个数 用户访问的次数 
    cin >> n >> m;
    int a;//临时 存放开出的字节数 
    vector<node> v(n);//存放结构体 
    vector<int> v1;//存放开出的数组种类数 
    for(int i = 0; i < n; i++) {
        node node;//新建结构体 
        cin >> node.id >> node.num;//输入 
        v[i] = node;//赋值 
    }
    for(int i = 0; i < m; i++) {
        cin >> a;//用户输入操作 
        int j = 0;
        while(v[j].num <= a){//当用户操作的值大于等于该数组的总量 a减去该数组的num 切换到下一数组 
            a = a - v[j].num;
            j++;
        }
        if(j > n){//若操作溢出 输出非法 continue继续下次循环 
            cout << "Illegal Access" << endl;
            continue;
        }
        v1.push_back(j);
        cout << a * 4 + v[j].id << endl;    //输出4*字节数+地址值 
    }
    
    int sum = 0;//v1数组中非0的种类数 
    for(auto it = v1.begin();it != v1.end();it++){
        if(*it != 0) sum++;
    }
    cout << sum;
}
```

## 7-5 取帽子 (25 分)

```c++
拼题er们觉得戴帽子会令自己看上去很帅，所以他们不管到哪里都会戴着帽子。有一天他们去到一家餐厅，服务员把他们的帽子收集了堆起来保管。当大家要离开的时候，发现帽子被像上图那样摞起来了。于是你的任务就是帮他们排好队，使得每个人都能按顺序顺利取到自己的帽子。
已知每顶帽子的大小都不相同，并且帽子的尺寸跟帽子主人的体重有关 —— 越重的人戴的帽子就越大。

输入格式：
输入第一行给出一个正整数 N (≤1 0 4 10 ^ 410 
4
 )，为拼题er的人数。随后一行给出 N 个不同的帽子尺寸，为不超过 1 0 5 10 ^ 510 
5
  的正整数，顺序是从帽子堆的底部向上给出。
最后一行给出 N 个不同的体重，顺序对应编号从 1 到 N 的拼题er。
体重是不超过 1 0 6 10 ^ 610 
6
 的正整数。一行中的数字以空格分隔。

输出格式：
在一行中按照取帽子的顺序输出帽子主人的编号。数字间以 1 个空格分隔，行首尾不得有多余空格。

输入样例：
10
12 19 13 11 15 18 17 14 16 20
67 90 180 98 87 105 76 88 150 124

输出样例：
3 4 8 6 10 2 1 5 9 7
样例说明：
第一顶帽子的尺寸是最大的 20，所以对应第 3 个人的最大体重 180，于是第 3 个人排在最前面。
第二顶帽子的尺寸是第 6 小的 16，对应第 6 小的体重 98，是第 4 个人，于是第 4 个人下一个走。
以此类推。
```

```
#include<bits/stdc++.h>
using namespace std;

int main() {
    int n;// 待处理帽子和人数 
    cin >> n;
    vector<int> hat(n),sortHat(n);//帽子原始数组和排序数组 
    vector<int> height(n),sortHeight(n);//体重原始数组和排序数组 

    for(int i = 0; i < n; i++) cin >> hat[i];//输入帽子 
    for(int i = 0; i < n; i++) cin >> height[i];//输入体重 

    sortHat = hat;
    sortHeight = height;
    sort(sortHat.begin(),sortHat.end());//对帽子大小排序（升序 
    sort(sortHeight.begin(),sortHeight.end());//对体重大小排序（升序 

    for(int i = n - 1; i >= 0; i--) {//帽子倒放 从后往前读 
        for(int j = 0; j < n; j++) {
            if(hat[i] == sortHat[j]) {//先定位i点处帽子的大小，找到排序对应j的帽子位置 
                for(int k = 0; k < n; k++) {
                    if(height[k] == sortHeight[j]) {//排序j对应的帽子即对应j点人 再找到他原本的次序k+1 
                        cout << k + 1 << " ";//
                        break;
                    }
                }
            }
        }
    }
}
```

##