2025年12月GESP真题及题解(C++八级): 宝石项链-平芜编程栈

2025年12月GESP真题及题解(C++八级): 宝石项链

题目描述

小 A 有一串包含n nn枚宝石的宝石项链，这些宝石按照在项链中的顺序依次以1 , 2 , … , n 1,2,\ldots,n1,2,…,n编号，第n nn枚宝石与第1 11枚宝石相邻。项链由m mm种宝石组成，其中第i ii枚宝石种类为t i t_iti。

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

输入格式

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

第二行，n nn个正整数t 1 , t 2 , … , t n t_1,t_2,\ldots,t_nt1,t2,…,tn，表示每枚宝石的种类。

输出格式

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

输入输出样例 1

输入 1

6 2 1 2 1 2 1 2

输出 1

输入输出样例 2

输入 2

7 3 3 1 3 1 2 1 2

输出 2

说明/提示

对于40 % 40\%40%的测试点，保证2 ≤ n ≤ 1000 2\le n\le 10002≤n≤1000。

对于所有测试点，保证2 ≤ n ≤ 10 5 2\le n\le 10^52≤n≤105，2 ≤ m ≤ n 2\le m\le n2≤m≤n，1 ≤ t i ≤ m 1\le t_i\le m1≤ti≤m，保证1 , 2 , … , m 1,2,\ldots,m1,2,…,m均在t 1 , t 2 , … , t n t_1,t_2,\ldots,t_nt1,t2,…,tn中出现。

思路分析

这是一个环形数组划分问题。我们需要将一个环形宝石项链（第n个宝石与第1个宝石相邻）划分为若干连续段，每段必须包含全部m种宝石，求最多能划分多少段。

核心难点

环形结构：数组是环形的，需要考虑循环的情况
最短包含所有宝石的段：要划分尽可能多的段，每段应该是包含所有m种宝石的最短连续段
贪心策略：每次找到最短的合法段，然后从下一位置继续寻找

算法思路

环形处理：将原数组复制一份接在后面，形成2n长度的数组，这样环形问题转化为线性问题
滑动窗口：使用双指针维护一个包含所有m种宝石的最短窗口
贪心划分：
- 从起点开始，找到最短的包含所有宝石的段
- 记录这个段的结束位置，然后从下一个位置继续寻找
- 重复直到覆盖整个环形数组
最大化段数：由于是环形，不同起点可能导致不同结果，需要尝试所有起点

时间复杂度优化

朴素方法：对于每个起点O(n)寻找，总O(n²)，会超时
优化方法：使用**倍增法（Binary Lifting）**预处理每个位置开始跳转的信息
- 预处理：对于每个位置i，计算从i开始取一段后下一个起点的位置
- 倍增表：f[i][k]表示从i开始取2^k段后到达的位置
- 查询：对于每个起点，用倍增快速计算最多能取多少段

具体步骤

数据准备：复制数组为2n长度
滑动窗口预处理：
- 对于每个位置i，找到以i为起点的最短合法段的结束位置
- 记录next[i] = 结束位置 + 1（下一段的起点）
构建倍增表：
- f[i][0] = next[i]（跳1段）
- f[i][k] = f[f[i][k-1]][k-1]（跳2^k段）
枚举起点计算：
- 对每个起点i，用倍增法计算最多能跳多少段
- 保持结束位置不超过i+n（环形限制）
取最大值：所有起点结果的最大值

代码实现

#include<bits/stdc++.h>usingnamespacestd;constintMAXN=2e5+5;// 2倍长度constintLOG=20;// 2^20 > 1e6intn,m;intt[MAXN];// 宝石数组（已复制为2倍长度）intcnt[MAXN];// 计数数组，记录当前窗口每种宝石数量intnxt[MAXN];// nxt[i]: 从i开始取一段后下一个起点位置intf[MAXN][LOG];// 倍增表：f[i][k]表示从i开始取2^k段后到达的位置intmain(){// 读入数据cin>>n>>m;for(inti=0;i<n;i++){cin>>t[i];t[i+n]=t[i];// 复制一份，处理环形}// 滑动窗口预处理每个位置的下一个起点inttypes=0;// 当前窗口内宝石种类数intr=0;// 右指针// 初始化计数数组for(inti=1;i<=m;i++)cnt[i]=0;// 遍历每个位置作为左端点for(intl=0;l<2*n;l++){// 扩展右指针，直到窗口包含所有m种宝石while(r<2*n&&types<m){cnt[t[r]]++;if(cnt[t[r]]==1)types++;r++;}// 如果找到了包含所有宝石的窗口，记录下一个起点if(types==m){nxt[l]=r;// 结束位置+1就是下一段起点}else{nxt[l]=2*n;// 标记为无效位置}// 移动左指针前，减少计数cnt[t[l]]--;if(cnt[t[l]]==0)types--;}// 构建倍增表// 初始化：跳2^0=1段for(inti=0;i<2*n;i++){f[i][0]=nxt[i];}// 计算2^k段for(intk=1;k<LOG;k++){for(inti=0;i<2*n;i++){if(f[i][k-1]<2*n){f[i][k]=f[f[i][k-1]][k-1];}else{f[i][k]=2*n;// 超出范围}}}// 枚举每个起点，计算最多段数intans=0;for(intstart=0;start<n;start++){intpos=start;// 当前位置intseg=0;// 段数// 从大到小尝试跳转for(intk=LOG-1;k>=0;k--){if(f[pos][k]<=start+n){// 跳2^k段后不超过环形范围seg+=(1<<k);// 增加段数pos=f[pos][k];// 更新位置}}ans=max(ans,seg);}cout<<ans<<endl;return0;}

功能分析

1. 数据预处理部分

// 复制数组处理环形for(inti=0;i<n;i++){t[i+n]=t[i];}

目的：将环形问题转化为线性问题
原理：在长度为2n的数组上，任何长度为n的窗口都对应原环形数组的一个起始位置

2. 滑动窗口预处理

while(r<2*n&&types<m){cnt[t[r]]++;if(cnt[t[r]]==1)types++;r++;}

功能：对于每个左端点l，找到最短的包含所有m种宝石的右端点
变量说明：
- types：当前窗口内不同宝石的种类数
- cnt[]：记录每种宝石的出现次数
- nxt[l]：从l开始取一段后，下一段的起始位置

3. 倍增表构建

for(intk=1;k<LOG;k++){for(inti=0;i<2*n;i++){if(f[i][k-1]<2*n){f[i][k]=f[f[i][k-1]][k-1];}}}

原理：f[i][k] = f[f[i][k-1]][k-1]表示从i跳2^{k段等价于先跳2}(k-1)段，再跳2^(k-1)段
LOG选择：2^20 ≈ 1e6 > 2×1e5，足够覆盖所有可能跳转

4. 枚举起点计算

for(intk=LOG-1;k>=0;k--){if(f[pos][k]<=start+n){seg+=(1<<k);pos=f[pos][k];}}

贪心策略：从高位向低位尝试跳转
约束条件：f[pos][k] <= start + n确保跳转后不超过环形范围
时间复杂度：每个起点O(log n)，总O(n log n)

5. 算法复杂度

时间复杂度：O(n log n)
- 滑动窗口预处理：O(n)（每个元素进出各一次）
- 倍增表构建：O(n log n)
- 枚举起点计算：O(n log n)
空间复杂度：O(n log n)（主要存储倍增表）

6. 关键点总结

环形处理技巧：数组复制是处理环形问题的常用方法
滑动窗口优化：双指针法在线性时间内找到所有最短合法段
倍增法应用：将多次跳转压缩为对数级别查询
贪心正确性：每次取最短段能最大化段数，这是本题的关键性质

7. 示例解析

以样例1为例：

n=6, m=2 宝石序列: 1 2 1 2 1 2

最短合法段长度均为2（包含1和2）
可以划分为3段：[1,2]、[1,2]、[1,2]
代码会找到所有起点中的最优解

各种学习资料，助力大家一站式学习和提升！！！

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"########## 一站式掌握信奥赛知识! ##########";cout<<"############# 冲刺信奥赛拿奖! #############";cout<<"###### 课程购买后永久学习，不受限制! ######";return0;}

1、csp信奥赛高频考点知识详解及案例实践：

CSP信奥赛C++动态规划：
https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转

CSP信奥赛C++标准模板库STL：
https://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转

信奥赛C++提高组csp-s知识详解及案例实践：
https://blog.csdn.net/weixin_66461496/category_13113932.html

2、csp信奥赛冲刺一等奖有效刷题题解：

CSP信奥赛C++初赛及复赛高频考点真题解析（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转

CSP信奥赛C++一等奖通关刷题题单及题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转

3、CSP信奥赛C++竞赛拿奖视频课：

https://edu.csdn.net/course/detail/40437 点击跳转

· 文末祝福 ·

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}

2025年12月GESP真题及题解(C++八级): 宝石项链