首页 › 试卷 › GESP编程能力等级认证 › GESP-C++八级 › 2025年12月CCF-GESP编程能力等级认证C++编程八级真题

2025年12月CCF-GESP编程能力等级认证C++编程八级真题 VIP

GESP-C++八级 共 27 题 2025 年 含标准答案与解析
返回试卷列表
本页为整卷浏览:先自己做一遍,再展开「查看答案与解析」核对。

一、单选题

1. 单选题

某平台生成“取件码”由6个字符组成:前4位为数字( 0 – 9 ),后2位为大写字母( A – Z ),其中字母不能为 I 、 O 。假设数字和字母均可重复使用,要求整个取件码中恰好有2个数字为奇数。共有多少种不同取件码?( )

  • A 1,440,000
  • B 2,160,000
  • C 2,535,000
  • D 8,640,000
查看答案与解析
答案:B
解析: 将取件码分为两部分处理:前4位为数字,后2位为字母。数字部分需满足恰好有2个奇数,其余2位为偶数。从4个位置中选择2个放置奇数,组合数为C(4,2)。每位奇数有5种可能(1,3,5,7,9),每位偶数有5种可能(0,2,4,6,8)。因此数字部分总数为C(4,2) × 5² × 5²。字母部分每位可选大写字母除I、O外的24个字母,共24²种。总方案数由乘法原理得:C(4,2) × 5⁴ × 24²。
2. 单选题

下列代码实现了归并排序(Merge Sort)的分治部分。为了正确地将数组 a 的 [左,右] 区间进行排序,横线处应该填入的是( )。

void merge_sort(int a[], int left, int right) {
    if (left >= right)
        return;
    int mid = (left + right) / 2;
    merge_sort(a, left, mid);
    merge_sort(a, mid + 1, right); // 在此处填入选项
    merge(a, left, mid, right);    // 合并操作
}
  • A merge_sort(a,中,右)
  • B merge_sort(a,中音+1,右)
  • C merge_sort(a,左,中音+1)
  • D merge_sort(a, mid - 1, right)
查看答案与解析
答案:B
解析: 归并排序通过递归将数组区间不断二分。当前函数已对[left, mid]区间进行递归调用,需对剩余部分进行同样操作。剩余部分起始位置为mid+1,结束位置为right,形成连续且不重叠的子区间。递归调用必须覆盖整个原区间[left, right],且子问题划分应保证边界正确衔接。合并操作前,两个子区间必须均已有序,因此第二个递归调用处理右半部分。
3. 单选题

某社团有男生8人、女生7人。现需选出1名队长(性别不限)、1名副队长(性别不限)、2名宣传委员(两人无角色区别,且必须至少1名女生)。假如一人不能兼任多职,共有多少种不同选法?( )

  • A 12012
  • B 11844
  • C 12474
  • D 11025
查看答案与解析
答案:A
解析: 先从15人中选出1名队长,有15种选法;剩余14人中选1名副队长,有14种选法。接着从剩下的13人中选2名宣传委员,要求两人无角色区别且至少1名女生。计算组合时需分情况:一是选出的2人中有1女1男,二是2人均为女生。分别计算两种情况的组合数并相加,得到满足条件的宣传委员选法总数。将队长选法、副队长选法与符合条件的宣传委员选法按乘法原理相乘,得出最终选法总数。注意每步选择均在未重复人选的前提下进行,且各职位互斥。
4. 单选题

二项式(2x-y)^2的展开式中 x^5y^3项的系数为( )。

  • A -7168
  • B 7168
  • C -1792
  • D 1792
查看答案与解析
答案:C
解析: 利用二项式定理展开 (2x - y)^8,通项公式为 C(8, k) * (2x)^(8-k) * (-y)^k。确定 x^5y^3 对应的项,需满足 8 - k = 5 且 k = 3。代入 k = 3 计算对应项的系数,包含组合数 C(8, 3)、2^5 和 (-1)^3 的乘积。
5. 单选题

下面是使用邻接矩阵实现的Dijkstra算法的核心片段,用于求单源最短路径。在找到当前距离起点最近的顶点u 后,需要更新其邻接点 j 的距离。横线处应填入的代码是( )。

for (int j = 1; j <= n; j++) { 
    if (!visited[j] && graph[u][j] < INF) { 
      if (________) { // 在此处填入选项 
        dis[j] = dis[u] + graph[u][j]; 
      } 
    } 
}
  • A dis[j] < dis[u] + graph[u][j]
  • B dis[j] > dis[u] + graph[u][j]
  • C graph[u][j] > dis[u] + dis[j]
  • D dis[j] > graph[u][j]
查看答案与解析
答案:B
解析: 在Dijkstra算法中,选定当前距离起点最近的未处理顶点u后,需遍历其所有邻接点j。对于每个邻接点j,若存在从u到j的边且通过u到达j的路径长度小于当前记录的最短距离,则更新j的最短距离。该判断条件基于比较经由u到达j的路径长度与原记录距离的大小关系,仅当新路径更短时执行更新操作。
6. 单选题

下面程序使用动态规划求两个字符串的最长公共子序列(LCS)长度,横线处应填入的是( )。

#include <algorithm> 
#include <string> 
#include <vector> 
using namespace std; 

int lcs_len(const string &a, const string &b) { 
  int n = (int)a.size(), m = (int)b.size(); 
  vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0)); 
  for (int i = 1; i <= n; i++) 
    for (int j = 1; j <= m; j++) 
      if (a[i - 1] == b[j - 1]) 
        dp[i][j] = dp[i - 1][j - 1] + 1; 
    else 
    ________; // 在此处填入选项 
  return dp[n][m]; 
}
  • A dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
  • B dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]);
  • C dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
  • D dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + 1;
查看答案与解析
答案:C
解析: 定义状态 dp[i][j] 表示字符串 a 的前 i 个字符与字符串 b 的前 j 个字符的最长公共子序列长度。初始化二维数组 dp,边界为 0。遍历两个字符串的每一个字符位置,当字符相等时,状态转移来源于左上角加一;当字符不相等时,状态转移来源于上方或左方的最大值,以保持当前最长公共子序列长度的最优性。最终结果由 dp[n][m] 给出,整个过程依据子问题的最优解构造父问题解。
7. 单选题

已知两个点A(x1,y3)和B(x2,y2)在平面直角坐标系中的坐标。下列C++表达式中,能正确计算这两点之间直线距离的是( )。

  • A sqrt((x1 - x2) ^ 2 + (y1 - y2) ^ 2)
  • B sqrt(pow(x1 - x2, 2) + pow(y1 - y2, 2))
  • C pow(x1 - x2, 2) + pow(y1 - y2, 2)
  • D abs(x1 - x2) + abs(y1 - y2)
查看答案与解析
答案:B
解析: 根据平面直角坐标系中两点间的距离公式,距离等于横坐标差的平方与纵坐标差的平方之和的算术平方根。计算过程需先对两坐标差分别求平方,再求和,最后对和取平方根。平方运算可通过乘法或幂函数实现,平方根运算需调用相应的数学函数完成。坐标的差值应取其代数差,不进行绝对值处理。
8. 单选题

已知 int a = 10; ,执行 int &amp;b = a; b = 20; 后,变量 a 的值是( )。

  • A 10
  • B 20
  • C 30
  • D 编译错误
查看答案与解析
答案:B
解析: 声明 int a = 10; 定义了一个整型变量 a 并初始化为 10。执行 int &b = a; 建立引用 b,使其成为 a 的别名,此后 b 与 a 绑定同一内存位置。执行 b = 20; 即通过引用 b 修改其所绑定的对象的值,该操作等价于直接修改 a 所占用的内存单元的内容。
9. 单选题

下列代码的时间复杂度(以 为自变量,忽略常数与低阶项)是( )。

long long s = 0; 
for (int i = 1; i <= n; i++) { 
    for (int j = 1; j * j <= i; j++) { 
      s += j; 
     } 
}
  • A O(n)
  • B O(n log n)
  • C O(n√n)
  • D O(n^2)
查看答案与解析
答案:C
解析: 分析外层循环的执行次数,确定其控制变量的变化规律。观察内层循环的条件表达式,推导每次外层循环迭代时内层循环的执行次数。将内外层循环的执行次数相乘,得到总操作次数的数量级。忽略常数因子与低阶项,提取最高次项以表示时间复杂度。
10. 单选题

下列程序实现了线性筛法(欧拉筛),用于在O(n)时间内求出1~n之间的所有质数。为了保证每个合数只被其最小质因子筛掉,横线处应填入的语句是( )。

for (int i = 2; i <= n; i++) { 
  if (!not_prime[i]) primes[++cnt] = i; 
  for (int j = 1; j <= cnt && i * primes[j] <= n; j++) { 
    not_prime[i * primes[j]] = true; 
    if (________) break; // 在此处填入选项 
  } 
}
  • A i + primes[j] == n
  • B primes[j] > i
  • C i % primes[j] == 0
  • D i % primes[j] != 0
查看答案与解析
答案:C
解析: 遍历每个数i,若未被标记为合数,则将其加入质数列表。随后枚举已知质数primes[j],将i与primes[j]的乘积标记为合数。标记过程中,当某个质数primes[j]能整除i时,停止后续标记。因primes[j]是i的最小质因子,后续更大的质数与i相乘所得合数的最小质因子仍为primes[j],应由其他数倍增筛去。
11. 单选题

在C++语言中,关于类的继承和访问权限,下列说法正确的是( )。

  • A 派生类可以访问基类的 private 成员。
  • B 基类的 protected 成员在私有继承(private inheritance)后,在派生类中变为 public 。
  • C 派生类对象在创建时,会先调用基类的构造函数,再调用派生类自己的构造函数。
  • D 派生类对象在销毁时,会先调用基类的析构函数,再调用派生类自己的析构函数。
查看答案与解析
答案:C
解析: 分析类继承中成员访问权限的变化规则,明确不同继承方式下基类成员在派生类中的可访问性。考察构造函数与析构函数的调用顺序机制,理解对象生命周期中初始化与清理阶段函数执行次序。区分成员访问控制符(private、protected、public)在继承过程中的作用范围变化,结合继承类型(公有、私有、保护继承)判断成员属性的转换逻辑。
12. 单选题

当输入 6 时,下列程序的输出结果为( )。

#include <iostream> 
using namespace std; 
int f(int n) { 
  if (n <= 3) return n; 
  return f(n - 1) + f(n - 2) + 2 * f(n - 3); 
} 
int main() { 
  int n; 
  cin >> n; 
  cout << f(n) << endl; 
  return 0; 
}
  • A 14
  • B 27
  • C 28
  • D 15
查看答案与解析
答案:B
解析: 分析函数 f 的递归结构,确定其在不同输入下的调用路径。当 n ≤ 3 时,f(n) 直接返回 n;否则,f(n) 依赖于 f(n-1)、f(n-2) 和 2 倍的 f(n-3) 之和。从输入值 6 开始,逐层展开递归调用,记录每层参数对应的子问题。通过自底向上或记忆化方式计算各子问题的值,避免重复计算。最终将所有递归分支的结果按函数定义组合,得到 f(6) 的完整表达式并求值。
13. 单选题

从1到999这999个正整数中,十进制表示中数字 5 恰好出现一次的数有多少个?( )

  • A 243
  • B 271
  • C 300
  • D 333
查看答案与解析
答案:A
解析: 将1到999的数按位数分类为一位数、两位数、三位数。对每一类,枚举数字5在十进制表示中恰好出现一次的所有可能位置:个位、十位、百位。针对每一位固定为5的情况,统计其余位上可填入的数字(0-9,除5外)的合法组合数,注意首位不能为0。分别计算每类中满足条件的数的个数,再按位数结构累加所有情况的结果。
14. 单选题

当输入 2023 时,下列程序的输出结果为( )。

#include <iostream> 
using namespace std; 

int main() { 
  int x, ans = 0; 
  cin >> x; 
  while (x != 0) { 
    x -= x & -x; 
    ans++; 
  } 
  cout << ans << endl; 
return 0; 
}


  • A 7
  • B 9
  • C 9
  • D 11
查看答案与解析
答案:C
解析: 程序读取整数x,初始化ans为0。循环中,每次将x减去x与-x的按位与结果,同时ans递增。x与-x的按位与运算得到x的最低位1所代表的值。每次操作消除x的二进制表示中最右边的1。循环执行次数等于x的二进制形式中1的个数。ans的最终值由输入x的二进制中1的位数决定。
15. 单选题

对连通无向图执行Kruskal算法。已按边权从小到大依次扫描到某条边e=(u,v)。此时在已经构建的部分MST结构中, (u,v)已在同一连通块内。关于边 的处理,下列说法正确的是( )。

  • A 必须选入MST,否则可能不连通。
  • B 一定不能选入MST(在此扫描顺序下)。
  • C 若后续出现更大的边权,可以回溯改选 。
  • D 只有当是当前最小边时才能舍弃。
查看答案与解析
答案:B
解析: Kruskal算法基于边权递增顺序处理边,维护当前选中边构成的森林连通性。每条边处理时需判断其两端顶点是否已存在于同一连通块中。该判断通过并查集等数据结构实现,用于检测加入该边是否会形成环。若两端已在同一连通块内,则该边连接的是同一树内两节点。此时该边可被跳过而不立即加入MST结构。算法继续处理下一条边,后续选择仅依赖未处理的边及其权值顺序。已舍弃的边不会影响后续连通性决策,且不触发回溯机制。边的选取与否完全由当前连通状态和边权顺序决定。

二、判断题

16. 判断题

若一项任务可用两种互斥方案完成:方案A有m种做法,方案B有n种做法,则总做法数为m+n。

  • A对
  • B错
查看答案与解析
答案:对
解析: 分析任务完成方式的互斥性,确认方案A与方案B之间无重叠做法。统计方案A所含的m种做法数量,独立统计方案B所含的n种做法数量。根据加法原理,当两类方法不可同时采用且覆盖全部可能路径时,总方法数为两者之和。验证m与n是否分别对应各自方案下的独立选择项,确保无共同实现路径存在于两方案之间。
17. 判断题

在C++语言中,引用一旦被初始化,就不能再改为引用另一个变量。

  • A对
  • B错
查看答案与解析
答案:对
解析: 分析C++中引用的绑定机制,观察引用在初始化时与变量建立的关联方式,考察该关联是否允许后续重新绑定到其他变量。检查语言标准对引用生命周期内所绑定对象的唯一性约束,确认是否存在语法或语义层面的支持以改变引用的目标。
18. 判断题

快速排序和归并排序的平均时间复杂度都是O(n log n),但快速排序是不稳定的排序算法,归并排序是稳定的排序算法。

  • A对
  • B错
查看答案与解析
答案:对
解析: 比较快速排序与归并排序的时间复杂度机制,分析两者在元素交换过程中的相对位置保持特性。快速排序通过基准元素划分区间并递归排序,元素可能在不同递归层中跨区间交换,导致相同值的相对顺序改变。归并排序将数组分割至最小单位后逐层合并,在合并过程中相同值按原序列顺序依次选入结果,维持了相等元素的原有次序。两种算法的平均时间复杂度均由分治策略的递归深度与每层处理规模决定,表现为O(n log n)。
19. 判断题

使用 math.h 或 cmath 头文件中的函数,表达式 sqrt(4) 的结果类型为 double 。

  • A对
  • B错
查看答案与解析
答案:对
解析: 分析表达式 sqrt(4) 的类型需考察 sqrt 函数在 math.h 或 cmath 中的声明。该函数被重载为多个版本,参数和返回类型与浮点类型相关。当传入整型常量 4 时,会触发隐式类型转换,将 int 提升为 double 调用对应重载版本。C++ 标准库中 sqrt 接受 float、double 或 long double 并返回对应类型,无整型版本。因此调用 sqrt(4) 实际执行的是 sqrt(double),结果类型由函数签名决定。
20. 判断题

在杨辉三角形中,第n行(从0开始计数,即第n+1 行有n+1个数)的所有数字之和等于2^n。

  • A对
  • B错
查看答案与解析
答案:对
解析: 分析杨辉三角形的构造规律,每一行的数值由上一行相邻两数相加得到。观察第n行数字之和的生成方式,结合二项式展开系数的性质,将该行所有元素求和转化为二项式系数之和的形式。利用组合恒等式,验证该和是否符合2^n的数学表达结构。通过数学归纳法或直接组合解释,推导行和与幂次之间的关系。
21. 判断题

使用二叉堆优化的Dijkstra最短路算法,在某些特殊情况下时间复杂度不如朴素实现的O(V^2)。

  • A对
  • B错
查看答案与解析
答案:对
解析: 分析图的顶点数V与边数E的数量级关系;考察二叉堆优化Dijkstra中每次边松弛操作引起的堆操作次数与复杂度;计算二叉堆版本总时间复杂度O((V + E) log V);对比稠密图中E接近V^2时该表达式的增长趋势;比较朴素算法在所有情况下均保持O(V^2)的时间复杂度;考虑当E足够大时,(V + E) log V可能超过V^2;识别图结构中边密度对两种实现方式效率的影响机制。
22. 判断题

n个不同元素依次入栈的出栈序列数与将n个不同元素划分成若干非空子集的方案数相等。

  • A对
  • B错
查看答案与解析
答案:错
解析: 分析n个不同元素依次入栈的出栈序列总数,该数值由卡特兰数公式C_n = (2n)! / ((n+1)! * n!) 给出。计算将n个不同元素划分为若干非空子集的方案总数,该数值由贝尔数B_n给出。比较卡特兰数列与贝尔数列在相同n值下的数值关系。考察两个数列的生成机制:卡特兰数描述的是受栈操作约束的排列模式,贝尔数描述的是集合划分的组合方式。分别列出小规模n(如n=1,2,3)时两个数列的具体数值并进行对应比较。观察两者递推公式的结构差异,卡特兰数满足C_n = Σ_{i=0}^{n-1} C_i * C_{n-1-i},贝尔数满足B_n = Σ_{k=0}^{n-1} C(n-1,k) * B_k。
23. 判断题

快速排序在最坏情况下的时间复杂度为O(n log n),可以通过随机化选择基准值(pivot)的方法完全避免退化。

  • A对
  • B错
查看答案与解析
答案:错
解析: 快速排序的时间复杂度取决于递归划分的平衡性。每次划分由基准值的选择决定,若基准值始终为最大或最小元素,将导致每层仅减少一个元素,形成n层递归,每层处理n、n-1、…个元素,时间复杂度为O(n²)。随机化选择基准值可改变划分结果的概率分布,使最坏情况发生的概率降低,但无法排除所有非均衡划分的可能性。因此,随机化影响划分的期望平衡性,不保证每次递归深度为O(log n)。算法复杂度分析包含最坏、平均与最好情况,随机化改变的是期望性能而非最坏情况的理论上界。
24. 判断题

在C++语言中,一个类可以拥有多个构造函数,也可以拥有多个析构函数。

  • A对
  • B错
查看答案与解析
答案:错
解析: 分析类的特殊成员函数定义规则,明确构造函数的重载机制与析构函数的唯一性约束。考察多个构造函数存在的语法支持条件,以及析构函数在类中可出现的次数限制。检查C++标准对构造函数和析构函数的数量规定,确认是否允许同时存在多个析构函数。
25. 判断题

求两个序列的最长公共子序列(LCS)时,使用滚动数组优化空间后,仍然可以还原出具体的LCS序列。

  • A对
  • B错
查看答案与解析
答案:错
解析: 使用动态规划求解最长公共子序列时,状态转移基于前一行或当前行的值更新。滚动数组通过只保存必要行(如当前行和上一行)来减少空间占用。还原具体LCS序列需回溯路径,可在计算过程中记录决策位置或利用原序列与滚动数组状态逆推匹配点。匹配字符的位置可通过比较当前状态与前一状态差异确定,逐步向前追踪至序列起始。此过程不依赖完整二维表,仅需当前维护的压缩状态及原始输入序列即可实现路径重建。

三、简答题

26. 简答题

猫和老鼠

时间限制:1.0 s

内存限制:512.0 MB

题目描述

猫和老鼠所在的庄园可以视为一张由n个点和m条带权无向边构成的连通图。结点依次以1,2,...,n编号,结点i(1≤i≤n)有价值为ci的奶酪。在m条带权无向边中,第i(1≤i≤m)条无向边连接结点ui与结点vi,边权wi表示猫和老鼠通过这条边所需的时间。

猫窝位于结点a,老鼠洞位于结点b。对于老鼠而言,结点u是安全的当且仅当:

老鼠能规划一条从结点u出发逃往老鼠洞的路径,使得对于路径上任意结点x(包括结点u与老鼠洞)都有:

猫从猫窝出发到结点x的最短时间严格大于老鼠从结点u沿这条路径前往结点x所需的时间。

老鼠在拿取安全结点的奶酪时不存在被猫抓住的可能,但在拿取不是安全结点的奶酪时则不一定。为了确保万无一失,老鼠决定只拿取安全结点放置的奶酪。请你计算老鼠所能拿到的奶酪价值之和。

输入格式

第一行,两个正整数n,m,分别表示图的结点数与边数。

第二行,两个正整数a,b,分别表示猫窝的结点编号,以及老鼠洞的结点编号。

第三行,n个正整数c1,c2,...,cn,表示各个结点的奶酪价值。

接下来 行中的第i行(1≤x≤m)包含三个正整数ui,vi,wi,表示图中连接结点ui与结点vi的边,边权为wi。

输出格式

输出一行,一个整数,表示老鼠所能拿到的奶酪价值之和。

输入样例 1

5 5
1 2
1 2 4 8 16
1 2 4
2 3 3
3 4 1
2 5 2
3 1 8

输出样例 1

22

输入样例 2

6 10
3 4
1 1 1 1 1 1
1 2 6
2 3 3
3 1 4
3 4 5
4 5 8
5 6 2
6 4 1
3 2 4
5 4 4
3 3 6

输出样例 2

3

数据范围

对于40的测试点,保证1≤n≤500,1≤m≤500。

对于所有测试点,保证1≤n≤105,1≤m≤105,1≤a,b≤n且a≠b,1≤ui,vi≤n,1≤wi≤109。

查看答案与解析
答案:<pre class="brush:cpp;toolbar:false;">#include &lt;cstdio&gt; #include &lt;algorithm&gt; #include &lt;vector&gt; #include &lt;queue&gt; using namespace std; const int N = 1e5 + 5; const long long oo = 1e18; int n, m; int a, b; int c[N]; vector&lt;pair&lt;int, int&gt;&gt; e[N]; long long dis[N]; priority_queue&lt;pair&lt;long long, int&gt;&gt; q; long long ans; int main() {     scanf("%d%d", &amp;n, &amp;m);     scanf("%d%d", &amp;a, &amp;b);     for (int i = 1; i &lt;= n; i++)         scanf("%d", &amp;c[i]);     for (int i = 1; i &lt;= m; i++) {         int u, v, w;         scanf("%d%d%d", &amp;u, &amp;v, &amp;w);         e[u].emplace_back(make_pair(v, w));         e[v].emplace_back(make_pair(u, w));     }     for (int i = 1; i &lt;= n; i++)         dis[i] = oo;     dis[b] = 0;     q.push(make_pair(-dis[b], b));     while (!q.empty()) {         auto p = q.top();         q.pop();         if (dis[p.second] != -p.first)             continue;         int u = p.second;         for (auto r : e[u]) {             int v = r.first, w = r.second;             if (dis[v] &gt; dis[u] + w) {                 dis[v] = dis[u] + w;                 q.push(make_pair(-dis[v], v));             }         }     }     for (int i = 1; i &lt;= n; i++)         if (dis[i] &lt; dis[a])             ans += c[i];     printf("%lld\n", ans);     return 0; }</pre>
这道题暂未补解析。
27. 简答题

宝石项链

时间限制:1.0 s

内存限制:512.0 MB

题目描述

小 A 有一串包含n枚宝石的宝石项链,这些宝石按照在项链中的顺序依次以1,2,...,n编号,第n枚宝石与第1枚宝石相邻。项链由m种宝石组成,其中第i枚宝石种类为ti。

小 A 想将宝石项链分给他的好朋友们。具体而言,小 A 会将项链划分为若干连续段,并且需要保证每段都包含全部种宝石。请帮小 A 计算在满足条件的前提下,宝石项链最多可以划分为多少段。

输入格式

第一行,两个正整数n,m,分别表示宝石项链中的宝石的数量与种类数。

第二行,n个正整数ti,t2,...,tn,表示每枚宝石的种类。

输出格式

输出一行,一个整数,表示宝石项链最多可以划分的段数。

输入样例 1

6 2
1 2 1 2 1 2

输出样例 1

3

输入样例 2

7 3
3 1 3 1 2 1 2

输出样例 2

2

数据范围

查看答案与解析
答案:<pre class="brush:cpp;toolbar:false;">#include &lt;cstdio&gt; #include &lt;algorithm&gt; using namespace std; const int L = 20; const int N = 2e5 + 5; const int oo = 1e9; int n, m; int t[N], jump[L][N]; int cnt[N], tot; int ans; int go(int u) {     int cnt = 0, ans = 0;     for (int i = L - 1; i &gt;= 0; i--)         if (cnt + jump[i][u] &lt;= n) {             cnt += jump[i][u];             ans += 1 &lt;&lt; i;             u = (u + jump[i][u] - 1) % n + 1;         }     return ans; } int main() {     scanf("%d%d", &amp;n, &amp;m);     for (int i = 1; i &lt;= n; i++) {         scanf("%d", &amp;t[i]);         t[i + n] = t[i];     }     for (int i = 1, r = 0; i &lt;= n; i++) {         while (tot &lt; m) {             r++;             if (!cnt[t[r]]++)                 tot++;         }         jump[0][i] = r - i + 1;         if (!--cnt[t[i]])             tot--;     }     for (int i = 1; i &lt; L; i++)         for (int j = 1; j &lt;= n; j++) {             int tar = (j + jump[i - 1][j] - 1) % n + 1;             jump[i][j] = min(jump[i - 1][j] + jump[i - 1][tar], oo);         }     for (int i = 1; i &lt;= n; i++)         ans = max(ans, go(i));     printf("%d\n", ans);     return 0; }</pre>
这道题暂未补解析。