一、编程题
1、在一个有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，说明存在生日相同的学生，我们按照题目要求输出他们的名字。最后，如果没有任何学生的生日相同，我们输出"None"。在输出名字时，我们按照题目要求，先按照日期从前到后的顺序输出，然后对生日相同的名字，按照名字从短到长的顺序输出，长度相同的按照字典序输出。我们使用Python的collections模块中的defaultdict函数来创建字典，使得当字典中不存在某个键时，会自动创建一个空列表作为该键的值。在输出名字时，我们使用sorted函数对名字列表进行排序，并使用lambda函数作为排序的key，按照名字从短到长的顺序进行排序，长度相同的按照字典序排序。
2、合法出栈序列
给定一个由不同小写字母构成的长度不超过8的字符串x，现在要将该字符串的字符依次压入栈中，然后再全部弹出。
要求左边的字符一定比右边的字符先入栈，出栈顺序无要求。
再给定若干字符串，对每个字符串，判断其是否是可能的x中的字符的出栈序列。
时间限制：1000
内存限制：65536
输入
第一行是原始字符串x 后面有若干行，每行一个字符串
输出
对除第一行以外的每个字符串，判断其是否是可能的出栈序列。如果是，输出"YES"，否则，输出"NO"
样例输入
abc
abc
bca
cab
样例输出
YES
YES
NO
参考答案：
无
解析：【喵呜刷题小喵解析】：这个问题可以通过模拟栈的操作来解决。对于每个待判断的字符串，我们遍历它的每个字符，同时维护一个栈来模拟入栈和出栈操作。在遍历字符串的字符时，我们需要考虑两个条件：1. 左边的字符一定比右边的字符先入栈，这意味着栈顶元素必须小于或等于当前字符。2. 出栈顺序无要求，这意味着栈顶元素可能是原始字符串中任何一个字符。因此，我们可以按照以下步骤进行模拟：1. 初始化一个空栈。2. 遍历待判断字符串的每个字符：* 如果栈不为空且栈顶元素小于当前字符且在原始字符串中栈顶元素的索引大于当前字符的索引，那么将栈顶元素出栈，直到满足条件1或栈为空。* 如果栈为空或栈顶元素大于等于当前字符，将当前字符入栈。* 如果栈顶元素小于当前字符且在原始字符串中栈顶元素的索引小于当前字符的索引，那么当前字符串不是合法的出栈序列，返回False。3. 如果遍历完待判断字符串后栈为空，那么它是合法的出栈序列，返回True，否则返回False。在主程序中，我们首先读入原始字符串，然后循环读入待判断字符串，对每个待判断字符串调用is_valid_sequence函数判断其是否是合法的出栈序列，并输出结果。时间复杂度为O(n*m)，其中n是待判断字符串的数量，m是字符串的长度。空间复杂度为O(m)，主要是栈的空间。
3、括号画家
Candela是一名漫画家，她有一个奇特的爱好，就是在纸上画括号。这一天，刚刚起床的Candela画了一排括号序列，其中包含小括号()、中括号[]和大括号{}，总长度为N。这排随意绘制的括号序列显得杂乱无章，于是Candela定义了什么样的括号序列是美观的：
(1) 空的括号序列是美观的；
(2) 若括号序列A是美观的，则括号序列(A)、[A]、{A}也是美观的；
(3) 若括号序列A、B都是美观的，则括号序列AB也是美观的；
例如 [(){}]() 是美观的括号序列，而 )({)[}]( 则不是。
现在Candela想知道她画出的括号序列是不是美观的。你能帮帮她吗？
时间限制：1000
内存限制：262144
输入
一个括号序列，长度不超过10000。
输出
如果它是美观的，输出Yes，否则输出No。
样例输入
{}[(){}]()
样例输出
Yes
参考答案：
无
解析：【喵呜刷题小喵解析】：本题是一个判断括号序列是否美观的问题。我们可以使用栈来解决这个问题。首先，我们遍历括号序列中的每一个字符。对于每一个字符，我们进行以下操作：1. 如果字符是左括号（即(、[、{），则将其压入栈中。2. 如果字符是右括号（即)、]、}，则判断栈是否为空。如果为空，说明没有与之匹配的左括号，直接返回False。如果不为空，则从栈顶弹出一个元素，检查该元素是否与当前的右括号匹配。如果匹配，则继续遍历；否则，说明当前的右括号没有与之匹配的左括号，返回False。遍历结束后，如果栈为空，说明所有的左括号都有与之匹配的右括号，返回True；否则，返回False。最后，我们根据判断结果输出Yes或No。
4、表达式求值
求一个可能包含加、减、乘、除、乘方运算的中缀表达式的值。
在计算机中，我们常用栈来解决这一问题。首先将中缀表达式转换到后缀表达式，然后对后缀表达式求值。
加、减、乘、除、乘方分别用+，-，*, /, ^来表示。表达式可以有圆括号()。
时间限制：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
参考答案：
无
解析：【喵呜刷题小喵解析】本题要求计算中缀表达式的值，可以使用栈来解决。首先将中缀表达式转换为后缀表达式，然后对后缀表达式求值。首先，我们定义一个栈，用于存储数字和运算符。然后，遍历表达式的每个字符，如果是数字，则将其转换为整数并压入栈中；如果是运算符，则判断栈顶运算符的优先级，如果栈顶运算符的优先级低于当前运算符或者优先级相同但当前运算符不是乘方运算符，则将栈顶运算符和左右两个操作数弹出，根据运算符进行相应的计算，并将结果压入栈中。最后，栈中剩下的就是表达式的值。在Python中，我们可以使用`split()`函数将表达式按照空格分割成多个部分，然后遍历每个部分进行处理。在本题中，我们还需要注意乘方的优先级比乘除都高，结合性是向左结合。除法的商向下取整。在本实现中，我们使用一个字符串来存储表达式，并使用空格作为分隔符。然后，我们遍历字符串的每个字符，如果是数字，则将其转换为整数并压入栈中；如果是运算符，则判断栈顶运算符的优先级，进行相应的计算。最后，栈中剩下的就是表达式的值。注意，本题中需要处理负数和乘方运算，乘方的优先级比乘除都高，除法的商向下取整。在本实现中，我们使用Python的`int()`函数将数字转换为整数，使用`pow()`函数进行乘方运算，使用`//`运算符进行除法运算。最后，我们还需要处理测试数据的组数，对于每组测试数据，我们读取一行表达式，并调用`calculate()`函数计算表达式的值，然后输出。
喵呜刷题：让学习像火箭一样快速，快来微信扫码，体验免费刷题服务，开启你的学习加速器！
