备战蓝桥杯 Day4

目录

注意：递推开long long

1140：验证子串

1131：基因相关性

1176：谁考了第k名

1177：奇数单增序列

1180：分数线划定

1184：明明的随机数

1185：单词排序

1186：出现次数超过一半的数

1187：统计字符数

1310：【例2.2】车厢重组

1188：菲波那契数列(2)

递推版

递归版

1189：Pell数列

递推版

1190：上台阶

递推版

---

注意：递推开long long

1140：验证子串 【题目描述】 输入两个字符串，验证其中一个串是否为另一个串的子串。 【输入】 输入两个字符串， 每个字符串占一行，长度不超过200且不含空格。 【输出】 若第一个串s1是第二个串s2的子串，则输出(s1) is substring of (s2) 否则，若第二个串s2是第一个串s1的子串，输出(s2) is substring of (s1) 否则，输出 No substring。 【输入样例】 abc dddncabca 【输出样例】 abc is substring of dddncabca

#include<iostream>
#include<string>
#include<map>
#include<algorithm>
using namespace std;
const int N = 1e2 + 10;
int a[N];
int cnt;
int main()
{string s1, s2;cin >> s1 >> s2;if (s1.length() > s2.length()){if (s1.find(s2) != -1)cout << s2 << " is substring of " << s1;elsecout << "No substring";}elseif (s2.find(s1) != -1)cout << s1 << " is substring of " << s2;elsecout << "No substring";
}

1131：基因相关性

【题目描述】

为了获知基因序列在功能和结构上的相似性，经常需要将几条不同序列的DNA进行比对，以判断该比对的DNA是否具有相关性。

现比对两条长度相同的DNA序列。定义两条DNA序列相同位置的碱基为一个碱基对，如果一个碱基对中的两个碱基相同的话，则称为相同碱基对。接着计算相同碱基对占总碱基对数量的比例，如果该比例大于等于给定阈值时则判定该两条DNA序列是相关的，否则不相关。

【输入】

有三行，第一行是用来判定出两条DNA序列是否相关的阈值，随后2行是两条DNA序列(长度不大于500)。

【输出】

若两条DNA序列相关，则输出“yes”，否则输出“no”。

【输入样例】

0.85
ATCGCCGTAAGTAACGGTTTTAAATAGGCC
ATCGCCGGAAGTAACGGTCTTAAATAGGCC

【输出样例】

yes

#include<iostream>
#include<string>
#include<map>
#include<algorithm>
using namespace std;
const int N = 1e2 + 10;
int a[N];
double cnt,ans;
int main()
{double k; cin >> k;string s1, s2;cin >> s1 >> s2;for(int i=1;i<s1.size();i++){if (s1[i] == s2[i])cnt++;}ans =cnt/ s1.length();if (ans >= k)cout << "yes";elsecout << "no";
}

1176：谁考了第k名

【题目描述】

在一次考试中，每个学生的成绩都不相同，现知道了每个学生的学号和成绩，求考第k名学生的学号和成绩。

【输入】

第一行有两个整数，分别是学生的人数n（1≤n≤100）n（1≤n≤100），和求第k名学生的k（1≤k≤n）k（1≤k≤n）。

其后有nn行数据，每行包括一个学号（整数）和一个成绩（浮点数），中间用一个空格分隔。

【输出】

输出第kk名学生的学号和成绩，中间用空格分隔。（注：请用%g%g输出成绩）

【输入样例】

5 3
90788001 67.8
90788002 90.3
90788003 61
90788004 68.4
90788005 73.9

【输出样例】

90788004 68.4

#include<iostream>
#include<string>
#include<map>
#include<algorithm>
using namespace std;
const int N = 1e2 + 10;
struct stu { int id; double score; }s[N];
bool cmp(stu a, stu b) { return a.score > b.score; }
int main()
{int n, k; cin >> n >> k;for (int i = 1; i <= n; i++)cin >> s[i].id >> s[i].score;sort(s + 1, s + 1 + n, cmp);cout << s[k].id << " " << s[k].score;return 0;
}

1177：奇数单增序列

【题目描述】

给定一个长度为N（不大于500）的正整数序列，请将其中的所有奇数取出，并按升序输出。

【输入】

第1行为 N；

第2行为 N 个正整数，其间用空格间隔。

【输出】

增序输出的奇数序列，数据之间以逗号间隔。数据保证至少有一个奇数。

【输入样例】

10
1 3 2 6 5 4 9 8 7 10

【输出样例】

1,3,5,7,9

输入数字判断奇偶，如果是偶数就存入数组，最后利用sort函数排序

#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<algorithm>
using namespace std;
const int N = 1e2 + 10;
int main()
{vector<int>a;int n; cin >> n ;for (int i = 1; i <= n; i++){int x; cin >> x;if (x % 2 == 1)a.push_back(x);}sort(a.begin(), a .end());for (int i = 0; i < a.size() - 1; i++)cout << a[i] << ",";cout << a[a.size()-1];return 0;
}

1180：分数线划定

【题目描述】

世博会志愿者的选拔工作正在 A 市如火如荼的进行。为了选拔最合适的人才，A市对所有报名的选手进行了笔试，笔试分数达到面试分数线的选手方可进入面试。面试分数线根据计划录取人数的150%150%划定，即如果计划录取mm名志愿者，则面试分数线为排名第m×150%m×150%（向下取整）名的选手的分数，而最终进入面试的选手为笔试成绩不低于面试分数线的所有选手。

现在就请你编写程序划定面试分数线，并输出所有进入面试的选手的报名号和笔试成绩。

【输入】

第一行，两个整数n，m（5≤n≤5000，3≤m≤n）n，m（5≤n≤5000，3≤m≤n），中间用一个空格隔开，其中nn 表示报名参加笔试的选手总数，mm 表示计划录取的志愿者人数。输入数据保证m×150%m×150%向下取整后小于等于nn。

第二行到第 n+1n+1 行，每行包括两个整数，中间用一个空格隔开，分别是选手的报名号k（1000≤k≤9999）k（1000≤k≤9999）和该选手的笔试成绩s（1≤s≤100）s（1≤s≤100）。数据保证选手的报名号各不相同。

【输出】

第一行，有两个整数，用一个空格隔开，第一个整数表示面试分数线；第二个整数为进入面试的选手的实际人数。

从第二行开始，每行包含两个整数，中间用一个空格隔开，分别表示进入面试的选手的报名号和笔试成绩，按照笔试成绩从高到低输出，如果成绩相同，则按报名号由小到大的顺序输出。

【输入样例】

6 3
1000 90
3239 88
2390 95
7231 84
1005 95
1001 88

【输出样例】

88 5
1005 95
2390 95
1000 90
1001 88
3239 88

【提示】

样例说明：m×150%=3×150%=4.5m×150%=3×150%=4.5，向下取整后为44。保证44个人进入面试的分数线为8888，但因为8888有重分，所以所有成绩大于等于8888的选手都可以进入面试，故最终有55个人进入面试。

#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<algorithm>
using namespace std;
const int N = 51e3 + 10;
struct p { int id; int score; }a[N];
int cmp(p a, p b)
{if (a.score == b.score)return a.id < b.id;return a.score > b.score;
}
int main()
{int n, m; cin >> n >> m;for (int i = 1; i <= n; i++){cin >> a[i].id >> a[i].score;}sort(a + 1, a + 1 + n, cmp);int line = m * 1.5;int sum = 0;for (int i = 1; i <= n; i++){if (a[i].score >= a[line].score)sum++;}cout << a[line].score <<" " << sum << endl;;for (int i = 1; i <= sum; i++){cout << a[i].id << " " << a[i].score << endl;}return 0;
}

1184：明明的随机数

【题目描述】

明明想在学校中请一些同学一起做一项问卷调查，为了实验的客观性，他先用计算机生成了N个1到1000之间的随机整数（N≤100），对于其中重复的数字，只保留一个，把其余相同的数去掉，不同的数对应着不同的学生的学号。然后再把这些数从小到大排序，按照排好的顺序去找同学做调查。请你协助明明完成“去重”与“排序”的工作。

【输入】

有2行，第1行为1个正整数，表示所生成的随机数的个数：N；

第2行有N个用空格隔开的正整数，为所产生的随机数。

【输出】

也是2行，第1行为1个正整数M，表示不相同的随机数的个数。第2行为M个用空格隔开的正整数，为从小到大排好序的不相同的随机数。

【输入样例】

10
20 40 32 67 40 20 89 300 400 15

【输出样例】

8
15 20 32 40 67 89 300 400

#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<algorithm>
using namespace std;
const int N = 51e3 + 10;
int main()
{int n; cin >> n;set<int>s;for (int i = 1; i <= n; i++){int x;cin >> x;s.insert(x);}cout << s.size() << endl;for (auto c : s)cout << c << " ";return 0;
}

1185：单词排序

【题目描述】

输入一行单词序列，相邻单词之间由1个或多个空格间隔，请按照字典序输出这些单词，要求重复的单词只输出一次。（区分大小写）

【输入】

一行单词序列，最少1个单词，最多100个单词，每个单词长度不超过50，单词之间用至少1个空格间隔。数据不含除字母、空格外的其他字符。

【输出】

按字典序输出这些单词，重复的单词只输出一次。

【输入样例】

She  wants  to go to Peking University to study  Chinese

【输出样例】

Chinese
Peking
She
University
go
study
to
wants

#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<algorithm>
using namespace std;
const int N = 51e3 + 10;
int main()
{string s;map<string,int>mp;while (cin >> s){mp.insert({ s,1 });}for (auto c : mp)cout << c.first << endl;return 0;
}

1186：出现次数超过一半的数

【题目描述】

给出一个含有n（0 < n <= 1000）个整数的数组，请找出其中出现次数超过一半的数。数组中的数大于-50且小于50。

【输入】

第一行包含一个整数n，表示数组大小；

第二行包含n个整数，分别是数组中的每个元素，相邻两个元素之间用单个空格隔开。

【输出】

如果存在这样的数，输出这个数；否则输出no。

【输入样例】

3
1 2 2

【输出样例】

2

#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<algorithm>
using namespace std;
const int N = 1e3 + 10;
int a[N], cnt[N];
int main()
{int n; cin >> n; int x;for (int i = 1; i <= n; i++){cin >> x;cnt[x+50]++;}for (int i = 1; i <= 100; i++){if (cnt[i] > n / 2){cout << i-50;return 0;}	}cout << "no";return 0;
}

1187：统计字符数

【题目描述】

给定一个由a-z这26个字符组成的字符串，统计其中哪个字符出现的次数最多。

【输入】

输入包含一行，一个字符串，长度不超过1000。

【输出】

输出一行，包括出现次数最多的字符和该字符出现的次数，中间以一个空格分开。如果有多个字符出现的次数相同且最多，那么输出ascii码最小的那一个字符。

【输入样例】

abbccc

【输出样例】

c 3

#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<algorithm>
using namespace std;
const int N = 1e3 + 10;
char cnt[N];
int main()
{string s; cin >> s;for (int i = 0; i < s.size(); i++){cnt[s[i]]++;}int max = 0; char maxid = 'a';for (char i = 'a'; i <= 'z'; i++){if (cnt[i] > max || cnt[i] == max && i < maxid){max = cnt[i];maxid = i;}}cout <<maxid<<" " << max;return 0;
}

1310：【例2.2】车厢重组

【题目描述】

在一个旧式的火车站旁边有一座桥，其桥面可以绕河中心的桥墩水平旋转。一个车站的职工发现桥的长度最多能容纳两节车厢，如果将桥旋转180度，则可以把相邻两节车厢的位置交换，用这种方法可以重新排列车厢的顺序。于是他就负责用这座桥将进站的车厢按车厢号从小到大排列。他退休后，火车站决定将这一工作自动化，其中一项重要的工作是编一个程序，输入初始的车厢顺序，计算最少用多少步就能将车厢排序。

【输入】

有两行数据，第一行是车厢总数N（不大于10000），第二行是N个不同的数表示初始的车厢顺序。

【输出】

一个数据，是最少的旋转次数。

【输入样例】

4
4 3 2 1

【输出样例】

6

#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<algorithm>
using namespace std;
const int N = 1e3 + 10;
int a[N];
int cnt;
int main()
{int n;cin >> n;for (int i = 1; i <= n; i++){cin >> a[i];}//外层遍历n-1次for (int j = 1; j <= n-1; j++){for (int i = 1; i <= n-j; i++){if (a[i] > a[i + 1]){swap(a[i + 1], a[i]);cnt++;}}}	cout << cnt;return 0;
}

1188：菲波那契数列(2)

【题目描述】

菲波那契数列是指这样的数列: 数列的第一个和第二个数都为11，接下来每个数都等于前面22个数之和。

给出一个正整数aa，要求菲波那契数列中第aa个数对10001000取模的结果是多少。

【输入】

第11行是测试数据的组数nn，后面跟着nn行输入。每组测试数据占1行，包括一个正整数a(1≤a≤1000000)a(1≤a≤1000000)。

【输出】

nn行，每行输出对应一个输入。输出应是一个正整数，为菲波那契数列中第aa个数对10001000取模得到的结果。

【输入样例】

4
5
2
19
1

【输出样例】

5
1
181
1

递推版

#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<algorithm>
using namespace std;
const int N = 1e6 + 10;
int a[N];
int main()
{int n; cin >> n;a[1] = a[2] = 1;int m = 1000;for (int i = 3; i <= 1e6; i++)a[i]=(a[i-1]%m+a[i-2]%m)%m;for (int i = 1; i <= n; i++){int x; cin >> x;cout << a[x] << endl;}return 0;
}

递归版

#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<algorithm>
using namespace std;
const int N = 1e6 + 10;
int a[N];	int m = 1000;
int fbnq(int x)
{if (x <= 2) return 1;return  (fbnq(x - 1) % m + fbnq(x - 2) % m) % m;
}
int main()
{int n; cin >> n;for (int i = 1; i <= n; i++){int x; cin >> x;cout << fbnq(x) << endl;;}return 0;
}

1189：Pell数列

【题目描述】

Pell数列a1,a2,a3,...a1,a2,a3,...的定义是这样的，a1=1,a2=2,...,an=2an−1+an−2(n>2)a1=1,a2=2,...,an=2an−1+an−2(n>2)。

给出一个正整数k，要求Pell数列的第k项模上32767是多少。

【输入】

第1行是测试数据的组数n，后面跟着n行输入。每组测试数据占1行，包括一个正整数k (1≤k<1000000)。

【输出】

n行，每行输出对应一个输入。输出应是一个非负整数。

【输入样例】

2
1
8

【输出样例】

1
408

递推版

#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<algorithm>
using namespace std;
const int N = 1e6 + 10;
int a[N];	int m =32767;
int main()
{int n; cin >> n;a[1] = 1; a[2] = 2;for (int i = 3; i <= 1e6; i++){a[i] =( 2 * a[i - 1]%m + a[i - 2]%m)%m;}for (int i = 1; i <= n; i++){int x; cin >> x;cout << a[x] << endl;}return 0;
}

递归版

#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<algorithm>
using namespace std;
const int N = 1e6 + 10;
int a[N];	int m =32767;
int pell(int x)
{if (x <= 2)return x;return  (2 * pell(x - 1) % m + pell(x - 2) % m) % m;
}
int main()
{int n; cin >> n;a[1] = 1; a[2] = 2;for (int i = 1; i <= n; i++){int x; cin >> x;cout <<pell(x) << endl;}return 0;
}

1190：上台阶

【题目描述】

楼梯有nn(0<n<710<n<71)阶台阶,上楼时可以一步上11阶,也可以一步上22阶,也可以一步上33阶，编程计算共有多少种不同的走法。

【输入】

输入的每一行包括一组测试数据，即为台阶数nn。最后一行为00，表示测试结束。

【输出】

每一行输出对应一行输入的结果，即为走法的数目。

【输入样例】

1
2
3
4
0

【输出样例】

1
2
4
7

 搜索版

#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<algorithm>
using namespace std;
const int N = 1e2 + 10;
int cnt;	
int x;//当前所站在的台阶数
int d[] = { 1,2,3 };
void dfs(int stairs)
{if (stairs < 0)return;if (stairs == 0){cnt++;return;}for (int i = 0; i < 3; i++){stairs -= d[i];dfs(stairs);stairs += d[i];}
}
int main()
{while (cin >> x && x){cnt = 0;dfs(x);cout << cnt << endl;;}return 0;
}

递推版

#include<iostream>
using namespace std;
#define int long long
const int N = 1e2 + 10;
int cnt;	
int a[N];
int x;//当要走到的台阶
signed main()
{a[1] = 1, a[2] = 2, a[3] = 4;for (int i = 4; i <= 71; i++){a[i] = a[i - 3] + a[i - 2] + a[i - 1];}while (cin >> x && x!=0){cout << a[x] << endl;}return 0;
}