居然出了一道动态规划题……模拟题也越来越恶心（变得越加又臭又长）

本周作业让我感觉比较有收获的题（从高到低）：

21.新型冠状病毒（COVID19）传播

1.字符串反转2

题目

【问题描述】

     给定一个句子（只包含字母和空格）， 将句子中的单词位置反转，单词用空格分割, 单词之间只有一个空格，前后没有空格。 比如： “hello xiao mi”-> “mi xiao hello”

【输入形式】

 输入数据有多组，每组占一行，包含一个句子(句子长度小于1000个字符)

【输出形式】

   对于每个测试示例，要求输出句子中单词反转后形成的句子

【样例输入】

hello xiao mi
I am a student

【样例输出】

mi xiao hello
student a am I
题解

跟上周那道题很像吗，不过不是对每个单词反转，而是把整句反转，单词不反转

用栈解决即可

代码
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <cstring>
#include <sstream>
using namespace std;
int main(){
    string s;
    while(getline(cin, s)){
        stringstream ss;
        stack<string> a;
        ss<<s;
        while(ss>>s){
            a.push(s);
        }
        while(!a.empty()){
            cout<<a.top()<<" ";
            a.pop();
        }
        cout<<endl;
    }
    return 0;
}

2.487-3279

题目

【问题描述】

   每个人都喜欢有令人难忘的电话号码。要想让电话号码变得令人难忘的一种方法是拼出一个令人难忘的单词或短语。例如，你可以拨打滑铁卢大学的电话，拨打令人难忘的电话号码TUT-GLOP。   有时只有一部分号码被用来拼写一个单词，例如，你可以拨打310-gino从Gino's订购披萨。   要使电话号码令人难忘的另一种方法是以一种令人难忘的方式对数字进行分组。你可以从比萨饼小屋中订购比萨饼，方法是拨打他们的“3个10”，即号码3-10-10-10。   电话号码的标准格式是七位的十进制数字，第三和第四位之间包含连字符（例如888-1200）。电话的键盘提供字母到数字的映射，如下所示：   A, B, C映射到2   D, E, F映射到3   G, H, I映射到4   J, K, L映射到5   M, N, O映射到6   P, R, S映射到7   T, U, V映射到8   W, X, Y映射到9   Q和Z没有映射。连接符不拨号，必要时可加上或去除。TUT-GLOP的标准格式是888-4567，310-GINO的标准格式是310-4466，3-10-10-10的标准格式是310-1010。   当两个电话号码有相同的标准格式时是等价的（拨同样的号码）。   你的公司正在编制本地企业的电话号码目录，作为质量控制的一部分，你需要检查没有两个（或多个）企业具有相同的电话号码。

【输入形式】

输入包括一个案例。输入的第一行为一个正整数，指定目录中电话号码的数目(最多100，000)。其余的各行列出目录中的电话号码，每个号码单独占一行。每个电话号码都是一个由十进制数字、大写字母(不包括Q和z)和连字符组成的字符串。字符串中的七个字符或是数字或是字母。

【输出形式】

对于出现超过一次的每个号码，按照标准格式及字典序每个输出一行，然后是空格，接着输出出现的次数。只出现1次的电话号码不输出。

【样例输入】

12
4873279
ITS-EASY
888-4567
3-10-10-10
888-GLOP
TUT-GLOP
967-11-11
310-GINO
F101010
888-1200
-4-8-7-3-2-7-9-
487-3279

【样例输出】

310-1010 2
487-3279 4
888-4567 3

【输入形式】

输入有多组测试数据。

输入第一行正整数T，表示有多少组测试数据。

后面有T行，每行一个非负整数，表示里程表显示数字，里面不含有数字3和8。该数字不超过10位。

40%的测试数据组数T 10 ≤ T ≤ 10^2；

30%的测试数据组数T 102 ≤ T ≤ 10^3；

20%的测试数据组数T 103 ≤ T ≤ 10^4；

10%的测试数据组数T 104 ≤ T ≤ 10^5；

【输出形式】

对于每组测试数据，输出一个整数占一行：真实的行程里程。

【样例输入】

6
0
1
12
159
111224459
124567976
【样例输出】

0
1
10
103
19212007
21913077

题解

看起来其实就是每个字符串做标准化处理后统计，一顿map了事

代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
using namespace std;
int main(){
    map<char, int> d;
    map<string, int> tel;
    d['0'] = '0';
    d['1'] = '1';
    d['2'] = d['A'] = d['B'] = d['C'] = '2';
    d['3'] = d['D'] = d['E'] = d['F'] = '3';
    d['4'] = d['G'] = d['H'] = d['I'] = '4';
    d['5'] = d['J'] = d['K'] = d['L'] = '5';
    d['6'] = d['M'] = d['N'] = d['O'] = '6';
    d['7'] = d['P'] = d['R'] = d['S'] = '7';
    d['8'] = d['T'] = d['U'] = d['V'] = '8';
    d['9'] = d['W'] = d['X'] = d['Y'] = '9';
    int n;
    scanf("%d", &n);
    while(n--){
        int num=0;
        string s,ss="";
        cin>>s;
        int l = s.length();
        for(int i=0; i<l; i++){
            if(s[i]=='-')continue;
            ss+=d[s[i]];
            num++;
            if(num==3)ss+='-';
            else if(num==7)break;
        }
        if(tel.find(ss) == tel.end())tel[ss]=1;
        else tel[ss]++;
    }
    for(map<string,int>::iterator it=tel.begin();it!=tel.end();it++){
		if(it->second>1){
			cout<<it->first<<" "<<it->second<<endl;
		}
	}
    return 0;
}

3.缺席考试的是谁？

题目

【问题描述】

程序设计考试结束了，传来个不好的消息：有一个学生没参加考试!需要尽快知道缺席考试的人是谁，以便尽快做出处理。

糟糕的是，尽管有签到表，但由于人数较多，签到情况比较混乱：有的签到表签在一张白纸上，有的虽然签在名册上，但并不是签在自己姓名旁，更有学生签到了别的签到表上……

现在只能根据这2n-1个姓名（名册上有n个学生姓名，签到有n-1个姓名，签到姓名和名册姓名可能混在一起了），来找到缺席考试的人是谁。唯一一个有利的条件是所有参加考试的人都签了名，且只签一次，签名也都正确无误。

现在任务交给你：编写一个程序，找出缺席考试的是谁。

【输入形式】

有多组测试数据。

每组测试数据开始一行，是一个正整数n，表示总人数，n=0意味着输入结束并且不需要处理。

以下2n-1行，每行一个字符串，长度不超过20，表示一个人的姓名。姓名有大小写的英文字母、常用汉字组成(注意每个汉字占2个字节，中英文姓名都不排除有重名情况)。

40%的测试数据1 ≤ n≤ 10；

30%的测试数据1 ≤ n≤ 100；

20%的测试数据1 ≤ n≤ 10^3；

10%的测试数据1 ≤ n≤ 10^4；

提示：大量输入数据，C/C++输入推荐使用scanf函数

【输出形式】

对于每组测试数据，输出一行，只包含一个字符串，表示缺席的人的姓名。

【样例输入】

2
张三
张三
李四
0

【样例输出】

李四
题解

这题实际上就是找只出现过一遍的名字，其它名字都是出现过两次的。

这里给两个方法：（我用的是第一种）

第一种是map存储，某个名字被录第一遍时存储，录第二遍的时候就删除（不是次数+1，不然后面找出来会超时），然后迭代器查map（map此时只存了答案）

第二种是对所有名字排序，然后查i和i+1是不是相同的（i为偶数，从0-(2n-4)），一直查到不是相同的。如果没查到就是i=2n-2的名字。

PS：用cin记得读入优化！

代码
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <map>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
	cout.tie(NULL);
    int n;
    while(cin>>n && n){
        n = 2*n-1;
        map<string, int> a;
        while(n--){
            string name;
            cin>>name;
            if(a.find(name) == a.end())a[name]=1;
            else a.erase(name);
        }
        for(map<string, int>::iterator it=a.begin(); it!=a.end(); it++)
            cout<<it->first<<endl;
    }
    return 0;
}

4.电话号码

题目

【问题描述】

Vasya有几本电话簿，记录了他的朋友们的电话号码，每一个朋友都可以有一或几个电话号码。

Vasya决定整理关于朋友电话号码的信息。给定n个字符串，来自于Vasya的电话簿中的条目。每一条都以朋友的姓名开头，然后跟着当前条目中的电话号码个数，然后是本人的电话号码。有可能几个相同的电话被记录在同一个记录中。

Vasya还认为，如果电话号码a是电话号码b的后缀（也就是说，号码b以a结尾），这两个号码被当作同一个电话号码，那么a被认为是无城市代码，它不应该被考虑。

输出整理后Vasya朋友的电话号码信息。有可能两个不同的人有相同的号码。如果一个人有两个电话号码x和y，x是y的后缀（即y以x结尾），则不输出x。

如果Vasya的电话簿中的某些朋友记录了几次，那么只需要记录一次。

【输入形式】

输入第一行一个整数n(1<=n<=20)，Vasya的电话簿上的条目数。

以下n行后面是描述中的格式记录。 朋友的姓名中不包含空字符，长度不超过10位，由小写英文字母组成。电话号码个数在110之间。每个电话号码的长度范围在110之间，可以包含前导0。

【输出形式】

输出Vasya的朋友的电话号码的有序信息。首先输出电话簿中的朋友数目m。

接下来的m行，包含以格式“姓名 电话号码个数 电话号码1 … 电话号码k”的条目，号码间以空格分隔。每个记录包含当前朋友的所有电话号码。

每个条目输出按照姓名字母序进行排序，电话号码按照从小到大的顺序排列（注意电话号码比较规则：”1”<”01”、”12”<”012”，依此类推）

【样例输入】

4
ivan 3 123 123 456
ivan 2 456 456
ivan 8 789 3 23 6 56 9 89 2
dasha 2 23 789

【样例输出】

2
dasha 2 23 789 
ivan 4 2 123 456 789
题解

这题属实复杂，直接看我代码注释边理解吧。

代码
#include <iostream>
#include <cstdio>
#include <set>
#include <map>
#include <algorithm>
#include <cstring>
using namespace std;
struct P{
    string name;
    int index=0;//记录tel使用长度
    string tel[200];//记录电话
}p[20];

bool cmp(P a, P b){//用于名字排序
    return a.name<b.name;
}

bool cmptel(string a,string b){//用于电话号码排序
    if(a.length()!=b.length())return a.length()<b.length();
    return a<b;
}

bool pd(string s1,string s2){//判断s1是不是s2后缀
    reverse(s1.begin(),s1.end());
    reverse(s2.begin(),s2.end());
    int l=s1.length(),i;
    for(i=0;i<l;i++)
        if(s1[i]!=s2[i])break;
    if(i==l)return true;
    return false;
}

int main(){
    int t;
    scanf("%d",&t);
    int num = 0;//记录总人数
    map<string, int> index;
    while(t--){
        string s;
        int n;
        cin>>s>>n;
		//录入名字
        if(index.find(s) == index.end()){
            p[num].name = s;
            index[s] = num++;
        }
        int id = index[s];
		//录入电话
        while(n--){
            cin>>s;
            p[id].tel[p[id].index++] = s;
        }
    }
    for(int i=0;i<num;i++){
        sort(p[i].tel, p[i].tel+p[i].index, cmptel);//对第i个人的所有电话进行排序，前面短后面长
		//电话长的不会是短的后缀
        for(int q=0;q<p[i].index-1;q++)
            for(int e=q+1;e<p[i].index;e++)
                if(pd(p[i].tel[q], p[i].tel[e])){//如果是后缀就吧这个电话清了
                    p[i].tel[q]="";
                    break;
                }
    }
    sort(p, p+num, cmp);//对名字排序
    cout<<num<<endl;
    for(int i=0;i<num;i++){
        int qaq=0;
		//记录非空电话数
        for(int j=0;j<p[i].index;j++){
            if(p[i].tel[j]=="")continue;
            qaq++;
        }
		//输出非空电话（前面处理时排序过了）
        cout<<p[i].name<<" "<<qaq<<" ";
        for(int j=0;j<p[i].index;j++){
            if(p[i].tel[j]=="")continue;
            cout<<p[i].tel[j]<<" ";
        }
        cout<<endl;
    }
    return 0;
}

5.点球大战

题目

【问题描述】在足球比赛中，有不少赛事，例如世界杯淘汰赛和欧洲冠军联赛淘汰赛中，当比赛双方经过正规比赛和加时赛之后仍然不分胜负时，需要进行点球大战来决定谁能够获得最终的胜利。点球大战的规则非常简单，两方轮流派出球员罚点球，每方各罚5个。当5轮点球结束以后如果仍然不分胜负，则进入一轮定胜负的阶段。两方各派一名球员罚点球，直到有一方罚进而另一方没有进为止。
在北美职业冰球联赛中，也有点球大战。与足球的规则不同的是，它只先罚3轮点球，随后就进入一轮定胜负的阶段，而其他的规则完全一样。
在本题中，输入将给出每次点球是否罚进，而你的任务则是输出一个“比分板”。

【输入形式】输入包含多组数据。每组数据的第一行包含一个整数N(1<=N<=18)，表示双方总共罚了多少个点球，N=0表示输入结束。随后有N行，每行是一个如下形式的字符串：
XXXX good：表示这个点球罚进
或者XXXX no good：表示这个点球没有罚进
其中XXXX表示球员名字（全部由字母和空格组成，保证不会出现歧义）
每一行保证不超过100个字符。
XXXX和good以及XXXX和no、no和good之间保证有且只有1个空格。
good、no good都是小写。本题是大小写相关的。
数据不保证点球大战一定结束，也不保证在结束以后立即结束这组数据（即：不用判断点球大战是否结束，只用把罚进的点球往比分上加即可）。

【输出形式】对每组数据，输出一个比分板。一个点球如果罚进，则在对应的地方标上’O’，如果没有进则标上’X’。先罚球的队伍的信息在上面，后罚的在下面。最右边标上两队的比分。具体格式参考样例输出。注意如果一轮点球只罚了一个，则后面那个点球对应的地方写上’-’。

【样例输入】

6
Riise good
Ballack good
Gerrard no good
Lampard no good
Fernando Torres good
Malouda good
9
Christiano Ronaldo no good
Messi no good
Giggs good
Abidal no good
Carrick good
Ronaldinho good
Rooney good
Henry no good
Tevez good
0

【样例输出】

1 2 3 Score
O X O 2
O X O 2
1 2 3 4 5 Score
X O O O O 4
X X O X - 1
题解

这题其实在于每行的空格数不定，所以取出倒数第二个判断是不是no比较麻烦

没关系，问题不大，我们整行读入，然后切割完丢进栈里，然后取第二个嘿嘿嘿

剩下的统计就是小事啦！

代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <stack>
#include <sstream>
using namespace std;
int main(){
    int n;
    while(cin>>n && n){
        cin.ignore();
        char a[2][10];
        for(int i=0;i<2;i++)
            for(int j=0;j<10;j++)
                a[i][j] = '-';
        int score[2]={0};
        for(int i=0;i<n;i++){
            string s;
            getline(cin, s);
            stringstream ss;
            ss<<s;
            stack<string> sta;
            while(ss>>s){
                sta.push(s);
            }
            sta.pop();
            int q=i%2,e=i/2;
            if(sta.top() == "no")a[q][e] = 'X';
            else a[q][e] = 'O',score[q]++;
        }
        for(int i=1;i<=(n+1)/2;i++){
            printf("%d ", i);
        }
        printf("Score\n");
        for(int i=0;i<2;i++){
            for(int j=0;j<(n+1)/2;j++)
                printf("%c ", a[i][j]);
            printf("%d\n", score[i]);
        }
    }
}

6.飞行棋

题目

【问题描述】

   大家当年一定都下过飞行棋吧。现在Lele和Yueyue要下的棋和这个很相似，只是更简单一点而已。   棋盘由N个格子组成，分别标记为第0格到第N-1格。格子分为两种，一种是普通格子，即表示在该格可以停留。否则是特殊的格子，一旦走到上面，就要根据上面标记的数飞到相应的格子上。如果飞到一个特殊的格子上，则可以继续飞。   除了第0格外，其他格子都只能容纳一个玩家。即一旦A玩家已经在某个格子上，B玩家又走到这里，A玩家则会被踢回第0格，而B玩家留在这个格子上面。   第N-1个格子是终点，一旦一个玩家走到这个格子上，该玩家获胜，游戏结束。   刚刚开始时，两个玩家都站在第0格上，依次扔骰子，根据骰子显示的点数走相应的格子数。比如，玩家在第0格，扔出了5点，则会走到第5个格子上。如果玩家走得超出了棋盘的范围，则要往回走一定的步数。比如，棋盘一共有7(0~6)个格子,玩家在第4格上，扔出了6点，最终他会走到第2格上(4->5->6->5->4->3->2)。   根据观察，骰子扔出来的数也是有规律的。   对于每一盘棋，扔出的第一个点数为 F0=(A*C+B)%6+1,第二个点数为 F1=(A*F0+B)%6+1,第三个点数为 F2=(A*F1+B)%6+1 ....依此类推。   每一盘棋都是由Lele先走，现在就请你当裁判，看谁能获胜。

【输入形式】

  本题目包含多组测试，请处理到文件结束。  每组数据占两行。  第一行有4个整数N,A,B,C(含义见题目描述，6<N<200,0<=A,B,C<=2^31)。  第二行有N个字符串，分别表示棋盘上第0个到第N-1个格子的内容。两个字符串之间用一个空格分隔开。  如果字符串为"N",则表示这个格子为普通格子。否则字符串为"GX"(X为0到N-1之间的整数)的形式，其中X表示玩家走到这个格子时，要马上飞到第X个格子。  数据保证第0个和第N-1个格子一定为"N"。

【输出形式】

  对于每组数据，在一行内输出结果。  如果Lele能赢这盘棋，则输出"Lele",如果Yueyue赢的话，就输出"Yueyue"。

【样例输入】

7 1 0 6
N G3 N N N N N
7 1 0 6
N G4 N N N N N

【样例输出】

Lele
Yueyue
题解

纯模拟，每步换人走，可以写个递推

然后每步走完判断有没有到达终点、超出边界、跳格、打到另一个人

代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int pos[2];
int n,a,b,c;
int map[200];
string name[2] = {"Lele","Yueyue"};

void go(int who, int step){
    pos[who]+=step;
    int other = (who+1)%2;
    if(pos[who]==n-1){cout<<name[who]<<endl;return;}
    if(pos[who]>=n)pos[who] = n-1 - (pos[who]-(n-1));
    if(map[pos[who]]>0)pos[who] = map[pos[who]];
    if(pos[who] == pos[other] && !pos[who])pos[other] = 0;
    go(other, (a*step+b)%6+1);
}

int main(){
    while(scanf("%d %d %d %d", &n,&a,&b,&c)!=EOF){
        memset(map, 0, sizeof(map));
        memset(pos, 0, sizeof(pos));
        for(int i=0;i<n;i++){
            string s;
            cin>>s;
            if(s[0]=='G')map[i]=s[1]-'0';
        }
        go(0, (a*c+b)%6+1);
    }
    return 0;
}

7.棋盘

题目

【问题描述】

    棋盘是指一个行和列编号从1~N的NxN的二进制矩阵，当行号和列号之和为偶数时该矩阵对应位置为黑色的(1)，否则为白色的(0)。以下图示为N=1、2、3时的棋盘。    ![](https://noionion-picture-bed.oss-cn-hangzhou.aliyuncs.com/img/2-7qaq.jpg)    給出一个NxN的二进制矩阵，请找出位于该矩阵内的最大尺寸的完整棋盘，以及最大尺寸棋盘的数量（棋盘可以交叠）。

【输入形式】

   每个测试用例的第一行是一个正整数N(1<=N<=2000)，表示給定矩阵的行数和列数，接下来的N行描述了这个矩阵：每行有N个字符，既可以是“1”（代表黑块），也可以是“0”（代表白块）。矩阵至少包含一个“1”字符。

【输出形式】

   输出最大尺寸棋盘的行列的大小，以及最大棋盘的个数，以空格分隔。

【样例输入】

5
00101
11010
00101
01010
11101

【样例输出】

3 3
题解

刚开始没注意到第一格要黑色，栽了。然后没想到直接暴力搜就行。。。

这里建议从大棋盘到小棋盘开始搜，搜到就能直接break了（搜索怎么搜？看注释！！！）

代码
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
int map[2000][2000],num[2000];
int main(){
    int n;
    scanf("%d", &n);
    for(int i=0;i<n;i++){
        string s;
        cin>>s;
        for(int j=0;j<n;j++)
            map[i][j] = s[j]-'0';
    }
    for(int size=n;size>0;size--){//搜索的棋盘边长
        int num=0;//记录该边长的符合棋盘数
        for(int i=0;i+size-1<n;i++)
            for(int j=0;j+size-1<n;j++)
			//枚举每个size*size方形左上角坐标
                if(map[i][j]==1){//判断第一个顶点是不是黑的
                    int q,e;
                    bool flag=true;
					//下面两层循环判断该方形是不是合法棋盘
                    for(q=i;q<i+size-1;q++){
                        for(e=j;e<j+size-1;e++)
                            if(map[q][e]+map[q+1][e]!=1 || map[q][e]+map[q][e+1]!=1 || map[q][e] != map[q+1][e+1]){
								//判断每个点的下方右方和右下方是不是0110或者1001结构
                                flag = false;break;
                            }
                        if(!flag)break;
                    }
                    if(flag)num++;
                }
        if(num>0)return printf("%d %d",size,num),0;
    }
}

8.Engine-字符串

题目

【问题描述】

   谷歌、百度等搜索引擎已经成为了互连网中不可或缺的一部分。在本题中，你的任务也是设计一个搜索论文的搜索引擎，当然，本题的要求比起实际的需求要少了许多。   本题的输入将首先给出一系列的论文，对于每篇论文首先给出标题，然后给出它被引用的次数。然后会有一系列的搜索询问，询问标题中包含特定关键词的论文有哪些。   每一个询问可能包含多个关键词，你需要找出标题包含所有关键词的论文。“包含”必须是标题中有一个词正好是给定的关键词，不区分大小写。  对每个询问，都按被引用的次数从多到少输出满足条件的论文的标题。如果有被引用的次数相同的论文，则按照论文在输入中的顺序排列，先给出的论文排在前面。

【输入形式】输入包含多组数据。
每组数据首先有一行包含一个整数N(1<=N<=1000)，表示论文的数目，N=0表示输入结束。每组论文的信息第一行是论文的标题，由字母（大小写均可）和空格组成，不超过10个词，每个词不超过20个字符，标题总共不超过250个字符。第二行是一个整数K(0<=K<=108)，表示它被引用的次数。在论文信息结束以后，有一行包含一个整数M(1<=M<=100)，表示询问的数目。接下来有M行，每行是一个询问，由L(1<=L<=10)个空格分开的词构成，每个词不超过20个字符。

【输出形式】

  对每个询问，按照题目给定的顺序输出满足条件的论文的标题；如果没有满足条件的论文，就不输出。在每组询问的输出之后输出一行“***”，在每组数据的输出之后输出一行“---”。

【样例输入1】

6
Finding the Shortest Path
120
Finding the k Shortest Path
80
Find Augmenting Path in General Graph
80
Matching in Bipartite Graph
200
Finding kth Shortest Path
50
Graph Theory and its Applications
40
6
shortest path
k shortest path
graph
path
find
application
0

【样例输出1】

Finding the Shortest Path
Finding the k Shortest Path
Finding kth Shortest Path
***
Finding the k Shortest Path
***
Matching in Bipartite Graph
Find Augmenting Path in General Graph
Graph Theory and its Applications
***
Finding the Shortest Path
Finding the k Shortest Path
Find Augmenting Path in General Graph
Finding kth Shortest Path
***
Find Augmenting Path in General Graph
***

***
---

【样例输入2】

1
Finding the Shortest Path
120
2
Path
Pat
0

【样例输出2】

Finding the Shortest Path
***
***
---

【样例说明】

需要查询的内容为“k shortest path”，他包含了3个独立的关键词。

题解

这题也老麻烦了。。。

第一个是查询时大小写不影响，也就是说读入时就要做标准化处理

第二个是得刚刚好长度的单词，比如find匹配不了finding，所以就不能直接字符串find啦

直接看代码注释吧。。。

代码
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <map>
#include <sstream>
using namespace std;
struct node{
    string truename;//存原先大小写分明的名字
    int time;//引用次数
    map<string,bool> dir;//标准化后的关键词
};

bool cmp(node a,node b){
    return a.time>b.time;
}

int main(){
    int n,m;
    while(cin>>n && n){
        node art[n];
        for(int i=0;i<n;i++){
            string s;
            int t;
            cin.ignore();
            getline(cin, s);
            scanf("%d", &t);
            art[i].truename = s;
            art[i].time = t;
            int l = s.length();
			//对原文章名标准化处理
            string temp="";
            for(int i=0;i<l;i++){
                if(s[i]>='A' && s[i]<='Z')
                    temp+=s[i]-'A'+'a';
                else temp+=s[i];
            }
			//切割关键词
            stringstream ss;
            ss<<temp;
            while(ss>>temp)
                art[i].dir[temp]=true;
        }
        scanf("%d",&m);
        cin.ignore();
        while(m--){
            string s;
            getline(cin,s);
			//标准化查询的关键词
            string temp="";
            int l = s.length();
            for(int i=0;i<l;i++){
                if(s[i]>='A' && s[i]<='Z')
                    temp+=s[i]-'A'+'a';
                else temp+=s[i];
            }
            s = temp;
            int index = 0;
            node forsort[n];//用于存匹配出来的文章
            for(int i=0;i<n;i++){
				//切割查询关键词
                stringstream ss;
                ss<<s;
                string temp;
                bool flag=true;
                while(ss>>temp){
                    if(art[i].dir.find(temp) == art[i].dir.end()){
						//匹配
                        flag = false;
                        break;
                    }
                    if(!flag)break;
                }
				//匹配到就存进去
                if(flag){
                    forsort[index].truename = art[i].truename;
                    forsort[index++].time = art[i].time;
                }
            }
            sort(forsort, forsort+index, cmp);//对匹配完的文章按次数排序
            for(int i=0;i<index;i++)
                cout<<forsort[i].truename<<endl;
            cout<<"***"<<endl;
        }
        cout<<"---"<<endl;
    }
    return 0;
}

9.字符串压缩

题目

【问题描述】

   给定一个由n个小写字母组成的字符串s，需要使用最少数量的钱币来压缩它。   压缩该字符串，必须将s表示为多个相互连接的非空字符串: s=t1t2...tk，其中第 i 个字符串按照下列两种方法之一编码：

如果|ti|=1，也就是说 ti为单个字符组成的字符串，编码时需要支付a个钱币

如果ti是t1t2…ti-1的子串，编码时需要支付b个钱币

  你的任务是计算压缩给定的字符串需要花费的最小钱币数。

【输入形式】

   输入的第一行包含3个用空格分隔的正整数：n、a和b(1≤n、a、b≤5000)，第二行为一个长度为n的小写字符串。

【输出形式】

   输出一个整数，表示你需要为压缩s所需要支付的最小钱币数。

【样例输入1】

3 3 1
aba

【样例输出1】

7

【样例输入2】

4 1 1
abcd

【样例输出2】

4

【样例输入3】

4 10 1
aaaa

【样例输出3】

12
题解

本来以为是贪心的，然后一想aaaa，emmm贪心不科学啊，按经验就是动态规划啦

知道是dp题后就简单了。老师放水说了一个一个加，那就很明显了

对于每个长度l，都有初始dp[l]=dp[l-1]+a

构建状态转移方程dp[l] = min(dp[l], dp[mid]+b)(以mid为切割点切割长度为l的子串，右半是左半的子串时转移。(l+1)/2<=mid<l)

代码
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int main(){
    int n,a,b;
    scanf("%d %d %d", &n,&a,&b);
    string s;
    cin>>s;
    int dp[5001];
    dp[0]=0;dp[1]=a;
    for(int i=2;i<=n;i++)
        dp[i]=999999999;
    for(int l=2;l<=n;l++){
        string ss = s.substr(0,l);//长度l的子串
        dp[l] = dp[l-1]+a;
        for(int mid=(l+1)/2;mid<l;mid++){//左半一定是长于右半的，所以mid从(l+1)/2开始
            string left=ss.substr(0,mid);//子串左半
            string right=ss.substr(mid,l);//子串右半
            if(left.find(right)!=left.npos)
                dp[l] = min(dp[l], dp[mid]+b);
        }
    }
    cout<<dp[n];
}

10.拼写检查

题目

【问题描述】

   作为一个新的拼写检查程序开发团队的成员，您将编写一个模块，用已知的所有形式正确的词典来检查给定单词的正确性。   如果字典中没有这个词，那么可以用下列操作中的一个来替换正确的单词（从字典中）：   1. 从单词中删除一个字母；   2. 用一个任意字母替换单词中的一个字母；   3. 在单词中插入一个任意字母。   你的任务是编写一个程序，为每个给定的单词找到字典中所有可能的替换。

【输入形式】

   输入的第一部分包含所有字典中的词，每个单词占用一行，以一个单一字符“#”作为结束。所有单词都不相同，字典中至多1000个单词。   接下来的部分包含所有需要进行检查的单词，同样每个单词占用一行。这部分也以一个单一字符“#”作为结束。至多有50个单词需要检查。   在输入中所有的单词（字典中的和需要检查的）都仅由小写字母组成，每个最多包含15个字符。

【输出形式】

   对于每个在输入中出现的单词，按照它们在输入的第二部分出现的顺序输出一行。如果该单词是正确的（也就是说它包含在字典中）则输出信息：“is correct”；如果该单词不正确，则首先输出该单词，然后输入符号':'（冒号），之后空一格，写出它所有可能的替代，以空格分隔。这些替代的单词按照它们在字典中（输入的第一部分）出现的顺序写出。如果没有可替代的单词，则在冒号后面直接输出换行。

【样例输入】

i
is
has
have
be
my
more
contest
me
too
if
award
#
me
aware
m
contest
hav
oo
or
i
fi
mre
#

【样例输出】

me is correct
aware: award
m: i my me
contest is correct
hav: has have
oo: too
or:
i is correct
fi: i
mre: more me
题解

这题也是又臭又长，看起来很麻烦但写起来也还好（我刚开始跳了这题

这题直接看代码注释吧

代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int main(){
    string s,d[1000];
    int num=0;
	//存字典
    while(cin>>s){
        if(s=="#")break;
        d[num++]=s;
    }
	//查询
    while(cin>>s){
        if(s=="#")break;
        int i;
        for(i=0;i<num;i++)
            if(s==d[i])break;
		//在字典里边
        if(i!=num){
            cout<<s+" is correct"<<endl;
            continue;
        }
		//不在字典里边（匹配）
        cout<<s+": ";
        int l1=s.length();
        for(i=0;i<num;i++){
            int l2=d[i].length();
            if(l1-l2>=-1 && l1-l2<=1){//显然有长度相差不大于1的而能够匹配到
				//然后我们分几种情况
				/*
				第一种是两个字符串短的那个加一个字符就能成为另一个，其中又分为3种，短的是长的前缀或后缀，或者中间加一个字符
				另一种是长度刚好但差一个字符不同

				我们匹配两个字符串的前缀相同长度q和后缀相同长度e，l为两者的长度的较小值
				*/
                int q,e,l=min(l1,l2);
				//如果一个是另一个前缀条件是q==l
                for(q=0;q<l;q++)
                    if(s[q]!=d[i][q])
                        break;
                if(q==l){
                    cout<<d[i]<<" ";
                    continue;
                }
				//如果一个是另一个后缀条件是e==l
                string temp1=s,temp2=d[i];
                reverse(temp1.begin(), temp1.end());
                reverse(temp2.begin(), temp2.end());
                for(e=0;e<l;e++)
                    if(temp1[e]!=temp2[e])
                        break;
                if(e==l){
                    cout<<d[i]<<" ";
                    break;
                }
				//如果两个长度不同，但是中间插入一个字符后两字符串相同条件是q+e==l
				//如果两个长度相同，那么中间改一个字符后两字符串相同条件是q+e==l-1
                if((q+e==l && l1!=l2) || (q+e==l-1 && l1==l2))
                    cout<<d[i]<<" ";
            }
        }
        cout<<endl;
    }
    return 0;
}

11.最小的K个数

题目

【问题描述】

输入n个整数，找出其中最小的k（k<=n）个不同数。例如输入4,5,1,6,1,7,3,8这8个数字，则最小的4个数字是1,3,4,5。

【输入形式】

每个测试案例包括2行：

第一行为2个整数n，k(1<=n，k<=200000)，表示数组的长度。

第二行包含n个整数，表示这n个数，数组中的数的范围是[0,1000 000 000]。

【输出形式】

对应每个测试案例，输出最小的k个数，并按从小到大顺序打印(如果不存在k个不同的数，则按照实际数量进行输出)。

【样例输入】

8 4
4 5 1 6 2 7 3 8

【样例输出】

1 2 3 4

【训练提示】

1、数的范围从0到1000000000，使用数组记录那些数出现过就不是太合适

2、需要去除重复的数，需要从小到大排序—-set就是一个不错的选择

题解

这个提示我没看到，但其实无所谓，set和map都自带排序，去重也无所谓，用map的话直接桶排序原理就是

代码
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <map>
using namespace std;
int main(){
    int n,k;
    scanf("%d %d",&n,&k);
    map<long long, int> a;
    while(n--){
        int x;
        scanf("%d", &x);
        a[x] = 1;
    }
    int index=0;
    for(map<long long,int>::iterator it = a.begin(); it!=a.end(); it++){
        printf("%lld ", it->first);
        index++;
        if(index==k)break;
    }
    return 0;
}

12.绩点计算

题目

【问题描述】

学校对本科生的成绩施行绩点制（GPA）。将学生的实际考分根据不同学科的不同学分按一定的公式进行计算。规定如下：

实际成绩 绩点

90-100 4.0

85-89 3.7

82-84 3.3

78-81 3.0

75-77 2.7

72-74 2.3

68-71 2.0

64-67 1.5

60-63 1.0

60以下 0

  1. 一门课程的学分绩点=该课绩点*该课学分

  2. 总评绩点=所有学科绩点之和/所有课程学分之和

现要求你编程求出某人的总评绩点(GPA)

【输入形式】

第一行 总的课程数n

第二行 相应课程的学分（两个学分间用空格隔开）

第三行 对应课程的实际得分

此处输入的所有数字均为整数

【输出形式】

输出有一行，总评绩点，保留两位小数

【样例输入】

5
4 3 4 2 3
91 88 72 69 56

【样例输出】

2.52
题解

水题一道，直接模拟过。。。

代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int main(){
    int n;
    scanf("%d", &n);
    int a[n];
    int asum=0;
    double sum=0;
    for(int i=0;i<n;i++){
        scanf("%d", &a[i]);
        asum+=a[i];
    }
    for(int i=0;i<n;i++){
        int qaq;
        scanf("%d", &qaq);
        if(qaq>=90)sum+=4.0*a[i];
        else if(qaq>=85)sum+=3.7*a[i];
        else if(qaq>=82)sum+=3.3*a[i];
        else if(qaq>=78)sum+=3.0*a[i];
        else if(qaq>=75)sum+=2.7*a[i];
        else if(qaq>=72)sum+=2.3*a[i];
        else if(qaq>=68)sum+=2.0*a[i];
        else if(qaq>=64)sum+=1.5*a[i];
        else if(qaq>=60)sum+=1.0*a[i];
    }
    double ans=sum/asum;
    printf("%.2f", ans);
    return 0;
}

13.xxx定律

题目

【问题描述】

   对于一个正整数n，如果是偶数，就把n砍掉一半；如果是奇数，把n变成 3*n+ 1后砍掉一半，直到该数变为1为止。   请计算需要经过几步才能将n变到1，具体可见样例。

【输入形式】

   测试包含多个用例，每个用例包含一个整数n,当n为0 时表示输入结束。（1<=n<=10000）

【输出形式】

   对于每组测试用例请输出一个数，表示需要经过的步数,每组输出占一行。

【样例输入】

3
2
0

【样例输出】

5
1
题解

其实这题应该叫“冰雹猜想”，也是纯模拟，一个while解决（能不写递归就不写递归）

代码
#include <iostream>
#include <cstdio>
using namespace std;
int main(){
    int n;
    while(scanf("%d", &n) && n){
        int i=0;
        while(n!=1){
            if(n%2==0)n/=2;
            else n=(3*n+1)/2;
            i++;
        }
        printf("%d\n",i);
    }
    return 0;
}

14.数的距离差

题目

【问题描述】

给定一组正整数，其中最大值和最小值分别为Max和Min, 其中一个数x到Max和Min的距离差定义为：

  abs(abs(x-Max)-(x-Min))

其中abs()为求一个数的绝对值

【输入形式】

包括两行，第一行一个数n，表示第二行有n个正整数

【输出形式】

输出一个数x，该数在所有n个数中的距离差最小；如果有两个数的距离差都是最小，输出较小的哪个

【样例输入1】

5
3 1 7 5 9

【样例输出1】

5

【样例输入2】

3
1 3 2

【样例输出2】

2
题解

显然这个数离最大值最小值的平均值越近越好，

所以我们考虑排序完直接lower_bound，然后查左右（当然直接暴力一个一个查也行）

代码
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int main(){
    int n;
    scanf("%d", &n);
    int a[n];
    for(int i=0;i<n;i++)scanf("%d", &a[i]);
    sort(a,a+n);
    int avg = (a[0]+a[n-1])/2;
    int i = lower_bound(a,a+n,avg)-a;
    if(a[i] == avg || i==0)printf("%d", avg);
    else if(abs(a[n-1]+a[0]-2*a[i-1]) <= abs(a[n-1]+a[0]-2*a[i]))printf("%d", a[i-1]);
    else printf("%d", a[i]);
}

15.亲和数

题目

问题描述】

古希腊数学家毕达哥拉斯在自然数研究中发现，220 的所有真约数(即不是自身的约数)之和为：

           1+2+4+5+10+11+20+22+44+55+110＝284。

而 284 的所有真约数为 1、2、4、71、 142，加起来恰好为 220。人们对这样的数感到很惊奇，并称之为亲和数。一般地讲，如果两个数中任何一个数都是另一个数的真约数之和，则这两个数就是亲和数。
你的任务就编写一个程序，判断给定的两个数是否是亲和数。

【输入形式】

输入若干行数据（大于0），每行一个实例,包含两个整数A,B； 其中 0 <= A,B <= 600000 ;

【输出形式】

对于每个测试实例，如果 A 和 B 是亲和数的话输出 YES，否则输出 NO

【样例输入】

220 284
100 200

【样例输出】

YES
NO
题解

把两个数的约数和分别算出来比较就行。。。水题一道

当然要优化也是有的，只是打起来麻烦，就不写了

代码
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int main(){
    int a,b;
    while(~scanf("%d %d", &a,&b)){
        int s1=0,s2=0;
        for(int i=1;i<=a/2;i++)
            if(a%i==0)
                s1+=i;
        for(int i=1;i<=b/2;i++)
            if(b%i==0)
                s2+=i;
        if(s1==b && s2==a)printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

16.金币

题目

【问题描述】

国王为他的忠诚的骑士支付金币。在他服役的第一天，骑士收到一枚金币。在接下来2天（第二天和第三天的服务），骑士每天收到2金币。在未来三天（第五，第四，和第六天的服务），骑士每天收到三金币。在未来四天（第七，第八，第九，和第十天的服务），骑士每天收到四金币。这一模式的付款方式将继续下去：在接下来的n天骑士每天将收到n枚金币，而在接接下来的n+1天每天将收到n+1枚金币，这里n是正整数。你的程序将确定在任何给定的天数（从第1天开始）支付给骑士的金币总数。

【输入形式】

输入包含至少一行，但不超过21行。输入的每一行包含一个测试案例的数据，即一个整数（1~10000），代表天数。

【输出形式】

每一行输出对应一个测试用例，由天数和支付给骑士的金币总数量组成，中间用空格分隔。

【样例输入】

10
6
10000
1000
21
22

【样例输出】

10 30
6 14
10000 942820
1000 29820
21 91
22 98
题解

计算i^2和（i和小于总天数），然后加上剩余天数*(i+1)就行

代码
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int main(){
    int n;
    while(~scanf("%d",&n)){
        int t=0,i=1,ans=0;
        while(t+i<n){
            ans+=i*i;
            t+=i++;
        }
        ans+=(n-t)*i;
        printf("%d %d\n",n,ans);
    }
    return 0;
}

17.小A的计算器

题目

【问题描述】

    以往的操作系统内部的数据表示都是二进制方式，小A新写了一个操作系统，系统内部的数据表示为26进制，其中0-25分别由a-z表示。    现在小A要在这个操作系统上实现一个计算器，这个计算器要能实现26进制数的加法运算。你能帮小A实现这个计算器吗？

【输入形式】

   输入的第一行包括一个整数N(1<=N<=100)。   接下来的N行每行包括两个26进制数x和y，它们之间用空格隔开，每个数的位数最多为10位,我们可以保证相加的结果的位数最多也是10位。每个数会用小A所设计的操作系统中的表示方法来表示，如：bsadfasdf。即每个数的各个位均由26个小写字母a-z中的一个来表示。

【输出形式】

    输出x和y相加后的结果，结果也要用题目中描述的26进制数来表示。

【样例输入】

4
ba cd
c b
b c
ba c

【样例输出】

dd
d
d
bc
题解

这题的数据量。。。字符串长度不大于10，26进制转化成10进制也不会爆int。可以直接转换成10进制作加法，然后再转化回来就行

那如果要应对大数据？用高精度加法吧(小学加法原理就是了)

具体可以看关于 C++ 高精度运算的几种方式

代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int main(){
    int n;
    scanf("%d", &n);
    while(n--){
        string a,b,c="";
        cin>>a>>b;
        reverse(a.begin(),a.end());
        reverse(b.begin(),b.end());
        int l1 = a.length(), l2 = b.length();
        int temp=0,i;
        for(i=0;i<l1 && i<l2;i++){
            int s = a[i]-'a' + b[i]-'a' + temp;
            temp = s/26;
            c += s%26 + 'a';
        }
        if(i==l1)
            for(;i<l2;i++){
                int s = b[i]-'a' + temp;
                temp = s/26;
                c += s%26 +'a';
            }
        if(i==l2)
            for(;i<l1;i++){
                int s = a[i]-'a' + temp;
                temp = s/26;
                c += s%26 +'a';
            }
        if(temp==1)c+='b';
        reverse(c.begin(),c.end());
        i=0;
        int l=c.length();
		//清楚前导0
        while(c[i]=='a')i++;
        string ans="";
        for(;i<l;i++)ans+=c[i];
        if(ans.length()==0)ans='a';
        cout<<ans<<endl;
    }
    return 0;
}

18.小丑排序

题目

【问题描述】

你在信天翁马戏团（是的，它是由一群小丑组成）从事管理工作，你刚刚写完一个程序的输出是将他们的姓名按长度为非递减的方式排列，名称列表（使每名至少只要它之前的）。然而，你的老板不喜欢这种输出方式，而是希望输出出现更对称，较短的字符串在顶部和底部，而较长的字符串在中间。他的规则是，每一对名称都是在该列表的相对的两端，并且在该组中的第一个名字总是在列表的顶部。比如在下面的第一个例子中，Bo和Pat是第一对，Jean和Kevin是第二对，等等。

【输入形式】

输入由1到多个字符串集合组成，最后一行为0表示输入结束，每个集合开始于一个整数n，表示该集合字符串的个数，接下来n行由n个字符串按长度非递减的方式排列，每个集合至少包含一个但不超过15个字符串，每个字符串不超过25个字符。

【输出形式】

对于每个集合，第一行输出”set-n”, n从1开始，接下来的若干行对应输入每个集合重新排列的结果，如样例所示。

【样例输入】

7
Bo
Pat
Jean
Kevin
Claude
William
Marybeth
6
Jim
Ben
Zoe
Joey
Frederick
Annabelle
5
John
Bill
Fran
Stan
Cece
0

【样例输出】

set-1
Bo
Jean
Claude
Marybeth
William
Kevin
Pat
set-2
Jim
Zoe
Frederick
Annabelle
Joey
Ben
set-3
John
Fran
Cece
Stan
Bill
题解

其实就是0,3,5…再倒回来到1，分奇偶判断下就行

代码
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
int main(){
    int index=1,n;
    while(scanf("%d", &n) && n){
        string s[n];
        for(int i=0;i<n;i++)
            cin>>s[i];
        printf("set-%d\n", index++);
        int i;
        for(i=0;i<n;i+=2)cout<<s[i]<<endl;
        if(i-1<n)i--;
        else i-=3;
        for(;i>0;i-=2)cout<<s[i]<<endl;
    }
    return 0;
}

19.数圈

题目

【问题描述】

以1为中心，用2,3,4, …, n, …, n*n的数字围绕着中心输出数圈， 如若n=4，则

7 8 9 10

6 1 2 11

5 4 3 12

16 15 14 13

【输入形式】

一个整数n(1<=n<=10)

【输出形式】

数圈矩阵

【样例输入】

5

【样例输出】

21 22 23 24 25
20 7 8 9 10
19 6 1 2 11
18 5 4 3 12
17 16 15 14 13
题解

我们找一找1的位置，找规律绕圈出来就行

代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int main(){
    int n;
    scanf("%d", &n);
    int a[n+1][n+1];
    memset(a,0,sizeof(a));
    int i=(n-1)/2, j=(n-1)/2;
    a[i][j]=1;
    int index=2;
    for(int k=1;k<=n;k++){
        for(int q=1;q<=k;q++)
            a[i][++j]=index++;
        for(int q=1;q<=k;q++)
            a[++i][j]=index++;
        k++;
        for(int q=1;q<=k;q++)
            a[i][--j]=index++;
        for(int q=1;q<=k;q++)
            a[--i][j]=index++;
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++)
            printf("%d ", a[i][j]);
        printf("\n");
    }
}

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
题解

又是一道统计的水题。。。

代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct P{
    int s=0,f=0,p=0;
    int c=0,j=0,b=0;
}a[2];

int main(){
    int n;
    scanf("%d", &n);
    while(n--){
        char ch1,ch2;
        cin>>ch1>>ch2;
        if(ch1 == ch2)a[0].p+=1,a[1].p+=1;
        else if(ch1 == 'C' && ch2 == 'J')a[0].s+=1,a[1].f+=1,a[0].c+=1;
        else if(ch1 == 'J' && ch2 == 'B')a[0].s+=1,a[1].f+=1,a[0].j+=1;
        else if(ch1 == 'B' && ch2 == 'C')a[0].s+=1,a[1].f+=1,a[0].b+=1;
        else if(ch2 == 'C' && ch1 == 'J')a[1].s+=1,a[0].f+=1,a[1].c+=1;
        else if(ch2 == 'J' && ch1 == 'B')a[1].s+=1,a[0].f+=1,a[1].j+=1;
        else if(ch2 == 'B' && ch1 == 'C')a[1].s+=1,a[0].f+=1,a[1].b+=1;
    }
    printf("%d %d %d\n", a[0].s,a[0].p,a[0].f);
    printf("%d %d %d\n", a[1].s,a[1].p,a[1].f);
    if(a[0].b>=a[0].c && a[0].b>=a[0].j)printf("B ");
    else if(a[0].c>a[0].b && a[0].c>=a[0].j)printf("C ");
    else printf("J ");
    if(a[1].b>=a[1].c && a[1].b>=a[1].j)printf("B ");
    else if(a[1].c>a[0].b && a[1].c>=a[1].j)printf("C ");
    else printf("J ");
    return 0;
}

21.新型冠状病毒（COVID19）传播

题目

【问题描述】

   然而，在大洋彼岸的 M 国，人们对COVID19并未引起足够重视，他们的领导人川建国同志甚至对居家隔离、戴口罩以及保持社交距离等措施非常不屑，该国疫情已经完全失控。   在一个风景秀丽的小镇，一天早上，有 N 名晨跑爱好者（编号 1 ～ N ）沿着优雅的江边景观道朝同一方向进行晨跑，第 i 名跑者从位置 Si 处起跑， 且其速度为 Vi。换句话说，对所有的实数 t ≥ 0，在时刻 t 时第 i 名跑者的位置为 Si + Vi ·t。    很不幸的是，其中一名跑者在 t = 0 的时刻感染了病毒，且是无症状感染者，这种病毒只会在同一时刻处在同一位置的跑者之间传播，新感染了病毒的跑者也会感染其他人，很显然，等待足够长的时间，那么病毒会感染 一些特定的跑者。   事后发现其中有一名跑者感染了新冠病毒，如果此人就是在 t = 0 时刻的那名感染者，那么，在 N 名晨跑爱好者中会有多少人感染新冠病毒？

【输入形式】

    输入包含三行：

第一行包含为两个整数 N 和 K，分别表示运动员的人数以及开始时感染了病毒的跑者编号。

第二行包含 N 个正整数 S1、S2、…、SN，用空格隔开，分别表示跑者的起始位置。

第三行包含 N 个正整数 V1、V2、…、VN，用空格隔开，分别表示跑者的速度。

【输出形式】

     输出为一个整数，表示最终被感染人数。

【样例输入】

6 3
3 9 8 5 7 5
6 6 5 4 6 3

【样例输出】

3

【样例说明】
【评分标准】

 对于50%的评测用例，0 < K ≤ N ≤ 10^2 对于70%的评测用例，0 < K ≤ N ≤ 10^4 对于90%的评测用例，0 < K ≤ N ≤ 10^6 对于100%的评测用例，0 < K ≤ N ≤ 10^7
题解

这题和第九题相对比较有思考量一点

找出所有感染者的思路较难，所以我们反向寻找，找到安全的人的数目。

而安全的人有什么特点呢？

我们将安全的人分为两个部分：一部分人初始位置小于零号感染者；另一部分人初始位置大于零号感染者。

初始位置小于零号感染者的人要想不被感染，其速度只能小于等于右边所有人的最小速度。因为我们将零号感染者看做在右边。右边速度最小的那个人一定会被零号感染者感染。而左边人的速度要是大于这个最小速度，那么也会被感染。

所以初始位置大于零号感染者的人要想不被感染，其速度只能大于等于左边所有人的最大速度。

然后就是各种代码了。你可以像我一样，直接以上面的思路直接模拟

也可以以速度作为第一关键字，位置作为第二关键字排序，然后找第一个位置大于零号等于位置的编号和最后一个位置小于等于零号位置的编号，这两个编号之间的人（包括编号对应人的本身）就是感染者（为什么？自行理解）

代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int a[2][10000005];
int main(){
    int n,k;
    scanf("%d %d",&n,&k);
    for(int i=0;i<2;i++)
        for(int j=0;j<n;j++)
            scanf("%d", &a[i][j]);
    int num=n;
    k--;
    int ma=0,mi=99999999;
    for(int i=0;i<n;i++){
        if(a[0][i]<=a[0][k])
            ma=max(ma,a[1][i]);
        if(a[0][i]>=a[0][k])
            mi=min(mi,a[1][i]);
    }
    for(int i=0;i<n;i++){
        if(a[0][i]<a[0][k] && a[1][i]<=mi)num--;
        else if(a[0][i]>a[0][k] && a[1][i]>=ma)num--;
    }
    printf("%d", num);
    return 0;
}

结

第二周复盘结束。有什么问题可以评论留言