A: 括号匹配
题目描述
输入一个只包含“(”和“)”两种字符的字符串，判断它是否是一个合法的括号匹配字符串。如果左右括号成对出现并且嵌套正确，那么认为它们是合法的。
例如：“(())()()”是一个合法的括号匹配字符串；而“()(()”不是一个合法的括号匹配字符串。
如果合法，程序将输出“True”，否则输出“False”。输入
多组输入。
第1行输入一个正整数T，表示输入样例数，T不超过100。
从第2行开始每行输入一个长度不超过1000，且只包含“(”和“)”的字符串。输出
输出所输入的字符串是否是合法的括号匹配字符串，如果合法输出“True”，否则输出“False”。
样例输入 Copy
2 (())()() ()(()样例输出 Copy
True False
#include <iostream>
#include <string>
using namespace std;
bool fun(string s)
{int z = 0;for (int i = 0; i < s.size(); i++)if (s[i] == '(')z++;else{if (z == 0)return false;z--;}return z == 0;
}
int main()
{int t;cin >> t;while (t--){string s;cin >> s;if (fun(s))cout << "True" << endl;elsecout << "False" << endl;}return 0;
}B: 中午吃什么
题目描述
“中午吃什么？”这是一个千古难题，小b今天中午打算点“饱了么”外卖。
正好最近“饱了么”推出了免单活动（免单：即订单金额退还，某一笔订单免单了代表这一笔订单不需要花钱）。
有 n (1≤n ≤2000) 个顾客点了外卖，第i个人点外卖的时间为 ai (0 ≤ ai ≤ 23) 小时，bi (0 ≤ bi ≤ 59) 分，花了 ci (1 ≤ c ≤ 5000) 元，以上数据均为整数。
花钱最多的 m (0<m≤n) 个人可以获得免单。如果有多人花钱一样多，则点单较早的顾客可以优先获得免单资格。
请问，哪些顾客可以被免单呢?输入
单组输入，第一行两个正整数n，m，表示外卖订单数和免单数。
接下来n行，每行三个正整数 ai，bi，ci，如题所示。输出
共输出 m 行，每行 3 个数，分别代表每名获得免单的顾客的下单时间（时、分），以及这个顾客的下单金额。使用空格隔开。
消费金额更高的顾客将会优先输出，如果下单金额相同，则下单时间早的顾客优先输出。样例输入 Copy
3 2 5 5 200 2 4 200 2 3 200样例输出 Copy
2 3 200 2 4 200
#include <iostream>
#include <algorithm>
using namespace std;
struct S
{int h;int mi;int j;
} a[2005];
bool cmp(S x, S y)
{if (x.j != y.j)return x.j > y.j;if (x.h != y.h)return x.h < y.h;elsereturn x.mi < y.mi;
}
int main()
{int n, m;cin >> n >> m;for (int i = 0; i < n; i++)cin >> a[i].h >> a[i].mi >> a[i].j;sort(a, a + n, cmp);for (int i = 0; i < m; i++)cout << a[i].h << ' ' << a[i].mi << ' ' << a[i].j << endl;return 0;
}C: 扑克牌接龙游戏
题目描述
小明最近喜欢上了一种非常简单的扑克牌接龙游戏。
游戏的玩法是这样的：
将扑克牌洗牌后平均分为两堆，每人轮流出一张牌进行接龙。如果某个人出的牌的大小和接龙牌堆中一张已有牌的大小相同（不考虑花色），那么他可以将这两张牌以及中间所有的牌全部收走并据为己有。例如：如果在接龙的牌堆中有一个3，你再出一个3，那么这两个3以及它们中间的牌都归你所有。
两个人依次出牌，最后比谁收到的牌最多即可获胜。
我们把这个问题稍作简化，如果是一个人在玩这个游戏。现在给你一串数字和字母表示扑克牌的次序，请问最多的一次可以收走多少张牌。输入
单组输入，输入占两行。
第1行是牌的总数n。(n<=1e5)
第2行输入n个数字或者字符（对应2、3、4、5、6、7、8、9、10和A、J、Q、K），两两之间用空格隔开。输出
输出一个整数，即最多一次可以收走的牌数。
样例输入 Copy
11 A 2 3 3 4 3 2 2 3 4 A样例输出 Copy
5提示
样例解释：当出第4张“3”时，可以收走第3张“3”和第4张“3”，共收走2张牌；当出第7张“2”时，可以收走第2张“2”以及第5张到第7张牌，即一共收走了“2,4,3,2”，共收走4张牌；当出第11张“A”时，可以收走第1张“A”和第8张到第11张牌，即一共收走了“A,2,3,4,A”，共收走5张牌。因此最多的一次收走5张牌。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 5;
void solve(){int n, m = 0;vector<string> s;cin >> n;while (n--){string a;cin >> a;if (s.size()){if (find(s.begin(), s.end(), a) != s.end()){int k = 1;while (find(s.begin(), s.end(), a) != s.end()){s.pop_back();k++;}m = max(m, k);}elses.push_back(a);}elses.push_back(a);}cout << m << "\n";
}
int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);solve();return 0;
}D: X星人的矩阵
题目描述
X星人设计了一个全部由正整数组成的矩阵，他希望你能够编写一个程序帮他找出这个矩阵的最大值，同时还需要统计该最大值出现的次数。
例如输入如下矩阵：
2 2 2
2 2 2
2 2 2
将输出2和9，表示该矩阵的最大值为2，一共出现了9次。输入
单组输入。
第1行输入两个正整数M和N，分别表示矩阵的行数和列数，1<=M<=1000，1<=N<=1000，M和N用英文空格隔开。
接下来M行每行输入N个不超过10000的正整数，两两之间用英文空格隔开。输出
输出两个正整数，第1个正整数对应该矩阵的最大值，第2个正整数对应该最大值出现的次数，两者之间用英文空格隔开。
样例输入 Copy
3 3 1 2 3 4 5 6 7 8 9样例输出 Copy
9 1
#include<iostream>
using namespace std;
int a[1024][1024];
int main()
{int m,n,s=0,i,j,k=0;scanf("%d%d",&m,&n);for(i=0;i<m;i++)for(j=0;j<n;j++){cin>>a[i][j];if(a[i][j]>k)k=a[i][j];}for(i=0;i<m;i++)for(j=0;j<n;j++)if(a[i][j]==k)s++;cout<<k<<' '<<s<<endl;return 0;
}E: X星人的数列
题目描述
爱冒险的X星人在一艘海底沉船上发现了一串神秘数列，这个数列的前8项如下：
3, 5, 10, 19, 38, 75, 150, 299
X星人对这串数列产生了浓厚的兴趣，他希望你能够帮他发现这个神秘数列中所蕴含的规律，并编写一个程序输出该数列前N项的和。
当输入一个正整数N时，请输出这个神秘数列前N项的和。输入
单组输入，每组输入一个正整数N（N<=20）。
输出
输出一个正整数，对应这个神秘数列前N项的和。
样例输入 Copy
6样例输出 Copy
150
#include<stdio.h>
int main()
{int s=0,n,i,a[20];scanf("%d",&n);a[0]=3;for(i=1;i<n;i++){if(i%2!=0)a[i]=2*a[i-1]-1;elsea[i]=2*a[i-1];}for(i=0;i<n;i++)s+=a[i];printf("%d\n",s);return 0;
}F: X星人的纸牌
题目描述
X星人最近在玩一个纸牌游戏，该游戏的规则如下：
(1) 一共有N张纸牌，每张纸牌上都写有一个大于等于1且小于等于100的正整数，这N张纸牌从左往右一字排开。
(2) X星人先取出一张纸牌，然后在其右边再取出一张纸牌，不要求两张纸牌连续，但是下一张纸牌上的数字要小于上一张纸牌，依次取出若干张纸牌，即完成一轮操作。
(3) 对剩下的纸牌按照上述规则进行第二轮操作。
(4) 通过若干轮操作后所有的纸牌将全部取出。
现在需要你编写一个程序计算X星人最少需要进行多少轮操作可以将所有纸牌全部取出。输入
单组输入。
第1行输入一个正整数N表示纸牌的数量，N<=1000。
第2行输入N个正整数，表示N张纸牌上对应的数字，两两之间用英文的空格隔开。输出
输出将所有纸牌全部取出所需要的最少操作轮数。
样例输入 Copy
8 45 12 34 90 45 56 8 14样例输出 Copy
4
#include <iostream>
using namespace std;
int a[1005];
int main()
{int n;cin >> n;for (int i = 0; i < n; i++)cin >> a[i];int s = 0;int sum=0;while (1){int t = a[0];for (int i = 1; i < n; i++){if (a[i] < t)t = a[i];else{a[s] = a[i];s++;}}sum++;if (s == 0)break;else{n = s;s = 0;}}cout<<sum<<endl;return 0;
}G: X星人的魅力
题目描述
X星MM是个很有魅力的人，但是她觉得魅力多多益善。
一天，幸运的她获得了一个魅力包，里面有N件可以提升魅力的饰品，每件饰品上都标有该饰品可以帮助X星MM增加的魅力值。
遗憾的是该魅力包有一个机关，只允许X星MM从中取M件饰品（M<N），取完M件之后魅力包就无法再打开了。
现在X星MM希望你能够帮她计算出她能够获得的最大魅力值。输入
单组输入。
每组输入两行，第1行输入两个正整数N和M，分别表示饰品的总数量和可以取出的饰品数量。(1<=M<N<=1000)
第2行输入N个正整数，分别表示N个饰品的魅力值，两两之间用英文空格隔开。每个饰品的魅力值均为不超过100的正整数。输出
输出一个正整数表示X星MM可以获得的最大魅力值。
样例输入 Copy
8 3 3 4 8 3 5 9 8 1样例输出 Copy
25
#include<stdio.h>
int main()
{int i,j,t,a[1000],m,n,s=0;scanf("%d%d",&m,&n);for(i=0;i<m;i++)scanf("%d",&a[i]);for(j=0;j<m-1;j++)for(i=0;i<m-1;i++)if(a[i]<a[i+1]){ t=a[i];a[i]=a[i+1];a[i+1]=t;}for(i=0;i<n;i++)s+=a[i];printf("%d\n",s);return 0;
}H: X星人的集会
题目描述
X星人每天集会时，热衷于以一个特定的顺序站队，将X星人编号为1∼N。
最初，X星人从左到右按照a1,a2,…,aN的顺序排列。最终，需要变成从左到右按照b1,b2,…,bN的顺序排列。
所以，需要对X星人队伍进行一系列的调整。
每次只能让一个X星人向左移动任意位置。
问，至少需要多少次操作，才能变成特定顺序的队伍。输入
第一行包括一个正整数n(1≤n≤1e5)
第二行包括a1,a2...an，数组an为1∼N的排列
第三行包括b1,b2...bn，数组bn为1∼N的排列输出
输出一个整数，表示所需的最少操作次数
样例输入 Copy
5 5 1 3 2 4 4 5 2 1 3样例输出 Copy
2
#pragma GCC optimize(2)
#include <iostream>
#include <string>
#include <cmath>
#include <set>
#include <map>
#include <algorithm>
#include <cstring>
#include <vector>
#include <stack>
#include <queue>
#include <unordered_set>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
const int N = 1e5+5;
const int M = 1e9+7;
const int inf = 0x3fffffff;
const int P = 13331;
void solve(){int n;cin>>n;vector<int> a(n+1),b(n+1);a[0]=0;b[0]=0;vector<bool> c(n+1,false);for(int i=1;i<=n;i++){cin>>a[i];}for(int i=1;i<=n;i++){cin>>b[i];}int i=1,j=1,s=0;while(j<=n&&i<=n){while(c[a[i]]){i++;}if(a[i]==b[j]){i++;j++;}else{s++;c[b[j]]=true;j++;}}cout<<s<<"\n";
}
int main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);//int t;cin>>t;while(t--)solve();return 0;
}I: Morse Code
题目描述
Morse code, also known as Morse code, is a kind of on-off signal code, which expresses different English letters, numbers and punctuation symbols through different order. It was invented in 1837 and is an early form of digital communication. Different from modern digital communication, Morse code consists of two basic signals: short point signal "•" and reading "drop"; Keep the long signal "-" for a certain time and read "Da".
In order to increase the difficulty of decoding, the communication group decided that there must be more than one short message number "•" between every two long signals "-" in Morse code of any length, otherwise it will be regarded as invalid code. For example, the number of schemes of an effective Morse code with a length of 3 is 5, which are respectively: - • -, - • •, • - •, • • -, • • •.
Here is the length of Morse code. Do you know the number of effective Morse code schemes?
输入
The input has multiple cases (no more than 100) of test data.
Each test case occupies one line, which is a positive integer N（1 ≤ N ≤ 1000000） represents the length of the Morse code given to you.
The end of input will be represented by a line of test case where A equal to 0. This test case should not be processed.
输出
Each test case outputs a line, which is an integer, that is, the modular result of 2021 by the number of schemes of effective Morse code.
样例输入 Copy
2 3 0样例输出 Copy
3
5
#include <iostream>
using namespace std;
int a[1000005];
int main()
{int n;while (cin >> n){if (n == 0)break;a[1] = 2;a[2] = 3;a[3] = 5;for (int i = 4; i <= n; i++){a[i] = a[i - 1] + a[i - 2];a[i] %= 2021;}cout << a[n] << endl;}return 0;
}J: Shennong tastes all kinds of herbs
题目描述
Shennong asked Chisongzi for advice on the way of longevity. Chisongzi taught Shennong how to choose fairy grass and prolong life. Chisongzi took Shennong to Shennongjia and told him: "there are fairy grasses on the mountain. It takes some time to pick each grass, and each grass also has its own use value. There are also three rare grasses on the mountain, which are used independently and have strange poison. However, any two rare grasses used at the same time can be equivalent to a fairy grass, and its use value is the product of the value of two rare grasses, but each rare grass can not be reused. I will give you a period of time. During this period, you should pick some grasses as much as possible to maximize the total use value of the grasses.
Shennong acted immediately, tasted all kinds of grass and fulfilled his mission. Do you know how Shennong accomplished this task?
输入
The input has multiple cases (no more than 100) of test data.
The first line of each test cases is two positive integers T（1 ≤ T ≤ 1000） and M（1 ≤ M ≤ 100）, representing the time used to collect grass and the number of fairy grass on Shennongjia. Next, there are M lines. Each line contains two positive integers t and v (1 ≤ t, v ≤ 100), representing the time of picking the fairy grass and the value of the fairy grass respectively. The last three lines are the picking time a (1 ≤ a ≤ 100) and use value b (- 100 ≤ b < 0) of three rare grasses.
The end of input will be represented by a line of test case where T and M are equal to 0. This test case should not be processed.
输出
Each test case outputs a line, which is an integer, indicating the maximum total use value of fairy grass that can be collected in T time.
样例输入 Copy
70 3 71 100 68 3 1 2 1 -2 1 -3 1 -4 0 0样例输出 Copy
15
#pragma GCC optimize(2)
#include <iostream>
#include <string>
#include <cmath>
#include <set>
#include <map>
#include <algorithm>
#include <cstring>
#include <vector>
#include <stack>
#include <queue>
#include <unordered_set>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
const int N = 1e5+5;
//const int M = 1e9+7;
const int inf = 0x3fffffff;
const int P = 13331;
int a[3][2];
void solve(){int T,M;while(cin>>T>>M&&(T||M)){vector<int> t(M+1),v(M+1);t[0]=0;v[0]=0;for(int i=1;i<=M;i++){cin>>t[i]>>v[i];}for(int i=0;i<3;i++){cin>>a[i][0]>>a[i][1];}vector<vector<int>> dp(M+1,vector<int>(T+1,0));for(int i=1;i<=M;i++){ for(int j=1;j<=T;j++){ if(t[i]<=j){dp[i][j]=max(dp[i-1][j],dp[i-1][j-t[i]]+v[i]);}else{dp[i][j]=dp[i-1][j];}}}int m=dp[M][T];if((T-a[0][0]-a[1][0])>=0){m=max(dp[M][T],(dp[M][T-a[0][0]-a[1][0]]+a[0][1]*a[1][1]));}if((T-a[0][0]-a[2][0])>=0){m=max(m,(dp[M][T-a[0][0]-a[2][0]]+a[0][1]*a[2][1]));}if((T-a[2][0]-a[1][0])>=0){m=max(m,(dp[M][T-a[1][0]-a[2][0]]+a[1][1]*a[2][1]));}cout<<m<<"\n";}
}
int main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);//int t;cin>>t;while(t--)solve();return 0;
}K: 数字游戏
题目描述
Kimi和Sunny在玩一个数字游戏。游戏规则如下：
(1) 每个人各随机抽取n张写有1-100中某个正整数的卡片，假定卡片的数量不限，随机抽取的数字中可能会有重复数字。
(2) 每一轮游戏双方各亮出一张卡片，卡片上数字大者加1分，数字小者不扣分，相等则都不加分。
(3) n轮游戏后得分高者获胜。
Kimi知道Sunny也很聪明，要想获胜不那么容易。他只想知道在两个人的数字都已经给定的情况下，他最多可以拿到多少分。
现在请你编写一个程序帮帮Kimi。输入
单组输入。
第1行输入一个正整数n表示每人随机抽取的卡片的数量，n不超过1000。
第2行包含n个1-100之间的正整数表示Kimi抽到的卡片上的数字，两两之间用英文空格隔开。
第3行包含n个1-100之间的正整数表示Sunny抽到的卡片上的数字，两两之间用英文空格隔开。输出
输出Kimi最多可以得到的分数。
样例输入 Copy
5 3 4 5 5 2 1 4 5 3 2样例输出 Copy
4
#include <iostream>
#include <algorithm>
using namespace std;
int a[1001],b[1001];
int main()
{int n;cin >> n;for (int i = 0; i < n; i++)cin >> a[i];for (int i = 0; i < n; i++)cin >> b[i];sort(a, a + n);sort(b, b + n);int s = 0;for (int i = 0, j = 0; i < n && j < n;){if (a[i] > b[j]){s++;i++;j++;}elsei++;}cout << s << endl;return 0;
}L: X星危机
题目描述
最近宇宙局势很乱，X星人感受到了来自Y星的巨大威胁。
X星人决定修建一系列防御工事，X星人首先在一张矩形地图上设计防御工事。
在该地图上，每一个小格称为一个单元。没有修建防御工事的单元用“*”表示，修建了防御工事的单元用“@”表示。多个相邻的防御工事单元（只考虑上、下、左、右相邻）可以连接到一起形成一个防御单元群（当然，也可能存在只有一个防御单元的防御单元群），X星人希望在每一个防御单元群中至少有一个这样一个防御单元，它的上、下、左、右全部都是防御单元，以便用来做指挥部或者存放重要物资。
现在给你一张防御工事地图，你能否编写一个程序统计有多少个满足要求的防御单元群？输入
单组输入。
第1行输入两个不超过1000的正整数m和n，表示矩阵的行和列，两者之间用英文空格隔开。
接下来m行，每行包含n个'*'或'@'，其中'*'表示非防御单元，'@'表示防御单元。输出
输出两个整数，分别为防御单元群的总个数和满足要求的防御单元群的个数。其中，满足要求的防御单元群是指在该防御单元群中至少存在一个防御单元，其上、下、左、右也是防御单元。
样例输入 Copy
5 5 *@@@@ @**** **@@@ **@@@ @@@@@样例输出 Copy
3 1
#include <iostream>
using namespace std;
const int N = 1005;
char a[N][N];
bool b[N][N];
int m,n;
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
bool t;
void dfs(int x, int y)
{if (x < 0 || x >= m || y < 0 || y >= n || a[x][y] == '*' || b[x][y])return;b[x][y] = true;if (a[x - 1][y] == '@' && a[x + 1][y] == '@' && a[x][y - 1] == '@' && a[x][y + 1] == '@')t = true;for (int i = 0; i < 4; i++){int nx = x + dx[i];int ny = y + dy[i];dfs(nx, ny);}
}
int main()
{cin >> m >> n;for (int i = 0; i < m; i++)for (int j = 0; j < n; j++)cin >> a[i][j];int s = 0, sum = 0;for (int i = 0; i < m; i++){for (int j = 0; j < n; j++){if (a[i][j] == '@' && !b[i][j]){s++;t = false;dfs(i, j);if (t)sum++;}}}cout << s << ' ' << sum << endl;return 0;
}M: 取球
题目描述
Kimi在一个箱子里放了A个红球和B个绿球（A和B都是不超过1000的正整数），现在按照以下规则来取球：
(1) 每次可以从箱子里面取出两个球。
(2) 如果取出来的球颜色相同，则再往箱子里放入一个绿球。
(3) 如果取出来的球颜色不相同，则再往箱子里放入一个红球。
请问箱子里面只剩下一个绿球的概率为多少？输入
单组输入。
输入两个正整数A和B表示在初始时刻箱子中的红球数和绿球数，A和B之间用空格隔开，且均为不超过1000的正整数。输出
输出按照规则取球之后箱子里面只剩下一个绿球的概率，输出结果四舍五入保留两位小数。
样例输入 Copy
2 2样例输出 Copy
1.00
#include <iostream>
using namespace std;
int main()
{int a, b;cin >> a >> b;if (a % 2 != 0)cout << "0.00" << endl;elsecout << "1.00" << endl;return 0;
}
