首页 › 题库 › C/C++编程考级 › 1 栈与队列

C/C++编程六级 题库

共 51 道题 ,第 2 / 3 页 · 按题型筛选,点「查看答案」核对解析
章节 1 栈与队列 清除
21 简答题 偏难 C/C++编程考级 ·C/C++编程六级 · 1 栈与队列

栈基本操作

依次读入序列元素1,2,...,n进栈,每进一个元素,机器可要求下一个元素进栈或弹栈,如此进行。给定一个输入序列,判断栈空时弹出的元素构成的序列是否可能等于给定的序列,如果是则输出栈的操作过程,否则输出“NO”。

时间限制:1000

内存限制:65535

输入

输入分两行 第一行为n的值(即序列元素个数) 第二行为给定的输入序列(序列元素均为整型)

输出

如果输入序列能够由题目规定的操作得到,则输出对栈的操作过程 否则直接输出“NO”

样例输入

7
4 5 3 6 2 7 1

样例输出

PUSH 1
PUSH 2
PUSH 3
PUSH 4
POP 4
PUSH 5
POP 5
POP 3
PUSH 6
POP 6
POP 2
PUSH 7
POP 7
POP 1

提示

给定序列中有可能有不在1...n之间的数字

答案与解析
参考答案
//解法1
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int n;
  cin>>n;
  int a[100001],t=1,i;
  int l1[100001],l2[100001],l=0;
  stack <int> s;
  for(i=1;i<=n;i++)
    cin>>a[i];
  i=1;
  int f=0;
  while(1)
  {
    s.push(t);
    l++;
    l1[l]=0;
    l2[l]=t;
    t++;
    while(1)
    {
      if(s.size()==0) break;
      if(a[i]!=s.top()) break;
      i++;
      l++;
      l1[l]=1;
      l2[l]=s.top();
      s.pop();
    }
    if(s.size()==0 && t-1==n && i-1==n) break;
    if(s.size()>0 && t-1==n && i-1<n)
    {
      cout<<"NO";
      return 0;
    }
  }
  for(i=1;i<=l;i++)
  {
    if(l1[i]==1) cout<<"POP ";
    else cout<<"PUSH ";
    cout<<l2[i]<<endl;
  }
  return 0;
}
//解法2
#include <bits/stdc++.h>
using namespace std;
int main()
{	
	queue<string> q;
	stack<int> s;
	string x="PUSH ",y="POP ";
	int n;
	cin>>n;
	for(int i=1,j=1,a;i<=n;i++){
		cin>>a;
		if(a>n){
			cout<<"NO";return 0;
		}
		if(s.empty()){
			s.push(j);
			q.push(x+char(j+'0'));
			j++;
		}
		while(s.top()<a){
			s.push(j);
			q.push(x+char(j+'0'));
			j++;
		}
		if(s.top()==a){
			s.pop();
			q.push(y+char(a+'0'));
		}
		else{
			cout<<"NO";return 0;
		}
	}
	if(!s.empty()){
		cout<<"NO";return 0;
	}
	while(!q.empty()){
		cout<<q.front()<<endl;
		q.pop();
	}
	return 0;
}
题目详情
22 简答题 偏难 C/C++编程考级 ·C/C++编程六级 · 1 栈与队列

双端队列

定义一个双端队列,进队操作与普通队列一样,从队尾进入。出队操作既可以从队头,也可以从队尾。编程实现这个数据结构。

时间限制:1000

内存限制:65535

输入

第一行输入一个整数t,代表测试数据的组数。 每组数据的第一行输入一个整数n,表示操作的次数。 接着输入n行,每行对应一个操作,首先输入一个整数type。 当type=1,进队操作,接着输入一个整数x,表示进入队列的元素。 当type=2,出队操作,接着输入一个整数c,c=0代表从队头出队,c=1代表从队尾出队。 n <= 1000

输出

对于每组测试数据,输出执行完所有的操作后队列中剩余的元素,元素之间用空格隔开,按队头到队尾的顺序输出,占一行。如果队列中已经没有任何的元素,输出NULL。

样例输入

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

样例输出

3
NULL
答案与解析
参考答案
//解法1
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int t;
  cin>>t;
  while(t--)
  {
    int n;
    cin>>n;
    int a,b,i;
    int l[100001],head=1,tail=0;
    for(i=1;i<=n;i++)
    {
      cin>>a>>b;
      if(a==1)
      {
        tail++;
        l[tail]=b;
      }
      else
      {
        if(b==0) head++;
        else tail--;
      }
    }
    if(tail-head<0 || head>tail) cout<<"NULL";
    else
      for(i=head;i<=tail;i++)
        cout<<l[i]<<" ";
    cout<<endl;
  }
  return 0;
}
//解法2
//用deque模拟一下即可
#include <bits/stdc++.h>
using namespace std;
string s;
int main()
{	
	int n,m,type,x;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>m;
		deque<int> q;
		for(int j=1;j<=m;j++){
			cin>>type>>x;
			if(type==1){
				q.push_back(x);
			}else {
				if(x==0)q.pop_front();
				else q.pop_back();
			}
		}
		if(q.empty()){
			cout<<"NULL";continue;
		}
		while(!q.empty()){
			cout<<q.front()<<" ";
			q.pop_front();
		}
		cout<<endl;
	}
	return 0;
}
题目详情
23 简答题 偏难 C/C++编程考级 ·C/C++编程六级 · 1 栈与队列

生日相同 2.0

在一个有180人的大班级中,存在两个人生日相同的概率非常大,现给出每个学生的名字,出生月日。试找出所有生日相同的学生。

时间限制:1000

内存限制:65536

输入

第一行为整数n,表示有n个学生,n ≤ 180。此后每行包含一个字符串和两个整数,分别表示学生的名字(名字第一个字母大写,其余小写,不含空格,且长度小于20)和出生月(1 ≤ m ≤ 12)日(1 ≤ d ≤ 31)。名字、月、日之间用一个空格分隔

输出

每组生日相同的学生,输出一行,其中前两个数字表示月和日,后面跟着所有在当天出生的学生的名字,数字、名字之间都用一个空格分隔。对所有的输出,要求按日期从前到后的顺序输出。 对生日相同的名字,按名字从短到长按序输出,长度相同的按字典序输出。如没有生日相同的学生,输出”None”

样例输入

6
Avril 3 2
Candy 4 5
Tim 3 2
Sufia 4 5
Lagrange 4 5
Bill 3 2

样例输出

3 2 Tim Bill Avril
4 5 Candy Sufia Lagrange
答案与解析
参考答案
//参考答案1
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define N 185
using namespace std;
struct ccc
{
	char name[N];
	int mouth;
	int day;
}student[N];
bool com(ccc a,ccc b)//排序,日期从小到大输出
{
	if(a.mouth==b.mouth)
	{
		return a.day<b.day;
	} 
	else return a.mouth<b.mouth;
}
int main()
{
	int n;
	while(scanf("%d ",&n)!=EOF)
	{
		char tmp[N][N];int sum=0,x=0;
		for(int i=0;i<n;i++)
		{
			scanf("%s %d%d",&student[i].name,&student[i].mouth,&student[i].day); 
		}
		sort(student,student+n,com);
		for(int i=0;i<n-1;i++)
		{
			while(student[i].day==student[i+1].day)//生日相同记录数量
			{
				strcpy(tmp[i],student[i].name);
				strcpy(tmp[i+1],student[i+1].name);
				sum++;i++;
			}
			if(sum>=1)//如果生日相同
			{
				x=1;
				printf("%d %d ",student[i].mouth,student[i].day);
				int a[N]={0};//学生名字长度
				int min=1000;
				for(int j=i-sum;j<i+1;j++)
				{
					a[j]=strlen(tmp[j]);
				}
				int m=sum+1,t;
				while(m>0)//每次找到最小的名字输出
				{
					for(int j=i-sum;j<i+1;j++)
					{
						if(a[j]<min)//长度最小
						{
							min=a[j];t=j;
						}
						else if(a[j]==min)
						{
							if(strcmp(tmp[j],tmp[t])<0)//字典序最小
							{
								t=j;
							}
						}
						if(j==i)
						{
							a[t]=1000;
						}
					}
					
					if(m==1)
					{
						printf("%s\n",tmp[t]);
						sum=0;
					}
					else printf("%s ",tmp[t]);
					m--;min=1000;
				}
			}
		}
		if(x==0)
		{
			printf("None");
		}
	}
	return 0;
}
//参考答案2
#include<stdio.h>
#include<string.h>
struct stuent{
    char name[100];
    int birth[2];
}stu[200];
struct stuent tmp;
int main(){
    int i,j,k;
    int n;
    int flag=0;
    scanf("%d",&n);
    for(i=0;i<n;i++){
        scanf("%s",stu[i].name);
        scanf("%d%d",&stu[i].birth[0],&stu[i].birth[1]);
    }   
    for(i=0;i<n;i++){
        for(j=n-1;j>i;j--){
            if(strlen(stu[j].name)<strlen(stu[j-1].name)){
                tmp=stu[j];
                stu[j]=stu[j-1];
                stu[j-1]=tmp; 
            }
            else if(strlen(stu[j].name)==strlen(stu[j-1].name)&&strcmp(stu[j].name,stu[j-1].name)<0){
                tmp=stu[j];
                stu[j]=stu[j-1];
                stu[j-1]=tmp; 
            }            
        }
    }
    for(i=0;i<n;i++){
        for(j=n-1;j>i;j--){
            if(stu[j].birth[0]<stu[j-1].birth[0]){
                 tmp=stu[j];
                stu[j]=stu[j-1];
                stu[j-1]=tmp; 
            }
            else if(stu[j].birth[0]==stu[j-1].birth[0]&&stu[j].birth[1]<stu[j-1].birth[1]){
                tmp=stu[j];
                stu[j]=stu[j-1];
                stu[j-1]=tmp;
            }       
        }
    }
    for(i=0;i<n;i=j){       
        for(j=i+1;j<n;j++){
            if(stu[i].birth[0]==stu[j].birth[0]&&stu[i].birth[1]==stu[j].birth[1])
              ;
            else break;
        }
        if((j-i)>1){flag=1;
          printf("%d %d ",stu[i].birth[0],stu[i].birth[1]);
        for(k=i;k<j;k++) printf("%s ",stu[k].name);
        printf("\n");  
        }
        
    }
    if(!flag) printf("None");
    return  0;
}
//参考答案3
//结构体排序+队列的基本操作 模拟一下即可
#include <bits/stdc++.h>
using namespace std;
struct Birthday{
	string name;
	int moth,day,len_B;
}b[200];
bool cmp(Birthday &a,Birthday &b){
	if(a.moth!=b.moth)	return a.moth<b.moth;
	else {
		if(a.day!=b.day) return a.day<b.day;
		else {
			if(a.len_B!=b.len_B) return a.len_B<b.len_B;
			else return a.name<b.name;
		}
	}
}
int main()
{	
	int n;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>b[i].name>>b[i].moth>>b[i].day;
		b[i].len_B=b[i].name.size();
	}
	sort(b,b+n,cmp);
	queue<string> Name;
	Birthday t=b[0];
	int sign=1;
	for(int i=1;i<n;i++){
		if(b[i].moth==t.moth && b[i].day==t.day){
			Name.push(b[i].name);
			sign=0;
		}
		else {
			if(!Name.empty()){
				cout<<t.moth<<" "<<t.day<<" "<<t.name<<" ";
				while(!Name.empty()){
					cout<<Name.front()<<" ";Name.pop();
				}
				cout<<endl;
			}
			t=b[i];
		}
	}
	if(!Name.empty()){
		cout<<t.moth<<" "<<t.day<<" "<<t.name<<" ";
		while(!Name.empty()){
			cout<<Name.front()<<" ";Name.pop();
		}
		cout<<endl;
	}
	if(sign) cout<<"None";
	return 0;
}
题目详情
24 简答题 偏难 C/C++编程考级 ·C/C++编程六级 · 1 栈与队列

合法出栈序列

给定一个由不同小写字母构成的长度不超过8的字符串x,现在要将该字符串的字符依次压入栈中,然后再全部弹出。

要求左边的字符一定比右边的字符先入栈,出栈顺序无要求。

再给定若干字符串,对每个字符串,判断其是否是可能的x中的字符的出栈序列。

 

时间限制:1000

内存限制:65536

输入

第一行是原始字符串x 后面有若干行,每行一个字符串

输出

对除第一行以外的每个字符串,判断其是否是可能的出栈序列。如果是,输出"YES",否则,输出"NO"

样例输入

abc
abc
bca
cab

样例输出

YES
YES
NO
答案与解析
参考答案
#include <bits/stdc++.h>
using namespace std;
string a,b;
int main()
{	
	cin>>a;
	while(cin>>b){
		stack<char> st;
		int j=0;
		for(int i=0;i<a.size();i++){
			if(!st.empty())
				if(st.top()==b[j]){
					st.pop();j++;
				}
			st.push(a[i]);
		}
		while(!st.empty()&&st.top()==b[j]&&j<b.size()){
				st.pop();j++;
		}
		if(st.empty())cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
	}
	return 0;
}


题目详情
25 简答题 偏难 C/C++编程考级 ·C/C++编程六级 · 1 栈与队列

括号画家(2023.9)

Candela是一名漫画家,她有一个奇特的爱好,就是在纸上画括号。这一天,刚刚起床的Candela画了一排括号序列,其中包含小括号()、中括号[]和大括号{},总长度为N。这排随意绘制的括号序列显得杂乱无章,于是Candela定义了什么样的括号序列是美观的:

(1) 空的括号序列是美观的;

(2) 若括号序列A是美观的,则括号序列(A)、[A]、{A}也是美观的;

(3) 若括号序列A、B都是美观的,则括号序列AB也是美观的;

例如 [(){}]() 是美观的括号序列,而 )({)[}]( 则不是。

现在Candela想知道她画出的括号序列是不是美观的。你能帮帮她吗?

时间限制:1000

内存限制:262144

输入

一个括号序列,长度不超过10000。

输出

如果它是美观的,输出Yes,否则输出No。

样例输入

{}[(){}]()

样例输出

Yes
答案与解析
参考答案
//青少年考级竞赛题库(tiku.scratchor.com)搜集整理,感谢网友提供代码! 
#include<iostream>
#include<algorithm>
#include<stack>
using namespace std;
stack<char>str;
//判断左右两个括号是否美观
bool beauty(char s1, char s2) {
	switch (s1) {
	case '{':
		if (s2 == '}')
			return true;
		else
			return false;
	case '[':
		if (s2 == ']')
			return true;
		else
			return false;
	case '(':
		if (s2 == ')')
			return true;
		else
			return false;
	}
}
int main()
{
	string Brackets;
	char s;
	int i = 0;
	cin >> Brackets;
	while (i < Brackets.length()) {
		s = Brackets[i];
		i++;
		str.push(s);				//将当前字符入栈
		char s2 = str.top();
		if (s2 == ']' || s2 == '}' || s2 == ')') 		//是右括号,进行判断是否与左括号美观
		{
			str.pop();				//将s2出栈
			if (str.empty()) {			//无左括号,肯定不美观
				cout << "No" << endl;
				return 0;
			}
			char s1 = str.top();			//s1是左括号
			if (beauty(s1, s2)) {			//美观,将s1出栈
				str.pop();							
			}
			else {				//不美观
				cout << "No" << endl;
				return 0;
			}
		}
	}
	cout << "Yes";
}


题目详情
26 简答题 偏难 C/C++编程考级 ·C/C++编程六级 · 1 栈与队列

表达式求值

求一个可能包含加、减、乘、除、乘方运算的中缀表达式的值。

在计算机中,我们常用栈来解决这一问题。首先将中缀表达式转换到后缀表达式,然后对后缀表达式求值。

加、减、乘、除、乘方分别用+,-,*, /, ^来表示。表达式可以有圆括号()。

时间限制:1000

内存限制:65536

输入

第一行为测试数据的组数N。 接下来的N行,每行是一个中缀表达式。 每个表达式中,圆括号、运算符和运算数相互之间都用空格分隔,运算数是整数。一般运算数可正可负(负数的符号和数字之间无空格),指数一定为自然数(0和正整数)。不必考虑除0的情况。每个运算数均可由int放下。不必考虑溢出。中缀表达式的字符串长度不超过600。乘方的优先级比乘除都高,结合性是向左结合,如2 ^ 3 ^ 4表示( 2 ^ 3 ) ^ 4 = 4096。除法的商向下取整。

输出

对每一组测试数据输出一行,为表达式的值

样例输入

2
31 * ( 5 - ( -3 + 25 ) ) + 70 ^ 2
2 * 5 + 6 * ( 7 - 8 ) + 6

样例输出

4373
10
答案与解析
参考答案
#include <bits/stdc++.h>
using namespace std;
int get_fast(string op) // 运算符的优先级
{
  int ans = -1;
  switch (op[0]) {
  case '+':
  case '-':
    ans = 1;
    break;
  case '*':
  case '/':
    ans = 2;
    break;
  case '^':
    ans = 3;
    break;
  }
  return ans;
}
vector<string> scaner(string s) // 字符串拆解放入vector
{
  vector<string> ans;
  string ops = "+-*/^()";
  string t = "";
  for (int i = 0; i < s.size(); i++) {
    if (s[i] == '-' && (i + 1 < s.size()) && s[i + 1] >= '0' && s[i + 1] <= '9')
      t = "-";
    else if (s[i] >= '0' && s[i] <= '9')
      t += s[i];
    else if (ops.find(s[i]) != string::npos)
      t += s[i];
    else if (s[i] == ' ') {
      if (t.size() > 0)
        ans.push_back(t);
      t = "";
    }
  }
  if (t.size())
    ans.push_back(t);
  return ans;
}
vector<string> infix_Suffix(vector<string> exp) // 中缀表达式转后缀表达式
{
  vector<string> ans;
  stack<string> st;
  string op = "+-*/^()";
  for (int i = 0; i < exp.size(); i++) {
    if (exp[i] == "(")
      st.push(exp[i]);
    else if (exp[i] == ")") {
      while (st.top() != "(") {
        ans.push_back(st.top());
        st.pop();
      }
      st.pop();
    } else if (op.find(exp[i]) != string::npos) {
      while (st.size() && get_fast(exp[i]) <= get_fast(st.top())) {
        ans.push_back(st.top());
        st.pop();
      }
      st.push(exp[i]);
    } else
      ans.push_back(exp[i]);
  }
  while (st.size()) {
    ans.push_back(st.top());
    st.pop();
  }
  return ans;
}
int suffix_calc(vector<string> exp) // 后缀表达式计算结果
{
  stack<int> num;
  string ops = "+-*/^";
  for (int i = 0; i < exp.size(); i++) {
    if (ops.find(exp[i]) != string::npos) {
      int a = num.top();
      num.pop();
      int b = num.top();
      num.pop();
      if (exp[i] == "+")
        num.push(b + a);
      else if (exp[i] == "-")
        num.push(b - a);
      else if (exp[i] == "*")
        num.push(b * a);
      else if (exp[i] == "/")
        num.push(b / a);
      else if (exp[i] == "^")
        num.push(pow(b * 1.0, a));
    } else
      num.push(atoi(exp[i].c_str()));
  }
  cout << num.top() << endl;
  return num.top();
}
int main() {
  string s;
  getline(cin, s);
  int n;
  n = atoi(s.c_str());
  while (n--) {
    getline(cin, s);
    vector<string> vs = scaner(s);
    vs = infix_Suffix(vs);
    suffix_calc(vs);
  }
  return 0;
}
题目详情
27 简答题 偏难 C/C++编程考级 ·C/C++编程六级 · 1 栈与队列

队列和栈(2023.12)

队列和栈是两种重要的数据结构,它们具有push k和pop操作。push k是将数字k加入到队列或栈中,pop则是从队列和栈取一个数出来。队列和栈的区别在于取数的位置是不同的。

队列是先进先出的:把队列看成横向的一个通道,则push k是将k放到队列的最右边,而pop则是从队列的最左边取出一个数。

栈是后进先出的:把栈也看成横向的一个通道,则push k是将k放到栈的最右边,而pop也是从栈的最右边取出一个数。

假设队列和栈当前从左至右都含有1和2两个数,则执行push 5和pop操作示例图如下:

          push 5          pop

队列 1 2  ------->  1 2 5 ------>  2 5

          push 5          pop

栈   1 2  ------->  1 2 5 ------>  1 2

现在,假设队列和栈都是空的。给定一系列push k和pop操作之后,输出队列和栈中存的数字。若队列或栈已经空了,仍然接收到pop操作,则输出error。

时间限制:1000

内存限制:65536

输入

第一行为m,表示有m组测试输入,m<100。 每组第一行为n,表示下列有n行push k或pop操作。(n<150) 接下来n行,每行是push k或者pop,其中k是一个整数。 (输入保证同时在队列或栈中的数不会超过100个)

输出

对每组测试数据输出两行,正常情况下,第一行是队列中从左到右存的数字,第二行是栈中从左到右存的数字。若操作过程中队列或栈已空仍然收到pop,则输出error。输出应该共2*m行。


样例输入

2
4
push 1
push 3
pop
push 5
1
pop

样例输出

3 5
1 5
error
error
答案与解析
参考答案
#include <stdio.h>
#include <string.h>
#define N 150
int stack[N], ps;
int queue[N], qh, qt;
char cmd[5];
int main(void) {
  int m, n, sflag, qflag, a, i;
  scanf("%d", &m);
  while (m--) {
    scanf("%d", &n);
    sflag = qflag = 0;
    ps = 0, qh = 0;
    qt = 0;
    while (n--) {
      scanf("%s", cmd);
      if (cmd[1] == 'u') {
        scanf("%d", &a);
        stack[ps++] = a;
        queue[qt++] = a;
      } else if (cmd[1] == 'o') {
        if (ps == 0)
          sflag = 1;
        if (qt - qh == 0)
          qflag = 1;
        ps--;
        qh++;
      }
    }
    if (qflag)
      printf("error\n");
    else {
      for (i = qh; i < qt; i++)
        printf("%d ", queue[i]);
      printf("\n");
    }
    if (sflag)
      printf("error\n");
    else {
      for (i = 0; i < ps; i++)
        printf("%d ", stack[i]);
      printf("\n");
    }
  }
  return 0;
}
题目详情
28 简答题 偏难 C/C++编程考级 ·C/C++编程六级 · 1 栈与队列

奇怪的括号(2023.12)

某天小A和同学在课堂上讨论到:“栈这种数据结构真是太优美了,既简单用途又广泛。”小B仰慕小A许久,于是他拿出了自己在网上抄写的一道题问小A,如何判断括号是否匹配呢

时间限制:1000

内存限制:65536

输入

多组数据,每组数据占一行,且都是由(、)、[、]、*、/这六种字符组成。

输出

每组数据输出一行,如果括号能匹配成功,输出True,否则输出False。括号匹配规则是: ( 和 ) 匹配 [ 和 ] 匹配 /* 和 */ 匹配 如果含有冗余字符也算匹配失败,例如 /***/ 是匹配失败的因为中间多了一个*。


样例输入

()/*[()]*/
*/**/

样例输出

True
False
答案与解析
参考答案
#include <bits/stdc++.h>
using namespace std;
string s;
int main() {
  while (cin >> s) {
    stack<char> st;
    for (int i = 0; i < s.size(); i++) {
      if (st.empty()) {
        st.push(s[i]);
      } else {
        if (s[i] == ')' && st.top() == '(')
          st.pop();
        else if (s[i] == ']' && st.top() == '[')
          st.pop();
        else if (s[i] == '/' && st.top() == '*' && st.size() >= 3) {
          st.pop();
          char a = st.top();
          st.pop();
          char b = st.top();
          st.pop();
          if (!(a == '*' && b == '/')) {
            st.push(b);
            st.push(a);
            st.push('*');
          }
        } else
          st.push(s[i]);
      }
    }
    if (st.empty())
      cout << "True" << endl;
    else
      cout << "False" << endl;
  }
  return 0;
}
题目详情
29 简答题 偏难 C/C++编程考级 ·C/C++编程六级 · 1 栈与队列

中缀表达式的值(2023.12)

人们熟悉的四则运算表达式称为中缀表达式,例如(23+34*45/(5+6+7))。在程序设计语言中,可以利用堆栈的方法把中缀表达式转换成保值的后缀表达式(又称逆波兰表示法),并最终变为计算机可以直接执行的指令,得到表达式的值。 给定一个中缀表达式,编写程序,利用堆栈的方法,计算表达式的值。

时间限制:200

内存限制:65536

输入

第一行为测试数据的组数N 接下来的N行,每行是一个中缀表达式。表达式中只含数字、四则运算符和圆括号,操作数都是正整数,数和运算符、括号之间没有空格。中缀表达式的字符串长度不超过600。

输出

对每一组测试数据输出一行,为表达式的值


样例输入

3
3+5*8
(3+5)*8
(23+34*45/(5+6+7))

样例输出

43
64
108


提示

注意:运算过程均为整数运算(除法运算'/'即按照C++定义的int除以int的结果,测试数据不会出现除数为0的情况),输出结果也为整数(可能为负)。 中间计算结果可能为负。

答案与解析
参考答案
#include <bits/stdc++.h>
using namespace std;
int get_fast(string op) // 运算符的优先级
{
  int ans = -1;
  switch (op[0]) {
  case '+':
  case '-':
    ans = 1;
    break;
  case '*':
  case '/':
    ans = 2;
    break;
  case '^':
    ans = 3;
    break;
  }
  return ans;
}
vector<string> scaner(string s) // 字符串拆解放入vector
{
  vector<string> ans;
  string ops = "+-*/^()";
  string t = "";
  for (int i = 0; i < s.size(); i++) {
    if (s[i] >= '0' && s[i] <= '9')
      t += s[i];
    else if (ops.find(s[i]) != string::npos) {
      if (t.size() > 0)
        ans.push_back(t);
      t = s[i];
      ans.push_back(t);
      t = "";
    }
  }
  if (t.size())
    ans.push_back(t);
  return ans;
}
vector<string> infix_Suffix(vector<string> exp) // 中缀表达式转后缀表达式
{
  vector<string> ans;
  stack<string> st;
  string op = "+-*/^()";
  for (int i = 0; i < exp.size(); i++) {
    if (exp[i] == "(")
      st.push(exp[i]);
    else if (exp[i] == ")") {
      while (st.top() != "(") {
        ans.push_back(st.top());
        st.pop();
      }
      st.pop();
    } else if (op.find(exp[i]) != string::npos) {
      while (st.size() && get_fast(exp[i]) <= get_fast(st.top())) {
        ans.push_back(st.top());
        st.pop();
      }
      st.push(exp[i]);
    } else
      ans.push_back(exp[i]);
  }
  while (st.size()) {
    ans.push_back(st.top());
    st.pop();
  }
  return ans;
}
int suffix_calc(vector<string> exp) // 后缀表达式计算结果
{
  stack<int> num;
  string ops = "+-*/^";
  for (int i = 0; i < exp.size(); i++) {
    if (ops.find(exp[i]) != string::npos) {
      int a = num.top();
      num.pop();
      int b = num.top();
      num.pop();
      if (exp[i] == "+")
        num.push(b + a);
      else if (exp[i] == "-")
        num.push(b - a);
      else if (exp[i] == "*")
        num.push(b * a);
      else if (exp[i] == "/")
        num.push(b / a);
      else if (exp[i] == "^")
        num.push(pow(b * 1.0, a));
    } else
      num.push(atoi(exp[i].c_str()));
  }
  cout << num.top() << endl;
  return num.top();
}
int main() {
  string s;
  int n;
  cin >> n;
  while (n--) {
    cin >> s;
    vector<string> vs = scaner(s);
    vs = infix_Suffix(vs);
    suffix_calc(vs);
  }
  return 0;
}
题目详情
30 简答题 偏难 C/C++编程考级 ·C/C++编程六级 · 1 栈与队列

智能陪护

智能陪护系统是一个自动为老人们分配机器人护工的系统。系统中有若干个机器人排队候选,当有老人下单时,系统自动将队列最前面的机器人派送给老人,该机器人就在老人下单的当天上岗了。当老人结算时,这个机器人就立刻结束任务,回到队列末尾排队等待下一次任务,必要时可以在当天就开始接任务。

本题就请你实现这样一个自动分配功能。

时间限制:6000

内存限制:65536

输入

输入在第一行中给出 2 个正整数:N(≤ 104)是机器人护工的数量—— 这里假设所有机器人护工从 1 到 N 编号,且一开始按照编号升序在系统队列中排队;K(≤ 105)是系统订单信息的条数。随后 K 行,每行给出一条订单信息,格式为: 老人ID 指令 日期 其中 老人ID是一个长度不超过 5 的字符串,由英文小写字母和数字组成;指令 为 1 表示下单,为 0 表示结算;日期是按照 年年年年月月日日 格式给出的,保证是一个 2022 年 1 月 1 日到 3022 年 12 月 31 日 之间的合法日期。 题目保证所有数据合理,即对每位老人,结算一定发生在下单之后,结算了一单才允许下另一单,且不存在只有下单没有结算、或只有结算没有下单的数据。

输出

按照下单的时间顺序,输出机器人护工的分配信息,每行输出一条,格式为: 老人ID - 机器人护工编号 如果同一天有多位老人下单或结算,保证先处理结算的,使得机器人能及时回到队列。对于同时下达相同指令的,则按照老人ID的升序排队处理。如果一位老人下单时,系统中没有机器人护工了,则需要等待。如果到老人结算时,都没有等到一位护工,则对应输出 老人ID - NONE 最后在一行中顺序输出队列中的机器人护工的编号。要求数字间以 1 个空格分隔,行首尾不得有多余空格。

样例输入

3 10
a01 0 20220202
a04 1 20220103
a02 1 20220101
a05 0 20220202
a03 1 20220101
a03 0 20220202
a04 0 20220201
a02 0 20220102
a05 1 20220101
a01 1 20220101

样例输出

a01 - 1
a02 - 2
a03 - 3
a05 - 2
a04 - NONE
1 3 2
答案与解析
参考答案
#include <cstdio>
#include <iostream>
#include <queue>
#include <algorithm>
#include <unordered_map>

using namespace std;

const int K = 1e5 + 10;
int n, k;
queue<int> que;
struct Order {
    string name;
    int type, dt;

    bool operator<(const Order& o) const {
        if (dt != o.dt) return dt < o.dt;
        if (type != o.type) return type < o.type;
        return name < o.name;
    }

    friend ostream& operator<<(ostream& out, const Order& o) {
        out << o.name << " " << o.type << " " << o.dt;
        return out;
    }
} orders[K];
unordered_map<string, int> mp;
queue<Order> wt_que;
unordered_map<string, bool> waiting;

int _ = []() {
    ios::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);
    return 0;
}();

int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) que.push(i);
    for (int i = 0; i < k; ++i) {
        cin >> orders[i].name >> orders[i].type >> orders[i].dt;
    }
    sort(orders, orders + k);
    for (int i = 0; i < k; ++i) {
        const Order& u = orders[i];
        // cout << u << "\n";
        if (u.type) {
            if (!que.empty()) {
                mp[u.name] = que.front();
                cout << u.name << " - " << que.front() << '\n';
                que.pop();
            } else {
                wt_que.push(u);
                waiting[u.name] = true;
            }
        } else {
            if (mp.find(u.name) != mp.end()) {
                while (!wt_que.empty() && !waiting[wt_que.front().name]) wt_que.pop();
                if (!wt_que.empty()) {
                    const Order& v = wt_que.front(); wt_que.pop();
                    mp[v.name] = mp[u.name];
                    cout << v.name << " - " << mp[u.name] << '\n';
                } else que.push(mp[u.name]);
                mp.erase(u.name);
            } else {
                cout << u.name << " - NONE\n";
                waiting[u.name] = false;
            }
        }
    }
    while (!que.empty()) {
        cout << que.front(); que.pop();
        cout << (que.empty() ? "\n" : " ");
    }


    return 0;
}
题目详情
31 简答题 偏难 C/C++编程考级 ·C/C++编程六级 · 1 栈与队列

词频统计

请编写程序,对一段英文文本,统计其中所有不同单词的个数,以及词频最大的前10%的单词。

所谓“单词”,是指由不超过80个单词字符组成的连续字符串,但长度超过15的单词将只截取保留前15个单词字符。而合法的“单词字符”为大小写字母、数字和下划线,其它字符均认为是单词分隔符。

时间限制:8000

内存限制:65536

输入

输入给出一段非空文本,最后以符号#结尾。输入保证存在至少10个不同的单词。

输出

在第一行中输出文本中所有不同单词的个数。注意“单词”不区分英文大小写,例如“PAT”和“pat”被认为是同一个单词。 随后按照词频递减的顺序,按照词频:单词的格式输出词频最大的前10%的单词。若有并列,则按递增字典序输出。

样例输入

This is a test.
The word “this” is the word with the highest frequency.
Longlonglonglongword should be cut off, so is considered as the same as longlonglonglonee. But this_8 is different than this, and this, and this…#
this line should be ignored.

样例输出

23
5:this
4:is

提示

(注意:虽然样例里单词the也出现了4次,但因为我们只要输出前10%(即23个单词中的前2个)单词,而按照字母序,the排第3位,所以不输出。)

答案与解析
参考答案
#include<iostream>
#include<cstring>
#include<algorithm>
#include<map>
#include<vector>

using namespace std;
typedef pair<string, int> PII;
map<string,int> mp;
map<string,int>::iterator it;
vector<PII> q;

bool cmp(PII a,PII b)  //   自定义排序方式
{
    if(a.second!=b.second) return a.second>b.second;  //  出现的次数
    else
        return a.first<b.first;    //   字母序
}

int main()
{
    string s;
    char x;
    while(~scanf("%c",&x)&&x!='#')  //  一个字符一个字符的读  遇到 # 结束
    {
        if( (x>='A'&&x<='Z') || (x>='a'&&x<='z') || (x>='0'&&x<='9') || x=='_')
        {
            if(x>='A'&&x<='Z') x=x-'A'+'a';   // 都转化成小写
            if(s.size()<15) s+=x;        //   如果大于 长度15   只要前十五个
        }
        else     //  遇到非合法字符
        {
            if(s.size()>0) mp[s]++,s.clear();   //  存到map<string,int> 中去
        }
    }
    for(it=mp.begin();it!=mp.end();it++)      //  把map  中的信息转入到  vector中去   也可转到结构体中  用结构体解决
        q.push_back({it->first,it->second});
    
    sort(q.begin(),q.end(),cmp);    // 按定义的方式排序
    
    cout<<q.size()<<endl;        //  输出一共单词个数
    int l=q.size()/10;
    
    for(int i=0;i<l;i++)      // 遍历前10%
        cout<<q[i].second<<':'<<q[i].first<<endl;
        
    return 0;
}
题目详情
32 简答题 偏难 C/C++编程考级 ·C/C++编程六级 · 1 栈与队列

小白鼠再排队2(2024-3-6级)

N只小白鼠(1 < N < 100),每只鼠头上戴着一顶有颜色的帽子。现在称出每只白鼠的重量,要求按照白鼠重量从小到大的顺序输出它们头上帽子的颜色。帽子的颜色用 “red”,“blue”等字符串来表示。不同的小白鼠可以戴相同颜色的帽子。白鼠的重量用整数表示。

时间限制:1000

内存限制:65536

输入

输入第一行为一个整数N,表示小白鼠的数目。 下面有N行,每行是一只白鼠的信息。第一个为正整数,表示白鼠的重量,不超过整型范围;第二个为字符串,表示白鼠的帽子颜色,字符串长度不超过10个字符。 注意:白鼠的重量各不相同。

输出

按照白鼠的重量从小到大的顺序输出白鼠的帽子颜色。


样例输入

3
30 red
50 blue
40 green

样例输出

red
green
blue
答案与解析
参考答案
//参考代码1
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <list>
#include <queue>
#include <stack>
#include <vector>

using namespace std;
struct sb {
  int z;
  char s[15];
} a[105];
bool cmp(sb a, sb b) { return a.z < b.z; }
int main() {
  int n;
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> a[i].z >> a[i].s;
  }
  sort(a + 1, a + 1 + n, cmp);
  for (int i = 1; i <= n; i++) {
    for (int j = 0; j < strlen(a[i].s); j++) {
      cout << a[i].s[j];
    }
    cout << endl;
  }
  return 0;
}
//参考代码2
#include <bits/stdc++.h>

using namespace std;
struct shu
{
    int n;
    string s;
}a[100010];
bool cmp(shu a,shu b)
{
    return a.n<b.n;
}
int main()
{
    int N;
    cin>>N;
    for(int i=0;i<N;i++)
    {
        cin>>a[i].n>>a[i].s;
    }
    sort(a,a+N,cmp);
    for(int i=0;i<N;i++)
    {
        cout<<a[i].s<<endl;
    }
}


题目详情
33 简答题 偏难 C/C++编程考级 ·C/C++编程六级 · 1 栈与队列

扩号匹配问题(2024-3-6级)

在某个字符串(长度不超过 100)中有左括号、 右括号和大小写字母;规定(与常见的算数式子一样) 任何一个左括号都从内到外与在它右边且距离最近的右括号匹配。 写一个程序, 找到无法匹配的左括号和右括号, 输出原来字符串, 并在下一行标出不能匹配的括号。 不能匹配的左括号用"$"标注,不能匹配的右括号用"?"标注.

时间限制: 3000

内存限制: 65536

输入

输入包括多组数据, 每组数据一行, 包含一个字符串, 只包含左右括号和大小写字母, 字符串长度不超过 100

输出

对每组输出数据, 输出两行, 第一行包含原始输入字符, 第二行由"$","?"和空格组成, "$"和"?"表示与之对应的左括号和右括号不能匹配。


样例输入

((ABCD(x)
)(rttyy())sss)(

样例输出

((ABCD(x)
$$       
)(rttyy())sss)(
?            ?$
答案与解析
参考答案
// 就近原则匹配:栈
// 遍历字符串
// 遇到左括号,将其下标入栈
// 右括号则先判断栈内元素情况
// 1.空,则将其下表记录到数组中
// 2.非空,则栈顶元素弹出(匹配到了)
// 将字符串便遍历后,将栈内元素记录入另一个数组
// 用两数组内的对应下标分别改成对应字符
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
string s;
char ans[N]; // 第二排的输出数组
stack<int> st;
int a[N], cnt = 1; // 未匹配的右括号的下标存储
int b[N], cnn = 1; // 未匹配的左括号的下标存储
int main() {
  while (getline(cin, s)) { // 输入不结束
    memset(ans, 0, sizeof(ans));
    memset(a, 0, sizeof(a));
    memset(b, 0, sizeof(b));
    cnt = 1;
    cnn = 1; // 数据初始化
    for (int i = 0; i < s.size(); i++) {
      if (s[i] == '(') {
        st.push(i); // 左括号统一入栈
      }
      if (s[i] == ')') {
        if (!st.empty()) {
          st.pop(); // 若栈非空,则可以匹配
        } else {
          a[cnt++] = i; // 否则无法匹配,记录
        }
      }
    }
    if (!st.empty())
      while (!st.empty()) {
        b[cnn++] = st.top();
        st.pop();
      } // 栈内数据(下标)的出栈
    for (int i = 1; i < cnn; i++) {
      ans[b[i]] = '$'; // 在ans内标记
    }
    for (int i = 1; i < cnt; i++) {
      ans[a[i]] = '?'; // 在ans内标记
    }
    cout << s << endl;
    for (int i = 0; i < s.size(); i++) {
      if (ans[i] == 0)
        cout << " ";
      if (ans[i] == '$')
        cout << "$";
      if (ans[i] == '?')
        cout << "?"; // 格式转化
    }
    cout << endl;
  }
  return 0;
}
//解法2:递归
#include <bits/stdc++.h>
using namespace std;
#define N 105
char s[N], sign[N];
int si, len;
void find()//找下一个右括号 如果找到,si指向右括号 如果没找到,做标记 
{
    int lp = si;//当前左括号的下标 
    si++;
    while(si < len)
    {
        if(s[si] == ')')
            return;
        else if(s[si] == '(')
            find();
        si++;
    }
    sign[lp] = '$';//没有找到右括号,左括号的位置标记为$ 
}
int main()
{
 while(cin >> s)
 {
     len = strlen(s);
  for(int i = 0; i < len; ++i)//初始化sign字符串为空格 
            sign[i] = ' ';
        sign[len] = '\0';
        si = 0;
        while(si < len)
        {
            if(s[si] == ')')//右括号的位置标记为? 
                sign[si] = '?';
            else if(s[si] == '(')
                find();
            si++;
        }
        cout << s << endl << sign << endl;
 }
 return 0;
}


题目详情
34 简答题 偏难 C/C++编程考级 ·C/C++编程六级 · 1 栈与队列

stack or queue(2024-3-6级)

栈和队列都是常用的线性结构,它们都提供两个操作:

Push:加入一个元素。

Pop:弹出一个元素。

不同的是,栈是”先进后出”,而队列则是”先进先出”。

给出一个线性结构的进出顺序,判定这个结构是栈还是队列。

时间限制:1000

内存限制:65535

输入

第一行输入一个整数t,代表有t组测试数据 对于每组测试数据,第一行输入一个整数n,代表操作的次数。 随后输入n行,每行包含两个整数 type val。 当type = 1时,表示该次操作为push操作,val表示进入的数字。当type=2时,表示该次操作为pop操作,val代表出来的数字。 3<=n<=2000

输出

每组测试数据输出一行。 输出该组数据对应的线性结构,”Stack” 或者 “Queue”。 题目保证是栈或者队列的一种。


样例输入

2
6
1 1
1 2
1 3
2 3
2 2
2 1
4
1 1
1 2
2 1
2 2

样例输出

Stack
Queue
答案与解析
参考答案
//参考代码1
#include <deque>
#include <iostream>

using namespace std;
int main() {
  int t;
  scanf("%d", &t);
  deque<int> ds; // imitating stack
  for (int i = 0; i < t; i++) {
    int n;
    bool tag = false;
    scanf("%d", &n);
    for (int j = 0; j < n; j++) {
      int type, val;
      scanf("%d%d", &type, &val);
      if (tag)
        continue;
      if (type == 1) {
        ds.push_back(val);
      } else {
        int s = ds.back();
        ds.pop_back();
        if (s != val) {
          printf("Queue\n");
          tag = true;
        }
      }
    }
    if (!tag)
      printf("Stack\n");
    ds.clear();
  }
}
//参考代码2
#include <bits/stdc++.h>

using namespace std;
string Struct;
bool H;
int push[2005];
int pop[2005];
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		int n,type,val,Innum=0,Outnum=0;
		cin>>n;
		for(int i=0;i<n;++i)
		{
			cin>>type>>val;
			if(type==1)
			{
				push[Innum++]=val;
			}
			else
			{
				pop[Outnum++]=val;
			}
		}
		int num=min(Innum,Outnum);
		H=false;
		for(int i=0;i<num;++i)
		{
			if(push[i]!=pop[i])
			{
				Struct="Stack";
				H=true;
				break;
			}
		}
		if(!H) Struct="Queue";
		cout<<Struct<<endl;
	} 
	return 0;
}


题目详情
35 简答题 偏难 C/C++编程考级 ·C/C++编程六级 · 1 栈与队列

利用队列进行数字排序(2024-3-6级)

对于 N 个数字, 有人提出了如下的排序策略:

例如, 对于数字 53、 47、 85、 38、 64、 23

先建立 10 个队列(0 到 9) , 用于存放数字的大小, 将这 N 个数字依个位存放入各自的队列之中, 然后再按队列 0 到队列 9 依次出队。

例如, 对于上面的数字, 依次进队后, 结果如下:

队列 3: 53、 23 队列 4: 64 队列 5: 85 队列 7: 47 队列 8: 38

将其依次出队后, 结果为 53,23,64,85,47,38

然后, 再将方才出队后的队对, 依照十位放入各自的队列之中, 然后再按队列 0 到队列 9 依次出队

例如, 对于上面刚刚出队的序列 53,23,64,85,47,38, 将其依次进队,结果如下:

队列 2: 23 队列 3: 38 队列 4: 47 队列 5: 53 队列 6: 64 队列 8: 85

将其依次出队后, 结果为 23,38,47,53,64,85.因为这组数字最大只是两位数, 所以排序结束。

如果还有更大的数字, 那么, 接下来就是其百位、 千位……(如果位数不够, 就补 0.比如最大的数字是四位数, 那么数字 23 就当成 0023处理)

请根据上述算法, 对这些数字进行排序

时间限制: 1000

内存限制: 65535

输入

分为两行, 第一行为一个数字 N(1 <= N <= 1000), 表示数字的个数第二行为 N 个数字(都是非负数) , 以空格相隔, 最大的数字不超过9999

输出

输出两个部分 第一个部分为第一次进队出队的结果, 先显示一行:Step1. 之后用Queue0:...表示, 共 10 行, 结果用空格分隔, 下同 之后为第二次进队出队的结果(如果需要第二次进队出队的话) , 先显示一行: Step2. 之后仍然用 Queue0:...表示, 共 10 行 之后如果需要的话, 则分别显示第三次、 第四次的进队出队结果 第二部分为一行,即将数字排序后的结果(升序排序)


样例输入

20
41 67 34 0 69 24 78 58 62 64 5 45 81 27 61 91 95 42 27 36

样例输出

Step1.
Queue0:0
Queue1:41 81 61 91
Queue2:62 42
Queue3:
Queue4:34 24 64
Queue5:5 45 95
Queue6:36
Queue7:67 27 27
Queue8:78 58
Queue9:69
Step2.
Queue0:0 5
Queue1:
Queue2:24 27 27
Queue3:34 36
Queue4:41 42 45
Queue5:58
Queue6:61 62 64 67 69
Queue7:78
Queue8:81
Queue9:91 95
0 5 24 27 27 34 36 41 42 45 58 61 62 64 67 69 78 81 91 95
答案与解析
参考答案
#include <math.h>
#include <stdio.h>
#include <stdlib.h>

#define ElemType int
#define MaxSize 2000
typedef struct ss {
  ElemType data[MaxSize];
  int front, rear;
} SqQueue;
void InitQueue(SqQueue *&q) {
  q = (SqQueue *)malloc(sizeof(SqQueue));
  q->front = q->rear = -1;
}
void DestoryQueue(SqQueue *&q) { free(q); }
bool QueueEmpty(SqQueue *q) { return (q->front == q->rear); }
bool enQueue(SqQueue *&q, ElemType e) {
  if (q->rear == MaxSize - 1)
    return false;
  q->rear++;
  q->data[q->rear] = e;
  return true;
}
bool deQueue(SqQueue *&q, ElemType &e) {
  if (q->rear == q->front)
    return false;
  q->front++;
  e = q->data[q->front];
  return true;
}
int Num(int h) // 返回h的位数
{
  int i = 0;
  if (h == 0)
    return 1;
  while (h > 0) {
    i++;
    h /= 10;
  }
  return i;
}
int data(int g, int num) // 返回num的第g位数字
{
  int result, i = 1;
  int k = Num(num); // 获取位数
  if (num == 0 || g > k)
    return 0;
  else if (num <= 9 && g == 1)
    return num;

  while (num >= 10 && i < g) {
    num /= 10;
    i++;
  }
  result = num % 10;
  return result;
}
int main() {
  int n, i = 0, j, a[100], max = 0, k = 0, e, t = 0;
  scanf("%d\n", &n);
  SqQueue *q[10];
  for (i = 0; i < 10; i++) {
    InitQueue(q[i]);
  }

  for (i = 0; i < n; i++) {
    if (i != n - 1)
      scanf("%d ", &a[i]);
    else
      scanf("%d", &a[i]);
  }                       // a[i]='\0';
  for (i = 0; i < n; i++) // 找出最大值
  {
    k = Num(a[i]);
    if (k > max)
      max = k;
  }
  //  printf("%d\n",max);
  for (i = 1; i <= max; i++) //
  {
    printf("Step%d.\n", i);

    for (j = 0; j < 10; j++) { // 建立0-9的队对应的数字并输出
      for (k = 0; k < n; k++) {
        if (data(i, a[k]) == j)
          enQueue(q[j], a[k]);
      }
    }
    t = 0;
    for (j = 0; j < 10; j++) {
      printf("Queue%d:", j);
      while (!QueueEmpty(q[j])) {
        deQueue(q[j], e);
        a[t++] = e;
        printf("%d ", e);
      }
      printf("\n");
    }
    // printf("\n");
  }
  for (i = 0; i < n; i++) {
    printf("%d ", a[i]);
  }
  printf("\n");
  system("pause");
  return 0;
}


题目详情
36 简答题 偏难 C/C++编程考级 ·C/C++编程六级 · 1 栈与队列

堆宝塔

堆宝塔游戏是让小朋友根据抓到的彩虹圈的直径大小,按照从大到小的顺序堆起宝塔。但彩虹圈不一定是按照直径的大小顺序抓到的。聪明宝宝采取的策略如下:

- 首先准备两根柱子,一根 A 柱串宝塔,一根 B 柱用于临时叠放。

- 把第 1 块彩虹圈作为第 1 座宝塔的基座,在 A 柱放好。

- 将抓到的下一块彩虹圈 C 跟当前 A 柱宝塔最上面的彩虹圈比一下,如果比最上面的小,就直接放上去;否则把 C 跟 B 柱最上面的彩虹圈比一下:

-- 如果 B 柱是空的、或者 C 大,就在 B 柱上放好;

-- 否则把 A 柱上串好的宝塔取下来作为一件成品;然后把 B 柱上所有比 C 大的彩虹圈逐一取下放到 A 柱上,最后把 C 也放到 A 柱上。

重复此步骤,直到所有的彩虹圈都被抓完。最后 A 柱上剩下的宝塔作为一件成品,B 柱上剩下的彩虹圈被逐一取下,堆成另一座宝塔。问:宝宝一共堆出了几个宝塔?最高的宝塔有多少层?

时间限制:1000

内存限制:262144

输入

输入第一行给出一个正整数 N(≤ 103),为彩虹圈的个数。第二行按照宝宝抓取的顺序给出 N 个不超过 100 的正整数,对应每个彩虹圈的直径。

输出

在一行中输出宝宝堆出的宝塔个数,和最高的宝塔的层数。数字间以 1 个空格分隔,行首尾不得有多余空格。

样例输入

11
10 8 9 5 12 11 4 3 1 9 15

样例输出

4 5

提示

样例解释: 

宝宝堆成的宝塔顺次为: - 10、8、5 - 12、11、4、3、1 - 9 - 15、9

答案与解析
参考答案
#include<bits/stdc++.h>
using namespace std;
int max(int a,int b)
{
	return a>b?a:b;
}
int main()
{
	int n;
	cin>>n;
	stack<int>A,B;
	int count=0;
	int max1=0;
	while(n--)
	{
		int C;
		cin>>C;
		if(A.empty()||C<A.top())
			A.push(C);
		else
		{
			if(B.empty()||C>B.top())
				B.push(C);
			else
			{
				max1=max(max1,A.size());
				while(A.size())
					A.pop();
				count++;
				while(!B.empty()&&B.top()>C)
				{
					A.push(B.top());
					B.pop();
				}
				A.push(C);
			}
		}
	}
	if(!A.empty())
	{
		max1=max(max1,A.size());
		count++;
		while(!A.empty())
		{
			A.pop();
		}
	}
	if(!B.empty())
	{
		max1=max(max1,B.size());
		count++;
		while(!B.empty())
		{
			B.pop();
		}
	}
	cout<<count<<" "<<max1;
}
题目详情
37 简答题 偏难 C/C++编程考级 ·C/C++编程六级 · 1 栈与队列

一头进两头出

某队列允许在其两端进行出队操作,但仅允许在一端进行入队操作。现给定入队的序列,请你判断一系列出队序列是否可能。例如按 1、2、3、4、5 的顺序入队,则 1、3、2、5、4 这样的出队序列是可以得到的,但 5、1、3、2、4 就是不可能得到的。

时间限制:1000

内存限制:262144

输入

输入首先在一行中给出两个正整数 N 和 K(≤ 10),分别是入队元素的个数和待查验的序列个数。随后一行给出 N 个两两不同的整数组成的入队序列;再跟着 K 行,每行给出由 N 个入队整数组成的出队序列。同行整数间以空格分隔。

输出

对每个需要查验的出队序列,如果是可能的,则在一行中输出 `yes`,否则输出 `no`。

样例输入

5 4
10 2 3 4 5
10 3 2 5 4
5 10 3 2 4
2 3 10 4 5
3 5 10 4 2

样例输出

yes
no
yes
yes
答案与解析
参考答案

整理中……

题目详情
38 简答题 偏难 C/C++编程考级 ·C/C++编程六级 · 1 栈与队列

学生课表

某大学有 40000 名学生,开了 2500 门课。给定所有课程的选课名单,你的任务是为每一位前来查询的学生打印其选课的课表。

时间限制:2000

内存限制:262144

输入

输入第一行给出 2 个正整数:N(≤ 40000)为查询课表的学生人数;K(≤ 2500)为课程总数。 下面给出每门课的选课名单(课程从 1 到 K 编号),格式为: 课程编号 选课人数 学生姓名1 学生姓名2 ... 其中 选课人数 不超过 200 人。学生姓名由 3 个英文大写字母和 1 位数字组成。 最后一行给出 N 个前来查询的学生姓名。 一行中的数字和姓名都以空格分隔。

输出

对每个前来查询的学生,在一行中输出学生的姓名、选课门数、升序输出的课程编号,其间以 1 个空格分隔。行首尾不得有多余空格。

样例输入

11 5
4 7
BOB5 DON2 FRA8 JAY9 KAT3 LOR6 ZOE1
1 4
ANN0 BOB5 JAY9 LOR6
2 7
ANN0 BOB5 FRA8 JAY9 JOE4 KAT3 LOR6
3 1
BOB5
5 9
AMY7 ANN0 BOB5 DON2 FRA8 JAY9 KAT3 LOR6 ZOE1
ZOE1 ANN0 BOB5 JOE4 JAY9 FRA8 DON2 AMY7 KAT3 LOR6 NON9

样例输出

ZOE1 2 4 5
ANN0 3 1 2 5
BOB5 5 1 2 3 4 5
JOE4 1 2
JAY9 4 1 2 4 5
FRA8 3 2 4 5
DON2 2 4 5
AMY7 1 5
KAT3 3 2 4 5
LOR6 4 1 2 4 5
NON9 0
答案与解析
参考答案
#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <algorithm>

using namespace std;

// 比较函数,用于对课程编号进行升序排序
bool compareCourse(const int& a, const int& b) {
    return a < b;
}

int main() {
    int N, K;
    cin >> N >> K;

    // 使用哈希表存储每门课程的选课学生姓名
    unordered_map<int, vector<string>> courseToStudents;

    // 读取每门课程的选课名单
    for (int i = 0; i < K; ++i) {
        int courseId, numStudents;
        cin >> courseId >> numStudents;

        vector<string> students;
        for (int j = 0; j < numStudents; ++j) {
            string studentName;
            cin >> studentName;
            students.push_back(studentName);
            courseToStudents[courseId].push_back(studentName);
        }
    }

    // 读取前来查询的学生姓名
    vector<string> queryStudents;
    for (int i = 0; i < N; ++(i)) {
        string studentName;
        cin >> studentName;
        queryStudents.push_back(studentName);
    }

    // 为每个查询的学生打印课表
    for (const string& studentName : queryStudents) {
        vector<int> selectedCourses;

        // 遍历所有课程,查找该学生所选的课程
        for (const auto& coursePair : courseToStudents) {
            const vector<string>& students = coursePair.second;
            if (find(students.begin(), students.end(), studentName)!= students.end()) {
                selectedCourses.push_back(coursePair.first);
            }
        }

        // 对所选课程进行升序排序
        sort(selectedCourses.begin(), selectedCourses.end(), compareCourse);

        // 输出学生课表信息
        cout << studentName << " " << selectedCourses.size() << " ";
        for (int courseId : selectedCourses) {
            cout << courseId << " ";
        }
        cout << endl;
    }

    return 0;
}
题目详情
39 简答题 偏难 C/C++编程考级 ·C/C++编程六级 · 1 栈与队列

删除字符串

image1.png

image2.png

答案与解析
参考答案
#include <iostream>
#include <string>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s, stk;
    cin >> s;
    for (char c : s) {
        stk.push_back(c);
        // 长度够3个字符才可以校验XYZ
        if (stk.size() >= 3) {
            int len = stk.size();
            if (stk[len - 3] == 'X' && stk[len - 2] == 'Y' && stk[len - 1] == 'Z') {
                // 弹出末尾三位
                stk.pop_back();
                stk.pop_back();
                stk.pop_back();
            }
        }
    }
    cout << stk << '\n';
    return 0;
}
题目详情
40 简答题 偏难 C/C++编程考级 ·C/C++编程六级 · 1 栈与队列

空间折叠

image3.png

image4.png

image5.png

image6.png

答案与解析
参考答案
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
const int MAXN = 1005;
const int INF = 0x3f3f3f3f;

int H, W;
char grid[MAXN][MAXN];
int dist[MAXN][MAXN];
// 普通四方向步行偏移
int dir4[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> H >> W;
    int ch, cw, dh, dw;
    cin >> ch >> cw >> dh >> dw;
    // 输入下标1转0
    int sx = ch - 1, sy = cw - 1;
    int tx = dh - 1, ty = dw - 1;
    for (int i = 0; i < H; i++) cin >> grid[i];

    memset(dist, 0x3f, sizeof dist);
    dist[sx][sy] = 0;
    deque<pii> dq;
    dq.emplace_back(sx, sy);

    while (!dq.empty())
    {
        auto [x, y] = dq.front();
        dq.pop_front();
        int curCost = dist[x][y];
        // 到达终点直接提前输出答案
        if (x == tx && y == ty) break;
        // 行动1:步行,代价0
        for (auto &d : dir4)
        {
            int nx = x + d[0], ny = y + d[1];
            if (nx < 0 || nx >= H || ny < 0 || ny >= W) continue;
            if (grid[nx][ny] == '#') continue;
            if (dist[nx][ny] > curCost)
            {
                dist[nx][ny] = curCost;
                dq.emplace_front(nx, ny);
            }
        }
        // 行动2:空间折叠,5*5范围,代价+1
        for (int dr = -2; dr <= 2; dr++)
        {
            for (int dc = -2; dc <= 2; dc++)
            {
                int nx = x + dr, ny = y + dc;
                if (nx < 0 || nx >= H || ny < 0 || ny >= W) continue;
                if (grid[nx][ny] == '#') continue;
                if (dist[nx][ny] > curCost + 1)
                {
                    dist[nx][ny] = curCost + 1;
                    dq.emplace_back(nx, ny);
                }
            }
        }
    }
    int ans = dist[tx][ty];
    cout << (ans == INF ? -1 : ans) << '\n';
    return 0;
}
题目详情