一、编程题
1、1.课程冲突
小 A 修了 n 门课程, 第 i 门课程是从第 ai 天一直上到第 bi 天。
定义两门课程的冲突程度为 : 有几天是这两门课程都要上的。
例如 a1=1,b1=3,a2=2,b2=4 时, 这两门课的冲突程度为 2。
现在你需要求的是这 n 门课中冲突程度最大的两门课的冲突程度。
时间限制：1000
内存限制：65536
输入
第一行一个正整数 n 表示课程数量。 接下来 n 行,每行两个正整数 ai,bi。 2 ≤ n≤ 1000, 1 ≤ ai ≤ bi ≤ 1000。
输出
输出一个整数表示最大的冲突程度
样例输入
```
3
1 3
2 4
5 5
```
样例输出
```
2
```
参考答案：
略
解析：【喵呜刷题小喵解析】这个问题可以通过暴力枚举所有课程对，然后计算它们的冲突程度来解决。对于每一对课程，我们可以遍历每一天，检查这一天是否在这两门课程的上课时间内。如果是，则冲突程度加一。最后，我们找出冲突程度最大的课程对，输出其冲突程度即可。首先，我们读入课程数量n和每门课程的上课时间范围ai和bi。然后，我们创建一个列表courses，用于存储每门课程的上课时间范围。接下来，我们使用两个嵌套的循环枚举所有课程对。对于每一对课程，我们遍历每一天，检查这一天是否在这两门课程的上课时间内。如果是，则冲突程度加一。最后，我们找出冲突程度最大的课程对，将其冲突程度输出即可。时间复杂度为O(n^2 * 1000)，其中n为课程数量，1000为每天的可能范围。虽然这个算法在数据量很大时可能超时，但在本题给定的数据量下是可行的。
2、2.42点
42是：
·组合数学上的第5个卡特兰数
·字符'*'的ASCII码
·钼的原子序数
·6与9的乘积结果的13进制表示
·生命、宇宙以及任何事情的终极答案
·以及……表达式(1+5)/2*(6-4)*7的值
因此，小机器人Marvin发明了这个叫42点的小游戏。在这个游戏中，玩家会获得n个数。玩家需要使用'+'、'-'、'*'、'/'、'('、')'以及这n个数构成一个合法的中缀表达式，并使得该表达式的值为42。n个数之间的顺序可以改变。表达式运算过程中只能出现整数。
由于过于抑郁，Marvin无力完成这个游戏，于是来找你帮忙。你的任务是对于给定的n个数，判断他们是否能根据上述游戏规则算出42。
时间限制：1000
内存限制：65536
输入
第一行为一个数n，1<=n<=6。 第二行为n个数，每个数均为[1,13]范围内的整数。
输出
输出一行，若可以算出42则输出“YES”，否则输出“NO”（注意大小写）。
样例输入
```
6
1 5 2 6 4 7
```
样例输出
```
YES
```
参考答案：
略
解析：【喵呜刷题小喵解析】首先，我们需要理解题目要求。题目要求我们根据给定的n个数，使用基本的四则运算和括号构成一个合法的中缀表达式，使得该表达式的值为42。根据题目要求，我们可以编写一个函数`judge`来判断给定的n个数是否能够构成满足条件的表达式。在`judge`函数中，我们使用四重循环来枚举所有可能的三个数的组合，以及这两个组合之间的运算符。对于每个组合，我们尝试将这三个数通过四则运算连接起来，并判断其结果是否为42。具体的，我们首先将第一个数和第二个数通过某个运算符连接起来，得到一个表达式`s1`。然后将第三个数和某个运算符连接起来，得到一个表达式`s2`。最后，我们将`s1`和`s2`通过另一个运算符连接起来，得到一个完整的表达式`s`。在得到表达式`s`之后，我们需要将其转化为合法的中缀表达式。具体地，我们将所有的`*`替换为`*(`，将所有的`)`替换为`)*`，将所有的`*`替换为`)*(1/0)`。这样，我们就可以使用`eval`函数来计算表达式`s`的值了。如果表达式`s`的值为42，那么我们就找到了一个满足条件的表达式，返回True。否则，我们继续枚举其他的组合和运算符，直到找到满足条件的表达式或者所有可能的组合都被枚举完。最后，我们在主函数中调用`judge`函数，并输出相应的结果。如果`judge`函数返回True，那么我们就输出"YES"，否则输出"NO"。
3、3.最长下坡
小明天天沿着未名湖环湖路跑，有时候也觉得蛮累。
累的时候跑下坡就很开心。小明想知道最长的一段下坡有多长。
环湖路是个圆形，周长n米。每隔一米测一下路面高度，两个测高点之间的高度是单调变化或不变的。
问最长的一段下坡有多少米长。小明只能顺时针跑。下坡必须高度单调减少。
时间限制：1000
内存限制：65536
输入
第一行是整数n，表示环湖路一共n米长(2<=n<=100)。 第二行是n个整数，每个整数范围[0,10000]，按顺时针顺序给出了n个测高点的高度
输出
最长下坡路段的长度
样例输入
```
样例输入1:
5
2 1 5 6 3
样例输入2：
5
2 1 5 4 3
样例输入3:
4
1 1 1 1
```
样例输出
```
样例输出1：
3
样例输出2
4
样例输出3
0
```
提示
这是个简单枚举题，枚举起点即可
参考答案：
略
解析：【喵呜刷题小喵解析】：这道题目需要我们找出最长的一段下坡的长度。根据题意，我们知道环湖路是个圆形，周长为n米，每隔一米测一下路面高度，两个测高点之间的高度是单调变化或不变的。下坡必须高度单调减少。我们可以使用枚举法来解决这个问题。枚举起点，从每个起点开始，找到最长的下坡长度。具体步骤如下：1. 读取输入的环湖路的周长n和顺时针顺序给出的n个测高点的高度。2. 初始化最长下坡长度为0，起始点为0。3. 枚举起点，从0到n-1。4. 对于每个起点，判断是否存在下坡，即当前点的高度是否大于下一个点的高度。5. 如果存在下坡，计算下坡的长度，即当前点的高度大于下一个点的高度时，长度加1，直到当前点的高度不再大于下一个点的高度。6. 如果计算出的下坡长度大于当前最长下坡长度，则更新最长下坡长度和起始点。7. 输出最长下坡长度。在Python中，我们可以使用列表来表示测高点的高度，使用map函数将输入的字符串转换为整数，使用while循环来计算下坡的长度，使用if语句来判断是否存在下坡。最终，输出最长下坡长度即可。
4、4.吃糖果
现有n(20 > n > 0)个糖果,每天可以吃1个,也可以每天吃2个,也可以每天吃3个，请计算共有多少种不同的吃法。
时间限制：1000
内存限制：65536
输入
输入的每一行包括一组测试数据，即为糖果数n。最后一行为0，表示测试结束。
输出
每一行输出对应一行输入的结果，即为吃法的数目。
样例输入
```
1
2
3
4
0
```
样例输出
```
1
2
4
7
```
参考答案：
略
解析：【喵呜刷题小喵解析】本题是一道经典的动态规划问题，可以使用动态规划算法来解决。首先，我们定义一个长度为n+1的数组dp，其中dp[i]表示有i个糖果时的吃法数目。然后，我们可以发现，对于任意i，dp[i]的值只与dp[i-1]、dp[i-2]和dp[i-3]的值有关，因为每天可以吃1个、2个或3个糖果。因此，我们可以使用递推公式dp[i] = dp[i-1] + dp[i-2] + dp[i-3]来计算dp[i]的值。最后，我们只需要遍历n个糖果，依次计算dp[i]的值，最终输出dp[n]即可。在代码中，我们使用了Python语言来实现这个算法。首先，我们定义了一个函数count_ways(n)，用于计算有n个糖果时的吃法数目。然后，我们依次读入每一组测试数据，调用count_ways(n)函数计算结果并输出。
5、5.放苹果
把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？（用K表示）5，1，1和1，5，1 是同一种分法。
时间限制：1000
内存限制：65536
输入
第一行是测试数据的数目t（0 <= t <= 20）。以下每行均包含二个整数M和N，以空格分开。1<=M，N<=10。
输出
对输入的每组数据M和N，用一行输出相应的K。
样例输入
```
1
7 3
```
样例输出
```
8
```
参考答案：
略
解析：【喵呜刷题小喵解析】本题是一个经典的组合问题，即“有多少种方式将M个相同的苹果放入N个相同的盘子中，允许有的盘子为空”。这种问题可以用组合数或者递归来解决。我们可以考虑从M个苹果中选择i个苹果放入第1个盘子，然后选择j个苹果放入第2个盘子，以此类推。这样，剩下的M-i-j个苹果就不能放入前i+j个盘子了，只能放入后面的N-(i+j)个盘子中。因此，问题就转化为将M-i-j个苹果放入N-(i+j)个盘子中的问题。具体地，我们可以使用两层循环来枚举i和j的值，然后计算满足条件的分法数目。具体地，当j>=i时，表示可以将j个苹果放入第2个盘子，而将i个苹果放入第1个盘子。因此，我们可以将K加1。最后，对于每一组输入的M和N，我们都可以计算出相应的K值，并输出即可。注意，由于题目中要求5，1，1和1，5，1是同一种分法，因此在计算K值时需要特别处理。具体地，我们可以将M和N都除以它们的最大公约数，然后再进行计算。但是，由于题目中给出了M和N的范围较小，因此我们可以直接暴力枚举所有的分法，而不需要使用最大公约数。
喵呜刷题：让学习像火箭一样快速，快来微信扫码，体验免费刷题服务，开启你的学习加速器！
