2022-12-10青少年软件编程（C语言）等级考试试卷（六级）解析

2022-12-10青少年软件编程（C语言）等级考试试卷（六级）解析
T1、区间合并
给定 n 个闭区间 [ai; bi]，其中i=1,2,...,n。任意两个相邻或相交的闭区间可以合并为一个闭区间。例如，[1;2] 和 [2;3] 可以合并为 [1;3]，[1;3] 和 [2;4] 可以合并为 [1;4]，但是[1;2] 和 [3;4] 不可以合并。
我们的任务是判断这些区间是否可以最终合并为一个闭区间，如果可以，将这个闭区间输出，否则输出no。
时间限制：1000
内存限制：65536
输入
第一行为一个整数n，3 ≤ n ≤ 50000。表示输入区间的数量。 之后n行，在第i行上（1 ≤ i ≤ n），为两个整数 ai 和 bi ，整数之间用一个空格分隔，表示区间 [ai; bi]（其中 1 ≤ ai ≤ bi ≤ 10000）。
输出
输出一行，如果这些区间最终可以合并为一个闭区间，输出这个闭区间的左右边界，用单个空格隔开；否则输出 no。
样例输入
5
5 6
1 5
10 10
6 9
8 10
样例输出
1 10

//样例代码 结构体排序
#include <bits/stdc++.h>
using namespace std;
struct Nod{int x,y;friend bool operator <(Nod a,Nod b){if(a.x!=b.x)return a.x<b.x;else return a.y<b.y;}
}node[50005];
int main()
{	int n;cin>>n;for(int i=0;i<n;i++)cin>>node[i].x>>node[i].y;sort(node,node+n);int lf=node[0].x;int rt=node[0].y;for(int i=1;i<n;i++){if(lf<=node[i].x&&node[i].x<=rt){rt=max(rt,node[i].y);}else {cout<<"no";return 0;}}cout<<lf<<" "<<rt;return 0;
}

T2、电话号码
给你一些电话号码，请判断它们是否是一致的，即是否有某个电话是另一个电话的前缀。比如：
Emergency 911
Alice 97 625 999
Bob 91 12 54 26
在这个例子中，我们不可能拨通Bob的电话，因为Emergency的电话是它的前缀，当拨打Bob的电话时会先接通Emergency，所以这些电话号码不是一致的。
时间限制：1000
内存限制：65536
输入
第一行是一个整数t，1 ≤ t ≤ 40，表示测试数据的数目。 每个测试样例的第一行是一个整数n，1 ≤ n ≤ 10000，其后n行每行是一个不超过10位的电话号码。
输出
对于每个测试数据，如果是一致的输出“YES”，如果不是输出“NO”。
样例输入
2
3
911
97625999
91125426
5
113
12340
123440
12345
98346
样例输出
NO
YES

//示例代码
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
struct Trie
{int c[10],s;Trie(){memset(c,0,sizeof(c));s=0;}
}t[N];int tot;
void clear(int x)
{t[x].s=0;for(int i=0;i<=9;i++)if(t[x].c[i])clear(t[x].c[i]),t[x].c[i]=0;
}
char s[15];
bool bt(int x)
{int len=strlen(s+1);bool bk=false;for(int i=1;i<=len;i++){int y=s[i]-'0';if(!t[x].c[y])t[x].c[y]=++tot;else if(i==len)bk=true;x=t[x].c[y];if(t[x].s)bk=true;}t[x].s++;return bk;
}
int main()
{int T;scanf("%d",&T);while(T--){bool bk=false;clear(0);tot=0;int n;scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%s",s+1);if(bk)continue;if(bt(0))bk=true;}if(bk)puts("NO");else puts("YES");}return 0;
}

T3、扑克牌排序
假设这里有36张扑克牌，分别为A1~A9,B1~B9,C1~C9,D1~D9，其中A代表方片，B代表草花，C代表红桃，D代表黑桃，那么，设定如下的排序规则：
1.对于两张卡牌，X1Y1与X2Y2，X1与X2表示A～D，Y1与Y2表示1～9，如果X1与X2不同，那么依照D>C>B>A的方式进行排序
2.假如有X1与X2相同时，那么就比较Y1与Y2的大小。
例如，对于如下的四张牌，有如下的升序排序结果：
D3，C4，A4，C1
升序排序的结果为A4，C1，C4，D3
有人提出了如下的排序策略：
先建立9个队列，用于存放点数的大小，将卡牌依点数存放入各自的队列之中，然后再按队列1到队列9依次出队。
例如，对于上面的结果，依次进队后，结果如下：
队列1：C1；队列3：D3，队列4：C4，A4
将其依次出队后，结果为C1，D3，C4，A4
然后，再建立4个队列，用于存放花色。将卡牌依花色A～D存放入队列1～4中，然后再按队列1到队列4依次出队。
例如，对于上面刚刚出队的序列C1，D3，C4，A4，将其依次进队，结果如下：
队列1：A4；队列3：C1，C4；队列4：D3
将其依次出队后，结果为A4，C1，C4，D3，排序结束。
请根据上面的算法，编写一个用队列对扑克牌排序的程序，要求依照上面的排序规则，根据先花色后点数的方法进行排序。
时间限制：1000
内存限制：65536
输入
输入分为两行，第一行为一个整数n，表示一共有n张牌（1<=n<=100） 第二行用XY的形式表示每一张牌，其中X为A～D，Y为1～9
输出
输出三个部分 第一个部分为第一次进队出队的结果，用Queue1:...表示，共9行，结果用空格分隔，下同 第二部分为第二次进队出队的结果，用QueueA:...表示，共4行 第三部分为一行，即将卡牌排序后的结果（升序排序）
样例输入
8
D8 A6 C3 B8 C5 A1 B5 D3
样例输出
Queue1:A1
Queue2:
Queue3:C3 D3
Queue4:
Queue5:C5 B5
Queue6:A6
Queue7:
Queue8:D8 B8
Queue9:
QueueA:A1 A6
QueueB:B5 B8
QueueC:C3 C5
QueueD:D3 D8
A1 A6 B5 B8 C3 C5 D3 D8
提示
第二次入队出队时，可以复用第一次时9个队列中的4个。所以其实只需要开辟9个队列即可。

//示例代码 队列的基本操作 模拟一下即可
#include <bits/stdc++.h>
using namespace std;
int main()
{	int n;string s;queue<string> qn[9];queue<string> color[4];queue<string> qs;cin>>n;for(int i=1;i<=n;i++){cin>>s;int t=s[1]-'0'-1;qn[t].push(s);}for(int i=0;i<=8;i++){cout<<"Queue"<<i+1<<":";while(!qn[i].empty()){s=qn[i].front();switch (s[0]) {case 'A':color[0].push(s);break;case 'B':color[1].push(s);break;case 'C':color[2].push(s);break;case 'D':color[3].push(s);break;}qn[i].pop();cout<<s<<" ";}cout<<endl;	}for(int i=0;i<=3;i++){cout<<"Queue"<<(char)('A'+i)<<":";while(!color[i].empty()){s=color[i].front();color[i].pop();qs.push(s);cout<<s<<" ";}cout<<endl;	}while(!qs.empty()){cout<<qs.front()<<" ";qs.pop();}return 0;
}

T4、现代艺术
在对二维艺术作品感到厌烦之后，伟大的艺术牛Picowso决定从事创作一项更为小众的艺术形式，一维画。
尽管目前她的画作可以用一个由颜色组成的长度为N(1~100000)的数组表示，但她的创作风格依然保持不变：从一张空白的矩形画布上，不断地画上一些矩形，在一维的情况下，这些矩形就只是一个区间。她用N种颜色，颜色编号为1~N进行创作，每种颜色只使用一次，之后使用的颜色可以完全的覆盖之前在相同位置上的颜色。
令Picowso感到十分沮丧的是，她的竞争对手Moonet似乎弄明白了如何复制她的这些一维画作，Moonet会画一些不相交的间隔，等待这些颜色晾干，然后再画另外的一些间隔，直到画完。Moonet每次每种颜色最多只能画一个间隔，但是他可以一次画不同颜色不相交的多个间隔，只要这些间隔没有重叠部分。之后Moonet再进行下一轮绘制。请计算Moonet为了复制一幅画需要画几个回合。
时间限制：10000
内存限制：65536
输入
第一行是一个整数N，之后N行包含了N个整数，范围0到N表示纸带每个格点的颜色，0表示没有涂色。
输出
输出一行，需要复制这幅画作的最少回合数，如果这幅画不可能是Picowso的画作输出-1（比如说这幅画不可能是通过一次在一条上画一层的方法进行创作的）
样例输入
7
0
1
4
5
1
3
3
样例输出
2
提示
在这个样例中，第一轮涂成0111133，第二轮涂成0145133，所以共需两轮。

// 示例代码  栈的灵活应用
#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int end_pos[N], a[N];
int n, result, flag = 1;
char v[N];
stack<int> s;
int main(){scanf("%d", &n);for(int i = 1;i <= n;i += 1){scanf("%d", &a[i]);end_pos[a[i]] = i; //记录每个颜色的终点位置}v[0] = 1;// 初始化 将0视为覆盖整个画布的第一种颜色end_pos[0] = n + 1;s.push(0);  for(int i = 1;i <= n && flag;i++){if(s.top() != a[i]){if(v[a[i]]) flag = 0;//颜色被使用过 标记非法s.push(a[i]); //加入新的颜色}v[a[i]] = 1; //标记该颜色被使用过result = max(result, (int)s.size());	if(i == end_pos[a[i]]){s.pop();//该颜色最后一次被使用 弹出改颜色} }if(!flag) cout<<-1;else cout<<result-1;return 0;
}