企业官网建设流程全解析

网站开发有什么,潍坊住房与城市建设部网站,小红书网络推广公司,ui设计培训学校哪里好2024年3月GESP真题及题解(C八级): 接竹竿 题目描述 小杨同学想用卡牌玩一种叫做“接竹竿”的游戏。 游戏规则是#xff1a;每张牌上有一个点数 v v v#xff0c;将给定的牌依次放入一列牌的末端。若放入之前这列牌中已有与这张牌点数相 同的牌#xff0c;则小杨同学会将这…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输入 11 6 1 2 2 3 1 3 4 1 3 1 6 1 5 5 6输出 11 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的卡牌。数据范围子任务分数T TTn nnq qqmax ⁡ A i \max A_imaxAi​特殊条件1 1130 3030≤ 5 \le 5≤5≤ 100 \le100≤100≤ 100 \le100≤100≤ 13 \le13≤132 2230 3030≤ 5 \le 5≤5≤ 1.5 × 10 4 \le 1.5\times10^4≤1.5×104≤ 1.5 × 10 4 \le 1.5\times10^4≤1.5×104≤ 13 \le13≤13所有询问的右端点等于n nn3 3340 4040≤ 5 \le 5≤5≤ 1.5 × 10 4 \le 1.5\times10^4≤1.5×104≤ 1.5 × 10 4 \le 1.5\times10^4≤1.5×104≤ 13 \le13≤13对于全部数据保证有1 ≤ T ≤ 5 1\le T\le 51≤T≤51 ≤ n ≤ 1.5 × 10 4 1\le n\le 1.5\times 10^41≤n≤1.5×1041 ≤ q ≤ 1.5 × 10 4 1\le q\le 1.5\times 10^41≤q≤1.5×1041 ≤ 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最近出现的位置代码实现#includebits/stdc.husingnamespacestd;typedeflonglongll;constintN1e510;inta[N];intnxt[N][30],p[20];// nxt[i][j]: 从位置i开始经过2^j次跳跃后到达的位置// pos[x]: 记录点数x最近出现的位置intmain(){intt;cint;while(t--){intn;cinn;memset(p,0,sizeofp);// 重置pos数组for(inti1;in;i){cina[i];// 初始化nxt数组n1表示超出边界for(intj0;j20;j)nxt[i][j]n1;}// 预处理计算nxt[i][0] - 每个位置第一次跳跃的目标// 从后往前遍历这样可以找到每个数字下一次出现的位置for(intin;i1;i--){if(!p[a[i]]){// 当前数字第一次出现从后往前看没有下一个相同数字nxt[i][0]n1;// 设置为n1表示无法跳跃p[a[i]]i;// 记录当前位置}else{// 当前数字之前出现过下一个相同数字的位置是pos[a[i]]nxt[i][0]p[a[i]];p[a[i]]i;// 更新为当前位置}}// 构建倍增表for(intin;i1;i--){for(intj1;j20;j){// nxt[i][j] 从i开始经过2^j次跳跃后的位置// 等价于先跳2^(j-1)次到位置x再从x1开始跳2^(j-1)次if(nxt[i][j-1]1n)nxt[i][j]nxt[nxt[i][j-1]1][j-1];}}// 处理查询intq;cinq;while(q--){intl,r;cinlr;intcl;// 当前处理位置intans0;// 最终剩余的牌数// 模拟游戏过程while(cr){// 阶段1处理那些不会触发消除的牌// 如果当前牌的下一个相同牌超出查询区间那么这张牌会留在队列中while(crnxt[c][0]r){c;// 移动到下一张牌ans;// 这张牌会留在队列中}if(cr)break;// 处理完毕// 阶段2处理会触发消除的牌// 使用倍增找到可以跳到的最远位置在区间内for(intj20;j0;j--){if(nxt[c][j]r){// 从当前位置ii跳到nxt[ii][j]// 这表示处理了从ii到nxt[ii][j]的所有牌cnxt[c][j];break;}}c;// 跳到下一张牌继续处理}coutans\n;}}return0;}功能分析(1) 预处理阶段for(intin;i1;i--){if(!p[a[i]]){nxt[i][0]n1;// 没有下一个相同数字p[a[i]]i;}else{nxt[i][0]p[a[i]];// 下一个相同数字的位置p[a[i]]i;}}倒序遍历: 从后往前遍历可以方便地找到每个数字下一次出现的位置n1表示边界: 使用n1表示无法跳跃或超出范围(2) 倍增表构建for(intj1;j20;j){if(nxt[i][j-1]1n)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然后从x1开始再进行2j − 1 ^{j-1}j−1次跳跃(3) 查询处理while(cr){// 处理不会消除的牌while(crnxt[c][0]r){c;ans;}if(cr)break;// 使用倍增跳过消除的牌for(intj20;j0;j--){if(nxt[c][j]r){cnxt[c][j];break;}}c;}不会消除的牌: 如果当前牌的下一个相同牌不在区间内那么这张牌会保留会消除的牌: 使用倍增找到可以跳到的最远位置然后跳过这段区间各种学习资料助力大家一站式学习和提升#includebits/stdc.husingnamespacestd;intmain(){cout########## 一站式掌握信奥赛知识! ##########;cout############# 冲刺信奥赛拿奖! #############;cout###### 课程购买后永久学习不受限制! ######;return0;}1、csp信奥赛高频考点知识详解及案例实践CSP信奥赛C动态规划https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转CSP信奥赛C标准模板库STLhttps://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转信奥赛C提高组csp-s知识详解及案例实践https://blog.csdn.net/weixin_66461496/category_13113932.html2、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.html4、CSP信奥赛C竞赛拿奖视频课https://edu.csdn.net/course/detail/40437 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}