第1题：stack or queue

栈和队列都是常用的线性结构，它们都提供两个操作：
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

以下是一个用C语言实现的解答示例：

#include <stdio.h>#define MAX_SIZE 2000typedef struct {int data[MAX_SIZE];int top;
} Stack;typedef struct {int data[MAX_SIZE];int front;int rear;
} Queue;void initStack(Stack *stack) {stack->top = -1;
}void initQueue(Queue *queue) {queue->front = 0;queue->rear = -1;
}void pushStack(Stack *stack, int value) {stack->data[++stack->top] = value;
}int popStack(Stack *stack) {return stack->data[stack->top--];
}void enqueue(Queue *queue, int value) {queue->data[++queue->rear] = value;
}int dequeue(Queue *queue) {return queue->data[queue->front++];
}int main() {int t;scanf("%d", &t);while (t--) {int n;scanf("%d", &n);int type, val;int isStack = 1; // Assume it's a stack initiallyint isQueue = 1; // Assume it's a queue initiallyStack stack;Queue queue;initStack(&stack);initQueue(&queue);while (n--) {scanf("%d %d", &type, &val);if (type == 1) {pushStack(&stack, val);enqueue(&queue, val);} else if (type == 2) {if (isStack) {if (val != popStack(&stack))isStack = 0;}if (isQueue) {if (val != dequeue(&queue))isQueue = 0;}}}if (isStack && !isQueue)printf("Stack\n");else if (!isStack && isQueue)printf("Queue\n");}return 0;
}

这个程序首先定义了栈（Stack）和队列（Queue）的结构体，然后实现了初始化栈和队列的函数。接下来，根据输入的操作类型和值，通过调用相应的函数来模拟栈和队列的操作。在每次出栈或出队列的操作中，都会判断是否满足栈或队列的特性，如果不满足，则将相应的标志位（isStack和isQueue）设置为0。最后，根据标志位的值输出结果。

注意：该程序假设输入的操作序列要么是栈，要么是队列，不能同时满足栈和队列的特性。

第2题：栈的基本操作

栈是一种重要的数据结构，它具有push k和pop操作。push k是将数字k加入到栈中，pop则是从栈中取一个数出来。
栈是后进先出的：把栈也看成横向的一个通道，则push k是将k放到栈的最右边，而pop也是从栈的最右边取出一个数。
假设栈当前从左至右含有1和2两个数，则执行push 5和pop操作示例图如下：
push 5 pop
1
栈 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
4
push 1
push 3
pop
push 5
1
pop
样例输出
1 5
error

以下是一个用C语言实现的解答示例：

#include <stdio.h>
#include <string.h>#define MAX_SIZE 100typedef struct {int data[MAX_SIZE];int top;
} Stack;void initStack(Stack *stack) {stack->top = -1;
}void push(Stack *stack, int value) {stack->data[++stack->top] = value;
}int pop(Stack *stack) {return stack->data[stack->top--];
}int isEmpty(Stack *stack) {return stack->top == -1;
}int main() {int m;scanf("%d", &m);while (m--) {int n;scanf("%d", &n);Stack stack;initStack(&stack);int i;char operation[5];int value;for (i = 0; i < n; i++) {scanf("%s", operation);if (strcmp(operation, "push") == 0) {scanf("%d", &value);push(&stack, value);} else if (strcmp(operation, "pop") == 0) {if (isEmpty(&stack)) {printf("error\n");break;} else {pop(&stack);}}}if (isEmpty(&stack))continue;while (!isEmpty(&stack)) {printf("%d ", pop(&stack));}printf("\n");}return 0;
}

该程序首先定义了栈（Stack）的结构体，然后实现了初始化栈、入栈（push）、出栈（pop）以及判断栈是否为空的函数。

在主函数中，首先读取测试数据的数量m，然后通过循环处理每组测试数据。对于每组测试数据，首先读取操作的数量n。随后，通过循环逐行读取操作，并根据操作类型执行相应的操作。如果收到pop操作时栈已经为空，则输出"error"，并跳出当前循环。在处理完n行操作后，如果栈不为空，则依次出栈并输出栈中的数字。

注意：根据题目要求，如果栈为空且仍然收到pop操作，则输出"error"。

第3题：发型糟糕的一天

农夫John 的N(1 ≤ N ≤ 80,000)只奶牛中，有一些也许正在经历发型糟糕的一天。每只奶牛对自己乱糟糟的发型都有自知之明，农夫John想知道所有奶牛能看到其他奶牛头顶的数量之和。
任意奶牛i身高记为 hi (1 ≤ hi ≤ 1,000,000,000)，所有奶牛面向东方（本题示意图的右面）依次站成一条线。因此，奶牛i能够看到在它前面的（奶牛i+1，i+2…）所有身高比它低的奶牛，直到被一头比它高的奶牛挡住
考虑如下的例子：
= =
= - = Cows facing right ->
= = =
= - = = =
= = = = = =
1 2 3 4 5 6 奶牛#1 可以看见奶牛#2, 3, 4的头顶
奶牛#2 无法看到任何奶牛的头顶
奶牛#3可以看见奶牛#4的头顶
奶牛#4无法看到任何奶牛的头顶
奶牛#5可以看见奶牛#6的头顶
奶牛#6无法看到任何奶牛的头顶!
用ci表示奶牛i能够看到头顶的奶牛个数；请计算c1 至cN的和。对于上面这个例子，其和为：3 + 0 + 1 + 0 + 1 + 0 = 5。
时间限制：2000
内存限制：65536
输入
第1行：奶牛数N第2行至N+1行：第i+1行包含一个整数，表示奶牛i的高度
输出
第1行：c1 至cN的累加和
样例输入
6
10
3
7
4
12
2
样例输出
5

这个问题可以通过使用栈来解决。我们可以从左到右遍历奶牛的身高，维护一个递增的栈，栈中存储的是奶牛的身高。

对于每只奶牛，我们需要找到它能看到的头顶奶牛数量。我们可以从栈顶开始，比较当前奶牛的身高和栈顶奶牛的身高。如果当前奶牛的身高大于栈顶奶牛的身高，那么栈顶奶牛就不会被当前奶牛看到，我们可以将其从栈中弹出。在这个过程中，我们可以计算栈顶奶牛能看到的头顶奶牛数量，并将其累加到最终的结果中。

最后，我们将当前奶牛的身高入栈。重复以上步骤直到遍历完所有的奶牛。

以下是一个用C语言实现的解答示例：

#include <stdio.h>#define MAX_SIZE 80000typedef struct {int height;int count;
} Cow;typedef struct {Cow data[MAX_SIZE];int top;
} Stack;void initStack(Stack *stack) {stack->top = -1;
}void push(Stack *stack, Cow value) {stack->data[++stack->top] = value;
}Cow pop(Stack *stack) {return stack->data[stack->top--];
}Cow top(Stack *stack) {return stack->data[stack->top];
}int main() {int N;scanf("%d", &N);Cow cows[MAX_SIZE];int i;for (i = 0; i < N; i++) {scanf("%d", &(cows[i].height));cows[i].count = 0;}Stack stack;initStack(&stack);long long total = 0;for (i = 0; i < N; i++) {while (stack.top >= 0 && cows[i].height >= top(&stack).height) {cows[i].count += top(&stack).count + 1;pop(&stack);}total += cows[i].count;push(&stack, cows[i]);}printf("%lld\n", total);return 0;
}

该程序首先定义了奶牛（Cow）和栈（Stack）的结构体。奶牛结构体包含奶牛的身高和能看到的头顶奶牛数量，栈结构体用于存储奶牛。

在主函数中，首先读取奶牛的数量N，并初始化奶牛数组。然后，使用一个循环从输入中读取每只奶牛的身高，并将其存储在奶牛数组中。同时，初始化一个栈。

接下来，使用一个循环遍历奶牛数组。对于每只奶牛，我们从栈顶开始，比较当前奶牛的身高和栈顶奶牛的身高。如果当前奶牛的身高大于栈顶奶牛的身高，我们将栈顶奶牛从栈中弹出，并计算栈顶奶牛能看到的头顶奶牛数量。然后，将这个数量累加到当前奶牛的count属性中。重复以上步骤直到当前奶牛的身高小于等于栈顶奶牛的身高。最后，将当前奶牛入栈。

在遍历完所有奶牛后，我们将每只奶牛的count属性累加到总和total中，并输出结果。

注意：由于结果可能非常大，所以使用了long long类型来保存总和total。

第4题：合影效果

小云和朋友们去爬香山，为美丽的景色所陶醉，想合影留念。如果他们站成一排，男生全部在左（从拍照者的角度），并按照从矮到高的顺序从左到右排，女生全部在右，并按照从高到矮的顺序从左到右排，请问他们合影的效果是什么样的（所有人的身高都不同）？
时间限制：1000
内存限制：65536
输入
第一行是人数n（2 <= n <= 40，且至少有1个男生和1个女生）。后面紧跟n行，每行输入一个人的性别（男male或女female）和身高（浮点数，单位米），两个数据之间以空格分隔。
输出
n个浮点数，模拟站好队后，拍照者眼中从左到右每个人的身高。每个浮点数需保留到小数点后2位，相邻两个数之间用单个空格隔开。
样例输入
6
male 1.72
male 1.78
female 1.61
male 1.65
female 1.70
female 1.56
样例输出
1.65 1.72 1.78 1.70 1.61 1.56

这个问题可以通过对输入进行处理，并按照规定的顺序排列人的身高来解决。

首先，我们可以创建一个结构体来表示每个人，包括其性别和身高信息。

然后，我们可以根据输入的性别和身高信息，将男生和女生分别存储在两个不同的数组中。

接下来，我们可以对男生数组按照身高从矮到高进行排序，并对女生数组按照身高从高到矮进行排序。

最后，我们可以创建一个结果数组，按照排好序的顺序将男生和女生的身高依次填入。

以下是一个用C语言实现的解答示例：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>#define MAX_SIZE 40typedef struct {char gender[10];float height;
} Person;int compare(const void *a, const void *b) {Person *personA = (Person *)a;Person *personB = (Person *)b;if (strcmp(personA->gender, "male") == 0 && strcmp(personB->gender, "male") == 0) {return personA->height - personB->height;} else if (strcmp(personA->gender, "female") == 0 && strcmp(personB->gender, "female") == 0) {return personB->height - personA->height;} else if (strcmp(personA->gender, "male") == 0 && strcmp(personB->gender, "female") == 0) {return -1;} else {return 1;}
}int main() {int n;scanf("%d", &n);Person people[MAX_SIZE];Person males[MAX_SIZE];Person females[MAX_SIZE];int maleCount = 0;int femaleCount = 0;int i;for (i = 0; i < n; i++) {scanf("%s %f", people[i].gender, &(people[i].height));if (strcmp(people[i].gender, "male") == 0) {males[maleCount++] = people[i];} else {females[femaleCount++] = people[i];}}qsort(males, maleCount, sizeof(Person), compare);qsort(females, femaleCount, sizeof(Person), compare);float result[MAX_SIZE];int resultCount = 0;int maleIndex = 0;int femaleIndex = 0;for (i = 0; i < n; i++) {if (strcmp(males[maleIndex].gender, "male") == 0) {result[resultCount++] = males[maleIndex++].height;} else {result[resultCount++] = females[femaleIndex++].height;}}for (i = 0; i < n; i++) {printf("%.2f ", result[i]);}printf("\n");return 0;
}