一、编程题
1、1.人生来就有三个生理周期，分别为体力、感情和智力周期，它们的周期长度为23天、28天和33天。每一个周期中有一天是高峰。在高峰这天，人会在相应的方面表现出色。例如，智力周期的高峰，人会思维敏捷，精力容易高度集中。因为三个周期的周长不同，所以通常三个周期的高峰不会落在同一天。对于每个人，我们想知道何时三个高峰落在同一天。对于每个周期，我们会给出从当前年份的第一天开始，到出现高峰的天数（不一定是第一次高峰出现的时间）。你的任务是给定一个从当年第一天开始数的天数，输出从给定时间开始（不包括给定时间）下一次三个高峰落在同一天的时间（距给定时间的天数）。例如：给定时间为10，下次出现三个高峰同天的时间是12，则输出2（注意这里不是3）。
时间限制：1000
内存限制：65536
输入
一行，包含四个整数：p, e, i和d，相邻两个整数之间用单个空格隔开。 p, e, i分别表示体力、情感和智力高峰出现的时间（时间从当年的第一天开始计算）。d 是给定的时间，可能小于p, e, 或 i。 所有给定时间是非负的并且小于等于365, 所求的时间小于等于21252。
输出
一个整数，即从给定时间起，下一次三个高峰同天的时间（距离给定时间的天数）。
样例输入
```
4 5 6 7
```
样例输出
```
16994
```
参考答案：首先，我们计算智力、感情和体力周期高峰分别出现在哪一天。对于智力周期，高峰出现的时间为：智力周期高峰时间 = d + (33 - (d % 33)) % 33对于感情周期，高峰出现的时间为：感情周期高峰时间 = d + (28 - (d % 28)) % 28对于体力周期，高峰出现的时间为：体力周期高峰时间 = d + (23 - (d % 23)) % 23然后，我们找到这三个高峰时间中最早的一天，记为min_day。最后，我们计算从给定时间到min_day的天数，即为所求结果。
解析：【喵呜刷题小喵解析】：
本题是一道关于时间周期和计算的问题。首先，我们需要理解题目中的三个周期：体力、感情和智力周期，它们的周期长度分别为23天、28天和33天。每一个周期中有一天是高峰，高峰这天，人会在相应的方面表现出色。
根据题目，我们需要计算从给定时间开始，下一次三个高峰落在同一天的时间（距离给定时间的天数）。
首先，我们需要找到智力、感情和体力周期高峰分别出现在哪一天。由于每个周期的高峰不会落在同一天，我们需要分别计算每个周期的高峰时间。
对于智力周期，高峰出现的时间为：智力周期高峰时间 = d + (33 - (d % 33)) % 33
对于感情周期，高峰出现的时间为：感情周期高峰时间 = d + (28 - (d % 28)) % 28
对于体力周期，高峰出现的时间为：体力周期高峰时间 = d + (23 - (d % 23)) % 23
然后，我们需要找到这三个高峰时间中最早的一天，记为min_day。这是因为我们需要找出下一次三个高峰落在同一天的时间，这个时间就是min_day。
最后，我们计算从给定时间到min_day的天数，即为所求结果。
注意，在计算周期高峰时间时，我们需要使用取模运算来确保结果在周期内。这是因为给定时间可能是周期的任意一天，我们需要找出距离给定时间最近的下一个高峰时间。
2、2.开关问题
有N个相同的开关，每个开关都与某些开关有着联系，每当你打开或者关闭某个开关的时候，其他的与此开关相关联的开关也会相应地发生变化，即这些相联系的开关的状态如果原来为开就变为关，如果为关就变为开。你的目标是经过若干次开关操作后使得最后N个开关达到一个特定的状态。对于任意一个开关，最多只能进行一次开关操作。你的任务是，计算有多少种可以达到指定状态的方法。（不计开关操作的顺序）
时间限制：1000
内存限制：65536
输入
输入第一行有一个数K，表示以下有K组测试数据。 每组测试数据的格式如下： 第一行 一个数N（0 < N < 29） 第二行 N个0或者1的数，表示开始时N个开关状态。 第三行 N个0或者1的数，表示操作结束后N个开关的状态。 接下来 每行两个数I J，表示如果操作第 I 个开关，第J个开关的状态也会变化。每组数据以 0 0 结束。
输出
如果有可行方法，输出总数，否则输出“Oh,it's impossible~!!” 不包括引号
样例输入
```
2
3
0 0 0
1 1 1
1 2
1 3
2 1
2 3
3 1
3 2
0 0
3
0 0 0
1 0 1
1 2
2 1
0 0
```
样例输出
```
4
Oh,it's impossible~!!
```
提示
第一组数据的说明： 一共以下四种方法： 操作开关1 操作开关2 操作开关3 操作开关1、2、3 （不记顺序）
参考答案：对于第一组测试数据，有4种可以达到指定状态的方法。对于第二组测试数据，没有可行方法。
解析：【喵呜刷题小喵解析】：
本题是一个典型的开关问题，需要利用图的遍历或图的着色等算法来解决。对于每组测试数据，我们可以将每个开关视为一个节点，将有关联的开关用边连接起来，构成一个图。
对于第一组测试数据，初始状态为0 0 0，目标状态为1 1 1。我们可以将每个开关的状态视为一个二进制数，其中0表示关，1表示开。因此，初始状态为000，目标状态为111。由于每个开关最多只能进行一次开关操作，我们需要找到一种方法，使得从初始状态到目标状态，每个开关只操作一次。
我们可以使用图的遍历或图的着色等算法来解决这个问题。具体来说，我们可以将每个开关的状态视为一个二进制数，其中0表示关，1表示开。对于每个开关，我们可以将其状态取反，即0变为1，1变为0，然后检查这样操作后是否可以达到目标状态。如果可以，我们将其计入结果中。
对于第一组测试数据，我们可以将开关1、2、3的状态都取反，得到111，这样就达到了目标状态。因此，有4种可以达到指定状态的方法，即只操作开关1、只操作开关2、只操作开关3、同时操作开关1、2、3。
对于第二组测试数据，初始状态为0 0 0，目标状态为1 0 1。我们可以尝试将开关1、2、3的状态都取反，得到111，但是这样并不能达到目标状态。因此，没有可行方法。
3、3.冰阔落 I
老王喜欢喝冰阔落。
初始时刻，桌面上有n杯阔落，编号为1到n。老王总想把其中一杯阔落倒到另一杯中，这样他一次性就能喝很多很多阔落，假设杯子的容量是足够大的。
有m 次操作，每次操作包含两个整数x与y。
若原始编号为x 的阔落与原始编号为y的阔落已经在同一杯，请输出"Yes"；否则，我们将原始编号为y 所在杯子的所有阔落，倒往原始编号为x 所在的杯子，并输出"No"。
最后，老王想知道哪些杯子有冰阔落。
时间限制：10000
内存限制：65536
输入
有多组测试数据，少于 5 组。 每组测试数据，第一行两个整数 n, m (n, m<=50000)。接下来 m 行，每行两个整数 x, y (1<=x, y<=n)。
输出
每组测试数据，前 m 行输出 "Yes" 或者 "No"。 第 m+1 行输出一个整数，表示有阔落的杯子数量。 第 m+2 行有若干个整数，从小到大输出这些杯子的编号。
样例输入
```
3 2
1 2
2 1
4 2
1 2
4 3
```
样例输出
```
No
Yes
2
1 3
No
No
2
1 4
```
参考答案：br />对于每组测试数据，首先进行m次操作，每次操作根据题目要求判断x和y是否已经在同一杯，如果已经在同一杯则输出"Yes"，否则将y所在杯子的所有阔落倒往x所在的杯子，并输出"No"。最后统计有阔落的杯子数量，并输出这些杯子的编号。
解析：【喵呜刷题小喵解析】
对于每组测试数据，首先读取n和m的值，然后进行m次操作。每次操作读取x和y的值，判断x和y是否已经在同一杯，如果已经在同一杯则输出"Yes"，否则将y所在杯子的所有阔落倒往x所在的杯子，并输出"No"。
对于判断x和y是否已经在同一杯，可以使用一个数组或者哈希表来记录每个杯子中是否有阔落。对于每次操作，如果x和y已经在同一杯，则输出"Yes"，否则将y所在杯子的所有阔落倒往x所在的杯子，即将y所在杯子的阔落标记删除，同时在x所在杯子中添加y的标记。
最后，统计有阔落的杯子数量，并输出这些杯子的编号。可以使用一个计数器来记录有阔落的杯子数量，同时使用一个数组或者哈希表来记录每个杯子中是否有阔落。对于每个杯子，如果有阔落，则将其编号输出，并将计数器加1。
需要注意的是，由于有多组测试数据，需要在每组测试数据之间清空数组或者哈希表，避免相互影响。同时，由于每组测试数据的n和m的值较大，需要使用高效的算法来处理。
4、4.最短路
给定一个n个点, m条边的有向图, 求从点S出发, 到其它所有点的最短路径.
时间限制：2000
内存限制：65536
输入
第一行一个整数T, 表示有T组数据 对于每组测试数据, 第一行三个整数n, m, S, 表示有n个点, m条边, 起点为S. 接下来m行, 每行三个整数x, y, z, 代表从x到y有长度为z的边 点的编号从1到n T <= 10, n <= 10000, m <= 20000, |z| <= 10000. 所有数据的n之和 <= 30000, 所有数据的m之和 <= 60000.输出
对于每组数据: 如果从S点出发可以走入负圈 (即到某些点的最短路径可以无限小), 那么输出一行Error. 否则, 输出一行用空格分隔的n个整数, 其中第i个整数表示从S点到i点的最短路长度. 如果从S点无法到达i点, 则第i个输出为”null”.
样例输入
```
4
5 7 1
1 2 3
2 3 4
3 4 8
1 3 9
4 5 1
1 4 5
1 5 10
4 4 1
1 2 -4
2 3 8
1 3 5
3 4 0
3 3 2
1 2 -3
2 3 -4
3 1 6
4 2 1
1 2 1
3 4 2
```
样例输出
```
0 3 7 5 6
0 -4 4 4
Error
0 1 null null
```
参考答案：对于每组数据，首先使用Dijkstra算法求出从起点S到所有点的最短路径。如果在求解过程中发现存在负圈，即存在从S点出发可以走入负圈的情况，则输出"Error"。否则，输出从S点到每个点的最短路径长度。如果无法从S点到达某个点，则输出"null"。
解析：【喵呜刷题小喵解析】：
本题要求求解从起点S到所有点的最短路径，可以使用Dijkstra算法来求解。Dijkstra算法是一种求解单源最短路径问题的经典算法，适用于边权非负的有向图。
对于每组数据，首先使用Dijkstra算法求出从起点S到所有点的最短路径。在求解过程中，如果发现存在负圈，即存在从S点出发可以走入负圈的情况，则输出"Error"。否则，输出从S点到每个点的最短路径长度。如果无法从S点到达某个点，则输出"null"。
由于输入数据较大，需要使用高效的算法来求解。Dijkstra算法的时间复杂度为O((V+E)logV)，其中V为顶点数，E为边数。由于本题中V和E都较大，因此需要优化算法以提高效率。可以使用堆来优化Dijkstra算法，将时间复杂度降低到O(ElogV)。
在求解过程中，需要记录每个点的最短路径长度和最短路径的来源点。对于每个点，记录其最短路径长度和最短路径的来源点，以便在求解过程中更新最短路径。
最后，按照题目要求输出从S点到每个点的最短路径长度。如果无法从S点到达某个点，则输出"null"。
喵呜刷题：让学习像火箭一样快速，快来微信扫码，体验免费刷题服务，开启你的学习加速器！
