2020年团体程序设计天梯赛-模拟赛

L1-5 判断题

判断题的评判很简单，本题就要求你写个简单的程序帮助老师判题并统计学生们判断题的得分。

输入格式：

输入在第一行给出两个不超过 100 的正整数 N 和 M，分别是学生人数和判断题数量。第二行给出 M 个不超过 5 的正整数，是每道题的满分值。第三行给出每道题对应的正确答案，0 代表“非”，1 代表“是”。随后 N 行，每行给出一个学生的解答。数字间均以空格分隔。

输出格式：

按照输入的顺序输出每个学生的得分，每个分数占一行。

输入样例：

3 6
2 1 3 3 4 5
0 0 1 0 1 1
0 1 1 0 0 1
1 0 1 0 1 0
1 1 0 0 1 1

输出样例：

13
11
12

#include<bits/stdc++.h>
using namespace std;
const int MAX = 1 << 20;
int N,M,K;
string str;
map<int,int>score;
map<int,int>ans;
int main()
{cin >> N >> M;for(int i = 0;i < M;i++){cin >> K;score[i] = K;}for(int i = 0;i < M;i++){cin >> K;ans[i] = K;}while(N--){int sum = 0;for(int i = 0;i < M;i++){cin >> K;if(K == ans[i])sum += score[i];}cout<<sum<<endl;}return 0;
}

L1-6 检查密码 

本题要求你帮助某网站的用户注册模块写一个密码合法性检查的小功能。该网站要求用户设置的密码必须由不少于6个字符组成，并且只能有英文字母、数字和小数点 .，还必须既有字母也有数字。

输入格式：

输入第一行给出一个正整数 N（≤ 100），随后 N 行，每行给出一个用户设置的密码，为不超过 80 个字符的非空字符串，以回车结束。

注意： 题目保证不存在只有小数点的输入。

输出格式：

对每个用户的密码，在一行中输出系统反馈信息，分以下5种：

• 如果密码合法，输出Your password is wan mei.；
• 如果密码太短，不论合法与否，都输出Your password is tai duan le.；
• 如果密码长度合法，但存在不合法字符，则输出Your password is tai luan le.；
• 如果密码长度合法，但只有字母没有数字，则输出Your password needs shu zi.；
• 如果密码长度合法，但只有数字没有字母，则输出Your password needs zi mu.。

输入样例：

5
123s
zheshi.wodepw
1234.5678
WanMei23333
pass*word.6

输出样例：

Your password is tai duan le.
Your password needs shu zi.
Your password needs zi mu.
Your password is wan mei.
Your password is tai luan le.

#include<bits/stdc++.h>
using namespace std;
const int MAX = 1 << 20;
int N, M;
string str;
// 只能有英文字母、数字和小数点 .，还必须既有字母也有数字
int main()
{cin >> N;getchar();while (N--){getline(cin, str);//   cout << str << ":";if (str.size() < 6){cout << "Your password is tai duan le." << endl;continue;}bool isnum = 0, ischar = 0,is = 0;for (int i = 0; i < str.size(); i++){if (isdigit(str[i]))isnum = 1;else if (str[i] >= 'A' && str[i] <= 'z')ischar = 1;else if (str[i] == '.' );else{cout << "Your password is tai luan le." << endl;is = 1;break;}}if(is)continue;if (isnum && !ischar)cout << "Your password needs zi mu." << endl;else if (!isnum && ischar)cout << "Your password needs shu zi." << endl;else cout << "Your password is wan mei." << endl;}return 0;
}

L1-7 谷歌的招聘 

2004 年 7 月，谷歌在硅谷的 101 号公路边竖立了一块巨大的广告牌（如下图）用于招聘。内容超级简单，就是一个以 .com 结尾的网址，而前面的网址是一个 10 位素数，这个素数是自然常数 e 中最早出现的 10 位连续数字。能找出这个素数的人，就可以通过访问谷歌的这个网站进入招聘流程的下一步。

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

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

输入格式：

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

输出格式：

在一行中输出 N 中最早出现的 K 位连续数字所组

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int L, K;
string s;inline bool Prime(long long x)
{if (x == 1)return 0;if (x == 2 || x == 3)return 1;if (x % 6 != 1 && x % 6 != 5)return 0;for (long long i = 5; i * i <= x; i += 6)if (x % i == 0 || x % (i + 2) == 0)return 0;return 1;
}int main()
{int i;cin >> L >> K;getchar();getline(cin, s);for (i = 0; i <= L - K; i++){string str = s.substr(i, K);//截取长度为k的字符串ll temp = stoi(str);//转化为一个整数if (Prime(temp)){cout << str;return 0;}}cout << "404";return 0;
}

成的素数。如果这样的素数不存在，则输出 404。注意，原始数字中的前导零也计算在位数之内。例如在 200236 中找 4 位素数，0023 算是解；但第一位 2 不能被当成 0002 输出，因为在原始数字中不存在这个 2 的前导零。

输入样例 1：

20 5
23654987725541023819

输出样例 1：

49877

输入样例 2：

10 3
2468001680

输出样例 2：

404

L2-1 出栈序列的合法性 

给定一个最大容量为 M 的堆栈，将 N 个数字按 1, 2, 3, ..., N 的顺序入栈，允许按任何顺序出栈，则哪些数字序列是不可能得到的？例如给定 M=5、N=7，则我们有可能得到{ 1, 2, 3, 4, 5, 6, 7 }，但不可能得到{ 3, 2, 1, 7, 5, 6, 4 }。

输入格式：

输入第一行给出 3 个不超过 1000 的正整数：M（堆栈最大容量）、N（入栈元素个数）、K（待检查的出栈序列个数）。最后 K 行，每行给出 N 个数字的出栈序列。所有同行数字以空格间隔。

输出格式：

对每一行出栈序列，如果其的确是有可能得到的合法序列，就在一行中输出YES，否则输出NO。

输入样例：

5 7 5
1 2 3 4 5 6 7
3 2 1 7 5 6 4
7 6 5 4 3 2 1
5 6 4 3 7 2 1
1 7 6 5 4 3 2

输出样例：

YES
NO
NO
YES
NO

#include<bits/stdc++.h>
using namespace std;
const int MAX = 1 << 20;
int N, M, K, num;
string str;
int main()
{//入队cin >> M >> N >> K;//：M（堆栈最大容量）、N（入栈元素个数）、K（待检查的出栈序while (K--){stack<int>s;queue<int>Q;for (int i = 0; i < N; i++){cin >> num;Q.push(num);}num = 1;while (!Q.empty()){s.push(num);num++;if (s.size() > M)break;while (!Q.empty() && !s.empty() && s.top() == Q.front()){s.pop();Q.pop();}}if (Q.empty())cout << "YES" << endl;else cout << "NO" << endl;}return 0;
}

L2-3 二叉搜索树的2层结点统计 

#include<bits/stdc++.h>
using namespace std;int N, M, maxdeap, num;
class Tree
{
public:int val;Tree* R;Tree* L;Tree(int n){val = n;L = R = NULL;}
};Tree* creat(Tree* root, int val, int deap)
{if (deap > maxdeap)maxdeap = deap;if (!root)root = new Tree(val);else if (val <= root->val)root->L = creat(root->L, val, deap + 1);//左子树上所有结点的值均小于或等于它的根结点的值else root->R = creat(root->R, val, deap + 1);return root;
}inline void preorder(Tree* T, int deap)//先序遍历 
{if (T == NULL) return;if (deap >= maxdeap - 1) num++;//如果已经在最下面两层，就开始对结点计数 preorder(T->L, deap + 1);preorder(T->R, deap + 1);
}int main()
{cin >> N;Tree* T = NULL;while (N--){cin >> M;T = creat(T, M, 1);}preorder(T, 1);cout << num;return 0;
}