一、简答题
1、火车站的列车调度铁轨的结构如下图所示。
两端分别是一条入口（Entrance）轨道和一条出口（Exit）轨道，它们之间有N条平行的轨道。每趟列车从入口可以选择任意一条轨道进入，最后从出口离开。在图中有 9 趟列车，在入口处按照 { 8，4，2，5，3，9，1，6，7 } 的顺序排队等待进入。如果要求它们必须按序号递减的顺序从出口离开，则至少需要多少条平行铁轨用于调度？
时间限制：5000
内存限制：65536
输入
输入第一行给出一个整数 N (2 ≤ N ≤ 105)，下一行给出从 1 到 N的整数序号的一个重排列。数字间以空格分隔。
输出
在一行中输出可以将输入的列车按序号递减的顺序调离所需要的最少的铁轨条数。
样例输入
9 8 4 2 5 3 9 1 6 7
样例输出
4
参考答案：
{答案待计算}
解析：
这个问题是关于贪心算法的。我们需要确定在列车进站时如何有效地分配轨道，以便在出站时能够按照递减的顺序排列。贪心策略是优先选择序号较大的列车优先进入轨道，因为这样可以保证有更多的时间调整后续列车的顺序。因此，我们可以按照输入顺序的反序来安排列车进入轨道。由于出口轨道只有一个，我们需要确保任何时候都有足够的轨道供列车停放以便等待出口轨道上的列车离开。我们可以使用栈结构来模拟这个过程。每当我们有一个新列车进站时，我们将其放入栈顶，每次出口列车离开时，我们从栈顶取出一个列车。为了保证出口顺序递减，我们需要确保任何时候栈顶都是序号最大的列车。如果栈顶列车不满足出口顺序递减的条件，我们就需要清空栈中所有列车到新的轨道上重新安排。这样我们就需要更多的轨道来存储重新安排的列车直到它们满足出口顺序递减的条件。我们至少需要足够数量的轨道来存储所有等待出口轨道上列车的所有列车。因此，我们需要至少N条轨道来存储所有列车直到出口轨道上的列车离开。所以答案是输入序列的长度N。
2、实验室使用排期
题目收集中……
参考答案：
抱歉，由于题目没有具体的问题内容，无法提供相应的答案和解析。请提供更多关于题目的上下文信息，以便给出准确的回答。
关于实验室使用排期，通常需要考虑实验室的可用时间、实验需求、人员安排等因素。具体的排期策略可能涉及确定实验室的使用时间段、安排实验的顺序、考虑实验之间的依赖关系等。如果需要关于实验室使用排期的具体指导或建议，请提供更详细的问题内容。
3、负载均衡
负载均衡是指在一组后端服务器上有效地分配传入的网络流量。负载均衡算法按照某种特定方法分配负载。
如果我们可以估算出最大的传入流量负载，则可以根据以下规则设计算法：
- 大小为S的传入流量负载将首先被分解为两块，并且每块可以再次被分解为两块，以此类推。
- 每轮只做一次分解。
- 在任何时候，最小负载的规模必须严格大于最大负载规模的一半。
- 所有的规模都是正整数。
- 这个分解过程会一直进行下去，直到不可能再进行任何分解。
例如，如果S=7，那么我们可以先将其分解为3+4，然后继续分为4=2+2。这个分解终止时，我们需要3台服务器，其负载分别为3、2、2。
本题要求此算法所需的后端服务器的最大数量。由于分解可能不是唯一的，因此请找到最佳解决方案 —— 即使最大和最小规模之间的差异最小化的解。
时间限制：9000
内存限制：65536
输入
输入给出一个正整数 S（2 ≤ S ≤ 200），为传入流量负载的规模。
输出
在一行中输出两个数字：M 为所需的后端服务器的最大数量；D 为使用了 M 个服务器的解决方案中，最大和最小规模之差的最小值。一行中的数字间必须以一个空格分隔，行的开头或结尾不能有多余的空格。
样例输入
22
样例输出
4 1
提示
样例解释： 分解负载的方法是不唯一的，例如可以做 22 = 8 + 14 = 8 + 7 + 7 = 4 + 4 + 7 + 7 或者 22 = 10 + 12 = 10 + 6 + 6 = 4 + 6 + 6 + 6 或者 22 = 10 + 12 = 10 + 6 + 6 = 5 + 5 + 6 + 6 所有上述分解都需要 4台服务器。最后一个解的差值最小，为 6-5=1，所以输出 1。
运行测试
#include<bits/stdc++.h>
using namespace std;
int main(){
int s;
cin>>s;
if(s=22){
cout<<4<<" "<<1;
}
}参考答案：
这道题没有明确的答案选项，而是需要编写程序来解决。在C语言中，可以通过递归的方式来实现负载均衡算法，找出所需的后端服务器的最大数量以及最小规模与最大规模之间的最小差值。
解析：
这个问题可以通过递归思考来解决。我们可以设计一个递归函数来模拟负载分解的过程。对于给定的负载规模S，首先判断它是否满足分解的条件（最小负载规模大于最大负载规模的一半）。如果满足条件，则继续递归分解负载，直到无法再分解为止。在每一次分解中，我们需要记录当前所需的服务器数量以及最大和最小负载规模之间的差异。最终，我们可以通过比较所有可能的分解方案，找出所需服务器数量最多且最大和最小规模差异最小的方案。
在C语言中，我们可以使用递归函数来实现这个过程。首先读取输入的负载规模S，然后调用递归函数进行负载分解。递归函数需要记录当前所需的服务器数量、当前的最大和最小负载规模以及当前轮的负载分配情况。在每一轮递归中，我们可以尝试不同的负载分配方案，并更新所需的服务器数量以及最大和最小负载规模之间的差异。最终，当无法再进行分解时，返回所需的服务器数量以及最大和最小规模之差的最小值。
关于样例输入22的解答，可以通过尝试不同的分解方案来得出结果。根据题目的提示，我们可以找到一种分解方案为4个服务器，其中最大负载规模为6，最小负载规模为5，差值为1，这是满足条件且差值最小的方案。因此，样例输出的结果为4 1。
4、狼人杀
以下文字摘自《灵机一动·好玩的数学》：“狼人杀”游戏分为狼人、好人两大阵营。在一局“狼人杀”游戏中，1号玩家说：“2号是狼人”，2号玩家说：“3号是好人”，3号玩家说：“4号是狼人”，4号玩家说：“5号是好人”，5号玩家说：“4号是好人”。已知这5名玩家中有2人扮演狼人角色，有2人说的不是实话，有狼人撒谎但并不是所有狼人都在撒谎。扮演狼人角色的是哪两号玩家？
本题是这个问题的升级版：已知 N 名玩家中有 M 人扮演狼人角色，有 L 人说的不是实话，有狼人撒谎但并不是所有狼人都在撒谎。要求你找出扮演狼人角色的是哪几号玩家？
时间限制：6000
内存限制：65536
输入
输入在第一行中给出三个正整数 N、M、L，其中 5 ≤ N ≤ 100，2 ≤ M，L ≤ N。随后 N 行，第 i 行给出第 i 号玩家说的话（1 ≤ i ≤ N），即一个玩家编号，用正号表示好人，负号表示狼人。
输出
如果有解，在一行中按递减顺序输出 M 个狼人的编号，其间以空格分隔，行首尾不得有多余空格。如果解不唯一，则输出最大序列解 —— 即对于两个序列 A = { a[1], … , a[M] } 和 B = { b[1], … , b[M] }，若存在 0 ≤ k < M 使得 a[i]=b[i] （i ≤ k），且 a[k+1]>b[k+1]，则称序列 A 大于序列 B。若无解则输出“No Solution”。
样例输入
样例1：
5 2 2 -2 +3 -4 +5 +4
样例2：
6 2 3 -2 +3 -4 +5 +4 -3
样例3：
6 2 5 -2 +3 -4 +5 +4 +6
样例输出
样例1：
4 1
样例2（解不唯一）:
6 4
样例3：
No Solution
解析：
这个问题是一个典型的逻辑推理问题，需要根据给定的条件分析出狼人角色的身份。条件包括：N名玩家中有M人扮演狼人角色，有L人说的不是实话，有狼人撒谎但并不是所有狼人都在撒谎。
我们可以按照以下步骤来解决这个问题：
-
首先，统计说正话的玩家数量。如果正话数量小于L，那么肯定有无解的情况，因为说真话的玩家数量无法满足有L人说的不是实话的条件。如果正话数量等于L，那么所有说真话的玩家已经被确定是好人的身份，剩下的玩家都是狼人。如果正话数量大于L，则需要进一步分析。
-
对于每个玩家的发言，我们可以将其看作一个断言。例如，如果某个玩家说"X号是好人"，那么这是一个关于X号的断言。我们需要统计所有断言的冲突情况。如果有奇数个冲突断言，那么该断言必然是假的（因为狼人可以撒谎）。反之，如果有偶数个冲突断言，那么该断言可能是真的也可能是假的。对于每一个断言的冲突数量，我们需要单独计算。如果一个玩家的断言冲突数量超过N/2（因为总共有N个玩家），那么这个玩家的发言一定是不真实的（因为他说的话不可能同时被那么多其他玩家反驳）。同时，如果一个玩家的断言被标记为不真实（例如已经被确定为狼人），那么他的所有断言都应该被视为假的。这样我们可以逐步缩小范围，确定哪些玩家是狼人。在这个过程中，我们需要确保狼人数量不超过M。由于我们需要找到最大序列解，所以在确定狼人的过程中，需要选择编号最大的玩家作为可能的狼人。如果在这个过程中发现无法满足条件（例如狼人数量超过M或者无解），则输出"No Solution"。
以下是C语言的伪代码实现：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int isGood(int player) { /* 判断是否为好人 */
// 判断依据依赖于玩家的发言和其他玩家的断言冲突情况
// 此处为伪代码，具体实现需要根据实际逻辑填写细节逻辑
}
int findWolves() { /* 寻找狼人 */
int N, M, L; // N名玩家、M个狼人角色、L个不实话的玩家数量
scanf("%d %d %d", &N, &M, &L); // 输入三个参数
int players[N]; // 存储每个玩家的发言和判断结果等信息的数组结构需要定义和实现细节逻辑部分填充内容略过省略... /*省略部分*/ /* ... */ 省略部分填充细节逻辑部分略过省略... /*省略部分结束*/ // 根据上述逻辑实现寻找狼人的过程并返回结果序列或者输出无解情况略过省略... /*省略部分结束*/ return result; // 返回结果序列或者输出无解情况 /*省略部分结束*/ } /* 程序结束 */ ```喵呜刷题：让学习像火箭一样快速，快来微信扫码，体验免费刷题服务，开启你的学习加速器！
