7-1 正整数A+B (15分)

题的目标很简单，就是求两个正整数A和B的和，其中A和B都在区间[1,1000]。稍微有点麻烦的是，输入并不保证是两个正整数。

输入格式：

输入在一行给出A和B，其间以空格分开。问题是A和B不一定是满足要求的正整数，有时候可能是超出范围的数字、负数、带小数点的实数、甚至是一堆乱码。

注意：我们把输入中出现的第1个空格认为是A和B的分隔。题目保证至少存在一个空格，并且B不是一个空字符串。

输出格式：

如果输入的确是两个正整数，则按格式A + B = 和输出。如果某个输入不合要求，则在相应位置输出?，显然此时和也是?。

输入样例1：

123 456

输出样例1：

123 + 456 = 579

输入样例2：

18

输出样例2：

? + 18 = ?

输入样例3：

-100 blabla bla…33

输出样例3：

? + ? = ?

#include <algorithm>#include <bitset>#include <cmath>#include <cstdio>#include <cstdlib>#include <cstring>#include <deque>#include <functional>#include <iostream>#include <map>#include <queue>#include <set>#include <stack>#include <string>#include <vector>#define INF 0x3f3f3f3fusing namespace std;int f(char *str){int i;int sum=0;for(i=0;str[i]!='\0';i++){if(str[i]>='9'||str[i]<='0')//忘记了加等号{return -1;}else{sum=sum*10+(str[i]-'0');}}if(sum>=1&&sum<=1000)//容易拉掉题目中这个条件{return sum;}else return -1;}int main(){char str1[10001],str2[10001];scanf("%s ",str1);scanf("%s",str2);int sum1,sum2;sum1=f(str1);sum2=f(str2);if(sum1==-1)printf("? + ");elseprintf("%d + ",sum1);if(sum2==-1)printf("? = ");elseprintf("%d = ",sum2);if(sum1==-1||sum2==-1)printf("?\n");elseprintf("%d\n",sum1+sum2);return 0;}

7-3 出租

下面是新浪微博上曾经很火的一张图：

一时间网上一片求救声，急问这个怎么破。其实这段代码很简单，index数组就是arr数组的下标，index[0]=2 对应 arr[2]=1，index[1]=0 对应 arr[0]=8，index[2]=3 对应 arr[3]=0，以此类推…… 很容易得到电话号码是18013820100。

本题要求你编写一个程序，为任何一个电话号码生成这段代码 —— 事实上，只要生成最前面两行就可以了，后面内容是不变的。

输入格式：

输入在一行中给出一个由11位数字组成的手机号码。

输出格式：

为输入的号码生成代码的前两行，其中arr中的数字必须按递减顺序给出。

输入样例：

18013820100

输出样例：

int[] arr = new int[]{8,3,2,1,0};int[] index = new int[]{3,0,4,3,1,0,2,4,3,4,4};

思路：这道题并不难，其实就是用arr数组依递减顺序来储存手机号码中的数字，然后index数组来储存arr数组中对应的电话号码数字的下标
注意：电话号码要以字符串的形式输入
代码：

#include <algorithm>#include <bitset>#include <cmath>#include <cstdio>#include <cstdlib>#include <cstring>#include <deque>#include <functional>#include <iostream>#include <map>#include <queue>#include <set>#include <stack>#include <string>#include <vector>#define INF 0x3f3f3f3fusing namespace std;bool compare(int a,int b){return a>b;}int main(){char str[11];scanf("%s",str);int arr[11];int index[11];int i;int j,flag;int k=0;arr[k++]=str[0]-'0';for(i=1;i<11;i++){j=0;flag=0;while(j<k){if(arr[j]!=str[i]-'0'){j++;}else{flag=1;break;}}if(!flag&&j==k)arr[k++]=str[i]-'0';}int m=0;sort(arr,arr+k,compare);//递减顺序来储存电话号码的数字for(i=0;i<11;i++){for(j=0;j<k;j++){if(str[i]-'0'==arr[j]){index[m++]=j;break;}}}printf("int[] arr = new int[]{");for(i=0;i<k;i++){if(i<k-1)printf("%d,",arr[i]);elseprintf("%d};\n",arr[i]);}printf("int[] index = new int[]{");for(i=0;i<m;i++){if(i<m-1)printf("%d,",index[i]);elseprintf("%d};\n",index[i]);}return 0;}

7-4 判断素数

本题的目标很简单，就是判断一个给定的正整数是否素数。

输入格式：
输入在第一行给出一个正整数N（≤ 10），随后N行，每行给出一个小于2
​31
​​ 的需要判断的正整数。

输出格式：
对每个需要判断的正整数，如果它是素数，则在一行中输出Yes，否则输出No。

输入样例：

211111

输出样例：

YesNo

素数：素数又称质数，即除了一和它本身没有其他约数的数

#include <algorithm>#include <bitset>#include <cmath>#include <cstdio>#include <cstdlib>#include <cstring>#includea <deque>#include <functional>#include <iostream>#include <map>#include <queue>#include <set>#include <stack>#include <string>#include <vector>#define INF 0x3f3f3f3fusing namespace std;int isPrime(int n){int i,flag=1;if(n<=1)flag=0;else if(n==2)flag=1;else if(n%2==0)flag=0;else{for(i=3;i<=sqrt(n)+1;i+=2)//很重要，要记住哦{if(n%i==0){flag=0;break;}}}return flag;}int main(){int m;int i,n;cin>>n;for(i=0;i<n;i++){cin>>m;if(isPrime(m)){printf("Yes\n");}elseprintf("No\n");}return 0;}

7-6 一帮一 (15分)

“一帮一学习小组”是中小学中常见的学习组织方式，老师把学习成绩靠前的学生跟学习成绩靠后的学生排在一组。本题就请你编写程序帮助老师自动完成这个分配工作，即在得到全班学生的排名后，在当前尚未分组的学生中，将名次最靠前的学生与名次最靠后的异性学生分为一组。

输入格式：
输入第一行给出正偶数N（≤50），即全班学生的人数。此后N行，按照名次从高到低的顺序给出每个学生的性别（0代表女生，1代表男生）和姓名（不超过8个英文字母的非空字符串），其间以1个空格分隔。这里保证本班男女比例是1:1，并且没有并列名次。

输出格式：
每行输出一组两个学生的姓名，其间以1个空格分隔。名次高的学生在前，名次低的学生在后。小组的输出顺序按照前面学生的名次从高到低排列。

输入样例：

80 Amy1 Tom1 Bill0 Cindy0 Maya1 John1 Jack0 Linda

输出样例：

Amy JackTom LindaBill MayaCindy John#include <algorithm>#include <bitset>#include <cmath>#include <cstdio>#include <cstdlib>#include <cstring>#include <deque>#include <functional>#include <iostream>#include <map>#include <queue>#include <set>#include <stack>#include <string>#include <vector>#define INF 0x3f3f3f3fusing namespace std;struct student{int num;char name[11];}a[51],b[51];int main(){int n;cin>>n;int i,j;for(i=0;i<n;i++){scanf("%d %s",&a[i].num,a[i].name);}int k=0;for(i=n-1;i>=n/2;i--){b[k++]=a[i];}for(i=0;i<n/2;i++){for(j=0;j<k;j++){if(b[j].num!=a[i].num){printf("%s %s\n",a[i].name,b[j].name);while(j<k){b[j]=b[j+1];j++;}k--;break;}}}return 0;}

7-8 Left-pad (20分)

根据新浪微博上的消息，有一位开发者不满NPM（Node Package Manager）的做法，收回了自己的开源代码，其中包括一个叫left-pad的模块，就是这个模块把javascript里面的React/Babel干瘫痪了。这是个什么样的模块？就是在字符串前填充一些东西到一定的长度。例如用去填充字符串GPLT，使之长度为10，调用left-pad的结果就应该是*****GPLT。Node社区曾经对left-pad紧急发布了一个替代，被严重吐槽。下面就请你来实现一下这个模块。

输入格式：

输入在第一行给出一个正整数N（≤10
​4
​​ ）和一个字符，分别是填充结果字符串的长度和用于填充的字符，中间以1个空格分开。第二行给出原始的非空字符串，以回车结束。

输出格式：

在一行中输出结果字符串。

输入样例1：

15 _I love GPLT

输出样例1：

____I love GPLT

输入样例2：

4 *

this is a sample for cut

输出样例2：

cut关于字符和字符串的输入和输出：getchar()函数不带任何参数，他从输入队列中返回下一个字符。ch=getchar();该语句与下面的语句效果相同：scanf("%c",&ch);putchar()函数打印它的参数，例如，下面的语句把之前赋给ch的值作为字符打印出来：putchar(ch);该语句与下面语句效果相同：printf("%c",ch);由于这些函数只处理字符，所以他们比更通用的scanf()和printf()函数更快、更简洁，这两个函数在C语言中，定义在stdio.h头文件中、、、、、、、在读取字符串的时候，scanf()和转换说明%s只能读取一个单词，可是在程序中经常要读取一整行输入，而不仅仅是一个单词。gets()函数简单易用，它读取整行输入，**直至遇到换行符**，然后丢弃换行符，储存其余字符，并在这些字符末尾添加一个空字符串使其成为一个C字符串。它常常和puts()函数配对使用，该函数用于显示字符串，并在末尾添加换行符。*该函数用于显示字符串，并在末尾添加换行符。*

代码

#include <algorithm>#include <stdio.h>#include <bitset>#include <cmath>#include <cstdio>#include <cstdlib>#include <cstring>#include <deque>#include <functional>#include <iostream>#include <map>#include <queue>#include <set>#include <stack>#include <string>#include <vector>#include<bits/stdc++.h>#define INF 0x3f3f3f3fusing namespace std;#define Max 100001int main(){int n;char ch;string str;cin>>n>>ch;getchar();//吃掉回车getline(cin,str);//PTA考试禁用gets()函数，所以用getline来代替int m=str.size();if(m>=n){for(int i=m-n;i<m;i++){putchar(str[i]);}cout<<endl;}else{int k=n-m;while(k--){printf("%c",ch);}cout<<str<<endl;}return 0;}

注意：PTA考试禁用gets函数，可以用cin.getline()函数或者fgets()函数来代替，但是fgets()函数有个缺点就是它可以读取’\n’字符，所以更加推荐使用cin.getline()

string str;getline(cin, str);

7-9 红色警报 (25分)
战争中保持各个城市间的连通性非常重要。本题要求你编写一个报警程序，当失去一个城市导致国家被分裂为多个无法连通的区域时，就发出红色警报。注意：若该国本来就不完全连通，是分裂的k个区域，而失去一个城市并不改变其他城市之间的连通性，则不要发出警报。

输入格式：
输入在第一行给出两个整数N（0 < N ≤ 500）和M（≤ 5000），分别为城市个数（于是默认城市从0到N-1编号）和连接两城市的通路条数。随后M行，每行给出一条通路所连接的两个城市的编号，其间以1个空格分隔。在城市信息之后给出被攻占的信息，即一个正整数K和随后的K个被攻占的城市的编号。

注意：输入保证给出的被攻占的城市编号都是合法的且无重复，但并不保证给出的通路没有重复。

输出格式：
对每个被攻占的城市，如果它会改变整个国家的连通性，则输出Red Alert: City k is lost!，其中k是该城市的编号；否则只输出City k is lost.即可。如果该国失去了最后一个城市，则增加一行输出Game Over.。

输入样例：

5 40 11 33 00 451 2 0 4 3

输出样例：

City 1 is lost.City 2 is lost.Red Alert: City 0 is lost!City 4 is lost.City 3 is lost.Game Over.

思路：并查集判断图的连通性
代码：

#include <algorithm>#include <stdio.h>#include <bitset>#include <cmath>#include <cstdio>#include <cstdlib>#include <cstring>#include <deque>#include <functional>#include <iostream>#include <map>#include <queue>#include <set>#include <stack>#include <string>#include <vector>#include<bits/stdc++.h>#define INF 0x3f3f3f3fusing namespace std;#define Max 100001struct p{int x;int y;//分别代表线路两端的两个城市}eg[5001];int parent[505];//寻找跟之间的关系//寻根操作int Find(int x){if(parent[x]!=x)parent[x]=Find(parent[x]);return parent[x];}//并集void Marge(int x,int y){if(Find(x)!=Find(y)){parent[Find(x)]=Find(y);}}int main(){int n,m;int u,v;int vis[505];cin>>n>>m;//初始化操作for(int j=0;j<n;j++){parent[j]=j;}for(int i=0;i<m;i++){cin>>u>>v;eg[i].x=u;eg[i].y=v;Marge(u,v);//把联通的城市并起来}int sum=0;//记录城市分为几块儿for(int i=0;i<n;i++){if(parent[i]==i){sum++;}}int k,num;cin>>k;//被攻占的城市的个数memset(vis,0,sizeof(vis));//初始化vis数组，vis数组的作用是标记某个城市被攻占for(int i=0;i<k;i++){for(int j=0;j<n;j++)//输入被攻占的城市时需要重新初始化{parent[j]=j;//初始化每个城市的根都是自身}cin>>num;//被攻占的城市vis[num]=1;//标记该城市已被攻占for(int i=0;i<m;i++){if(vis[eg[i].x]==1||vis[eg[i].y]==1)continue;//重新开始，进行下一次循环Marge(eg[i].x,eg[i].y);//否则，就要并起来，未被攻占的城市之间本来就有关系的当然要并起来}int cnt=0;for(int i=0;i<n;i++)//看看现在的城市被分为几块儿{if(parent[i]==i)cnt++;}if(cnt-1==sum||cnt==sum)//少了一个城市，但这个城市并不影响整体连通性或者是少了一个城市，这个城市本身就是独立的printf("City %d is lost.\n",num);elseprintf("Red Alert: City %d is lost!\n",num);sum=cnt;//更新块数}if(k>=n)printf("Game Over.\n");return 0;}

代码参考该博客

7-10 列车调度 (25分)
火车站的列车调度铁轨的结构如下图所示。

两端分别是一条入口（Entrance）轨道和一条出口（Exit）轨道，它们之间有N条平行的轨道。每趟列车从入口可以选择任意一条轨道进入，最后从出口离开。在图中有9趟列车，在入口处按照{8，4，2，5，3，9，1，6，7}的顺序排队等待进入。如果要求它们必须按序号递减的顺序从出口离开，则至少需要多少条平行铁轨用于调度？

输入格式：
输入第一行给出一个整数N (2 ≤ N ≤10
​5
​​ )，下一行给出从1到N的整数序号的一个重排列。数字间以空格分隔。

输出格式：
在一行中输出可以将输入的列车按序号递减的顺序调离所需要的最少的铁轨条数。

输入样例：

98 4 2 5 3 9 1 6 7

输出样例：

4

//自己敲的代码虽然运行超时，但是思路还是对的，就是不知道如何优化，所以参考了别人的代码，思路虽然一样，但代码的想法完全不同
//思路：火车进站其实就是火车的编号入栈，但是要入栈的火车编号要和已有的火车轨道（栈）上的火车编号进行比较，只有小于栈顶元素才能入栈，否则就建立新的栈（轨道）
自己敲的代码（部分测试用例超时）

#include <algorithm>#include <stdio.h>#include <bitset>#include <cmath>#include <cstdio>#include <cstdlib>#include <cstring>#include <deque>#include <functional>#include <iostream>#include <map>#include <queue>#include <set>#include <stack>#include <string>#include <vector>#include<bits/stdc++.h>#define INF 0x3f3f3f3fusing namespace std;#define Max 100001int main(){int N;cin>>N;int i;int a[Max];for(i=1;i<=N;i++){cin>>a[i];}int k=0;stack<int>s[10001];s[k++].push(a[1]);for(i=2;i<=N;i++){int j=0;int flag=0;while(j<k){if(a[i]<s[j].top()){s[j].push(a[i]);flag=1;break;}j++;}if(!flag){s[k++].push(a[i]);}}cout<<k<<endl;return 0;}

正确代码

#include <algorithm>#include <stdio.h>#include <bitset>#include <cmath>#include <cstdio>#include <cstdlib>#include <cstring>#include <deque>#include <functional>#include <iostream>#include <map>#include <queue>#include <set>#include <stack>#include <string>#include <vector>#include<bits/stdc++.h>#define INF 0x3f3f3f3fusing namespace std;#define Max 100001int main(){int n;cin>>n;int a[Max];//a数组的长度代表轨道的个数int len=0;for(int i=0;i<n;i++){int x;cin>>x;if(len==0||a[len-1]<x)//1、如果数组长度为0或者说没有车进站，那么就将车进站，2、如果将要进站的车的编号要大于（a[len-1)中储存的车的编号是a数组中最大的，所以如果进站的车的编号要比a[len-1]大的话，那么就要新开一个轨道来存放它{a[len++]=x;}else{int l=0,r=len-1;while(l<r)//二分查找，节省运行时间{int mid=(l+r)/2;if(a[mid]>x)r=mid;elsel=mid+1;}a[l]=x;//找到并更新}}cout<<len<<endl;return 0;}

7-11 互评成绩 (25分)
学生互评作业的简单规则是这样定的：每个人的作业会被k个同学评审，得到k个成绩。系统需要去掉一个最高分和一个最低分，将剩下的分数取平均，就得到这个学生的最后成绩。本题就要求你编写这个互评系统的算分模块。

输入格式：
输入第一行给出3个正整数N（3 < N ≤10
​4
​​ ，学生总数）、k（3 ≤ k ≤ 10，每份作业的评审数）、M（≤ 20，需要输出的学生数）。随后N行，每行给出一份作业得到的k个评审成绩（在区间[0, 100]内），其间以空格分隔。

输出格式：
按非递减顺序输出最后得分最高的M个成绩，保留小数点后3位。分数间有1个空格，行首尾不得有多余空格。

输入样例：

6 5 388 90 85 99 6067 60 80 76 7090 93 96 99 9978 65 77 70 7288 88 88 88 8855 55 55 55 55

输出样例：

87.667 88.000 96.000

本题没有难度，但是需要非常细心，由于我太着急，所以拉了条件，导致浪费了时间，还没做出来
代码：

#include <algorithm>#include <stdio.h>#include <bitset>#include <cmath>#include <cstdio>#include <cstdlib>#include <cstring>#include <deque>#include <functional>#include <iostream>#include <map>#include <queue>#include <set>#include <stack>#include <string>#include <vector>#include<bits/stdc++.h>#define INF 0x3f3f3f3fusing namespace std;#define Max 100001bool cmp(double a,double b){return a>b;}int main(){int n,k,m;cin>>n>>k>>m;double ans[10001];memset(ans,0,sizeof(ans));int score;int p=0;while(n--){int Maxn=0;int Minn=INF;int sum=0;for(int i=1;i<=k;i++){cin>>score;sum=sum+score;if(Maxn<score)Maxn=score;if(Minn>score)Minn=score;}ans[p++]=(sum-Maxn-Minn)*1.0/(k-2);}sort(ans,ans+p,cmp);for(int i=m-1;i>=0;i--){if(i)printf("%.3lf ",ans[i]);elseprintf("%.3lf\n",ans[i]);}return 0;}