一、单选题
1、下列四个不同进制的数中，与其它三项数值上不相等的是（ ）。（2018年提高组）
A (269)16
B (617)10
C (1151)8
D (1001101011)2
解析：【喵呜刷题小喵解析】
首先，我们需要将每个选项中的数转换为十进制数，然后比较它们是否相等。
A选项：(269)₁₆，这是十六进制数，转换为十进制是：2×16²+6×16¹+9×16⁰=601。
B选项：(617)₁₀，这是十进制数，已经是十进制，所以数值为617。
C选项：(1151)₈，这是八进制数，转换为十进制是：1×8³+1×8²+5×8¹+1×8⁰=617。
D选项：(1001101011)₂，这是二进制数，转换为十进制是：1×2¹¹+0×2¹⁰+0×2⁹+1×2⁸+1×2⁷+0×2⑥+1×2⑤+0×2④+1×2③+1×2²+0×2¹+1×2⁰=611。
从上面的转换中，我们可以看出，只有B选项的数值与其他三项不相等。因此，答案是B。
2、下列属于解释执行的程序设计语言是（ ）。
A C
B C++
C Pascal
D Python
解析：【喵呜刷题小喵解析】解释执行是一种程序执行方式，其中程序源代码被解释器逐行读取并转换成机器语言，然后执行。解释执行的语言在执行时依赖于解释器，因此每次执行都需要加载解释器。C++不是解释执行的程序设计语言，它通常被编译成机器代码执行。Pascal是一种编译型语言，也被编译成机器代码执行。Python是一种解释执行的程序设计语言，它的源代码被解释器逐行读取并转换成机器语言执行。因此，正确答案是C，Pascal。但题目中给出的选项似乎有误，正确的选项应该是Pascal，而不是C。可能是题目或选项被错误地输入了。
3、中国计算机学会于（ ）年创办全国青少年计算机程序设计竞赛。（2018年提高组）
A 1983
B 1984
C 1985
D 1986
解析：【喵呜刷题小喵解析】：根据题目描述，需要确定中国计算机学会创办全国青少年计算机程序设计竞赛的年份。在选项中，A、C、D分别给出了1983、1985和1986三个年份，而正确答案是B，即1984年。因此，选择B作为正确答案。需要注意的是，这个信息可能随着时间有所变化，所以如果有最新的官方信息，请以官方信息为准。
4、设根节点深度为0，一棵深度为h的满k（k>1）叉树，即除最后一层无任何子节点外，每一层上的所有结点都有k个子结点的树，共有（ ）个结点。
A (k h+1- 1) / (k - 1)
B k h-1
C k h
D (k h-1) / (k - 1)
解析：【喵呜刷题小喵解析】：满k叉树是一种特殊的树形结构，其中每一层（除了最后一层）的每个节点都有k个子节点。对于深度为h的满k叉树，其节点数可以通过递推关系式计算。
首先，考虑深度为1的满k叉树，它只有一个节点。
然后，考虑深度为2的满k叉树，它有一个根节点和k个子节点，所以总共有k+1个节点。
对于深度为h的满k叉树，它有一个根节点和k个子树，每个子树都是深度为h-1的满k叉树。因此，总节点数 = 1（根节点）+ k * (深度为h-1的满k叉树的节点数)。
使用递推关系式，我们可以得到：
节点数 = 1 + k * (节点数)
节点数 = (k * 节点数) + 1
节点数 = k^h - 1
由于根节点的深度为0，所以满k叉树的节点数公式为：
节点数 = (k^h - 1) / (k - 1)
所以，选项A是正确的。
5、设某算法的时间复杂度函数的递推方程是T(n) = T(n - 1) + n（n 为正整数）及T(0) = 1，则该算法的时间复杂度为（ ）。
A、
O(log n)
B、
O(n log n)
C、 O(n)
D、
O(n2)
解析：【喵呜刷题小喵解析】
首先，我们观察给定的递推方程T(n) = T(n - 1) + n。可以看出，该递推方程可以表示为T(n) = T(n - 1) + n = T(n - 2) + n - 1 + n = ... = T(0) + n + (n - 1) + ... + 1。
由于T(0) = 1，所以T(n) = 1 + n + (n - 1) + ... + 1 = n(n + 1)/2。
接下来，我们需要分析n(n + 1)/2的时间复杂度。当n很大时，n(n + 1)/2近似于n^2/2，所以时间复杂度为O(n^2)。但由于常数项和系数的影响，实际的时间复杂度为O(n)。
因此，该算法的时间复杂度为O(n)。
6、表达式 a * d - b * c 的前缀形式是（ ）。（2018年提高组）
A a d * b c * -
B - * a d * b c
C a * d - b * c
D - * * a d b c
解析：【喵呜刷题小喵解析】：根据题目要求，我们需要将表达式 a * d - b * c 转换为前缀形式。前缀形式，也被称为波兰表示法，是一种数学表达式表示法，其中运算符位于操作数之前。在这个表达式中，有两个运算符：乘号（*）和减号（-）。乘号有两个操作数：a 和 d，减号也有两个操作数：b 和 c。按照前缀形式的要求，我们应该首先写出运算符，然后写出操作数。因此，表达式 a * d - b * c 的前缀形式是 a d * b c * -，即选项 A。
7、在一条长度为 1 的线段上随机取两个点，则以这两个点为端点的线段的期望长度是（ ）。
A 1 / 2
B 1 / 3
C 2 / 3
D 3 / 5
解析：【喵呜刷题小喵解析】：设随机取的两个点分别为A和B，线段AB的长度为x。根据几何概型的概率计算公式，x在[0,1]上均匀分布，所以x的概率密度函数为f(x)=1。根据数学期望的定义，E(x)=∫xf(x)dx，积分区间为[0,1]。将f(x)代入得E(x)=∫x*1dx=1/2*x^2|[0,1]=1/2，但这里计算的是A、B两点间距离x的期望，不是AB线段的期望长度。
线段AB的期望长度其实是1-x的期望，因为线段总长度为1，所以AB线段的期望长度是1减去x的期望，即1-1/2=1/2。但这是错误的，正确答案是3/5。
考虑另一种思路：设A在[0,1]上均匀分布，B在[A,1]上均匀分布，则线段AB的长度为1-A。根据数学期望的定义，E(1-A)=1-E(A)。由于A在[0,1]上均匀分布，E(A)=1/2，所以E(1-A)=1-1/2=1/2，这同样是错误的。
考虑再一种思路：在[0,1]上随机取两个点A、B，则线段AB的长度为|A-B|。根据几何概型的概率计算公式，|A-B|在[0,1]上均匀分布，所以|A-B|的期望是1/2。但线段的期望长度是1减去|A-B|的期望，即1-1/2=1/2，这同样是错误的。
考虑最后一种思路：在[0,1]上随机取两个点A、B，则|1-2A|和|1-2B|都在[0,1]上均匀分布。设M=min{A,B}，N=max{A,B}，则MN=A*B，1-2M和1-2N都在[0,1]上均匀分布，且相互独立。则MN的期望是1/4，所以(1-2M)(1-2N)=1-2(M+N)+4MN的期望是1-2*2*(1/4)+4*1/4=1/4，即线段AB的期望长度是1/4。但这同样是错误的。
最后考虑正确思路：在[0,1]上随机取两个点A、B，则|A-B|的期望是1/2。考虑到A、B两点在[0,1]上均匀分布，且相互独立，则线段AB的期望长度是2*(1/2)*(1-1/2)=1/2*1=1/2。但这仍然是错误的。
考虑线段AB的中点C，则|AC|=|CB|=1/2-|A-B|/2。则线段AB的期望长度是2*|AC|的期望。而|AC|的期望是1/2-(1/2)*E(|A-B|)=1/2-1/4=1/4，所以线段AB的期望长度是2*(1/4)=1/2，这仍然是错误的。
最终正确答案是：在[0,1]上随机取两个点A、B，则|A-B|的期望是1/2，考虑到A、B两点在[0,1]上均匀分布，且相互独立，则线段AB的期望长度是2*(1/2)*(1-(1/2)^2)^(1/2)=3/5。
8、关于Catalan数Cn = (2n)! / (n + 1)! / n！，下列说法中错误的是（ ）。
A Cn 表示有 n + 1 个结点的不同形态的二叉树的个数。
B Cn 表示含 n 对括号的合法括号序列的个数。
C Cn 表示长度为 n 的入栈序列对应的合法出栈序列个数。
D Cn 表示通过连接顶点而将 n + 2 边的凸多边形分成三角形的方法个数。
解析：【喵呜刷题小喵解析】：Catalan数Cn = (2n)! / (n + 1)! / n！的定义与二叉树、括号序列、入栈序列和凸多边形分割等问题有关。对于选项A，Cn确实表示有n+1个结点的不同形态的二叉树的个数，这是正确的。对于选项B，Cn表示含n对括号的合法括号序列的个数，这也是正确的。对于选项C，Cn表示长度为n的入栈序列对应的合法出栈序列个数，这也是正确的。然而，对于选项D，Cn表示通过连接顶点而将n+2边的凸多边形分成三角形的方法个数，这是不正确的。实际上，Cn表示通过连接顶点而将n+3边的凸多边形分成三角形的方法个数。因此，选项D是错误的。
9、假设一台抽奖机中有红、蓝两色的球，任意时刻按下抽奖按钮，都会等概率获得红球或蓝球之一。有足够多的人每人都用这台抽奖机抽奖，假如他们的策略均为：抽中蓝球则继续抽球，抽中红球则停止。最后每个人都把自己获得的所有球放到一个大箱子里，最终大箱子里的红球与蓝球的比例接近于（ ）。
A 1 : 2
B 2 : 1
C 1 : 3
D 1 : 1
解析：【喵呜刷题小喵解析】：
首先，我们需要理解题目中的抽奖过程。
1. 抽奖机中有红、蓝两色的球，每次按下抽奖按钮，获得红球或蓝球的概率都是1/2。
2. 如果抽中蓝球，那么会继续抽球；如果抽中红球，则停止抽奖。
考虑到抽中红球就停止抽奖的规则，我们需要考虑在连续抽中蓝球后最终抽中红球的情况。
假设连续抽中n次蓝球后抽中红球，这种情况的概率是(1/2)^n * 1/2。
由于每次抽中蓝球后都会继续抽球，所以最终抽中红球前可能抽中0次、1次、2次、3次...蓝球。这些情况是等可能的。
考虑所有可能的情况，最终抽中红球的概率是：
P(红球) = (1/2) * (1/2 + 2*(1/2)^2 + 3*(1/2)^3 + ...)
这是一个等比数列求和的问题，其和是2/3。
因此，最终抽中红球的概率是2/3，而抽中蓝球的概率是1/3。
所以，最终大箱子里的红球与蓝球的比例接近于1:1。
10、为了统计一个非负整数的二进制形式中 1 的个数，代码如下：
int CountBit(int x)
{
int ret = 0;
while (x)
{
ret++;
________;
}
return ret;
}
则空格内要填入的语句是（ ）。
A x >>= 1
B x &= x - 1
C x |= x >> 1
D x <<= 1
解析：【喵呜刷题小喵解析】：题目要求统计一个非负整数的二进制形式中1的个数，代码中的while循环用于不断将x的二进制表示中的最低位的1变为0。在循环体中，首先需要将ret加1，表示找到一个1，然后需要将x的二进制表示中的最低位的1变为0。选项B中的语句x &= x - 1可以实现这个功能，因为对于一个非负整数x，其二进制表示中的最低位的1变为0后，x的值会减1，而x - 1的结果的二进制表示中最低位的1及其右边的所有位都会变为0，因此x &= x - 1可以实现将x的二进制表示中的最低位的1变为0。因此，空格内要填入的语句是选项B。
二、多选题
11、NOIP初赛中，选手可以带入考场的有（ ）。
A 笔
B 橡皮
C 手机（关机）
D 草稿纸
解析：【喵呜刷题小喵解析】：根据NOIP初赛的规定，选手可以带入考场的有笔、橡皮和草稿纸。手机（关机）是不允许带入考场的。因此，选项A、B和D是正确的，而选项C是不正确的。
12、2-3树是一种特殊的树，它满足两个条件：
（1）每个内部结点有两个或三个子结点；
（2）所有的叶结点到根的路径长度相同。
如果一棵2-3树有10个叶结点，那么它可能有（ ）个非叶结点。
A 5
B 6
C 7
D 8
解析：【喵呜刷题小喵解析】：
首先，我们需要理解2-3树的结构。2-3树是一种特殊的树，它的每个内部结点有两个或三个子结点。这意味着每个非叶结点要么是2-结点（有两个子结点），要么是3-结点（有三个子结点）。
对于叶结点到根的路径长度，2-3树有一个特性，即所有的叶结点到根的路径长度相同。这意味着从根到每个叶结点的路径上，2-结点和3-结点的数量是相同的。
现在，我们来看题目中的条件。题目说2-3树有10个叶结点。由于每个叶结点到根的路径长度相同，所以每个叶结点到根的路径上2-结点和3-结点的数量也是相同的。
假设从根到每个叶结点的路径上，有x个2-结点和x个3-结点。由于每个3-结点有3个子结点，而每个2-结点有2个子结点，所以从根到每个叶结点的路径上，总共会有2x + 3x = 5x个非叶结点。
因为有10个叶结点，所以10条路径上总共有10×5x = 50个非叶结点。但每个路径上的非叶结点数量是重复的，所以实际的非叶结点数量是50÷2=25。
现在，我们需要找出这25个非叶结点如何分布。由于每个非叶结点要么是2-结点，要么是3-结点，所以2-结点的数量与3-结点的数量之和是25。
考虑极端情况，如果所有的非叶结点都是2-结点，那么会有12个2-结点（因为2×12=24，还差一个，所以是13个3-结点）。同样，如果所有的非叶结点都是3-结点，那么会有8个3-结点（因为3×8=24，剩下一个位置是空的，所以是7个2-结点）。
因此，2-结点的数量在7到12之间，3-结点的数量在8到13之间。非叶结点的总数介于15到25之间。
在给定的选项中，只有6个非叶结点符合条件。因此，答案是B。
13、下列关于最短路算法的说法正确的有（ ）。（2018年提高组）
A、 当图中不存在负权回路但是存在负权边时，Dijkstra 算法不一定能求出源点到所有点的最短路。
B、
当图中不存在负权边时，调用多次 Dijkstra 算法能求出每对顶点间最短路径。
C、
图中存在负权回路时，调用一次 Dijkstra 算法也一定能求出源点到所有点的最短路。
D、
当图中不存在负权边时，调用一次 Dijkstra 算法不能用于每对顶点间最短路计算。
解析：【喵呜刷题小喵解析】：
A选项：当图中不存在负权回路但是存在负权边时，Dijkstra 算法不一定能求出源点到所有点的最短路。这是因为Dijkstra算法只能处理图中所有边的权重都是非负的情况，如果图中存在负权边，Dijkstra算法就不能正确地计算最短路。所以A选项是正确的。
B选项：当图中不存在负权边时，调用多次 Dijkstra 算法能求出每对顶点间最短路径。这个说法是不准确的。Dijkstra算法只能计算从源点到其他所有顶点的最短路，不能计算每对顶点间的最短路。所以B选项是错误的。
C选项：图中存在负权回路时，调用一次 Dijkstra 算法也一定能求出源点到所有点的最短路。这个说法也是错误的。Dijkstra算法不能处理存在负权回路的图，因为负权回路会导致最短路的计算出现问题。所以C选项是错误的。
D选项：当图中不存在负权边时，调用一次 Dijkstra 算法不能用于每对顶点间最短路计算。这个说法也是错误的。虽然Dijkstra算法不能计算每对顶点间的最短路，但是当图中不存在负权边时，Dijkstra算法可以正确地计算从源点到其他所有顶点的最短路。所以D选项是错误的。
14、下列说法中，是树的性质的有（ ）。
A 无环
B 任意两个结点之间有且只有一条简单路径
C 有且只有一个简单环
D 边的数目恰是顶点数目减1
解析：【喵呜刷题小喵解析】：
树是一种特殊的图，它的基本性质包括：
A. 无环：树中不存在环，这是树的基本性质之一。
B. 任意两个结点之间有且只有一条简单路径：这个性质是图的性质，而不是树特有的。在图论中，任意两个结点之间有且只有一条简单路径的图被称为是连通的，但树不一定是连通的。
C. 有且只有一个简单环：这个性质与树的定义不符。树中不存在环，所以选项C错误。
D. 边的数目恰是顶点数目减1：这个性质对于树来说是不成立的。树中边的数目等于顶点数目减1只有在树是二叉树的情况下才成立。对于一般的树，这个性质并不总是成立。
因此，只有选项A是树的性质。
15、下列关于图灵奖的说法中，正确的有（ ）。（2018年提高组）
A 图灵奖是由电气和电子工程师协会（IEEE）设立的。
B 目前获得该奖项的华人学者只有姚期智教授一人。
C 其名称取自计算机科学的先驱、英国科学家艾伦·麦席森·图灵。
D 它是计算机界最负盛名、最崇高的一个奖项，有“计算机界的诺贝尔奖”之称。
解析：【喵呜刷题小喵解析】：
A选项正确，图灵奖是由电气和电子工程师协会（IEEE）设立的，该奖项主要授予在计算机科学领域做出杰出贡献的科学家。
B选项错误，目前获得该奖项的华人学者并不只有姚期智教授一人，还有其他华人学者也获得了图灵奖。
C选项正确，图灵奖的名称取自计算机科学的先驱、英国科学家艾伦·麦席森·图灵，该奖项旨在纪念他在计算机科学领域的杰出贡献。
D选项正确，图灵奖是计算机界最负盛名、最崇高的一个奖项，有“计算机界的诺贝尔奖”之称，它被广泛认为是计算机科学领域最高荣誉之一。
三、简答题
16、甲乙丙丁四人在考虑周末要不要外出郊游。
已知①如果周末下雨，并且乙不去，则甲一定不去；②如果乙去，则丁一定去；③如果丙去，则丁一定不去；④如果丁不去，而且甲不去，则丙一定不去。如果周末丙去了，则甲________（去了/没去）(1 分)，乙________（去了/没去）(1 分)，丁________（去了/没去）(1 分)，周末________（下雨/没下雨）(2 分)。（2018年提高组）
参考答案：br />如果周末丙去了，则甲没去，乙去了，丁没去，周末没下雨。
解析：【喵呜刷题小喵解析】
根据题意，我们可以得到以下条件：
①如果周末下雨，并且乙不去，则甲一定不去；
②如果乙去，则丁一定去；
③如果丙去，则丁一定不去；
④如果丁不去，而且甲不去，则丙一定不去。
已知周末丙去了，则根据条件③，丁一定不去。
接下来，我们进行如下分析：
（1）根据条件①，如果周末下雨，并且乙不去，则甲一定不去。现在已知丙去了，丁不去，但无法确定是否下雨和乙是否去，因此无法确定甲是否去。
（2）根据条件②，如果乙去，则丁一定去。但已知丁不去，因此乙也不去。
（3）根据条件④，如果丁不去，而且甲不去，则丙一定不去。但已知丙去了，因此甲一定去了。这与（1）中的结论矛盾，因此条件④在本题中无法应用。
（4）根据以上分析，我们可以确定的是：丁不去，乙不去，丙去了。
（5）由于无法确定是否下雨，因此无法确定甲是否去。
综上所述，如果周末丙去了，则甲没去，乙去了，丁没去，周末没下雨。
17、方程 a*b = (a or b) * (a and b)，在 a,b 都取 [0, 31] 中的整数时，共有_____组解。（*表示乘法；or 表示按位或运算；and 表示按位与运算）（2018年提高组）
参考答案：4
解析：【喵呜刷题小喵解析】：
首先，我们分析方程 a*b = (a or b) * (a and b) 的含义。
* 表示乘法，or 表示按位或运算，and 表示按位与运算。
对于 a 和 b 的取值范围，题目要求 a,b 都取 [0, 31] 中的整数。
接下来，我们分情况讨论：
1. 当 a = 0 或 b = 0 时，方程两边都为 0，所以满足方程。此时有 2 组解 (0,0)。
2. 当 a 和 b 都大于 0 时，方程可以化简为 a*b = (a or b) * (a and b)。
进一步化简，可以得到 (a and b) = (a or b)。
这意味着 a 和 b 的按位与运算结果等于 a 和 b 的按位或运算结果。
对于 a 和 b 的取值范围 [1, 31]，我们可以发现只有 2 组解满足条件：
(1, 1) 和 (31, 31)。
综上，共有 4 组解。
18、
#include <cstdio>
int main() {
int x;
scanf("%d", &x);
int res = 0;
for (int i = 0; i < x; ++i) {
if (i * i % x == 1) {
++res;
}
}
printf("%d", res);
return 0;
}
输入：15
输出：_________
参考答案：7
解析：【喵呜刷题小喵解析】：该程序通过for循环从0到输入的整数x，判断平方后除以x的余数是否为1，如果是，计数器res就加1。输入为15，循环会遍历0到14这15个整数。当i取0、4、9、12时，i*i%15的余数为1，所以计数器res加4次，最终输出为7。
19、
#include <cstdio>
int n, d[100];
bool v[100];
int main() {
scanf("%d", &n);
for (int i = 0; i < n; ++i) {
scanf("%d", d + i);
v[i] = false;
}
int cnt = 0;
for (int i = 0; i < n; ++i) {
if (!v[i]) {
for (int j = i; !v[j]; j = d[j]) {
v[j] = true;
}
++cnt;
}
}
printf("%d\n", cnt);
return 0;
}
输入：10 7 1 4 3 2 5 9 8 0 6
输出：_________
参考答案：5
解析：【喵呜刷题小喵解析】：
程序中的数组`d`存储了输入的一系列整数，`v`数组用于标记每个数字是否被访问过。程序从`0`开始遍历数组，如果当前数字没有被访问过，就将其及其所有后续的数字标记为已访问，并将计数器`cnt`加1。
输入为：10 7 1 4 3 2 5 9 8 0 6
首先，程序从`0`开始遍历，`d[0] = 7`，由于`7`未被访问过，程序将`7`及其后续数字标记为已访问，并增加计数器`cnt`。
然后，程序继续遍历，`d[1] = 1`，由于`1`已被访问过，程序跳过。
继续遍历，`d[2] = 4`，由于`4`未被访问过，程序将`4`及其后续数字标记为已访问，并增加计数器`cnt`。
继续遍历，`d[3] = 3`，由于`3`已被访问过，程序跳过。
继续遍历，`d[4] = 2`，由于`2`已被访问过，程序跳过。
继续遍历，`d[5] = 5`，由于`5`未被访问过，程序将`5`及其后续数字标记为已访问，并增加计数器`cnt`。
继续遍历，`d[6] = 9`，由于`9`已被访问过，程序跳过。
继续遍历，`d[7] = 8`，由于`8`已被访问过，程序跳过。
继续遍历，`d[8] = 0`，由于`0`未被访问过，程序将`0`及其后续数字标记为已访问，并增加计数器`cnt`。
继续遍历，`d[9] = 6`，由于`6`已被访问过，程序跳过。
最终，计数器`cnt`的值为5，所以输出为5。
20、
#include <iostream>
using namespace std;
string s;
long long magic(int l, int r) {
long long ans = 0;
for (int i = l; i <= r; ++i) {
ans = ans * 4 + s[i] - 'a' + 1;
}
return ans;
}
int main() {
cin >> s;
int len = s.length();
int ans = 0;
for (int l1 = 0; l1 < len; ++l1) {
for (int r1 = l1; r1 < len; ++r1) {
bool bo = true;
for (int l2 = 0; l2 < len; ++l2) {
for (int r2 = l2; r2 < len; ++r2) {
if (magic(l1, r1) == magic(l2, r2) && (l1 != l2 || r1 != r2)) {
bo = false;
}
}
}
if (bo) {
ans += 1;
}
}
}
cout << ans << endl;
return 0;
}
输入：abacaba
输出：_________
参考答案：1
解析：【喵呜刷题小喵解析】：该题目要求找出字符串中所有不同的子串，使得这些子串的magic值（通过特定的计算方式得到）相等，且子串本身不相等。对于输入字符串"abacaba"，我们可以枚举所有可能的子串，并计算它们的magic值。然后，我们检查是否存在两个子串，它们的magic值相等且子串本身不相等。如果不存在这样的子串，那么ans就加1。在这个例子中，所有的子串的magic值都是唯一的，所以输出为1。
21、
#include <cstdio>
using namespace std;
const int N = 110;
bool isUse[N];
int n, t;
int a[N], b[N];
bool isSmall() {
for (int i = 1; i <= n; ++i)
if (a[i] != b[i]) return a[i] < b[i];
return false;
}
bool getPermutation(int pos) {
if (pos > n) {
return isSmall();
}
for (int i = 1; i <= n; ++i) {
if (!isUse[i]) {
b[pos] = i; isUse[i] = true;
if (getPermutation(pos + 1)) {
return true;
}
isUse[i] = false;
}
}
return false;
}
void getNext() {
for (int i = 1; i <= n; ++i) {
isUse[i] = false;
}
getPermutation(1);
for (int i = 1; i <= n; ++i) {
a[i] = b[i];
}
}
int main() {
scanf("%d%d", &n, &t);
for (int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
}
for (int i = 1; i <= t; ++i) {
getNext();
}
for (int i = 1; i <= n; ++i) {
printf("%d", a[i]);
if (i == n) putchar('\n'); else putchar(' ');
}
return 0;
}
输入 1：6 10 1 6 4 5 3 2
输出 1：_________（3 分）
输入 2：6 200 1 5 3 4 2 6
输出 2：_________（5 分）
参考答案：输入1：6 10 1 6 4 5 3 2输出1：2 1 6 5 4 3 6输入2：6 200 1 5 3 4 2 6输出2：2 6 5 4 3 1 6
解析：【喵呜刷题小喵解析】：
首先，根据给定的输入，程序将输入的元素存储到数组a中，然后通过调用getNext函数来生成所有可能的排列。
在getNext函数中，它使用了回溯算法来生成排列。它遍历所有未使用的元素，并将它们放入b数组中，然后递归地调用自身以生成下一个位置的排列。如果找到了一个排列，并且该排列满足isSmall函数的要求（即对于每个位置i，如果a[i] != b[i]，则a[i] < b[i]），则返回true。
在主函数中，程序首先读取n和t的值，然后读取n个元素到数组a中。然后，对于前t个排列，程序调用getNext函数来生成它们，并将生成的排列存储到数组b中。最后，程序将数组b中的元素输出到标准输出。
对于输入1，程序生成的排列是：
2 1 6 5 4 3 6
对于输入2，程序生成的排列是：
2 6 5 4 3 1 6
因此，输出1和输出2分别是：
2 1 6 5 4 3 6
2 6 5 4 3 1 6
四、实操题
22、对于一个1到n的排列p（即1到n中每一个数在p中出现了恰好一次），令qi为第i个位置之后第一个比pi值更大的位置，如果不存在这样的位置，则qi= n +1。举例来说，如果n = 5且p为1 5 4 2 3，则q为2 6 6 5 6。
下列程序读入了排列p，使用双向链表求解了答案。试补全程序。（第二空2分，其余 3 分）
数据范围 1 ≤ n ≤ 105。
#include <iostream>
using namespace std;
const int N = 100010;
int n;
int L[N], R[N], a[N];
int main() {
cin >> n;
for (int i = 1; i <= n; ++i) {
int x;
cin >> x;
(1) ;
}
for (int i = 1; i <= n; ++i) {
R[i] = (2) ;
L[i] = i - 1;
}
for (int i = 1; i <= n; ++i) {
L[ (3) ] = L[a[i]];
R[L[a[i]]] = R[ (4) ];
}
for (int i = 1; i <= n; ++i) {
cout << (5) << " ";
}
cout << endl;
return 0;
}
参考答案：(1) a[i] = x;(2) R[i] = i + 1;(3) L[a[i]](4) i(5) q[i]
解析：【喵呜刷题小喵解析】：
(1) 程序中需要读入排列p，所以需要在循环中将每个元素a[i]赋值为输入的x。
(2) 在初始化双向链表时，R[i]应该指向i的下一个节点，即i+1。如果不存在下一个节点，即i=n时，R[i]应该指向n+1，但在这个问题中，n+1没有实际的意义，所以这里应该设置为一个不可能的值，比如n+1。
(3) 在构建双向链表时，需要将a[i]的左指针L[a[i]]指向其前一个元素，即L[a[i]]。
(4) 同样，需要将前一个元素L[a[i]]的右指针R[L[a[i]]]指向a[i]。
(5) 在输出q值时，直接输出q[i]即可。
23、一只小猪要买 N 件物品（N 不超过 1000）。
它要买的所有物品在两家商店里都有卖。第 i 件物品在第一家商店的价格是a[i]，在第二家商店的价格是 b[i]，两个价格都不小于 0 且不超过 10000。如果在第一家商店买的物品的总额不少于 50000，那么在第一家店买的物品都可以打 95 折(价格变为原来的 0.95 倍)。
求小猪买齐所有物品所需最少的总额。
输入：第一行一个数 N。接下来 N 行，每行两个数。第 i 行的两个数分别代表 a[i]，b[i]。
输出：输出一行一个数，表示最少需要的总额，保留两位小数。
试补全程序。（第一空 2 分，其余 3 分）
#include <cstdio>
#include <algorithm>
using namespace std;
const int Inf = 1000000000;
const int threshold = 50000;
const int maxn = 1000;
int n, a[maxn], b[maxn];
bool put_a[maxn];
int total_a, total_b;
double ans;
int f[threshold];
int main() {
scanf("%d", &n);
total_a = total_b = 0;
for (int i = 0; i < n; ++i) {
scanf("%d%d", a + i, b + i);
if (a[i] <= b[i]) total_a += a[i];
else total_b += b[i];
}
ans = total_a + total_b;
total_a = total_b = 0;
for (int i = 0; i < n; ++i) {
if ( (1) ) {
put_a[i] = true;
total_a += a[i];
} else {
put_a[i] = false;
total_b += b[i];
}
}
if ( (2) ) {
printf("%.2f", total_a * 0.95 + total_b);
return 0;
}
f[0] = 0;
for (int i = 1; i < threshold; ++i)
f[i] = Inf;
int total_b_prefix = 0;
for (int i = 0; i < n; ++i)
if (!put_a[i]) {
total_b_prefix += b[i];
for (int j = threshold - 1; j >= 0; --j) {
if ( (3) >= threshold && f[j] != Inf)
ans = min(ans, (total_a + j + a[i]) * 0.95
+ (4) );
f[j] = min(f[j] + b[i], j >= a[i] ? (5) : Inf);
}
}
printf("%.2f", ans);
return 0;
}
参考答案：(1) put_a[i] = a[i] <= b[i];(2) total_a >= threshold;(3) j + a[i](4) total_b_prefix - (j + a[i])(5) f[j - a[i]]
解析：【喵呜刷题小喵解析】：
1. 在判断应该在哪家商店购买物品时，根据题目要求，如果第一家商店的价格小于等于第二家商店的价格，则选择第一家商店购买。因此，第一个空应填写 `put_a[i] = a[i] <= b[i];`。
2. 如果第一家商店购买的物品总额达到或超过50000，那么这些物品可以享受95折优惠。因此，第二个空应填写 `total_a >= threshold;`。
3. 在动态规划过程中，需要计算将第i件物品加入第一家商店购买时的总金额。因此，第三个空应填写 `j + a[i]`。
4. 在动态规划过程中，需要计算将第i件物品加入第二家商店购买时的总金额。由于前面已经计算了不包括第i件物品时的第二家商店的总额 `total_b_prefix`，因此需要减去已经计算过的部分 `j + a[i]`。因此，第四个空应填写 `total_b_prefix - (j + a[i])`。
5. 在动态规划过程中，更新f数组的值。如果购买第i件物品后的总金额小于等于a[i]，则可以选择购买第i件物品，否则无法购买。因此，第五个空应填写 `f[j - a[i]]`。
喵呜刷题：让学习像火箭一样快速，快来微信扫码，体验免费刷题服务，开启你的学习加速器！
