C/C++编程六级 题库
栈基本操作
依次读入序列元素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;
}双端队列
定义一个双端队列,进队操作与普通队列一样,从队尾进入。出队操作既可以从队头,也可以从队尾。编程实现这个数据结构。
时间限制: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;
}生日相同 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;
}合法出栈序列
给定一个由不同小写字母构成的长度不超过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;
}括号画家(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";
}表达式求值
求一个可能包含加、减、乘、除、乘方运算的中缀表达式的值。
在计算机中,我们常用栈来解决这一问题。首先将中缀表达式转换到后缀表达式,然后对后缀表达式求值。
加、减、乘、除、乘方分别用+,-,*, /, ^来表示。表达式可以有圆括号()。
时间限制: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;
}队列和栈(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;
}奇怪的括号(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;
}中缀表达式的值(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;
}智能陪护
智能陪护系统是一个自动为老人们分配机器人护工的系统。系统中有若干个机器人排队候选,当有老人下单时,系统自动将队列最前面的机器人派送给老人,该机器人就在老人下单的当天上岗了。当老人结算时,这个机器人就立刻结束任务,回到队列末尾排队等待下一次任务,必要时可以在当天就开始接任务。
本题就请你实现这样一个自动分配功能。
时间限制: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;
}词频统计
请编写程序,对一段英文文本,统计其中所有不同单词的个数,以及词频最大的前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;
}小白鼠再排队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;
}
}扩号匹配问题(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;
}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;
}利用队列进行数字排序(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;
}堆宝塔
堆宝塔游戏是让小朋友根据抓到的彩虹圈的直径大小,按照从大到小的顺序堆起宝塔。但彩虹圈不一定是按照直径的大小顺序抓到的。聪明宝宝采取的策略如下:
- 首先准备两根柱子,一根 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;
}一头进两头出
某队列允许在其两端进行出队操作,但仅允许在一端进行入队操作。现给定入队的序列,请你判断一系列出队序列是否可能。例如按 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
整理中……
学生课表
某大学有 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;
}删除字符串


#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;
}空间折叠




#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;
}