2023环翠区编程挑战赛中学组题解

T1. 出栈序列

题目描述

栈是一种“先进后出”的数据结构，对于一个序列$1,2,...,n$，其入栈顺序是$1,2,...n$，但每个元素出栈的时机可以自由选择。

例如$1$入栈、$1$出栈，$2$入栈、$3$入栈、$3$出栈、$2$出栈，于是出栈序列为 $132$。

对于入栈顺序$12...n$，出栈序列有很多个，但出栈序列的总数不是$12...n$的全排列数，因为有些排列不满足出入栈规则。

例如$312$就不是一个合法的出栈序列，因为$3$先出栈意味着此时$1$和$2$在栈里面，入栈顺序是$12$，于是出栈必须是$21$。

小明仔细研究了出入栈的规则，它发现凡是不合法的出栈序列都有一个规律，至少有一个数，后面比它小的数，存在递增的情况。

现在请你帮助小明编写程序，对于给定的出栈序列，判断是否合法。

输入格式：

第一行$t$，表示$t$组数据
对每组数据
第一行$n$，表示序列长度
第二行$\mathrm{1..}n$的一个排列，表示要判断的出栈序列

输出格式：

$t$行，每行Yes或No，表示出栈序列是否合法

输入样例1:

2
3
1 2 3
3
3 1 2

输出样例1:

Yes
No

数据范围

所有数据：$t<=5$
样例1-3：$n<=100$
样例4-5：$n<=2000$
样例6-10：$n<=10^5$

代码实现

#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int a[N], stk[N], top;
int main()
{int t;scanf("%d", &t);while(t --){int n, x;scanf("%d", &n);int in = 1, out; //进栈in，出站outfor(int i = 1; i <= n; i ++) {scanf("%d", &out);while(in <= out) stk[top ++] = in ++; //将小于等当前入栈元素的所有数据入栈if(stk[top - 1] == out) { top --; } //检查栈顶元素是否为要出栈的数据else break;}if(top == 0) puts("Yes");else puts("No");}
}

领头牛

题目描述

在我国有一处牧场，里面养育着两种牛分别是$H$牛和$G$牛。为了方便实时管理我们需要在牛群中选出领头牛，这样我们只需要牵着领头牛其他牛自然就会跟着走。

现在我们要分别选出$H$领头牛和$G$领头牛凑成一对。

现在我们让牛群站成一排，例如： $GHHG$ ，每头牛都有一个属性“领导能力”。假设第 $1$ 头牛的领导能力为 $2$ ，那么他可以领导包含自身之后的两头牛也就是 “$GH$” 。

但是光有领导能力是不够做领头牛的，领头牛的要求满足两种要求之一：

• 能够领导自身品种全部的牛；
• 能够领导对方的领头牛。

我们会给出队伍顺序和每头牛的领导能力，请问有多少对领头牛？

输入格式

第一行输入 $n$ 表示牛的数量；
第二行输入$n$个字符，有$G$和$H$组成，表示牛的排列顺序；
第三行输入$n$个数，表示牛的领导能力。

输出格式：

输出一个整数$n$表示可以凑成几对领导牛。

输入样例1：

4
GHHG
2 2 1 1

输出样例1：

1

样例1说明：

第一头牛$G$，可以领导$2$头牛“$GH$”，没有包含全部的$G$牛，但是第二头牛$H$可以领导$2$头牛“$HH$”，包含了所有的$H$牛，所以第二头$H$牛是领头牛，那么第一头$G$牛包含了对方的领头牛，所以第一头$G$牛也是领头牛。
现在就是$G$有一头领头牛，$H$有一头领头牛，那么只能凑一对$(1，2)$。

输入样例2：

3
GGH
2 2 1

输出样例2：

2

样例2说明：

第一头牛$G$，领导$2$头牛“$GG$”包含全部的$G$牛，所以是领头牛；
第二头牛$G$，领导$2$头牛“$GH$”包含对方领头牛，所以是领头牛；
第三头牛$H$，领导$1$头牛“$H$”包含全部H牛，所以是领头牛；
配对$（1，3）$，$（2，3）$所以有$2$种

数据范围：

对于20%的数据：$1\le n\le 20$ ；
对于40%的数据：$1\le n\le 100$；
对于60%的数据：$1\le n\le 5000$；
对于80%的数据：$1\le n\le 20000$；
对于100%的数据：$1\le n\le 100000$。​​

代码实现（80分）

模拟，时间复杂度为$O(n^2)$

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 2e5 + 10;
char s[N];
int a[N], g[N], h[N];
int main()
{int n, x;cin >> n;cin >> s + 1;int s1 = 0, s2 = 0;for(int i = 1; i <= n; i ++){if(s[i] == 'G') s1 ++;else s2 ++;}for(int i = 1; i <= n; i ++) {cin >> x;a[i] = i + x - 1; //a[i]保存领导能力到达的位置}//处理第一种领导者：其记录的名单上包含它的品种的所有奶牛for(int i = 1; i <= n; i ++){int gg = 0, hh = 0;for(int j = i; j <= a[i]; j ++){if(s[j] == 'G') gg ++;else hh ++;}if(s[i] == 'G' && gg == s1) g[i] = 1; //标记为领导者else if(s[i] == 'H' && hh == s2) h[i] = 1; //标记为领导者}//处理第二种领导者：其记录的名单上记录了另一品种奶牛的“领导者”。for(int i = 1; i <= n; i ++){for(int j = i; j <= a[i]; j ++){if(s[i] == 'G' && h[j] == 1){g[i] = 1;break;}else if(s[i] == 'H' && g[j] == 1){h[i] = 1;break;}}}int c1 = 0, c2 = 0;for(int i = 1; i <= n; i ++)if(g[i]) c1 ++;for(int i = 1; i <= n; i ++)if(h[i]) c2 ++;cout << c1 * c2 << endl;
}

代码实现（100分）

朴素做法的问题在于使用了两层循环，其实第二层循环可以使用前缀和进行优化，用空间换时间。

• s1[]前缀和数组，s1[i]表示前i个字符中字符G的个数
• s2[]前缀和数组，s2[i]表示前i个字符中字符H的个数
• gs[]前缀和数组，gs[i]表示前i头牛中第一类G品种领导者的数量
• hs[]前缀和数组，hs[i]表示前i头牛中第一类H品种领导者的数量

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 2e5 + 10;
char s[N];
int a[N], s1[N], s2[N], g[N], h[N], gs[N], hs[N];
int main()
{int n;cin >> n;cin >> s + 1;for(int i = 1; i <= n; i ++) {cin >> x;a[i] = i + x - 1; //a[i]保存领导能力到达的位置}//s1[i]前缀和, 表示前i个字符中字符G的个数//s2[i]前缀和, 表示前i个字符中字符H的个数for(int i = 1; i <= n; i ++){s1[i] = s1[i - 1], s2[i] = s2[i - 1];if(s[i] == 'G') s1[i] ++;else s2[i] ++;}//处理第一种领导者：其记录的名单上包含本身的品种的所有奶牛for(int i = 1; i <= n; i ++){//gg表示从i到a[i]位置所有G的个数//hh表示从i到a[i]位置所有H的个数int gg = s1[a[i]] - s1[i - 1], hh = s2[a[i]] - s2[i - 1];//其记录的名单上包含本身的品种的所有奶牛if(s[i] == 'G' && gg == s1[n]) g[i] = 1; //将i位置标记为'G'的领导者else if(s[i] == 'H' && hh == s2[n]) h[i] = 1;//将i位置标记为'H'的领导者}//gs[i]前缀和，表示前i个奶牛中G的第一种领导者个数//hs[i]前缀和，表示前i个奶牛中H的第一种领导者个数for(int i = 1; i <= n; i ++){gs[i] = gs[i - 1], hs[i] = hs[i - 1];if(g[i]) gs[i] ++;if(h[i]) hs[i] ++;}//ga表示G的第一种领导者个数，ha表示H的第一种领导者个数int ga = gs[n], ha = hs[n];//处理第二种领导者：其记录的名单上记录了另一品种奶牛的“领导者”。for(int i = 1; i <= n; i ++){  //其记录的名单上记录了另一品种奶牛的领导者if(s[i] == 'G' && (hs[a[i]] - hs[i - 1]) != 0) ga ++;else if(s[i] == 'H' && (gs[a[i]] - gs[i - 1]) != 0) ha ++;}cout << ga * ha << endl;
}

两端对齐

题目描述

小明最近在用软件写文档时发现，在英文内容的键入时，软件会自动添加一些额外的空格到内容中，使得整段英文在文本区域的两端对齐，并且不会出现单个单词被拆分到两行的情况，看上去整齐又美观。

现在给定一篇文章中的$n$个单词，请试着将其按顺序以“两端对齐”的方式输出，要求：

• 单词间至少由一个空格隔开，行末单词后无空格
• 各行字符数均为$m$个，必要时可以在单词间补充额外的空格
• 一行内单词间的空格数要尽量相同，若始终不能均匀分配，那么左侧的空格数可以多一些
• 输出行数要尽可能少一些，也即每行放置的单词要尽可能多一些
  最后一行要左对齐，单词间不再插入额外的空格，末尾补空格至$m$个字符

输入格式：

第一行输入两个数$n$、$m$
接下来$n$行，每行$1$个单词$s_{}i$​​ ，均由小写字母构成

输出格式：
输出排版后的文章（数据保证有解）

输入样例：

10 14
to
be
or
not
to
be
that
is
a
question

输出样例：

to  be  or not
to  be that is
a question

样例说明：

第1行在前两个单词后分别额外添加了一个空格；
第2行在第一个单词后额外添加了一个空格；
最后一行在末尾额外添加了4个空格。
各行均为$14$个字符，输出的换行符不算入$m$。

数据范围：

对于30%的数据：$1\le n\le 100$，
对于60%的数据：$1\le n\le 1000$ ，
对于100%的数据：$1\le n\le 10^4$、$1\le m\le 10^6$，$1\le |s_i|\le 100$

代码实现（模拟？）

时间复杂度$O(n^2)$

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e4 + 10;
string a[N];
int main()
{int n, m;cin >> n >> m;for(int i = 0; i < n; i ++) cin >> a[i];string s = a[0]; //保存每行由单词和一个空格组成的字符串int cnt = 1; //每行单词的数量for(int i = 1; i < n; i ++){int len = s.size() + 1 + a[i].size(); //每行单词的长度if(len <= m) { s = s + ' ' + a[i]; cnt ++; }//每行字符串的长度不超过melse { //加入新单词后长度超过m            int b = m - s.size(); //需要填补空格int c = b / cnt; //平均每个单词需要额外添加的空格数量int r = b % cnt; //剩余需要在左侧补充的空格数量for(int j = i - cnt; j < i; j ++) // 输出单词{if(j != i - 1) cout << a[j] << " "; //不是本行最后一个单词，添加一个空格else cout << a[j]; //本行最后一个单词不添加空格for(int k = 0; k < c; k ++) cout << " "; //输出平均的空格if(r != 0) { //输出需要在做出补充的剩余空格，每个单词只补一个cout << " ";r --;}}cout << endl;s = a[i];cnt = 1;}}cout << s << endl; //输出最后一行的单词
}

T4. 免费超市

题解在我的另一篇博客，环翠区中小学生编程挑战赛题解中学组T4：免费超市