一、编程题
1、1.交易市场
市场里面一共有n种物品，有m种交易途径，每个交易途径可以由(x,y,z)
表示，意思是可以用第x种物品换成第y种物品，并且得到z元的收益（z均大于0）。最开始你只有第一种物品，请问最多可以赚取多少收益。
时间限制：1000
内存限制：65536
输入
第一行两个正整数n和m(n ≤ 1000，m ≤ 4000) 接下来m行，每行三个正整数x, y, z，意思是可以用第x种物品换成第y种物品，并且得到z元的收益。（1 ≤ x,y ≤ n, 1 ≤ z ≤ 100）
输出
一个整数表示最大收益，如果可以赚取无穷多的收益则输出1000000000
样例输入
3 3
1 2 2
2 3 3
1 3 4
样例输出
5
参考答案：
略
解析：【喵呜刷题小喵解析】本题是一道典型的动态规划问题，可以使用拓扑排序+动态规划的方法解决。首先，我们需要建立一个邻接矩阵表示物品之间的交易关系，其中graph[i][j]表示第i种物品可以换取第j种物品并且得到多少收益。然后，我们还需要建立一个数组indeg，表示每个物品的入度，即有多少种物品可以交换得到该种物品。接下来，我们使用拓扑排序+动态规划的思想来解决问题。我们用一个队列q来保存待处理的物品，初始时只有第一种物品。然后，我们每次从队列中取出一个物品x，如果x等于n+1，说明已经处理完了所有物品，此时更新最大收益res。如果x的入度indeg[x]为0，说明x可以由其他物品交换得到，此时我们可以尝试用x交换得到其他物品，并将交换后的物品和当前收益加入队列。如果x的入度indeg[x]不为0，说明x不能直接交换得到，此时我们需要将x交换得到的每种物品和当前收益加入队列，并将这些物品的入度减1。最后，我们输出最大收益res，如果res为0，则输出1000000000表示可以赚取无穷多的收益。注意，由于题目中要求时间限制为1000，内存限制为65536，因此我们需要尽可能优化算法的时间复杂度和空间复杂度。在本题中，我们使用了拓扑排序+动态规划的方法，时间复杂度为O(nm)，空间复杂度为O(n^2)，满足题目要求。
2、2.问题求解
给定一个正整数N，求最小的M满足比N大且M与N的二进制表示中有相同数目的1。
举个例子，假如给定N为78，二进制表示为1001110，包含4个1，那么最小的比N大的并且二进制表示中只包含4个1的数是83，其二进制是1010011，因此83就是答案。
时间限制：1000
内存限制：65536
输入
输入若干行，每行一个数N(1 ≤ N ≤ 1000000)，如果这行为0表示输入结束。
输出
对于每个N,输出对应的M。
样例输入
1
2
3
4
78
0
样例输出
2
4
5
8
83
参考答案：
略
解析：【喵呜刷题小喵解析】首先，我们需要一个函数`count_bits(n)`来计算一个数的二进制表示中1的个数。这个函数通过不断地将n与1进行位与运算，并右移n，直到n变为0。每次位与运算的结果如果是1，就增加计数器。然后，我们需要一个函数`find_m(n)`来找到比n大的最小的数m，使得m的二进制表示中1的个数与n相同。这个函数从n+1开始，每次增加1，直到找到一个数m，使得m的二进制表示中1的个数等于目标值。最后，我们读取输入，直到输入为0，然后对每个输入n，调用`find_m(n)`并输出结果。
3、3.泳池
小C在一个排水系统不太好的学校上学。又是一个下雨天，学校里高低不平积了很多水。小C突发奇想：如果大雨一直下，多久以后我可以在学校里游泳呢？
学校是 N x N 的坐标方格 grid 中，每一个方格的值 grid(i,j)表示在位置 (i,j) 的高度。现在开始下雨了。当时间为 t 时，此时雨水导致方格中任意位置的水位为 t 。你可以从一个方格游向四周相邻的任意一个方格，但是前提是此时水位必须同时淹没这两个方格。假定小C的游动是不耗时的。
现在小C从坐标方格的左上(0,0)出发。最少耗时多久他才能到达坐标方格的右下平台 (N-1, N-1)？
时间限制：1000
内存限制：65536
输入
第一行有一个整数N，以下是一个N*N的方阵，代表各处的高度。 输入范围： 2 ≤ N ≤ 300 0 ≤ Height ≤ 10000000
输出
输出一个整数，代表最少等待时间T
样例输入
样例输入1：
2
0 2
1 3
样例输入2：
5
0 1 2 3 4
24 23 22 21 5
12 13 14 15 16
11 17 18 19 20
10 9 8 7 6
样例输出
样例输出1：
3
样例输出2：
16
提示
样例1：时间为3时，才可以游向平台(1,1)，此时水位为3。 样例2：时间为16时，水位为16，此时才能保证(0,0)和(4,4)是联通的（请自行找出一条通路）。
参考答案：
略
解析：【喵呜刷题小喵解析】：本题是一道典型的广度优先搜索（BFS）问题，可以使用队列来实现。首先，我们定义一个队列 `queue`，初始时只有起点 `(0, 0, 0)`，其中 `(x, y, time)` 表示当前的位置和对应的时间。然后，我们定义一个集合 `visited`，用于记录已经访问过的位置。接着，我们定义四个方向 `(0, 1), (0, -1), (1, 0), (-1, 0)`，分别表示右、左、下、上。在每一次循环中，我们取出队列中的第一个元素 `(x, y, time)`，如果 `(x, y)` 是终点 `(N-1, N-1)`，则直接返回时间 `time`。否则，我们遍历四个方向，对于每一个方向，计算出下一个位置 `(nx, ny)`，如果 `(nx, ny)` 在网格范围内且没有被访问过，则判断当前位置的水位是否小于等于时间 `time`，如果是，则将 `(nx, ny, time)` 加入队列，并将 `(nx, ny)` 加入 `visited` 集合。如果不是，则直接跳出当前方向的遍历。如果无法到达右下角，则返回 -1。时间复杂度为 O(N^2)，空间复杂度为 O(N^2)。
4、4.抓牛
农夫知道一头牛的位置，想要抓住它。农夫和牛都位于数轴上，农夫起始位于点N(0<=N<=100000)，牛位于点K(0<=K<=100000)。农夫有两种移动方式：
1、从X移动到X-1或X+1，每次移动花费一分钟
2、从X移动到2*X，每次移动花费一分钟
假设牛没有意识到农夫的行动，站在原地不动。农夫最少要花多少时间才能抓住牛？
时间限制：2000
内存限制：65536
输入
两个整数，N和K
输出
一个整数，农夫抓到牛所要花费的最小分钟数
样例输入
5 17
样例输出
4
参考答案：
略
解析：【喵呜刷题小喵解析】这道编程题要求找到农夫抓住牛所需的最小时间。农夫有两种移动方式：移动到当前位置的相邻位置（左或右）或移动到当前位置的两倍。牛不会移动，农夫需要从位置N移动到位置K来抓住牛。首先，我们可以观察到，如果N大于或等于K，那么农夫只需要移动到K的位置就可以抓住牛，所需时间就是N和K之间的差值。如果N小于K，我们需要使用广度优先搜索（BFS）来找到最短路径。我们从位置N开始，尝试所有可能的移动方式，直到我们到达位置K或者尝试了所有可能的位置。在BFS中，我们使用一个队列来保存待探索的位置和当前的步数。我们还使用一个集合来保存已经访问过的位置，以避免重复探索。最后，我们调用函数catch_cow，输入N和K，并打印出结果。如果N大于或等于K，函数将返回N和K之间的差值；否则，它将返回通过BFS找到的最短路径的步数。
喵呜刷题：让学习像火箭一样快速，快来微信扫码，体验免费刷题服务，开启你的学习加速器！
