C/C++编程（1~8级）全部真题・点这里
第1题：区间合并
给定 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
这个问题可以通过对输入的闭区间进行合并操作来解决。我们可以使用一个变量来追踪当前的合并区间范围，并根据每个输入的闭区间更新这个范围。
首先，我们可以将输入的闭区间按照左边界从小到大进行排序。
然后，我们可以使用两个变量start和end来表示当前的合并区间范围，初始值分别为第一个闭区间的左右边界。
接下来，我们可以遍历排序后的闭区间列表，对于每个闭区间，检查它是否与当前的合并区间相交或相邻。如果相交或相邻，则更新当前的合并区间范围，将start更新为当前闭区间的左边界，将end更新为当前闭区间的右边界。
最后，如果遍历完所有闭区间后，最终的合并区间范围等于输入的闭区间列表的最小和最大值，就说明这些区间可以最终合并为一个闭区间，输出这个闭区间的左右边界；否则输出"no"。
以下是一个用C语言实现的解答示例：
#include <stdio.h>
#include <stdlib.h>
typedef struct {
int left;
int right;
} Interval;
int compare(const void *a, const void *b) {
Interval *intervalA = (Interval *)a;
Interval *intervalB = (Interval *)b;
return intervalA->left - intervalB->left;
}
int main() {
int n;
scanf("%d", &n);
Interval intervals[n];
int i;
for (i = 0; i < n; i++) {
scanf("%d %d", &(intervals[i].left), &(intervals[i].right));
}
qsort(intervals, n, sizeof(Interval), compare);
int start = intervals[0].left;
int end = intervals[0].right;
for (i = 1; i < n; i++) {
if (intervals[i].left <= end) {
if (intervals[i].right > end) {
end = intervals[i].right;
}
} else {
printf("no\n");
return 0;
}
}
if (start == intervals[0].left && end == intervals[n - 1].right) {
printf("%d %d\n", start, end);
} else {
printf("no\n");
}
return 0;
}
该程序首先定义了一个表示闭区间的结构体（Interval），其中包括左边界和右边界属性。
在主函数中，首先读取区间的数量n，并创建用于存储所有闭区间的数组（intervals）。
然后，使用一个循环从输入中读取每个闭区间的左边界和右边界，并将其存储在对应的数组元素中。
接下来，使用qsort函数对闭区间数组进行排序，排序规则由compare函数定义。compare函数按照左边界从小到大的顺序进行排序。
然后，创建两个变量（start和end），并将它们的初始值设置为第一个闭区间的左边界和右边界。
使用一个循环遍历排序后的闭区间数组，对于每个闭区间，判断它是否与当前的合并区间相交或相邻。如果相交或相邻，则更新当前的合并区间范围，将start更新为当前闭区间的左边界，将end更新为当前闭区间的右边界。
最后，如果遍历完所有闭区间后，最终的合并区间范围的左边界等于闭区间数组的最小值，且右边界等于闭区间数组的最大值，就说明这些区间可以最终合并为一个闭区间，输出这个闭区间的左右边界；否则输出"no"。
注意：为了方便起见，该程序假设输入的闭区间已经按照左边界从小到大进行了排序。如果输入的闭区间没有排序，你可以在读取完所有闭区间后使用qsort函数进行排序。
另外，该程序使用了C标准库中的函数，因此需要包含相应的头文件（stdio.h和stdlib.h）。
第2题：电话号码
给你一些电话号码，请判断它们是否是一致的，即是否有某个电话是另一个电话的前缀。比如：
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
这个问题可以通过构建一个前缀树（Trie）来解决。前缀树是一种树状数据结构，用于存储一组字符串，并支持高效地查找字符串的前缀。
首先，我们可以定义一个前缀树节点的结构，包括一个布尔变量isEnd表示是否是一个字符串的结尾，以及一个指向子节点的指针数组。
然后，我们可以使用一个函数来构建前缀树。对于每个电话号码，我们从根节点开始，依次遍历号码的每一位数字。如果当前数字对应的子节点不存在，我们就创建一个新的节点，并更新当前节点的子节点指针。然后，将当前节点指向子节点，并继续遍历下一位数字。最后，将当前节点的isEnd标记设置为true，表示当前节点是一个电话号码的结尾。
接下来，我们可以使用另一个函数来判断一组电话号码是否一致。对于每个电话号码，我们从根节点开始，依次遍历号码的每一位数字。如果当前节点的isEnd标记为true，说明当前号码是另一个号码的前缀，返回"NO"。如果当前数字对应的子节点不存在，说明当前号码不是任何号码的前缀，返回"YES"。否则，将当前节点指向子节点，并继续遍历下一位数字。如果遍历完所有号码后都没有返回"NO"，则返回"YES"。
下面是一个用C语言实现的解答示例：
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#define NUM_CHILDREN 10
typedef struct TrieNode {
bool isEnd;
struct TrieNode* children[NUM_CHILDREN];
} TrieNode;
TrieNode* createNode() {
TrieNode* node = (TrieNode*)malloc(sizeof(TrieNode));
node->isEnd = false;
memset(node->children, 0, sizeof(node->children));
return node;
}
void insert(TrieNode* root, char* phoneNumber) {
TrieNode* curr = root;
int len = strlen(phoneNumber);
for (int i = 0; i < len; i++) {
int index = phoneNumber[i] - '0';
if (curr->children[index] == NULL) {
curr->children[index] = createNode();
}
curr = curr->children[index];
}
curr->isEnd = true;
}
bool isConsistent(TrieNode* root, char* phoneNumber) {
TrieNode* curr = root;
int len = strlen(phoneNumber);
for (int i = 0; i < len; i++) {
int index = phoneNumber[i] - '0';
if (curr->isEnd) {
return false;
}
if (curr->children[index] == NULL) {
return true;
}
curr = curr->children[index];
}
return true;
}
void freeTrie(TrieNode* root) {
if (root == NULL) {
return;
}
for (int i = 0; i < NUM_CHILDREN; i++) {
freeTrie(root->children[i]);
}
free(root);
}
int main() {
int t;
scanf("%d", &t);
while (t--) {
int n;
scanf("%d", &n);
TrieNode* root = createNode();
bool consistent = true;
while (n--) {
char phoneNumber[11];
scanf("%s", phoneNumber);
if (consistent) {
if (!isConsistent(root, phoneNumber)) {
consistent = false;
}
insert(root, phoneNumber);
}
}
if (consistent) {
printf("YES\n");
} else {
printf("NO\n");
}
freeTrie(root);
}
return 0;
}
该程序首先定义了一个前缀树节点的结构体（TrieNode），其中包括一个布尔变量isEnd表示是否是一个字符串的结尾，以及一个指向子节点的指针数组。
第3题：扑克牌排序
假设这里有36张扑克牌，分别为A1
A9,B1B9,C1C9,D1D9，其中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个队列即可。
下面是用C语言编写的扑克牌排序程序，使用队列实现：
#include <stdio.h>
#include <stdlib.h>
#define MAX_CARDS 100
#define MAX_QUEUE_SIZE 9
// 定义扑克牌结构体
typedef struct {
char suit; // 花色
int number; // 点数
} Card;
// 定义队列结构体
typedef struct {
Card cards[MAX_CARDS];
int front;
int rear;
} Queue;
// 初始化队列
void initQueue(Queue *queue) {
queue->front = 0;
queue->rear = -1;
}
// 判断队列是否为空
int isQueueEmpty(Queue *queue) {
return queue->front > queue->rear;
}
// 入队
void enqueue(Queue *queue, Card card) {
queue->rear++;
queue->cards[queue->rear] = card;
}
// 出队
Card dequeue(Queue *queue) {
Card card = queue->cards[queue->front];
queue->front++;
return card;
}
// 按花色入队
void enqueueBySuit(Queue *queues, char suit, Card card) {
int index;
switch (suit) {
case 'A':
index = 0;
break;
case 'B':
index = 1;
break;
case 'C':
index = 2;
break;
case 'D':
index = 3;
break;
default:
return;
}
enqueue(&queues[index], card);
}
// 按花色出队
void dequeueBySuit(Queue *queues, char suit, Queue *resultQueue) {
int index;
switch (suit) {
case 'A':
index = 0;
break;
case 'B':
index = 1;
break;
case 'C':
index = 2;
break;
case 'D':
index = 3;
break;
default:
return;
}
while (!isQueueEmpty(&queues[index])) {
Card card = dequeue(&queues[index]);
enqueue(resultQueue, card);
}
}
// 比较两张牌的大小
int compareCards(Card card1, Card card2) {
if (card1.suit != card2.suit) {
switch (card1.suit) {
case 'D':
return -1;
case 'C':
if (card2.suit == 'D')
return 1;
else
return -1;
case 'B':
if (card2.suit == 'D' || card2.suit == 'C')
return 1;
else
return -1;
case 'A':
if (card2.suit == 'D' || card2.suit == 'C' || card2.suit == 'B')
return 1;
else
return -1;
}
} else {
return card1.number - card2.number;
}
return 0;
}
// 扑克牌排序
void sortCards(Card *cards, int n) {
Queue queues[MAX_QUEUE_SIZE]; // 9个队列
Queue resultQueue; // 结果队列
Card sortedCards[MAX_CARDS]; // 排序后的牌
int i, j;
// 初始化队列
for (i = 0; i < MAX_QUEUE_SIZE; i++) {
initQueue(&queues[i]);
}
initQueue(&resultQueue);
// 第一次进队出队，按点数入队
for (i = 0; i < n; i++) {
enqueueBySuit(queues, cards[i].suit, cards[i]);
}
printf("Queue1:");
while (!isQueueEmpty(&queues[0])) {
Card card = dequeue(&queues[0]);
printf(" %c%d", card.suit, card.number);
enqueue(&resultQueue, card);
}
printf("\n");
// 第二次进队出队，按花色入队
for (i = 0; i < MAX_QUEUE_SIZE; i++) {
dequeueBySuit(queues, 'A' + i, &resultQueue);
}
printf("QueueA:");
for (i = 0; i < MAX_QUEUE_SIZE; i++) {
while (!isQueueEmpty(&queues[i])) {
Card card = dequeue(&queues[i]);
printf(" %c%d", card.suit, card.number);
enqueue(&resultQueue, card);
}
}
printf("\n");
// 排序后的结果
printf("Result:");
i = 0;
while (!isQueueEmpty(&resultQueue)) {
sortedCards[i] = dequeue(&resultQueue);
printf(" %c%d", sortedCards[i].suit, sortedCards[i].number);
i++;
}
printf("\n");
}
int main() {
int n;
scanf("%d", &n);
Card cards[MAX_CARDS];
int i;
// 读取扑克牌
for (i = 0; i < n; i++) {
char suit;
int number;
scanf(" %c%d", &suit, &number);
cards[i].suit = suit;
cards[i].number = number;
}
// 扑克牌排序
sortCards(cards, n);
return 0;
}
使用上述代码，你可以输入扑克牌的数量和每张牌的花色与点数，然后程序将按照给定的排序规则进行排序，并输出进队出队的结果和排序后的结果。
第4题：现代艺术
在对二维艺术作品感到厌烦之后，伟大的艺术牛Picowso决定从事创作一项更为小众的艺术形式，一维画。
尽管目前她的画作可以用一个由颜色组成的长度为N(1100000)的数组表示，但她的创作风格依然保持不变：从一张空白的矩形画布上，不断地画上一些矩形，在一维的情况下，这些矩形就只是一个区间。她用N种颜色，颜色编号为1N进行创作，每种颜色只使用一次，之后使用的颜色可以完全的覆盖之前在相同位置上的颜色。
令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，所以共需两轮。
下面是解决这个问题的C语言代码：
#include <stdio.h>
#include <stdlib.h>
int main() {
int N;
scanf("%d", &N);
int *colors = (int *)malloc((N+1) * sizeof(int));
int *visited = (int *)calloc((N+1), sizeof(int));
for (int i = 1; i <= N; i++) {
scanf("%d", &colors[i]);
}
int rounds = 0;
int maxIndex = 0;
while (maxIndex < N) {
int nextMaxIndex = maxIndex;
for (int i = 1; i <= N; i++) {
if (!visited[i] && colors[i] == maxIndex + 1) {
visited[i] = 1;
nextMaxIndex = i;
}
}
if (nextMaxIndex == maxIndex) {
printf("-1\n");
free(colors);
free(visited);
return 0;
}
maxIndex = nextMaxIndex;
rounds++;
}
printf("%d\n", rounds);
free(colors);
free(visited);
return 0;
}
该程序首先读取输入的整数N，表示颜色的数量。然后，它使用动态内存分配来创建两个数组：colors和visited。colors数组用于存储每个格点的颜色，visited数组用于跟踪已经访问的格点。
接下来，程序使用循环读取N行输入，并将每个颜色存储在colors数组中。
然后，程序开始模拟Moonet复制画作的过程。它使用一个循环来找到当前未被访问的、具有最大颜色值（maxIndex + 1）的格点，并将其标记为已访问。然后，它更新maxIndex为该格点的索引，并增加回合数。
如果在某个回合中找不到未访问的、具有最大颜色值的格点，则说明无法复制Picowso的画作，程序输出-1并结束。
最后，程序输出回合数，并释放动态分配的内存。
