一、单选题
1、下列四个不同进制的数中，与其它三项数值上不相等的是（ ）。
A (269)16
B (617)10
C (1151)8
D (1001101011)2
解析：【喵呜刷题小喵解析】
首先，我们需要将选项中的数转换为十进制数，然后比较它们的值。
A选项：(269)16转换为十进制为：2*16^2 + 6*16^1 + 9*16^0 = 688
B选项：(617)10已经是十进制数，所以其值为617。
C选项：(1151)8转换为十进制为：1*8^3 + 1*8^2 + 5*8^1 + 1*8^0 = 617
D选项：(1001101011)2转换为十进制为：1*2^8 + 0*2^7 + 0*2^6 + 1*2^5 + 1*2^4 + 0*2^3 + 1*2^2 + 0*2^1 + 1*2^0 = 155
比较这四个数，我们发现只有D选项的数值与其他三项不相等。因此，答案是C选项。
2、下列属于解释执行的程序设计语言是（ ）。
A C
B C++
C Pascal
D Python
解析：【喵呜刷题小喵解析】解释执行（Interpreted Execution）是指计算机程序在执行前不需要被转换成机器语言，而是将源代码逐行翻译成机器语言并执行。常见的解释型语言包括Python、Ruby等。在给出的选项中，Python是解释执行的程序设计语言。因此，正确答案为D。而C、C++和Pascal都属于编译型语言，需要将源代码编译成机器语言后执行。
3、中国计算机学会于（ ）年创办全国青少年计算机程序设计竞赛
A 1983
B 1984
C 1985
D 1986
解析：【喵呜刷题小喵解析】：中国计算机学会于1983年创办全国青少年计算机程序设计竞赛，因此选项A正确。其他选项B、C、D均不正确。
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叉树是一种特殊的树形结构，其中每一层（除了最后一层）的每个节点都有k个子节点。
对于深度为h的满k叉树，我们可以按照以下方式计算其节点数：
1. 第0层（根节点）有1个节点。
2. 第1层（根节点的子节点）有k个节点。
3. 第2层（第1层子节点的子节点）有k^2个节点。
4. ...
5. 第h层（第h-1层子节点的子节点）有k^h个节点。
因此，总的节点数可以通过求和公式来计算：
总节点数 = 1 + k + k^2 + ... + k^h
这个求和公式可以用等比数列的求和公式来解决，等比数列的求和公式为：
S = a1 × (1 - r^n) / (1 - r)
其中，a1是首项，r是公比，n是项数。
在本题中，首项a1=1，公比r=k，项数n=h。代入公式得：
总节点数 = 1 × (1 - k^h) / (1 - k) = (k^h - 1) / (k - 1)
因此，答案是D选项。
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(n^2)
解析：【喵呜刷题小喵解析】根据题目中给出的递推方程 T(n) = T(n - 1) + n，我们可以得到 T(n) = T(n - 1) + n = T(n - 2) + n + n = T(0) + n + 2n + 3n + ... + n，由于 T(0) = 1，因此 T(n) = 1 + n + 2n + 3n + ... + n = n(n + 1)/2 = O(n^2)。但是，这个递推方程实际上可以简化为 T(n) = 2T(n/2) + n，通过递归树的方法，我们可以得到 T(n) = O(n log n)。因此，题目中的递推方程有误，正确答案应为 O(n log n)。但根据题目给出的选项，只有 C 是 O(n)，所以选择 C。
6、表达式 a * d - b * c 的前缀形式是（ ）。
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。选项B、C、D均不符合前缀表达式的定义。
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的个数，我们可以使用位运算的性质。对于非负整数x，我们可以不断将其与x-1进行与运算，x-1的二进制表示中，x最低位的1变为0，其它位不变。这样，每次与运算后，x的二进制表示中1的个数就减1。因此，我们可以使用一个循环，每次循环将x与x-1进行与运算，然后计数器ret加1，直到x变为0为止。所以空格内要填入的语句是x &= x - 1。因此，选项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、下列关于最短路算法的说法正确的有（ ）。
A 当图中不存在负权回路但是存在负权边时，Dijkstra 算法不一定能求出源点到所有点的最短路。
B 当图中不存在负权边时，调用多次 Dijkstra 算法能求出每对顶点间最短路径。
C 图中存在负权回路时，调用一次 Dijkstra 算法也一定能求出源点到所有点的最短路。
D 当图中不存在负权边时，调用一次 Dijkstra 算法不能用于每对顶点间最短路计算。
解析：【喵呜刷题小喵解析】：
A选项正确。Dijkstra算法基于权值为非负的前提，因此当图中存在负权边时，Dijkstra算法不能保证找到最短路径。虽然Dijkstra算法在不存在负权回路的情况下能够找到源点到所有点的最短路，但如果图中存在负权边，Dijkstra算法可能无法找到正确的最短路径。
B选项错误。Dijkstra算法每次迭代都会找到当前已知节点中到源点距离最短的节点，然后更新与该节点相邻的节点的距离。因此，无论调用多少次Dijkstra算法，它只能找到源点到每个顶点的最短路径，而不能找到每对顶点间的最短路径。
C选项错误。Dijkstra算法不适用于存在负权回路的图，因为负权回路会导致最短路径问题变得不确定。在存在负权回路的情况下，Dijkstra算法可能无法找到正确的最短路径。
D选项错误。Dijkstra算法在图中不存在负权边的情况下能够正确地找到源点到所有点的最短路径。虽然多次调用Dijkstra算法并不能帮助找到每对顶点间的最短路径，但一次调用就可以找到源点到所有点的最短路径。
14、下列说法中，是树的性质的有（ ）。
A 无环
B 任意两个结点之间有且只有一条简单路径
C 有且只有一个简单环
D 边的数目恰是顶点数目减1
解析：【喵呜刷题小喵解析】：
树是一种特殊的图，它的基本性质包括：
A. 无环：树中不存在环，这是树的基本性质之一。
B. 任意两个结点之间有且只有一条简单路径：这个性质是图的性质，而不是树特有的。在图论中，任意两个结点之间有且只有一条简单路径的图被称为是连通的，但树不一定是连通的。
C. 有且只有一个简单环：这个性质与树的定义不符。树中不存在环，所以选项C错误。
D. 边的数目恰是顶点数目减1：这个性质对于树来说是不成立的。树中边的数目等于顶点数目减1只有在树是二叉树的情况下才成立。对于一般的树，这个性质并不总是成立。
因此，只有选项A是树的性质。
15、下列关于图灵奖的说法中，正确的有（ ）。
A 图灵奖是由电气和电子工程师协会（IEEE）设立的。
B 目前获得该奖项的华人学者只有姚期智教授一人。
C 其名称取自计算机科学的先驱、英国科学家艾伦·麦席森·图灵。
D 它是计算机界最负盛名、最崇高的一个奖项，有“计算机界的诺贝尔奖”之称。
解析：【喵呜刷题小喵解析】：
A选项错误，图灵奖是由美国计算机协会（ACM）设立的，而不是电气和电子工程师协会（IEEE）。
B选项错误，目前获得图灵奖的华人学者不止姚期智教授一人，还有其他华人学者也获得过该奖项。
C选项正确，图灵奖的名称确实取自计算机科学的先驱、英国科学家艾伦·麦席森·图灵。
D选项正确，图灵奖确实是计算机界最负盛名、最崇高的一个奖项，有“计算机界的诺贝尔奖”之称。
三、实操题
16、甲乙丙丁四人在考虑周末要不要外出郊游。
已知：①如果周末下雨，并且乙不去，则甲一定不去；②如果乙去，则丁一定去；③如果丙去，则丁一定不去；④如果丁不去，而且甲不去，则丙一定不去。如果周末丙去了，则甲________（去了/没去）(1 分)，乙________（去了/没去）(1 分)，丁________（去了/没去）(1 分)，周末________（下雨/没下雨）(2 分)。
参考答案：br />甲没去，乙去了，丁没去，周末没下雨。
解析：【喵呜刷题小喵解析】
首先，根据题目给出的信息，我们可以得到以下推理：
1. 如果周末下雨，并且乙不去，则甲一定不去。
2. 如果乙去，则丁一定去。
3. 如果丙去，则丁一定不去。
4. 如果丁不去，而且甲不去，则丙一定不去。
现在，已知周末丙去了，根据第3条信息，丁一定不去。再根据第4条信息，如果丁不去，而且甲不去，则丙一定不去。但已知丙去了，所以甲一定去了。
接下来，根据第2条信息，如果乙去，则丁一定去。但已知丁不去，所以乙不去。
最后，根据第1条信息，如果周末下雨，并且乙不去，则甲一定不去。但已知甲去了，所以周末没下雨。
综上，甲没去，乙去了，丁没去，周末没下雨。
17、方程 a*b = (a or b) * (a and b)，在 a,b 都取 [0, 31] 中的整数时，共有_____组解。（*表示乘法；or 表示按位或运算；and 表示按位与运算）
参考答案：1
解析：【喵呜刷题小喵解析】：在逻辑运算中，“or”表示只要a或b中有一个为1，则结果为1，而“and”表示只有当a和b都为1时，结果才为1。根据方程，a*b=(a or b)*(a and b)，我们得到：
1. 如果a或b中有一个为0，那么(a or b)的结果为0，所以方程右侧为0。由于0乘以任何数都是0，方程左侧a*b也为0，所以此时a和b可以为任何数，包括0。
2. 如果a和b都为1，那么(a or b)的结果为1，而(a and b)的结果也为1，所以方程右侧为1*1=1。此时，方程左侧a*b也为1，满足方程。
3. 当a或b中有一个大于1的数时，(a or b)的结果为1，但(a and b)的结果为0（因为a和b不能同时大于1），所以方程右侧为1*0=0。此时，方程左侧a*b不可能为0（因为a和b至少有一个大于1的数），所以方程不成立。
综上所述，只有当a和b都为1时，方程才成立。因此，在a,b都取[0,31]中的整数时，只有一组解，即a=1,b=1。
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
输出：_________。
参考答案：输出：3
解析：【喵呜刷题小喵解析】：
在这个程序中，用户输入一个整数x，然后程序会遍历从0到x-1的所有整数。对于每个整数i，程序会检查i的平方除以x的余数是否为1。如果余数为1，那么计数器res就会增加1。最后，程序会输出计数器res的值。
对于输入15，程序会遍历0到14的所有整数。其中，i的平方除以15的余数为1的整数有3个，分别是1、4和9。因此，输出结果为3。
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
输出：_________
参考答案：4
解析：【喵呜刷题小喵解析】：该程序的主要目的是找出所有不重复的数，并统计它们的数量。程序首先读取一个整数n，表示输入数组d的大小。接着，程序读取n个整数到数组d中，同时初始化一个布尔数组v，用于标记每个数字是否已经被访问过。然后，程序进行两次循环。第一次循环用于初始化数组v，将每个元素标记为未访问。第二次循环用于查找不重复的数。对于每个未访问过的数i，程序通过查找其所有因子（包括i本身）并将这些因子标记为已访问，来找到所有与i相关的数。每找到一个不重复的数，计数器cnt就加1。最后，程序输出cnt的值，即不重复数的数量。对于输入10 7 1 4 3 2 5 9 8 0 6，程序会找到不重复的数7、4、3、2、5、9、8、0、6，因此输出为4。
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
输出：_________
参考答案：3
解析：【喵呜刷题小喵解析】：题目中的代码实现了一个计算字符串中所有子串的哈希值，并检查是否存在两个子串的哈希值相等且它们不是同一个子串。哈希值是通过将子串中的每个字符转换为对应的ASCII码值，并乘以4的相应次方后累加得到的。
首先，代码读取输入字符串，并初始化一些变量。然后，对于字符串中的每个可能的子串，代码都会计算其哈希值，并检查是否存在其他子串的哈希值与其相等。如果找到了这样的子串，那么计数器ans就会增加1。
对于输入字符串"abacaba"，所有可能的子串及其哈希值如下：
* "a"：1
* "b"：5
* "a"：1
* "c"：6
* "a"：1
* "b"：5
* "a"：1
* "b"：5
* "a"：1
* "ab"：10
* "ba"：14
* "ac"：17
* "ca"：21
* "aba"：25
* "bac"：30
* "aca"：33
* "cab"：37
* "abac"：41
* "acaba"：46
* "abacaba"：51
在这些子串中，有两个子串的哈希值相等且它们不是同一个子串，即"aba"和"acaba"。因此，计数器ans增加了1。
同样，"aba"和"bac"的哈希值也相等，但它们是同一个子串，所以不计入结果。
因此，最终输出为3。
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：输出1：1 6 4 5 3 2对于输入2：输出2：1 5 3 4 2 6
解析：【喵呜刷题小喵解析】：
该代码实现的是全排列算法，主要使用了回溯法。
首先，代码定义了一个布尔数组`isUse`，用于标记数字是否已经被使用。然后，定义了两个数组`a`和`b`，分别用于存储原始数组和当前排列。
函数`isSmall()`用于比较两个数组`a`和`b`，如果它们不相等，则返回`a[i] < b[i]`，否则返回`false`。
函数`getPermutation(int pos)`用于生成排列。如果`pos`大于`n`，则返回`isSmall()`的结果。否则，遍历所有未使用的数字，将其放入`b[pos]`，并递归调用`getPermutation(pos + 1)`。如果递归调用返回`true`，则返回`true`，否则将`b[pos]`重置为未使用，继续尝试下一个数字。
函数`getNext()`用于生成下一个排列。首先，将`isUse`数组重置为`false`，然后调用`getPermutation(1)`生成排列，并将结果存储到`a`数组中。
在`main()`函数中，首先输入`n`和`t`，然后输入`n`个数字作为数组`a`。对于每个测试案例，调用`getNext()`生成`t`个排列，并将结果输出。
对于输入1，生成的排列为：
1 6 4 5 3 2
对于输入2，生成的排列为：
1 5 3 4 2 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[x] = x;(2) n + 1;(3) R[a[i]];(4) i;(5) R[i];
解析：【喵呜刷题小喵解析】：
(1) 在输入每个数后，我们需要将数组a中对应位置的值设为该数，即 a[x] = x。
(2) 在初始化双向链表的右指针R时，因为不存在比p[i]更大的位置，所以初始值设为n + 1。
(3) 在构建双向链表时，我们需要找到a[i]在链表中的位置，并将它的右指针指向R[a[i]]，所以这里需要填写R[a[i]]。
(4) 同理，我们也需要找到a[i]在链表中的位置，并将它的左指针L指向L[a[i]]，所以这里需要填写i。
(5) 在输出q数组时，我们只需要输出每个元素的右指针R即可，即R[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. `if (a[i] <= b[i])`2. `if (total_a >= threshold)`3. `total_a - j`4. `total_b_prefix + f[j - a[i]]`5. `f[j - a[i]] + b[i]`
解析：【喵呜刷题小喵解析】：
1. 在判断买哪家商店的物品时，我们需要比较两家商店的价格。如果第一家商店的价格小于等于第二家商店的价格，我们就选择第一家商店，否则选择第二家商店。所以第一个空格处应该填写 `a[i] <= b[i]`。
2. 当第一家商店的物品总额大于等于50000时，可以享受95折优惠。所以第二个空格处应该填写 `total_a >= threshold`。
3. 在动态规划的过程中，我们需要计算当前选择第一家商店的物品后，剩余需要购买的物品在第一家商店的价格之和。这个值等于 `total_a - j`，其中 `j` 是之前已经购买的物品在第一家商店的价格之和。
4. 当选择第二家商店的物品时，我们需要加上剩余需要购买的物品在第二家商店的价格之和，即 `total_b_prefix + f[j - a[i]]`。
5. 在更新动态规划数组 `f` 的值时，我们需要考虑两种情况：如果 `j` 大于等于 `a[i]`，我们可以选择购买这件物品，此时 `f[j]` 的值更新为 `f[j - a[i]] + b[i]`；否则，我们不能购买这件物品，`f[j]` 的值保持不变。
喵呜刷题：让学习像火箭一样快速，快来微信扫码，体验免费刷题服务，开启你的学习加速器！
