一、编程题
1、波兰表达式
波兰表达式是一种把运算符前置的算术表达式，例如普通的表达式2 + 3的波兰表示法为+ 2 3。波兰表达式的优点是运算符之间不必有优先级关系，也不必用括号改变运算次序，例如(2 + 3) * 4的波兰表示法为* + 2 3 4。本题求解波兰表达式的值，其中运算符包括+ - * /四个。
时间限制：1000
内存限制：65536
输入
输入为一行，其中运算符和运算数之间都用空格分隔，运算数是浮点数。
输出
输出为一行，表达式的值。 可直接用printf(“%f\n”, v)输出表达式的值v。
样例输入
* + 11.0 12.0 + 24.0 35.0
样例输出
1357.000000
参考答案：
无
解析：【喵呜刷题小喵解析】该题目要求计算波兰表达式的值。波兰表达式是一种把运算符前置的算术表达式，例如普通的表达式2 + 3的波兰表示法为+ 2 3。波兰表达式的优点是运算符之间不必有优先级关系，也不必用括号改变运算次序。本题中，运算符包括+、-、*、/四个。输入为一行，其中运算符和运算数之间都用空格分隔，运算数是浮点数。输出为一行，表达式的值。在C语言中，我们可以使用scanf函数来读取输入，使用switch语句来处理不同的运算符。对于除法运算，需要特别处理除数为0的情况。最后，使用printf函数输出表达式的值。在上面的代码中，我们首先定义了一些变量，包括运算符op，两个运算数num1和num2，以及结果变量result。然后，使用while循环来读取输入，直到没有输入为止。在循环中，使用scanf函数读取一个字符和两个浮点数，如果读取成功，就使用switch语句来处理不同的运算符。最后，使用printf函数输出计算结果。需要注意的是，在计算除法时，需要特别处理除数为0的情况，否则会导致程序崩溃。另外，如果输入的运算符不是+、-、*、/之一，程序会输出错误信息并退出。
2、括号配对
字符串中可能有三种成对的括号，“( )”、“[ ]”、“{ }”。请判断字符串的括号是否都正确配对。无括号也算正确配对。括号交叉算不正确配对，例如"12{34[78}ab]“就不算正确配对。但是一对括号被包含在另一对括号里面，例如"12{ab[8]}“不影响正确性。
时间限制：1000
内存限制：65536
输入
第一行为整数n(n<40)，接下来有n行，每行一个无空格的字符串，长度小于1000。
输出
对每行字符串，如果括号配对，输出"YES”，否则输出"NO”。
样例输入
2
12{ab[8]}
12{34[78}ab]
样例输出
YES
NO
参考答案：
无
解析：【喵呜刷题小喵解析】：本题要求判断字符串的括号是否都正确配对。可以使用栈来解决这个问题。遍历字符串中的每个字符，如果字符是左括号，则将其压入栈中；如果字符是右括号，则检查栈顶元素是否与其匹配，如果匹配，则弹出栈顶元素，否则说明括号不匹配，输出"NO"。如果遍历结束后栈为空，则说明所有括号都正确配对，输出"YES"；否则说明括号不匹配，输出"NO"。在Python中，可以使用列表来模拟栈，使用append()方法将元素压入栈中，使用pop()方法将栈顶元素弹出。在判断括号是否匹配时，可以使用字典来存储每个左括号对应的右括号，以便快速查找。具体实现时，首先读入整数n，表示有n行字符串需要判断。然后对于每行字符串，使用栈来存储左括号，遍历字符串中的每个字符，根据字符类型进行相应的操作。最后根据栈是否为空来判断括号是否匹配，并输出相应的结果。
3、扑克牌排序
假设这里有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个队列即可。
参考答案：
无
解析：【喵呜刷题小喵解析】首先，我们读取输入的牌数n和每张牌的数值。然后，我们进行第一次入队出队。根据每张牌的花色，我们将其放入对应的队列中。队列的编号从1到9，对应花色A到D。我们按照队列1到队列9的顺序，依次取出队列中的牌，并打印出队列编号和队列中的牌。如果队列为空，则不打印。取出牌后，我们按照点数对队列中的牌进行排序，并再次打印出排序后的牌。接着，我们进行第二次入队出队。我们根据每张牌的花色，将其放入对应的队列中。队列A到队列D分别对应花色A到D。我们按照队列A到队列D的顺序，依次取出队列中的牌，并打印出队列编号和队列中的牌。如果队列为空，则不打印。取出牌后，我们按照点数对队列中的牌进行排序，并再次打印出排序后的牌。最后，我们按照牌的顺序，打印出排序后的牌。注意，在第二次入队出队时，我们可以复用第一次的队列。因此，我们只需要开辟9个队列即可。在第二次入队出队时，我们只需要将牌放入对应的队列中，并按照队列的顺序依次取出队列中的牌，并打印出队列编号和队列中的牌。取出牌后，我们按照点数对队列中的牌进行排序，并再次打印出排序后的牌。
4、
- 滑动窗口
- 给定一个长度为n（n<=10^6）的数组。有一个大小为k的滑动窗口从数组的最左端移动到最右端。你可以看到窗口中的k个数字。窗口每次向右滑动一个数字的距离。
- 下面是一个例子：
- 数组是 [1 3 -1 -3 5 3 6 7]， k = 3。
-
窗口位置 最小值 最大值 [1 3 -1] -3 5 3 6 7 -1 3 1 [3 -1 -3] 5 3 6 7 -3 3 1 3 [-1 -3 5] 3 6 7 -3 5 1 3 -1 [-3 5 3] 6 7 -3 5 1 3 -1 -3 [5 3 6] 7 3 6 1 3 -1 -3 5 [3 6 7] 3 7 -
你的任务是得到滑动窗口在每个位置时的最大值和最小值。
时间限制：20000
内存限制：65536
输入
输入包括两行。 第一行包括n和k，分别表示数组的长度和窗口的大小。 第二行包括n个数字。
输出
输出包括两行。 第一行包括窗口从左至右移动的每个位置的最小值。 第二行包括窗口从左至右移动的每个位置的最大值。
样例输入
8 3
1 3 -1 -3 5 3 6 7
样例输出
-1 -3 -3 -3 3 3
3 3 5 5 6 7
参考答案：
无
解析：【喵呜刷题小喵解析】这个问题可以通过使用双端队列（deque）来解决。双端队列可以在头部和尾部添加或删除元素，因此它非常适合用于解决滑动窗口问题。首先，我们创建两个双端队列，一个用于存储最小值，另一个用于存储最大值。然后，我们遍历数组，对于每个元素，我们将其添加到两个队列中。如果队列的长度超过了窗口的大小，我们就从队列的头部删除元素。接下来，我们计算当前窗口的最小值和最大值。最小值是当前窗口中的最小值，我们可以通过比较队列中的元素来找到它。最大值也是同样的，但是我们需要找到队列中的最大值。最后，我们打印出每个窗口的最小值和最大值。由于我们需要打印出每个窗口的最小值和最大值，所以我们需要在每个窗口的末尾打印出当前窗口的最小值和最大值。这个算法的时间复杂度是O(n)，其中n是数组的长度。这是因为我们需要遍历整个数组一次，并且对于每个元素，我们将其添加到队列中，并从队列的头部删除元素，这需要常数时间。
喵呜刷题：让学习像火箭一样快速，快来微信扫码，体验免费刷题服务，开启你的学习加速器！
