T1. 出栈序列
题目描述
栈是一种“先进后出”的数据结构,对于一个序列1,2,...,n1,2, ...,n1,2,...,n,其入栈顺序是1,2,...n1,2, ...n1,2,...n,但每个元素出栈的时机可以自由选择。
例如111入栈、111出栈,222入栈、333入栈、333出栈、222出栈,于是出栈序列为 1321\ 3\ 21 3 2。
对于入栈顺序12...n1\ 2\ ...\ n1 2 ... n,出栈序列有很多个,但出栈序列的总数不是12...n1\ 2\ ...\ n1 2 ... n的全排列数,因为有些排列不满足出入栈规则。
例如3123\ 1\ 23 1 2就不是一个合法的出栈序列,因为333先出栈意味着此时111和222在栈里面,入栈顺序是121\ 21 2,于是出栈必须是212\ 12 1。
小明仔细研究了出入栈的规则,它发现凡是不合法的出栈序列都有一个规律,至少有一个数,后面比它小的数,存在递增的情况。
现在请你帮助小明编写程序,对于给定的出栈序列,判断是否合法。
输入格式:
第一行ttt,表示ttt组数据
对每组数据
第一行nnn,表示序列长度
第二行1..n1..n1..n的一个排列,表示要判断的出栈序列
输出格式:
ttt行,每行Yes
或No
,表示出栈序列是否合法
输入样例1:
2
3
1 2 3
3
3 1 2
输出样例1:
Yes
No
数据范围
所有数据:t<=5t<=5t<=5
样例1-3:n<=100n<=100n<=100
样例4-5:n<=2000n<=2000n<=2000
样例6-10:n<=105n<=10^5n<=105
代码实现
#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");}
}
领头牛
题目描述
在我国有一处牧场,里面养育着两种牛分别是HHH牛和GGG牛。为了方便实时管理我们需要在牛群中选出领头牛,这样我们只需要牵着领头牛其他牛自然就会跟着走。
现在我们要分别选出HHH领头牛和GGG领头牛凑成一对。
现在我们让牛群站成一排,例如: GHHGGHHGGHHG ,每头牛都有一个属性“领导能力”。假设第 111 头牛的领导能力为 222 ,那么他可以领导包含自身之后的两头牛也就是 “GHGHGH” 。
但是光有领导能力是不够做领头牛的,领头牛的要求满足两种要求之一:
- 能够领导自身品种全部的牛;
- 能够领导对方的领头牛。
我们会给出队伍顺序和每头牛的领导能力,请问有多少对领头牛?
输入格式
第一行输入 nnn 表示牛的数量;
第二行输入nnn个字符,有GGG和HHH组成,表示牛的排列顺序;
第三行输入nnn个数,表示牛的领导能力。
输出格式:
输出一个整数nnn表示可以凑成几对领导牛。
输入样例1:
4
GHHG
2 2 1 1
输出样例1:
1
样例1说明:
第一头牛GGG,可以领导222头牛“GHGHGH”,没有包含全部的GGG牛,但是第二头牛HHH可以领导222头牛“HHHHHH”,包含了所有的HHH牛,所以第二头HHH牛是领头牛,那么第一头GGG牛包含了对方的领头牛,所以第一头GGG牛也是领头牛。
现在就是GGG有一头领头牛,HHH有一头领头牛,那么只能凑一对(1,2)(1,2)(1,2)。
输入样例2:
3
GGH
2 2 1
输出样例2:
2
样例2说明:
第一头牛GGG,领导222头牛“GGGGGG”包含全部的GGG牛,所以是领头牛;
第二头牛GGG,领导222头牛“GHGHGH”包含对方领头牛,所以是领头牛;
第三头牛HHH,领导111头牛“HHH”包含全部H牛,所以是领头牛;
配对(1,3)(1,3)(1,3),(2,3)(2,3)(2,3)所以有222种
数据范围:
对于20%的数据:1≤n≤201 ≤ n ≤ 201≤n≤20 ;
对于40%的数据:1≤n≤1001 ≤ n ≤ 1001≤n≤100;
对于60%的数据:1≤n≤50001 ≤ n ≤ 50001≤n≤5000;
对于80%的数据:1≤n≤200001 ≤ n ≤ 200001≤n≤20000;
对于100%的数据:1≤n≤1000001 ≤ n ≤ 1000001≤n≤100000。
代码实现(80分)
模拟,时间复杂度为O(n2)O(n^2)O(n2)
#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;
}
两端对齐
题目描述
小明最近在用软件写文档时发现,在英文内容的键入时,软件会自动添加一些额外的空格到内容中,使得整段英文在文本区域的两端对齐,并且不会出现单个单词被拆分到两行的情况,看上去整齐又美观。
现在给定一篇文章中的nnn个单词,请试着将其按顺序以“两端对齐”的方式输出,要求:
- 单词间至少由一个空格隔开,行末单词后无空格
- 各行字符数均为mmm个,必要时可以在单词间补充额外的空格
- 一行内单词间的空格数要尽量相同,若始终不能均匀分配,那么左侧的空格数可以多一些
- 输出行数要尽可能少一些,也即每行放置的单词要尽可能多一些
最后一行要左对齐,单词间不再插入额外的空格,末尾补空格至mmm个字符
输入格式:
第一行输入两个数nnn、mmm
接下来nnn行,每行111个单词sis_isi ,均由小写字母构成
输出格式:
输出排版后的文章(数据保证有解)
输入样例:
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个空格。
各行均为141414个字符,输出的换行符不算入mmm。
数据范围:
对于30%的数据:1≤n≤1001\le n \le1001≤n≤100,
对于60%的数据:1≤n≤10001\le n \le10001≤n≤1000 ,
对于100%的数据:1≤n≤1041\le n \le10^41≤n≤104、1≤m≤1061\le m \le10^61≤m≤106,1≤∣si∣≤1001\le|s_i|\le1001≤∣si∣≤100
代码实现(模拟?)
时间复杂度O(n2)O(n^2)O(n2)
#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:免费超市