2018-2019赛季多校联合新生训练赛第五场补题与题解（中石油）
总结：这场比赛比的我很迷啊，刚开始一个多小时就a了七道题，然后往后怎么做都做不出来题了。。。我也不知道为什么，反正比赛途中因为一个题做不出来直接自闭（疯狂锤头），通过这场比赛我发现一件事情：打比赛的时候心态要好，不能急躁，因为你会发现，急躁的话没有任何用处，并不是说你如果急了的话可以多a一道题什么的。 但是心态好的意思不是放弃比赛，比赛的时候该紧张还是得紧张，拿出百分之二百的注意力来比赛 如果发现不会做的没有关系，又不是说以后都不可能学会了，不会做的话排名比较低什么的都没有关系，还是要放平心态，大不了像现在一样赛后补题。
其实我每一次补题都比那些做出10多道的大佬费劲的多，因为他们都做出的题我都不会啊！所以我还得现学。。。 这次的成绩是71名（铜牌）也是我打中石油成绩最差的一次 这场我得好好补补题啊！ 开始吧！
问题 A: 【字符串】ISBN号码
题目描述
每一本正式出版的图书都有一个ISBN号码与之对应，ISBN码包括9位数字、1位识别码和3位分隔符，其规定格式如“x-xxx-xxxxx-x”，其中符号“-”就是分隔符（键盘上的减号），最后一位是识别码，例如0-670-82162-4就是一个标准的ISBN码。ISBN码的首位数字表示书籍的出版语言，例如0代表英语；第一个分隔符“-”之后的三位数字代表出版社，例如670代表维京出版社；第二个分隔符后的五位数字代表该书在该出版社的编号；最后一位为识别码。
识别码的计算方法如下：
首位数字乘以1加上次位数字乘以2……以此类推，用所得的结果mod 11，所得的余数即为识别码，如果余数为10，则识别码为大写字母X。例如ISBN号码0-670-82162-4中的识别码4是这样得到的：对067082162这9个数字，从左至右，分别乘以1，2，…,9,再求和，即0×1+6×2+……+2×9=158，然后取158 mod 11的结果4作为识别码。
你的任务是编写程序判断输入的ISBN号码中识别码是否正确，如果正确，则仅输出“Right”；如果错误，则输出你认为是正确的ISBN号码。
输入
输入只有一行，是一个字符序列，表示一本书的ISBN号码（保证输入符合ISBN号码的格式要求）。
输出
输出共一行，假如输入的ISBN号码的识别码正确，那么输出“Right”，否则，按照规定的格式，输出正确的ISBN号码（包括分隔符“-”）。
样例输入
复制样例数据 0-670-82162-4
样例输出
Right
这道题我先把所有的数代表的号码加在一起，然后取模以后就是正确的答案，再分类讨论，看一下是否是10，如果是10的话判断一下最后一位是不是‘X’如果是就输出正确，如果不对的话就输出‘X’； 然后看下一种情况，如果不对的话就输出sum就ok了！ 代码：
#include<bits/stdc++.h>
using namespace std;
int main() {
string a;
cin>>a;
int sum=0;
sum+=(a[0]-'0')*1;
sum+=(a[2]-'0')*2;
sum+=(a[3]-'0')*3;
sum+=(a[4]-'0')*4;
sum+=(a[6]-'0')*5;
sum+=(a[7]-'0')*6;
sum+=(a[8]-'0')*7;
sum+=(a[9]-'0')*8;
sum+=(a[10]-'0')*9;
sum%=11;
if(sum==10) {
if(a[12]=='X') {
cout<<"Right";
return 0;
}
else {
cout<<a[0]<<"-"<<a[2]<<a[3]<<a[4]<<"-"<<a[6]<<a[7]<<a[8]<<a[9]<<a[10]<<"-"<<"X";
return 0;
}
}
else
if(a[12]-'0'==sum) {
cout<<"Right";
return 0;
}
else {
cout<<a[0]<<"-"<<a[2]<<a[3]<<a[4]<<"-"<<a[6]<<a[7]<<a[8]<<a[9]<<a[10]<<"-"<<sum;
return 0;
}
}
问题 B: 第N个智慧数
题目描述
一个正整数如果能表示成了两个正整数的平方差，则称这个数为“智慧数”，比如16就等于5的平方减去3的平方，所以16就是一个智慧数，从1开始的自然数列中，将“智慧数”从小到大编号为1,2,3，„„，n。现输入一个正整数n，输出第n个“智慧数”。
输入
仅包含一个正整数 n（1≤n≤100）。
输出
仅包含一个正整数，表示编号为 n 的智慧数。
样例输入
复制样例数据 3
样例输出
7
这题可以把所有的平方差全部算出来，然后打个表，放到set里面自动去重排序，最后输出就行了
#include<bits/stdc++.h>
using namespace std;
int a[]={打表}; 这里有个小技巧，可以加一个,这样就不用每个都自己写了！
int main() {
set<int>ss;
for(int i=0;i<4000;i++)
ss.insert(a[i]);
int n,sum=0;
cin>>n;
for(set<int>::iterator it=ss.begin();it!=ss.end();it++)
{
sum++;
if(sum==n)
{
cout<<*it;
break;
}
}
}
打表的代码：
#include <iostream>
#include <cstdio>
#define maxn 100
using namespace std;
int main(){
freopen("db.txt","w",stdout);
for(int i=1;i<=n;i++)
for(int j=1;j<i;j++)
cout<<i*i-j*j;
}
枚举一下就ok了！
问题 C: 第m大的身份证号码
题目描述
身份证号是我国公民的唯一识别码，它由18位数字或字母组成（只可能最后一位是字母）。18位身份证号码各位的含义如下：第1-2位为省、自治区、直辖市代码；第3-4位为地级市、盟、自治州代码；第5-6位为县、县级市、区代码。第7-14位为出生年月日，比如19970401代表1997年4月1日；第15-16位为顺序号，第17位代表性别，男为单数，女为双数；第18位为校验码，0-9和X。作为尾号的校验码，是把前十七位数字代入统一
的公式计算出来的，解答本题你不用关心是如何计算出来的。现在给你n个身份证号码，请你按照出生年月日的字典序（年龄从大到小）输出第m个人的身份证号。
输入
第一行包含两个正整数n和m，两数间用一个空格分隔，接下来的n行每行为一个形如上述格式的身份证号码（不需要关心校验码的正确性，不影响本题解答）。
输出
仅包含一行，为题目要求的一个身份证号码。
样例输入
复制样例数据 4 2
110108196004063022
13021119640203652X
420333197902112718
210222200012036512
样例输出
13021119640203652X
这题比较简单，只需要定义一个结构体数组，然后放两个string变量，用另一个变量存放第一个变量的6-13位，最后用结构体
排序把身份证号给排出来，再输出第m个就行了 代码：
#include<bits/stdc++.h>
using namespace std;
struct node {
string a;
string b;
}c[100000];
bool cmp(node a,node b) {
return a.b<b.b;
}
int main() {
int n,m;
cin>>n>>m;
for(int i=0;i<n;i++) {
cin>>c[i].a;
int l=c[i].a.size();
for(int j=6;j<=13;j++)
c[i].b+=c[i].a[j];
}
sort(c,c+n,cmp);
cout<<c[m-1].a;
}
问题 D: 锯木棍
题目描述
有一根粗细均匀长度为L的木棍，先用红颜色刻度线将它m等分，再用蓝色刻度线将其n等分（m>n），然后按所有刻度线将该木棍锯成小段，计算并输出长度最长的木棍的长度和根数。
输入
仅有一行，包含三个正整数 L，m 和 n，两两之间用一个空格分隔。 （1≤L≤100000）
输出
包含两个正整数 a 和 k，分别表示最长木棍的长度和根数。（为了简化题目的难度，所有的测试数据中 m 和 n 一定是 L 的约数）。两数间用一个空格分隔。
样例输入
复制样例数据 12 6 4
样例输出
2 4
这道题我刚开始分了很多种情况。。分了一个奇数一个偶数，一个偶数一个奇数，俩都是奇数或者偶数这几种情况，做到最后发现，这样做在里面还得分出来好几种情况，所以自闭了，也没做出来，后来看了大佬博客，再加上别人的思路，发现可以把所有的标记自己先打上，说明棍子已经被锯断了，然后把这根棍子分成了好几个部分，每一个点是1，如果没遇到被锯断的点sum就++ ，如果遇到了就让maxn更新一下，取最大值，如果算出来的数等于最大值的话就把最大的加一，边更新变算根数，到最后输出就ok
放一个传送门：[大佬博客](https://www.cnblogs.com/baccano-acmer/p/10122339.html)
```cpp
#include<bits/stdc++.h>
using namespace std;
int bk[200000];
int main() {
int l,m,n;
cin>>l>>m>>n;
int a=l/m;
int b=l/n;
for(int i=1;i<=l;i++) {
if(i%a==0)
bk[i]=1;
if(i%b==0)
bk[i]=1;
}
int sum=0;
int ans=0;
int maxn=-999999;
for(int i=1;i<=l;i++) {
if(bk[i]==0)
sum++;
else {
sum++;
maxn=max(maxn,sum);
if(sum==maxn)
ans++;
sum=0;
}
}
cout<<maxn<<" "<<ans;
}
问题 E: 坐标统计
题目描述
输入 n 个点在平面上的坐标（横纵坐标都是整数），对于每个点可以控制所有位于它左下方的点（即横坐标 x 和纵坐标 y 都比它小），它可以控制的点的数目称为“战斗力”。依次输出每个点的战斗力，最后输出战斗力最高的点的编号（如果若干个点的战斗力并列最高，输出其中最大的编号）。
输入
第一行包含一个正整数n，接下来的n行，每行描述一个点的坐标，第i+1行包含两个正整数x和y，表示编号为i的点的横坐标为x，纵坐标为y。（1<=n<=100，1<=x<=1000，1<=y<=1000）
输出
共有n+1行第1行到第n行，每行包含一个整数，第i行的整数表示编号为i的点的战斗力，第n+1行表示战斗力最高的点的编号。
样例输入
复制样例数据 6
4 2
6 6
4 8
15 6
11 9
8 14
样例输出
0
1
0
1
3
3
6
这题也是一道基础题，只要在输入的时候判断一下坐标关系就行了，注意必须x和y都比给定值小才能++ 代码：
#include<bits/stdc++.h>
using namespace std;
struct node {
int x;
int y;
int sum;
int id;
}a[10000];
bool cmp(node a,node b) {
if(a.sum!=b.sum)
return a.sum>b.sum;
else
return a.id>b.id;
}
int main() {
int n;
cin>>n;
for(int i=0;i<n;i++) {
cin>>a[i].x>>a[i].y;
a[i].id=i+1;
}
for(int i=0;i<n;i++) {
for(int j=0;j<n;j++) {
if(i!=j) {
if(a[i].x>a[j].x&&a[i].y>a[j].y)
a[i].sum++;
}
}
}
for(int i=0;i<n;i++)
cout<<a[i].sum<<endl;
sort(a,a+n,cmp);
cout<<a[0].id;
}
问题 F: 打印月历
给你一个年份y和一个月份m，请你按照样例的格式打印出y年第m月的月历。例如当y=2015，m=1时，2015年1月的月历打印效果就应该如下：
样例的格式中，第一行为代表星期的字母，第一个字母S代表星期日，第二个字母M代表星期一，以此类推，第七个字母S代表星期六，第一个字母的左边没有空格，两个字母之间有三个空格分隔。接下来的几行是第m月的日期，每一列的数都与本列的第一个字母左对齐，同一行的两个日期之间要有若干个空格分隔。为了简化题目的难度，输入还会给出一个正整数n（n小于8），表示第y年的1月1日是星期n。例如201514的含义是要输出2015年1月的月历，2015年1月1日是星期四。
输入
仅有一行，包含三个正整数 y，m 和 n，两数间用一个空格分隔。
输出
包含符合题目要求的若干行
此处无声胜有声（待解决2333）
问题 G: 分割绳子
题目描述
现有N条绳子，它们的长度分别为L1，L2，„„，Ln，如果从它们中切割出K条长度相同的绳子，这K条绳子每条最长能有多长？
输入
共有两行，第一行包含两个正整数N和K，用一个空格分隔；第二行包含N个数，依次表示N条绳子的长度，两数间用一个空格分隔。每条绳子长度的小数不超过两位。（1<=N<=1000，1<=K<=1000，1<=Li<=10000）
输出
仅包含一个数，表示所得K绳子的最大长度。答案四舍五入保留小数点后两位。
样例输入
复制样例数据 4 11
8.02 7.43 4.57 5.39
样例输出
2.00
此处无声胜有声（待解决2333）
问题 H: 换座位
题目描述
期中考试结束了，班主任想给同学们重新安排座位，所以她让同学们按学号1至n的顺序依次在教室外排好队，然后在队伍中挑选一些同学来改变他们的位置。班主任想知道最终有多少个同学的位置发生了变化。
楠楠是个信息学高手，班主任把这个任务交给楠楠来完成。
输入
第一行，输入一个整数n(n<=100)，表示有n个同学。
第二行，有n个整数，依次表示换位后的学号。
输出
输出有多少个同学的位置发生了变化。
样例输入
复制样例数据 10
1 2 5 4 6 3 7 8 9 10
样例输出
3
提示
只有学号为5，6，3共3位同学的位置发生了变化。
这题直接从i=1开始输入，然后如果a[i]！=i sum++即可
#include<bits/stdc++.h>
using namespace std;
int a[200];
int main() {
int n;
cin>>n;
int sum=0;
for(int i=1;i<=n;i++) {
cin>>a[i];
if(a[i]!=i)
sum++;
}
cout<<sum;
}
问题 I: 找M进制数
题目描述
在信息学课上，楠楠学习了进制数。
他知道了原来数不仅可以表示成十进制，还可以表示成二进制，八进制，十六进制，甚至是二十进制，三十进制都可以。而且它们都有一个相同的运算规则：逢M进一，例如：二进制逢二进一，八进制逢八进一。因此，M进制数中每一位上的数可以用0～M-1来表示，即二进制数中只有0和1两种数字，八进制数中有0，1，2…7共八种数字。但是若M大于10时，大于等于10的数字用大写字母表示，例如十六进制数中有0，1，2…9，A…F共16种数字。
现在老师给出N个任意进制数，要求统计出N个数中合法的M进数的个数。
输入
输入数据有多行。
第一行，有两个整数N(1<=N<=100000)和M(2<=M<=36)，分别表示任意进制数的个数和M进制。
接下来有N行，每行一个由数字和大写字母构成的任意进制数,位数小于50。
输出
输出N个任意进制数中，合法的M进制数的个数。
样例输入
复制样例数据 5 16
102
AFF
5A
890
5S
样例输出
4
提示
因为“5S”中“S”不是16进制数的合法数字，故只有4个合法的16进制数。
这题先输入一下 开一个string数组，输入n个string类型的字符串，分成两种情况：小于等于10和大于10 分别讨论一下两种情况
，第一种情况如果出现大于输入的m或者字母的话就算错，如果是正确的，就让sum++，下面一种情况是m>=11的时候，这时候数字就对这个数没有影响了（因为进制都大于10了，所以任意的数都行）还要像上面判断十进制以前的时候一样，注意不要让最大的字母大于进制就行了 代码：
#include<bits/stdc++.h>
using namespace std;
string a[200000];
int main() {
int n,m;
cin>>n>>m;
for(int i=0;i<n;i++)
cin>>a[i];
int sum=0;
int f;
for(int i=0;i<n;i++) {
f=0;
if(m<=10) {
int l=a[i].size();
for(int j=0;j<l;j++) {
if(a[i][j]>='A'&&a[i][j]<='Z'||a[i][j]-'0'>m-1) {
f=1;
break;
}
}
if(f==0)
sum++;
}
else if(m>=11) {
int k=a[i].size();
for(int g=0;g<k;g++) {
if(a[i][g]>='A') {
if(a[i][g]-'A'+1+10>m) {
f=1;
break;
}
}
}
if(f==0)
sum++;
}
}
cout<<sum;
}
问题 J: 循环小数
题目描述
数学课上，楠楠学习了一个新的知识。
两数相除，如果得不到整数商，会有两种情况：一种是得到有限小数，另一种是得到无限小数。从小数点后某一位开始依次不断地重复出现前一个或一节数字的十进制无限小数，叫做循环小数，如2.9666…, (在数学中它读作“二点九六，六循环” ）， 定义循环小数的缩写法是将第一个循环节以后的数字全部略去，并将第一个循环节首末用括号括起来。
例如：
2.966666… 缩写为 2.9(6)
35.232323…缩写为 35.(23)
楠楠发现，根据循环小数的特征，很快能算出这个循环小数中小数点后第n位的数字，你能吗？
输入
输入数据有两行。
第一行，输入一个整数n(n<=100000)，表示求小数点后的第n位。
第二行，一个字符串，用缩写法表示的一个循环小数。
输出
输出一个整数，求出循环小数中小数点后第n位的数字。
样例输入
复制样例数据 10
352.19(7)
样例输出
7
这题我刚开始读错题了，因为样例里小数点只有括号，所以wa了一次，后来读对题目发现当小数点后的数恰好等于输入的位数的时候就不对。。我也不知道为什么，先放一个当时写的代码上来： 两个string分别是存小数点后括号外面的数和循环节的：
#include<bits/stdc++.h>这是错误代码！！！
using namespace std;
int main() {
int n;
cin>>n;
string a;
cin>>a;
int l=a.size();
string s;
int b;
for(int i=0;i<l;i++) {
if(a[i]=='(') {
s+=a[i+1];
b=i+1;
for(int j=b+1;j<l;j++)
if(a[j]-'0'>=0&&a[j]-'0'<=9)
s+=a[j];
else
break;
}
}
string ss;
int c;
for(int i=0;i<l;i++) {
if(a[i]=='.') {
b=i+1;
for(int j=b;a[j]!=')';j++)
if(a[j]-'0'>=0&&a[j]-'0'<=9)
ss+=a[j];
else
break;
}
}
cout<<ss;
if(ss[0]-'0'>=0&&ss[0]-'0'<=9)
l=ss.size();
else
l=0;
cout<<l<<endl;
int ll=s.size();
if(n<=ss.size()) {
cout<<ss[n-1];
return 0;
}
else {
n-=l;
int ans=n%ll;
if(ans==0) {
cout<<s[ll-1];
return 0;
}
else {
cout<<s[ans-1];
return 0;
}
}
}
这题待填坑。。。
问题 K: 单纯质因数
题目描述
读五年级的楠楠刚学完了质数、合数、因数、质因数等概念。
他还知道了每个合数都可以写成几个质数相乘的形式，其中每个质数都是这个合数的因数，叫做这个合数的质因数．把一个合数用质因数相乘的形式表示出来，叫做分解质因数．
聪明爱动脑筋的楠楠突然对具有互不相同的质因数的合数产生了兴趣。例如：30=235，它有互不相同的质因数；70=257，它也有互不相同的质因数。若一个合数中所有的质因数互不相同，则把它称之为具有单纯质因数的合数。他想知道还有哪些数是单纯质因数的合数。
你现在要帮楠楠解决的问题是：已知N,依次输出N以内所有具有单纯质因数的合数。
输入
输入数据只一个整数N（10<=N<=100000）。
输出
依次输出N以内所有具有单纯质因数的合数。
样例输入
复制样例数据 12
样例输出
6 10
这题没来及看 待解决！
问题 L: 安装饮水机
题目描述
为倡导城市低碳生活，市文明办计划举办马拉松比赛，为确保比赛安全，沿途设置了一些观察点。每个观察点派一个观察员驻守。由于天气比较炎热，需要在沿途安装一些饮水机，使得观察员可以去取水喝。由于观察员每移动一个单位的路程，需要耗费一个单位的体力。而每个观察员的体力有限，只能在他体力能支持的范围内去取水喝，要不他就会渴死或累死。
聪明的楠楠也参与了这次比赛的筹备工作。他的任务是设计一个理想的安装饮水机方案，使得安装的饮水机最少，但又保证所有观察员都能取到水喝。
输入
输入数据有若干行。。
第一行，仅一个整数，表示有N(0<n<=1000)个观察点。
接下来有N行，每行两个整数S(0<S<=100000)和W(0<W<=50000)，其中S表示某个观察点到起点的路程，W表示该观察点中驻点观察员的体力。
输出
输出最少要安装几台饮水机。
样例输入
复制样例数据 4
6 3
12 2
1 5
14 5
样例输出
2
提示
他可以将饮水机安装在距离起点为6和12的位置上，这样所有的观察员都能喝到水。方案有多种，只需输出最少需要几台饮水机即可。
这题也没来及看啊 待填坑！
问题 M: 分木块
题目描述
小洪今天来到伐木场参观，刚好伐木场的工人遇到一个难题，他们希望小洪帮忙解决。难题是已经知道有n棵木头的长度，先将这n棵木头截成100厘米长度的木块，再将剩余木块截成10厘米长度的木块，最后将剩余木块截成1厘米长度的小木块，现在是想让你统计出这些木块最终能截成多少条100厘米、10厘米、1厘米的木块。
输入
第一行是一个整数n，表示有n棵木头需要加工 n<=50 。
第二行是n个整数，表示以厘米为单位的所有木头的长度（所有木头小于100000）。
输出
第一行：一个整数，代表截成100厘米长度木块的条数。
第二行：一个整数，代表截成10厘米长度木块的条数。
第三行：一个整数，代表截成1厘米长度木块的条数。
样例输入
复制样例数据 2
154 160
样例输出
2
11
4
这题直接分就行了，也算是一道基础编程题；大于100就减去100，计数器++ 10 的亦然
#include<bits/stdc++.h>
using namespace std;
int a[100];
int main() {
int n;
cin>>n;
for(int i=0;i<n;i++)
cin>>a[i];
int d=0;
int b=0;
int c=0;
for(int i=0;i<n;i++) {
while(a[i]>=100) {
a[i]-=100;
d++;
}
while(a[i]>=10) {
a[i]-=10;
b++;
}
c+=a[i];
}
cout<<d<<"\n"<<b<<"\n"<<c;
}
问题 N: 活动人数
题目描述
小洪的老师想用奖品来调动学生参加某项智力比拼活动的积极性，奖品有一个初始的吸引值L(1 <= L <= 50)。已知每一个学生都有一个抵抗诱惑的值ri(0 <= ri <=100)，只有奖品的吸引值大于或者等于学生的抵抗诱惑值时，这个学生才会积极参加这个项活动。
随着活动的开展，每当有一名学生积极参加这项活动时，会使这个奖品的吸引值增加k (1 <= k<= 20)，从而可能使得先前不够积极的同学抵挡不住诱惑从而参与进来。
现在小洪的班中共有n (1 <=n<= 1000) 位同学，小洪想请你帮忙统计出最终会积极参加这项活动的最大人数。
输入
第一行三个整数n、L、k，分别代表小洪班人数、奖品初始吸引值和每增一人参与活动时奖品吸引值的增加值。
第二行：n个整数，代表每个学生的抵抗诱惑的值。
输出
一个整数，代表最后有多少学生参加这项活动。
样例输入
复制样例数据 5 2 3
2 6 12 5 14
样例输出
3
提示
奖品的初始吸引值是2，那么只有第一位学生(2<=2)参加这项活动,因为有一位学生参加活动，那么奖品的吸引力就增加为：2+3=5，刚好第四位学生抵抗诱惑值为5，那么第四位同学也参加这项活动，奖品的吸引力变为：5+3=8,这样只有第二位学生的诱惑值6<8，那么第2位学生也参加活动，使奖品吸引力变为：8+3=11,最后再也没有学生的诱惑值小于等于11，这样就只有3位学生参加这项活动。
这题感觉是一道贪心题，先把输入进去的数排个序，因为诱惑值小的学生容易被吸引，所以把小的放前面，一直到不能再吸引的时候就不能继续吸引人了。
#include<bits/stdc++.h>
using namespace std;
int a[2000];
int main() {
int n,l,k;
cin>>n>>l>>k;
for(int i=0;i<n;i++)
cin>>a[i];
int sum=0;
sort(a,a+n);
for(int i=0;i<n;i++) {
if(a[i]<=l) {
sum++;
l+=k;
}
}
cout<<sum;
}