2023年12月 GESP C++ 7级

定义变量 double x，如果下面代码输入为 $100$，输出最接近( )。

对于下面动态规划方法实现的函数，以下选项中最适合表达其状态转移函数的为( )。

下面代码可以用来求最长上升子序列（LIS）的长度，如果输入是：$5$ $1$ $7$ $3$ $5$ $9$，则输出是( )。

C++ 语言中，下列关于关键字 static 的描述不正确的是( )。

$G$ 是一个非连通无向图，共有 $28$ 条边，则该图至少有( )个顶点。

哈希表长 $31$，按照下面的程序依次输入 $4$ $17$ $28$ $30$ $4$，则最后的 $4$ 存入哪个位置？（ ）

某二叉树 $T$ 的先序遍历序列为：{A B D F C E G H}，中序遍历序列为：{B F D A G E H C}，则下列说法中正确的是( )。

下面代码段可以求两个字符串 $s1$ 和 $s2$ 的最长公共子串（LCS），下列相关描述不正确的是（ ）。

图的广度优先搜索中既要维护一个标志数组标志已访问的图的结点，还需哪种结构存放结点以实现遍历？( )

对关键字序列 {$44$，$36$，$23$，$35$，$52$，$73$，$90$，$58$} 建立哈希表，哈希函数为 $h(k)=k\%7$，执行下面的 Insert 函数，则等概率情况下的平均成功查找长度（即查找成功时的关键字比较次数的均值）为( )。

学生在读期间所上的某些课程中需要先上其他的课程，所有课程和课程间的先修关系构成一个有向图 $G$，有向边 $<U,V>$ 表示课程 $U$ 是课程 $V$ 的先修课，则要找到某门课程 $C$ 的全部先修课下面哪种方法不可行？( )

一棵完全二叉树有 $2023$ 个结点，则叶结点有多少个？( )

用下面的邻接表结构保存一个有向图 $G$ ， InfoType 和 VertexType 是定义好的类。设 $G$ 有 $n$ 个顶点、 $e$ 条弧，则求图 $G$ 中某个顶点 $u$ （其顶点序号为 $k$ ）的度的算法复杂度是( )。

给定一个简单有向图 $G$ ，判断其中是否存在环路的下列说法哪个最准确？( )

从顶点 v1v_1v1​ 开始遍历下图 $G$ 得到顶点访问序列，在下面所给的 $4$ 个序列中符合广度优先的序列有几个？( ) {v1v_1v1​ v2v_2v2​ v3v_3v3​ v4v_4v4​ v5v_5v5​} ，{v1v_1v1​ v2v_2v2​ v4v_4v4​ v3v_3v3​ v5v_5v5​}，{v1v_1v1​ v4v_4v4​ v2v_2v2​ v3v_3v3​ v5v_5v5​}，{v1v_1v1​ v2v_2v2​ v4v_4v4​ v5v_5v5​ v3v_3v3​}

小杨这学期准备参加 GESP 的 7 级考试，其中有关于三角函数的内容，他能够通过下面的代码找到结束循环的角度值。( )

小杨在开发画笔刷小程序（applet），操作之一是选中黄颜色，然后在下面的左图的中间区域双击后，就变成了右图。这个操作可以用图的泛洪算法来实现。( )

假设一棵完全二叉树共有 $N$ 个节点，则树的深度为 ⌊log⁡2N⌋+1\lfloor \log_2 N \rfloor + 1⌊log2​N⌋+1。( )

给定一个数字序列 A1A_1A1​，A2A_2A2​，A3A_3A3​，...，AnA_nAn​，要求 $i$ 和 $j$（$1\le i\le j\le n$），使 Ai+⋯+AjA_i + \dots + A_jAi​+⋯+Aj​ 最大，可以使用动态规划方法来求解。( )

若变量 $x$ 为 double 类型正数，则 log(exp(x)) > log10(x)。( )

简单有向图有 $n$ 个顶点和 $e$ 条弧，可以用邻接矩阵或邻接表来存储，二者求节点 $u$ 的度的时间复杂度一样。( )

某个哈希表键值 $x$ 为整数，为其定义哈希函数 $H(x)=x\%p$，则 $p$ 选择素数时不会产生冲突。( )

动态规划只要推导出状态转移方程，就可以写出递归程序来求出最优解。( )

广度优先搜索（BFS）能够判断图是否连通。( )

在 C++ 中，如果定义了构造函数，则创建对象时先执行完缺省的构造函数，再执行这个定义的构造函数。()

试题名称：商品交易

时间限制：1.0 s | 内存限制：512.0 MB

题目描述

市场上共有 $N$ 种商品，编号从 $0$ 至 $N-1$ ，其中，第 $i$ 种商品价值 viv_ivi​ 元。

现在共有 $M$ 个商人，编号从 $0$ 至 $M-1$ 。在第 $j$ 个商人这，你可以使用你手上的第 xjx_jxj​ 种商品交换商人手上的第 yjy_jyj​ 种商品。每个商人都会按照商品价值进行交易，具体来说，如果 vxj>vyjv_{x_j}>v_{y_j}vxj​​>vyj​​，他将会付给你 vxj−vyjv_{x_j}-v_{y_j}vxj​​−vyj​​元钱；否则，那么你需要付给商人 vyj−vxjv_{y_j}-v_{x_j}vyj​​−vxj​​ 元钱。除此之外，每次交易商人还会收取 $1$ 元作为手续费，不论交易商品的价值孰高孰低。

你现在拥有商品 $a$ ，并希望通过一些交换来获得商品 $b$ 。请问你至少要花费多少钱？（当然，这个最小花费也可能是负数，这表示你可以在完成目标的同时赚取一些钱。）

输入格式

第一行四个整数 $N,M,a,b$，分别表示商品的数量、商人的数量、你持有的商品以及你希望获得的商品。保证 $0\le a,b<N$ ，保证 $a\ne b$。

第二行 $N$ 个用单个空格隔开的正整数 v0,v1,…,vN−1v_0,v_1,…,v_{N-1}v0​,v1​,…,vN−1​ ，依次表示每种商品的价值。保证 1≤vi≤1091≤v_i≤10^91≤vi​≤109。

接下来 $M$ 行，每行两个整数 xj,yjx_j,y_jxj​,yj​ ，表示在第 $j$ 个商人这，你可以使用第 xjx_jxj​ 种商品交换第 yjy_jyj​ 种商品。保证 0≤xj,yj<N0≤x_j,y_j<N0≤xj​,yj​<N，保证 xj≠yjx_j≠y_jxj​=yj​ 。

输出格式

输出一行一个整数，表示最少的花费。特别地，如果无法通过交换换取商品 $b$ ，请输出 No solution。

样例输入 #1

3 5 0 2
1 2 4
1 0
2 0
0 1
2 1
1 2

样例输出 #1

5

样例输入 #2

3 3 0 2
100 2 4
0 1
1 2
0 2

样例输出 #2

-95

样例输入 #3

4 4 3 0
1 2 3 4
1 0
0 1
3 2
2 3

样例输出 #3

No solution

说明/提示

数据范围

对于 30% 的测试点，保证 $N\le 10$，$M\le 20$。

对于 70% 的测试点，保证 N≤103N ≤10^3N≤103，M≤104M≤10^4M≤104。

对于 100% 的测试点，保证 N≤105N≤10^5N≤105，M≤2×105M≤2×10^5M≤2×105。

试题名称：纸牌游戏

时间限制：1.0 s | 内存限制：512.0 MB

题目描述

你和小杨在玩一个纸牌游戏。

你和小杨各有 $3$ 张牌，分别是 $0、1、2$。你们要进行 $N$ 轮游戏，每轮游戏双方都要出一张牌，并按 $1$ 战胜 $0$，$2$ 战胜 $1$，$0$ 战胜 $2$ 的规则决出胜负。第 $i$ 轮的胜者可以获得 2×ai2 \times a_i2×ai​ 分，败者不得分，如果双方出牌相同，则算平局，二人都可获得 aia_iai​ 分 $(i=1,2,\cdots ,N)$。

玩了一会后，你们觉得这样太过于单调，于是双方给自己制定了不同的新规则。小杨会在整局游戏开始前确定自己全部 $n$ 轮的出牌，并将他的全部计划告诉你；而你从第 $2$ 轮开始，要么继续出上一轮出的牌，要么记一次“换牌”。游戏结束时，你换了 $t$ 次牌，就要额外扣 b1+⋯+btb_1+\cdots+b_tb1​+⋯+bt​ 分。

请计算出你最多能获得多少分。

输入格式

第一行一个整数 $N$，表示游戏轮数。

第二行 $N$ 个用单个空格隔开的非负整数 a1,⋯ ,aNa_1,\cdots,a_Na1​,⋯,aN​，意义见题目描述。

第三行 $N-1$ 个用单个空格隔开的非负整数 b1,⋯ ,bN−1b_1,\cdots,b_{N-1}b1​,⋯,bN−1​，表示换牌的罚分，具体含义见题目描述。由于游戏进行 $N$ 轮，所以你至多可以换 $N-1$ 次牌。

第四行 $N$ 个用单个空格隔开的整数 c1,⋯ ,cNc_1,\cdots,c_Nc1​,⋯,cN​，依次表示小杨从第 $1$ 轮至第 $N$ 轮出的牌。保证 ci∈0,1,2c _i\in{0,1,2}ci​∈0,1,2。

输出格式

一行一个整数，表示你最多获得的分数。

样例输入 #1

4
1 2 10 100
1 100 1
1 1 2 0

样例输出 #1

219

样例输入 #2

6
3 7 2 8 9 4
1 3 9 27 81
0 1 2 1 2 0

样例输出 #2

56

说明/提示

样例解释 1

你可以第 $1$ 轮出 $0$，并在第 $2,3$ 轮保持不变，如此输掉第 $1,2$ 轮，但在第 $3$ 轮中取胜，获得 $2\times 10=20$ 分；

随后，你可以在第 $4$ 轮中以扣 $1$ 分为代价改出 $1$ ，并在第 $4$ 轮中取得胜利，获得 $2\times 100=200$ 分。

如此，你可以获得最高的总分 $20+200-1=219$。

数据范围

对于 $30\%$ 的测试点，保证 $N\le 15$。

对于 $60\%$ 的测试点，保证 $N\le 100$。

对于所有测试点，保证 $N\le 1,000$；保证 0≤ai,bi≤1060 \le a_i,b_i \le 10^60≤ai​,bi​≤106。