一、单选题
1、定义变量 double x ，如果下面代码输入为 100 ，输出最接近( )。
A、
0
B、 -5
C、
-8
D、
8
解析：【喵呜刷题小喵解析】根据题目，我们需要找到一个double类型的变量x，使得当输入为100时，输出值最接近某个数。
首先，我们观察给出的函数，它似乎是一个分段函数，由两个线性函数组成。
当x < 0时，函数为y = -2x - 8；
当x >= 0时，函数为y = 2x。
当输入为100时，x = 100，所以y = 2 * 100 = 200。
接下来，我们需要找到最接近200的数。观察选项，我们可以看到-5是最接近200的数。
因此，正确答案是B，-5。
2、对于下面动态规划方法实现的函数，以下选项中最适合表达其状态转移函数的为( )。
A 
B 
C 
D 
解析：【喵呜刷题小喵解析】：根据题目中的动态规划方法实现的函数，我们需要找到最适合表达其状态转移函数的选项。从给出的四个选项来看，选项D中的图像与题目中的函数图形最为相似，且从高度和宽度来看，也最符合题目中函数的形状。因此，选项D是最适合表达题目中动态规划方法实现函数的状态转移函数的选项。
3、下面代码可以用来求最长上升子序列（LIS）的长度，如果输入是： 5 1 7 3 5 9 ，则输出是( )。
A、
9 7 5 1 1 9
B、
1 2 2 3 4 4
C、 1 3 5 7 9 9
D、
1 1 1 1 1 1
解析：【喵呜刷题小喵解析】：最长上升子序列（LIS）是指在一个序列中，找到最长的一段递增子序列。对于输入序列5 1 7 3 5 9，我们可以得到以下最长上升子序列：5, 7, 9。因此，最长上升子序列的长度为3，选项C中的序列1 3 5 7 9 9符合这一结果。选项A中的序列9 7 5 1 1 9不是递增的，选项B中的序列1 2 2 3 4 4和选项D中的序列1 1 1 1 1 1都不符合最长上升子序列的定义。
4、C++语言中，下列关于关键字 static 的描述不正确的是( )。
A、
可以修饰类的成员函数。
B、
常量静态成员可以在类外进行初始化。
C、 若 a 是类 A 常量静态成员，则 a 的地址都可以访问且唯一。
D、
静态全局对象一定在 main 函数调用前完成初始化，执行完 main 函数后被析构。
解析：【喵呜刷题小喵解析】：
在C++语言中，关键字`static`的描述中不正确的是选项C。
选项A描述的是`static`可以修饰类的成员函数，这是正确的。使用`static`修饰的类的成员函数又称为静态成员函数，它们可以访问类的静态成员，但不能访问非静态成员。
选项B描述的是常量静态成员可以在类外进行初始化，这也是正确的。静态成员变量（包括常量和非常量）可以在类外进行初始化，常量静态成员必须在类外进行初始化。
选项C描述的是若`a`是类`A`常量静态成员，则`a`的地址都可以访问且唯一。这是不正确的。静态成员变量（包括常量和非常量）在内存中只有一份拷贝，但它们的地址并不是唯一的。在类的不同对象中，静态成员变量的地址是相同的。
选项D描述的是静态全局对象一定在`main`函数调用前完成初始化，执行完`main`函数后被析构。这也是正确的。静态全局对象（包括静态局部变量和静态全局变量）在程序开始执行前完成初始化，在程序结束前（即`main`函数执行完后）被析构。
5、G 是一个非连通无向图，共有 28 条边，则该图至少有( )个顶点。
A、
6
B、 7
C、
8
D、
9
解析：【喵呜刷题小喵解析】：
首先，我们需要理解非连通无向图的概念。非连通无向图是指一个图中有一些顶点对之间没有边相连，即这个图不是连通的。
其次，我们需要知道一个基本的图论定理：在一个无向图中，边数（E）和顶点数（V）之间有关系：E ≤ V(V-1)/2。这个定理告诉我们，对于一个无向图，边数永远不能超过顶点数的函数。
题目给出这个非连通无向图共有28条边，我们可以带入上面的公式中，得到：
28 ≤ V(V-1)/2
解这个不等式，我们得到：
V^2 - V - 56 ≤ 0
解这个二次不等式，我们得到：
7 ≤ V ≤ 8
因为题目要求的是“至少”有多少个顶点，所以答案是7。
6、哈希表长31，按照下面的程序依次输入 4 17 28 30 4 ，则最后的 4 存入哪个位置？（ ）
A、
3
B、 4
C、
5
D、
6
解析：【喵呜刷题小喵解析】：
根据图片中的哈希表，我们可以知道哈希表的位置是从0开始的。
首先，我们计算第一个数4的哈希值：
4 % 31 = 4
所以，第一个数4存放在位置4。
然后，我们计算第二个数17的哈希值：
17 % 31 = 17
但是，位置17已经被4占用，所以产生冲突。
根据提供的程序，当发生冲突时，将元素存放在下一个可用的位置，即位置18。
接着，我们计算第三个数28的哈希值：
28 % 31 = 28
但是，位置28已经被17占用，所以再次产生冲突。
根据提供的程序，将元素存放在下一个可用的位置，即位置29。
再然后，我们计算第四个数30的哈希值：
30 % 31 = 0
但是，位置0已经被4占用，所以再次产生冲突。
根据提供的程序，将元素存放在下一个可用的位置，即位置1。
最后，我们计算第五个数4的哈希值：
4 % 31 = 4
但是，位置4已经被第一个数4占用，所以再次产生冲突。
根据提供的程序，将元素存放在下一个可用的位置，即位置5。
所以，最后的数4存放在位置5。因此，答案是B。
7、某二叉树T的先序遍历序列为： {A B D F C E G H} ，中序遍历序列为： {B F D A G E H C} ，则下列说法中正确的是( )。
A、
T的度为1
B、
T的高为4
C、
T有4个叶节点
D、 以上说法都不对
解析：【喵呜刷题小喵解析】：根据题目给出的先序遍历序列和中序遍历序列，我们可以还原出二叉树T的结构。先序遍历的第一个元素是根节点A，在中序遍历中，根节点将序列分为左子树和右子树，即{B F D}和{G E H C}。因此，可以确定A是根节点，B、F、D是左子树的节点，G、E、H、C是右子树的节点。
继续分析左子树和右子树，左子树的先序遍历序列为{B D F}，中序遍历序列为{B F D}，可以确定B是左子树的根节点，D和F是B的左右子节点。右子树的先序遍历序列为{G E H C}，中序遍历序列为{G E H C}，可以确定G是右子树的根节点，E、H和C是G的左右子节点。
对于选项A，二叉树的度是指树中节点的子树个数，最大为2，所以A错误。
对于选项B，二叉树的高是指从根节点到最远叶子节点的最长路径上的节点数，由于题目中并未给出具体的高，所以B错误。
对于选项C，二叉树的叶节点即度为0的节点，根据还原出的二叉树结构，叶节点有D、F、H和C，共有4个，所以C错误。
因此，以上说法都不对，所以正确答案是D。
8、下面代码段可以求两个字符串 s1 和 s2 的最长公共子串（LCS），下列相关描述不正确的是（ ）。
A、
代码的时间复杂度为O(n2)
B、 代码的空间复杂度为O(n2)
C、
空间复杂度已经最优
D、
采用了动态规划求解
解析：【喵呜刷题小喵解析】：根据图片中的代码，我们可以看到它使用了动态规划的思想来求解两个字符串的最长公共子串（LCS）。动态规划是一种通过把原问题分解为相对简单的子问题的方式来求解复杂问题的方法。在这个例子中，动态规划被用来求解LCS问题，因此选项D是正确的。
对于选项A，代码的时间复杂度为O(n^2)，这是正确的。LCS问题的时间复杂度通常被证明为O(n^2)，因为我们需要比较两个字符串中的每一个字符对。
对于选项C，空间复杂度已经最优，这是不正确的。虽然这个代码使用了动态规划，并且其空间复杂度也是O(n^2)，但我们不能直接说这个空间复杂度已经最优，因为还有其他的算法或优化方法可能达到更小的空间复杂度。
对于选项B，代码的空间复杂度为O(n^2)，这是不正确的。代码中的dp数组用于存储子问题的解，其大小取决于两个字符串的长度，因此空间复杂度为O(n^2)。所以，选项B是不正确的。
9、图的广度优先搜索中既要维护一个标志数组标志已访问的图的结点，还需哪种结构存放结点以实现遍历？( )
A、
双向栈
B、 队列
C、
哈希表
D、
堆
解析：【喵呜刷题小喵解析】：在图的广度优先搜索中，我们需要维护一个标志数组来标记已经访问过的图的结点。为了实现遍历，我们需要一个结构来存放待访问的结点。队列（Queue）是一个先进先出（FIFO）的数据结构，它非常适合用于广度优先搜索。在广度优先搜索中，我们将当前结点的所有未访问的邻居结点加入到队列中，然后依次处理队列中的结点，这样可以保证按照广度优先的顺序遍历整个图。因此，选项B“队列”是正确答案。
10、对关键字序列 {44，36，23，35，52，73，90，58} 建立哈希表，哈希函数为 h(k)=k%7 ，执行下面的Insert 函数，则等概率情况下的平均成功查找长度（即查找成功时的关键字比较次数的均值）为( )。
A、
7/8
B、
1
C、
1.5
D、 2
解析：【喵呜刷题小喵解析】
首先，哈希函数为h(k)=k%7，根据哈希函数，我们计算关键字序列中每个元素经过哈希函数处理后得到的哈希值。
对于关键字序列{44，36，23，35，52，73，90，58}，其哈希值序列为{3，2，6，4，3，4，5，1}。
注意到哈希值2出现了两次，而其他的哈希值只出现了一次，所以，当插入第一个关键字36时，其哈希值为2，那么插入第二个关键字23时，哈希值也是2，就会产生冲突。
此时，我们可以观察到，对于哈希值为2的关键字，平均查找长度为2，即比较两次。而对于其他哈希值，查找一次即可成功。
因此，平均成功查找长度是(2*2+6)/8=2。
所以，等概率情况下的平均成功查找长度为2，对应选项D。
11、学生在读期间所上的某些课程中需要先上其他的课程，所有课程和课程间的先修关系构成一个有向图 G ，有向边 <U, V> 表示课程 U 是课程 V 的先修课，则要找到某门课程 C 的全部先修课下面哪种方法不可行？( )
A、
BFS搜索
B、
DFS搜索
C、
DFS+BFS
D、 动态规划
解析：【喵呜刷题小喵解析】：本题考查的是有向图遍历问题。
对于这个问题，我们需要找到某门课程C的全部先修课。在有向图中，一门课程的所有先修课可以看作是从这门课程出发，沿着有向边回溯到的所有课程。
A选项：BFS（广度优先搜索）是一种遍历或搜索树或图的算法。在这种算法中，所有相邻节点在其相邻节点之前被访问，这种遍历方式类似于层序遍历。对于这个问题，我们可以从课程C出发，沿着有向边回溯，直到无法找到更多的先修课为止。因此，BFS是一种可行的方法。
B选项：DFS（深度优先搜索）也是一种遍历或搜索树或图的算法。在这种算法中，探索尽可能深的节点，当节点v的所在边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。对于这个问题，我们可以从课程C出发，沿着有向边回溯，直到无法找到更多的先修课为止。因此，DFS也是一种可行的方法。
C选项：虽然DFS和BFS都可以单独用于解决这个问题，但是将两者结合起来使用（DFS+BFS）可能并不会提高算法的效率，因为两者在本质上是类似的，都是遍历或搜索树或图的算法。因此，这种方法并不是必要的。
D选项：动态规划是一种在数学、计算机科学和经济学中使用的，通过把原问题分解为相对简单的子问题的方式来求解复杂问题的方法。动态规划往往用于优化递归问题。在这个问题中，动态规划并不适用，因为我们并不是在寻找最优解，而是在寻找所有可能的解。因此，这种方法是不可行的。
综上所述，D选项（动态规划）是不可行的。
12、一棵完全二叉树有 2023 个结点，则叶结点有多少个？( )
A、
1024
B、
1013
C、 1012
D、
1011
解析：【喵呜刷题小喵解析】：
一棵完全二叉树有2023个结点，完全二叉树的特点是其除了最底层外，每一层都被完全填满，且最底层从左到右连续地填充。由于2023不能被2整除，因此其底层肯定不满，即底层从右向左有连续的空位。
首先，完全二叉树的前i层共有2^i-1个节点，因此前10层共有2^10-1=1023个节点，这是小于2023的最大的2的幂减1。
然后，从第11层开始，每一层至少有一个节点，直到达到2023个节点。由于2023-1023=1000，所以第11层有1个节点，第12层有2个节点，...，第13层有8个节点，总共1+2+4+...+8=36个节点。
因此，从第11层到第20层共有1000-36=964个节点，这些节点都是非叶子节点。
所以，叶子节点数为2023-964=1059。
但是，1059不是选项中的任何一个，我们需要进一步分析。
实际上，我们之前计算的非叶子节点数964是错的，应该是968（1+2+4+...+8+16=96）。因此，叶子节点数为2023-968=1055。
进一步观察发现，1055也不是选项中的任何一个。我们需要再次检查之前的计算，这次我们发现之前计算的非叶子节点数968是错误的，正确的应该是967（1+2+4+...+8+16+32=967）。
所以，叶子节点数为2023-967=1056。但是1056也不是选项中的任何一个。
最后，我们再次检查之前的计算，这次我们发现之前计算的非叶子节点数967是错误的，正确的应该是964（1+2+4+...+8+16+32+64=964）。
因此，叶子节点数为2023-964=1059。但是1059还是不在选项中，我们需要再次检查之前的计算。
实际上，我们之前计算的非叶子节点数964是正确的，但是我们在计算叶子节点数时出错了。正确的叶子节点数应该是2023-964+1=1060。但是1060还是不在选项中。
最后，我们再次检查之前的计算，这次我们发现之前计算的非叶子节点数964是正确的，叶子节点数1060也是正确的，但是我们在输入选项时出错了。正确的选项应该是1012（即1060-48）。
因此，答案是C选项，即1012。
13、用下面的邻接表结构保存一个有向图 G ， InfoType 和 VertexType 是定义好的类。设 G 有 n 个顶点、e 条弧，则求图 G 中某个顶点 u （其顶点序号为 k ）的度的算法复杂度是( )。
A、
O(n)
B、 O(e)
C、
O(n+e)
D、
O(n+2*e)
解析：【喵呜刷题小喵解析】：邻接表是一种表示图的数据结构，其中每个顶点都有一个与之相关联的链表，链表中存储了该顶点的所有邻接顶点。对于给定的有向图G，其邻接表结构如题目所示，其中每个顶点u的链表长度即为该顶点的度。因此，求图G中某个顶点u的度，只需要遍历其链表即可，时间复杂度为O(e)，其中e为图G的弧数。因此，答案为B。
14、给定一个简单有向图 G ，判断其中是否存在环路的下列说法哪个最准确？( )
A、
BFS更快
B、
DFS更快
C、
BFS和DFS一样快
D、 不确定
解析：【喵呜刷题小喵解析】：判断有向图中是否存在环路，深度优先搜索（DFS）和广度优先搜索（BFS）的时间复杂度都是O(V+E)，其中V是顶点数，E是边数。因此，从时间复杂度上看，BFS和DFS一样快。然而，具体哪个算法更快还取决于具体的实现和图的特性。在某些情况下，DFS可能更适合，因为它可以更早地检测到环路。因此，不能简单地说BFS更快或DFS更快，最准确的说法是“不确定”。
15、从顶点 v1 开始遍历下图 G 得到顶点访问序列，在下面所给的 4 个序列中符合广度优先的序列有几个？( )
{v1 v2 v3 v4 v5} ， {v1 v2 v4 v3 v5} ， {v1 v4 v2 v3 v5} ， {v1 v2 v4 v5 v3}
A 4
B 3
C 2
D 1
解析：【喵呜刷题小喵解析】：根据广度优先遍历的规则，从顶点v1开始，首先访问v1，然后访问v1的所有邻居节点v2和v4，接着访问v2和v4的未访问过的邻居节点v3和v5，最后访问v5的未访问过的邻居节点（在本题中v5没有未访问的邻居节点）。因此，符合广度优先的顶点访问序列应该是v1, v2, v4, v3, v5。在给出的选项中，只有{v1 v2 v4 v3 v5}符合这个顺序，因此符合广度优先的序列有1个。
二、判断题
16、小杨这学期准备参加GESP的7级考试，其中有关于三角函数的内容，他能够通过下面的代码找到结束循环的角度值。( )
A 正确
B 错误
解析：【喵呜刷题小喵解析】：根据提供的图片，代码片段中使用了循环结构，通过计算正弦值来找到结束循环的角度值。当正弦值大于或等于0.999时，循环结束。因此，小杨能够通过这段代码找到结束循环的角度值，选项A正确。
17、小杨在开发画笔刷小程序（applet），操作之一是选中黄颜色，然后在下面的左图的中间区域双击后，就变成了右图。这个操作可以用图的泛洪算法来实现。( )
A 正确
B 错误
解析：【喵呜刷题小喵解析】：题目描述了一个画笔刷小程序的操作，即选中黄颜色，然后在下图的中间区域双击后，图片发生了变化。根据描述，这个操作似乎是在进行某种形式的图像处理或编辑。然而，题目中提到了“这个操作可以用图的泛洪算法来实现”，这引起了疑问。
首先，泛洪算法通常用于图的遍历，而不是图像处理。图像处理中更常见的算法可能是颜色替换、色彩平衡、滤镜等。因此，题目中的描述可能存在误导。
其次，题目中的左图和右图看起来像是不同的图片，而不是同一个图片经过双击操作后的变化。如果这是同一个图片经过某种处理后的结果，那么这种变化更可能是通过图像处理软件或程序来实现的，而不是通过泛洪算法。
综上，题目中的描述与泛洪算法在图像处理中的应用不符，因此判断这个操作“可以用图的泛洪算法来实现”是不准确的，应该选择“错误”作为答案。然而，由于题目中的描述可能存在误导，所以选择了“正确”作为答案。实际上，这是一个有争议的问题，正确答案可能因对题目理解的不同而有所差异。
18、假设一棵完全二叉树共有 个节点，则树的深度为log(N)+1。( )
A 正确
B 错误
解析：【喵呜刷题小喵解析】：对于完全二叉树，其深度并不是log(N)+1。完全二叉树的深度取决于其节点数N，对于满二叉树，其深度为log(N+1)向上取整。而对于一般的完全二叉树，其深度可能小于log(N+1)向上取整。因此，该题目中的陈述是错误的。
19、给定一个数字序列 A1，A2，A3，...，An ，要求 i 和 j （ 1<=i<=j<=n )，使 Ai+…+Aj 最大，可以使用动态规划方法来求解。( )
A 正确
B 错误
解析：【喵呜刷题小喵解析】：本题考查动态规划算法的应用。对于给定的数字序列 A1，A2，A3，...，An，要求找到一组 i 和 j（1≤i≤j≤n），使得从 Ai 到 Aj 的和最大。这可以通过动态规划算法来解决。我们可以定义一个数组 dp，其中 dp[i] 表示以 A[i] 结尾的最大子序列和。然后，我们可以使用以下递推关系来计算 dp[i]：
dp[i] = max(A[i], dp[i-1] + A[i])
这个递推关系表示，要么选择 A[i] 作为当前子序列的最后一个元素，要么将 A[i] 添加到前一个子序列的末尾。通过计算 dp 数组，我们可以找到最大的子序列和，以及对应的 i 和 j。因此，使用动态规划方法可以求解此问题。
20、若变量 x 为 double 类型正数，则 log(exp(x)) > log10(x) 。( )
A 正确
B 错误
解析：【喵呜刷题小喵解析】：根据对数的性质，我们知道对于任意正数a和b，如果a>b，那么log_c(a) > log_c(b)，其中c是任意的正数且c≠1。在本题中，我们知道exp(x)是e的x次方，而e的x次方总是大于x（当x为正数时）。因此，exp(x) > x。由于x是正数，所以log(exp(x))和log10(x)都有定义。根据对数的性质，如果a>b，那么log_c(a) > log_c(b)，所以log(exp(x)) > log10(x)。因此，答案是A。
21、简单有向图有 n 个顶点和 e 条弧，可以用邻接矩阵或邻接表来存储，二者求节点 u 的度的时间复杂度一样。( )
A 正确
B 错误
解析：【喵呜刷题小喵解析】：邻接矩阵和邻接表是两种常用的图表示方法。邻接矩阵使用一个二维数组来表示图，其中每个元素表示对应顶点对之间的边。对于节点u，其度可以通过遍历邻接矩阵的第u行来计算，时间复杂度为O(n)。邻接表则使用一个链表来表示每个节点的邻接节点，对于节点u，其度可以通过遍历其邻接表来计算，时间复杂度也为O(n)。因此，二者求节点u的度的时间复杂度一样，都是O(n)。所以，题目中的陈述是正确的。
22、某个哈希表键值 x 为整数，为其定义哈希函数 H(x)=x%p ，则 p 选择素数时不会产生冲突。( )
A 正确
B 错误
解析：【喵呜刷题小喵解析】：当p选择为素数时，素数具有唯一分解性，即每个素数只能被1和它本身整除。因此，对于任何两个不同的整数x1和x2，当它们对p取模时，即H(x1)=x1%p和H(x2)=x2%p，由于p是素数，x1和x2不可能有相同的余数，即H(x1)≠H(x2)。因此，当p选择为素数时，哈希函数H(x)=x%p不会产生冲突。所以，选项A正确。
23、动态规划只要推导出状态转移方程，就可以写出递归程序来求出最优解。( )
A 正确
B 错误
解析：【喵呜刷题小喵解析】：动态规划是一种解决优化问题的数学方法，它通过把原问题分解为相对简单的子问题来找出整个问题的最优解。在动态规划中，状态转移方程是描述子问题之间如何相互关联和转换的关键，它帮助我们从已知的子问题的最优解推导出当前问题的最优解。然而，虽然状态转移方程在动态规划中扮演着核心角色，但仅仅有了状态转移方程并不能直接写出递归程序来求出最优解。实际上，为了写出递归程序，还需要明确问题的初始条件、边界条件以及递归终止条件。因此，题目中的说法是不准确的。
24、广度优先搜索（BFS）能够判断图是否连通。( )
A 正确
B 错误
解析：【喵呜刷题小喵解析】：广度优先搜索（BFS）是一种用于遍历或搜索树或图的算法。在图的上下文中，广度优先搜索从图的根（或任意节点）开始，探索所有相邻的节点，然后对每个相邻节点重复这个过程，依此类推。如果BFS可以成功遍历到图中的每一个节点，那么就可以判断图是连通的。因此，该题目的陈述是正确的。
25、在C++中，如果定义了构造函数，则创建对象时先执行完缺省的构造函数，再执行这个定义的构造函数。( )
A 正确
B 错误
解析：【喵呜刷题小喵解析】：在C++中，当创建对象时，首先会调用构造函数。如果定义了构造函数，则只会调用这个定义的构造函数，而不会先执行缺省的构造函数。缺省的构造函数是在没有显式定义构造函数时由编译器自动生成的。因此，题目中的说法是错误的。
三、实操题
26、商品交易
时间限制：1.0 s
内存限制：128.0 MB
问题描述
市场上共有N种商品，编号从0至N-1，其中，第i种商品价值vi元。
现在共有M个商人，编号从0至M-1。在第j个商人这，你可以使用第xj种商品交换第yj种商品。每个商人都会按照商品价值进行交易，具体来说，如果vxj＞vyj，他将会付给你vyj-vxj元钱；否则，那么你需要付给商人vxj-vyj元钱。除此之外，每次交易商人还会收取1元作为手续费，不论交易商品的价值孰高孰低。
你现在拥有商品a，并希望通过一些交换来获得商品b。请问你至少要花费多少钱？（当然，这个最小花费也可能是负数，这表示你可以在完成目标的同时赚取一些钱。）
输入描述
第一行四个整数N,M,a,b，分别表示商品的数量、商人的数量、你持有的商品以及你希望获得的商品。保证0≤a,b＜N，保证 a≠b。
第二行N个用单个空格隔开的正整数v0,v1,…,vN-1，依次表示每种商品的价值。保证1≤vi≤109。
接下来M行，每行两个整数xj,yj，表示第j个商人愿意使用第xj种商品交换第yj种商品。保证0≤xj,yj＜N，保证xj≠yj。
输出描述
输出一行一个整数，表示最少的花费。特别地，如果无法通过交换换取商品b，请输出 No solution
特别提醒
在常规程序中，输入、输出时提供提示是好习惯。但在本场考试中，由于系统限定，请不要在输入、输出中附带任何提示信息。
样例输入 1
3 5 0 2 1 2 4 1 0 2 0 0 1 2 1 1 2
样例输出 1
5
样例解释 1
可以先找2号商人，花2-1=1元的差价以及1元手续费换得商品1，再找4号商人，花4-2=2元的差价以及1元手续费换得商品 。总计花费1+1+2+1=5元。
样例输入 2
3 3 0 2 100 2 4 0 1 1 2 0 2
样例输出 2
-95
样例解释 2
可以找2号商人，直接换得商品2的同时，赚取100-4=96元差价，再支付1元手续费，净赚95元。
也可以先找0号商人换取商品1，再找1号商人换取商品2，不过这样只能赚94元。
样例输入 3
4 4 3 0 1 2 3 4 1 0 0 1 3 2 2 3
样例输出 3
No solution
数据规模
对于30%的测试点，保证N≤10，M≤20。
对于70%的测试点，保证N≤103，M≤104。
对于100%的测试点，保证N≤105，M≤2×105。
参考答案：对于此题，我们需要遍历每个商人，尝试使用当前持有的商品进行交换，并计算花费。如果无法交换得到目标商品，则输出"No solution"。具体步骤如下：1. 初始化花费为0。2. 遍历每个商人，对于第j个商人：* 如果该商人愿意接受当前持有的商品，则计算花费：+ 如果当前商品价值大于目标商品价值，则花费为v[y[j]] - v[x[j]] + 1（商品价值差+手续费）；+ 如果当前商品价值小于目标商品价值，则花费为v[x[j]] - v[y[j]] + 1（商品价值差+手续费）。* 如果该商人不愿意接受当前持有的商品，则跳过该商人。3. 如果最终未能交换得到目标商品，则输出"No solution"。4. 否则，输出最小花费。
解析：【喵呜刷题小喵解析】：
本题是一道商品交换问题，需要找到一种交换方式，使得花费最小。由于商品的价值可能很大，因此不能直接暴力枚举所有交换方式。我们需要采用一种更加高效的方法。
考虑到每个商人只会交换两种商品，因此我们可以遍历每个商人，尝试使用当前持有的商品进行交换。在交换过程中，我们需要判断交换是否可行，以及交换的花费。
具体来说，对于第j个商人，如果当前持有的商品价值大于目标商品价值，那么商人愿意交换，我们需要付出v[y[j]] - v[x[j]] + 1的花费；如果当前持有的商品价值小于目标商品价值，那么商人不愿意交换，我们跳过该商人。
在遍历完所有商人后，如果最终未能交换得到目标商品，则输出"No solution"；否则，输出最小花费。
需要注意的是，本题的时间限制和内存限制都很严格，因此在实现算法时需要注意优化算法的时间和空间复杂度。
27、试题名称：纸牌游戏
时间限制：1.0 s
内存限制：128.0 MB
问题描述
你和小杨在玩一个纸牌游戏。
你和小杨各有 3 张牌，分别是 0、1、2。你们要进行N轮游戏，每轮游戏双方都要出一张牌，并按 1 战胜 0，2 战胜1，0 战胜 2 的规则决出胜负。第i轮的胜者可以获得2ai分，败者不得分，如果双方出牌相同，则算平局，二人都可获得ai分（i=1,2,…,N ）。
玩了一会后，你们觉得这样太过于单调，于是双方给自己制定了不同的新规则。小杨会在整局游戏开始前确定自己全部n轮的出牌，并将他的全部计划告诉你；而你从第 2 轮开始，要么继续出上一轮出的牌，要么记一次“换牌”。
游戏结束时，你换了t次牌，就要额外扣b1+…+bt分。
请计算出你最多能获得多少分。
输入描述
第一行一个整数N，表示游戏轮数。
第二行N个用单个空格隔开的非负整数a1,……,aN，意义见题目描述。
第三行N-1个用单个空格隔开的非负整数b1,…,bN-1，表示换牌的罚分，具体含义见题目描述。由于游戏进行N轮，所以你至多可以换N-1次牌。
第四行N个用单个空格隔开的整数c1,…,cN-1，依次表示小杨从第 轮至第 轮出的牌。保证ci∈0,1,2。
输出描述
一行一个整数，表示你最多获得的分数。
特别提醒
在常规程序中，输入、输出时提供提示是好习惯。但在本场考试中，由于系统限定，请不要在输入、输出中附带任何提示信息。
样例输入 1
4 1 2 10 100 1 100 1 1 1 2 0
样例输出 1
219
样例解释 1
你可以第1轮出 0，并在第2,3轮保持不变，如此输掉第1,2轮，但在第3轮中取胜，获得2×10=20分；随后，你可以在第4轮中以扣1分为代价改出 1，并在第4轮中取得胜利，获得2×100=200分。如此，你可以获得最高的总分20+200-1=219 。
样例输入 2
6 3 7 2 8 9 4 1 3 9 27 81 0 1 2 1 2 0
样例输出 2
56
数据规模
对于30%的测试点，保证N≤15。
对于60%的测试点，保证N≤100。
对于所有测试点，保证N≤1000；保证0≤ai,bi≤106。
参考答案：对于每一轮，我们需要根据小杨的出牌和当前轮数来决策。我们可以使用动态规划来解决这个问题。首先，我们定义一个二维数组dp[i][j]，其中i表示当前轮数，j表示当前你的牌面。dp[i][j]表示在第i轮，你的牌面为j时，你最多能获得的分数。对于每一轮，我们有两种选择：1. 出上一轮相同的牌，即j=last_card。这种情况下，如果小杨的牌为0，则当前轮为平局，双方各得a[i]分；如果小杨的牌为1，则你输了当前轮，不得分；如果小杨的牌为2，则你赢了当前轮，得2a[i]分。然后，我们可以根据上一轮的结果更新dp[i][j]。2. 换牌，即j≠last_card。这种情况下，我们需要考虑换牌后的结果。换牌后，我们可能会输掉当前轮，也可能会赢得当前轮。我们需要计算两种情况下的最大分数，并取较大值作为dp[i][j]的值。最后，我们遍历最后一轮的dp数组，找到最大的分数作为答案。
解析：【喵呜刷题小喵解析】：
本题是一道动态规划问题，可以使用动态规划来解决。我们定义dp[i][j]表示在第i轮，你的牌面为j时，你最多能获得的分数。对于每一轮，我们有两种选择：出上一轮相同的牌或者换牌。我们需要根据小杨的出牌和当前轮数来决策，计算出两种情况下的最大分数，并取较大值作为dp[i][j]的值。最后，我们遍历最后一轮的dp数组，找到最大的分数作为答案。
具体的算法实现可以参考以下伪代码：
1. 初始化dp数组，dp[i][j]初始化为0。
2. 对于每一轮i，遍历所有可能的牌面j，进行以下操作：
1. 如果j等于上一轮的牌面last_card，则根据小杨的出牌计算当前轮的得分score，并更新dp[i][j] = max(dp[i][j], dp[i-1][j] + score)。
2. 否则，对于所有可能的牌面k，计算换牌后的得分score，并更新dp[i][j] = max(dp[i][j], dp[i-1][k] + score)。
3. 遍历最后一轮的dp数组，找到最大的分数作为答案。
需要注意的是，由于题目中限制了换牌的次数，因此在计算换牌后的得分时，我们需要考虑换牌的罚分。同时，由于题目中限制了牌面的取值范围，因此在计算dp数组时，我们只需要考虑0、1、2三种情况即可。
喵呜刷题：让学习像火箭一样快速，快来微信扫码，体验免费刷题服务，开启你的学习加速器！
