2024年3月GESP真题及题解(C++八级): 接竹竿

2024年3月GESP真题及题解(C++八级): 接竹竿

题目描述

小杨同学想用卡牌玩一种叫做“接竹竿”的游戏。

游戏规则是：每张牌上有一个点数v vv，将给定的牌依次放入一列牌的末端。若放入之前这列牌中已有与这张牌点数相
同的牌，则小杨同学会将这张牌和点数相同的牌之间的所有牌全部取出队列（包括这两张牌本身）。

小杨同学现在有一个长度为n nn的卡牌序列A AA，其中每张牌的点数为A i A_iAi​（1 ≤ i ≤ n 1\le i\le n1≤i≤n）。小杨同学有q qq次询问。第i ii次（1 ≤ i ≤ q 1\le i\le q1≤i≤q）询问时，小杨同学会给出l i , r i l_i,r_ili​,ri​小杨同学想知道如果用下标在[ l i , r i ] [l_i,r_i][li​,ri​]的所有卡牌按照下标顺序玩“接竹竿”的游戏，最后队列中剩余的牌数。

输入格式

一行包含一个正整数T TT，表示测试数据组数。

对于每组测试数据，第一行包含一个正整数n nn，表示卡牌序列A AA的长度。

第二行包含n nn个正整数A 1 , A 2 , … , A n A_1,A_2,\dots,A_nA1​,A2​,…,An​，表示卡牌的点数A AA。

第三行包含一个正整数q qq，表示询问次数。

接下来q qq行，每行两个正整数l i , r i l_i,r_ili​,ri​表示一组询问。

输出格式

对于每组数据，输出q qq行。第i ii行（1 ≤ i ≤ q 1\le i\le q1≤i≤q）输出一个非负整数，表示第i ii次询问的答案。

输入输出样例 1

输入 1

1 6 1 2 2 3 1 3 4 1 3 1 6 1 5 5 6

输出 1

1 1 0 2

说明/提示

样例解释

对于第一次询问，小杨同学会按照1 , 2 , 2 1,2,21,2,2的顺序放置卡牌，在放置最后一张卡牌时，两张点数为2 22的卡牌会被收走，因此最后队列中只剩余一张点数为1 11的卡牌。

对于第二次询问，队列变化情况为：

{ } → { 1 } → { 1 , 2 } → { 1 , 2 , 2 } → { 1 } → { 1 , 3 } → { 1 , 3 , 1 } → { } → { 3 } \{\}\to\{1\}\to\{1,2\}\to\{1,2,2\}\to\{1\}\to\{1,3\}\to\{1,3,1\}\to\{\}\to\{3\}{}→{1}→{1,2}→{1,2,2}→{1}→{1,3}→{1,3,1}→{}→{3}。因此最后队列中只剩余一张点数为3 33的卡牌。

数据范围

对于全部数据，保证有1 ≤ T ≤ 5 1\le T\le 51≤T≤5，1 ≤ n ≤ 1.5 × 10 4 1\le n\le 1.5\times 10^41≤n≤1.5×104，1 ≤ q ≤ 1.5 × 10 4 1\le q\le 1.5\times 10^41≤q≤1.5×104，1 ≤ A i ≤ 13 1\le A_i\le 131≤Ai​≤13。

思路分析

1. 算法思路

这个实现的核心思想是通过跳跃来模拟消除过程，而不是实际模拟栈的操作。关键点如下：

• nxt[ i ] [ 0 ] [i][0][i][0]: 表示从位置i的牌开始，第一次遇到相同牌的位置
• nxt[ i ] [ j ] [i][j][i][j]: 表示从位置i开始，经过2 j 2^j2j次消除（每次消除包括一对相同牌及其间的所有牌）后到达的位置
• 倍增思想: 通过预计算的跳跃表，可以快速跳过多次消除过程

2. 数据结构设计

• a[N]: 存储卡牌序列
• nxt[N][30]: 倍增表，nxt[ i ] [ j ] [i][j][i][j]表示从i开始经过2^j次跳跃后的位置
• p[20]: 记录每种点数（1-13）最近出现的位置

代码实现

#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;constintN=1e5+10;inta[N];intnxt[N][30],p[20];// nxt[i][j]: 从位置i开始，经过2^j次跳跃后到达的位置// pos[x]: 记录点数x最近出现的位置intmain(){intt;cin>>t;while(t--){intn;cin>>n;memset(p,0,sizeofp);// 重置pos数组for(inti=1;i<=n;i++){cin>>a[i];// 初始化nxt数组，n+1表示超出边界for(intj=0;j<=20;j++)nxt[i][j]=n+1;}// 预处理：计算nxt[i][0] - 每个位置第一次跳跃的目标// 从后往前遍历，这样可以找到每个数字下一次出现的位置for(inti=n;i>=1;i--){if(!p[a[i]]){// 当前数字第一次出现（从后往前看），没有下一个相同数字nxt[i][0]=n+1;// 设置为n+1表示无法跳跃p[a[i]]=i;// 记录当前位置}else{// 当前数字之前出现过，下一个相同数字的位置是pos[a[i]]nxt[i][0]=p[a[i]];p[a[i]]=i;// 更新为当前位置}}// 构建倍增表for(inti=n;i>=1;i--){for(intj=1;j<=20;j++){// nxt[i][j] = 从i开始，经过2^j次跳跃后的位置// 等价于：先跳2^(j-1)次到位置x，再从x+1开始跳2^(j-1)次if(nxt[i][j-1]+1<=n)nxt[i][j]=nxt[nxt[i][j-1]+1][j-1];}}// 处理查询intq;cin>>q;while(q--){intl,r;cin>>l>>r;intc=l;// 当前处理位置intans=0;// 最终剩余的牌数// 模拟游戏过程while(c<=r){// 阶段1：处理那些不会触发消除的牌// 如果当前牌的下一个相同牌超出查询区间，那么这张牌会留在队列中while(c<=r&&nxt[c][0]>r){c++;// 移动到下一张牌ans++;// 这张牌会留在队列中}if(c>r)break;// 处理完毕// 阶段2：处理会触发消除的牌// 使用倍增找到可以跳到的最远位置（在区间内）for(intj=20;j>=0;j--){if(nxt[c][j]<=r){// 从当前位置ii跳到nxt[ii][j]// 这表示处理了从ii到nxt[ii][j]的所有牌c=nxt[c][j];break;}}c++;// 跳到下一张牌继续处理}cout<<ans<<"\n";}}return0;}

功能分析

(1) 预处理阶段

for(inti=n;i>=1;i--){if(!p[a[i]]){nxt[i][0]=n+1;// 没有下一个相同数字p[a[i]]=i;}else{nxt[i][0]=p[a[i]];// 下一个相同数字的位置p[a[i]]=i;}}

• 倒序遍历: 从后往前遍历可以方便地找到每个数字下一次出现的位置
• n+1表示边界: 使用n+1表示"无法跳跃"或"超出范围"

(2) 倍增表构建

for(intj=1;j<=20;j++){if(nxt[i][j-1]+1<=n)nxt[i][j]=nxt[nxt[i][j-1]+1][j-1];}

• 递归关系:n x t [ i ] [ j ] = n x t [ n x t [ i ] [ j − 1 ] + 1 ] [ j − 1 ] nxt[i][j] = nxt[nxt[i][j-1]+1][j-1]nxt[i][j]=nxt[nxt[i][j−1]+1][j−1]
• 含义: 从i开始，先进行2j − 1 ^{j-1}j−1次跳跃到达位置x，然后从x+1开始再进行2j − 1 ^{j-1}j−1次跳跃

(3) 查询处理

while(c<=r){// 处理不会消除的牌while(c<=r&&nxt[c][0]>r){c++;ans++;}if(c>r)break;// 使用倍增跳过消除的牌for(intj=20;j>=0;j--){if(nxt[c][j]<=r){c=nxt[c][j];break;}}c++;}

• 不会消除的牌: 如果当前牌的下一个相同牌不在区间内，那么这张牌会保留
• 会消除的牌: 使用倍增找到可以跳到的最远位置，然后跳过这段区间

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

#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、GESP C++考级真题题解：

GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转

GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转

GESP(C++ 七级+八级)真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13117178.html

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

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

· 文末祝福 ·

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