网站建设风险是什么意思,如何做网站结构及栏目策划,汉化版网站开发软件,厦门市建设工程造价协会官方网站2021信奥赛C提高组csp-s复赛真题及题解#xff1a;回文 题目描述 给定正整数 nnn 和整数序列 a1,a2,…,a2na_1, a_2, \ldots, a_{2 n}a1​,a2​,…,a2n​#xff0c;在这 2n2 n2n 个数中#xff0c;1,2,…,n1, 2, \ldots, n1,2,…,n 分别各出现恰好 222 次。现在进行 2n2 n…2021信奥赛C提高组csp-s复赛真题及题解回文题目描述给定正整数n nn和整数序列a 1 , a 2 , … , a 2 n a_1, a_2, \ldots, a_{2 n}a1​,a2​,…,a2n​在这2 n 2 n2n个数中1 , 2 , … , n 1, 2, \ldots, n1,2,…,n分别各出现恰好2 22次。现在进行2 n 2 n2n次操作目标是创建一个长度同样为2 n 2 n2n的序列b 1 , b 2 , … , b 2 n b_1, b_2, \ldots, b_{2 n}b1​,b2​,…,b2n​初始时b bb为空序列每次可以进行以下两种操作之一将序列a aa的开头元素加到b bb的末尾并从a aa中移除。将序列a aa的末尾元素加到b bb的末尾并从a aa中移除。我们的目的是让b bb成为一个回文数列即令其满足对所有1 ≤ i ≤ n 1 \le i \le n1≤i≤n有b i b 2 n 1 − i b_i b_{2 n 1 - i}bi​b2n1−i​。请你判断该目的是否能达成如果可以请输出字典序最小的操作方案具体在【输出格式】中说明。输入格式每个测试点包含多组测试数据。输入的第一行包含一个整数T TT表示测试数据的组数。对于每组测试数据第一行包含一个正整数n nn。第二行包含2 n 2 n2n个用空格隔开的整数a 1 , a 2 , … , a 2 n a_1, a_2, \ldots, a_{2 n}a1​,a2​,…,a2n​。输出格式对每组测试数据输出一行答案。如果无法生成出回文数列输出一行-1否则输出一行一个长度为2 n 2 n2n的、由字符L或R构成的字符串不含空格其中L表示移除开头元素的操作 1R表示操作 2。你需要输出所有方案对应的字符串中字典序最小的一个。字典序的比较规则如下长度均为2 n 2 n2n的字符串s 1 ∼ 2 n s_{1 \sim 2 n}s1∼2n​比t 1 ∼ 2 n t_{1 \sim 2 n}t1∼2n​字典序小当且仅当存在下标1 ≤ k ≤ 2 n 1 \le k \le 2 n1≤k≤2n使得对于每个1 ≤ i k 1 \le i k1≤ik有s i t i s_i t_isi​ti​且s k t k s_k t_ksk​tk​。输入输出样例 1输入 12 5 4 1 2 4 5 3 1 2 3 5 3 3 2 1 2 1 3输出 1LRRLLRRRRL -1说明/提示【样例解释 #1】在第一组数据中生成的的b bb数列是[ 4 , 5 , 3 , 1 , 2 , 2 , 1 , 3 , 5 , 4 ] [4, 5, 3, 1, 2, 2, 1, 3, 5, 4][4,5,3,1,2,2,1,3,5,4]可以看出这是一个回文数列。另一种可能的操作方案是LRRLLRRRRR但比答案方案的字典序要大。【数据范围】令∑ n \sum n∑n表示所有T TT组测试数据中n nn的和。对所有测试点保证1 ≤ T ≤ 100 1 \le T \le 1001≤T≤1001 ≤ n , ∑ n ≤ 5 × 10 5 1 \le n, \sum n \le 5 \times {10}^51≤n,∑n≤5×105。测试点编号T ≤ T \leT≤n ≤ n \len≤∑ n ≤ \sum n \le∑n≤特殊性质1 ∼ 7 1 \sim 71∼710 101010 101050 5050无8 ∼ 10 8 \sim 108∼10100 10010020 20201000 10001000无11 ∼ 12 11 \sim 1211∼12100 100100100 1001001000 10001000无13 ∼ 15 13 \sim 1513∼15100 1001001000 1000100025000 2500025000无16 ∼ 17 16 \sim 1716∼171 115 × 10 5 5 \times {10}^55×1055 × 10 5 5 \times {10}^55×105无18 ∼ 20 18 \sim 2018∼20100 1001005 × 10 5 5 \times {10}^55×1055 × 10 5 5 \times {10}^55×105有21 ∼ 25 21 \sim 2521∼25100 1001005 × 10 5 5 \times {10}^55×1055 × 10 5 5 \times {10}^55×105无特殊性质如果我们每次删除a aa中两个相邻且相等的数存在一种方式将序列删空例如a [ 1 , 2 , 2 , 1 ] a [1, 2, 2, 1]a[1,2,2,1]。思路分析数据结构a[1..2n]原始输入序列。b[x]数值x首次出现的位置用于构建配对关系。c[i]位置i的配对位置满足a[i]a[c[i]]且c[c[i]]i。q1,q2双端队列分别存储左段和右段的下标。q1保持原序q2逆序存储便于同时从两端访问。核心函数slv(ch)第一步根据ch确定第一次操作方向并找到配对位置o c[st]。区间划分剩余下标分为左段[l, r]和右段[l2, r2]分别按顺序推入q1和按逆序推入q2。贪心构造前半部分n步每一步从整体左端 (p) 或整体右端 (q) 取出一个下标并移除其配对下标位于r或s。按字典序由小到大的顺序检查四种合法情况取左端配对右段左端 → 当前操作L配对取出方向R。取左端配对左段右端 → 当前操作L配对取出方向L。取右端配对左段右端 → 当前操作R配对取出方向L。取右端配对右段左端 → 当前操作R配对取出方向R。若四种均不满足当前方案无解。生成完整操作串ans记录前半部分的每一步操作长度n。sf记录每一步配对元素被取出时的操作方向长度n首字符固定L对应最后一步。将sf反转后拼接到ans后得到长度为2n的完整操作序列。字典序最小保证先尝试L作为第一步失败后才尝试R。每一步优先尝试取L且L时优先匹配右段左端R时优先匹配左段右端。最后一步固定为L剩余唯一元素时取左字典序更小。上述贪心策略确保在所有可行方案中输出字典序最小的操作串。复杂度每组数据仅需一次线性扫描建立配对关系以及线性次的队列操作。总复杂度O(∑n)在∑n ≤ 5×10^5的限制下可轻松通过洛谷所有测试点。代码实现#includebits/stdc.husingnamespacestd;constintN1000005;intT,n,m;inta[N],b[N],c[N];// a:原数组, b:值首次出现位置, c:配对位置boolslv(charch){dequeintq1,q2;// q1:左段(原序), q2:右段(逆序)string ans,sf;// ans:前半操作, sf:后半操作(待反转)ansch;sfL;// 最后一步强制取左into;// 与第一次取出的数配对的位置if(chL){oc[1];for(inti2;io;i)q1.push_back(i);for(intin;io;--i)q2.push_back(i);}else{oc[n];for(inti1;io;i)q1.push_back(i);for(intin-1;io;--i)q2.push_back(i);}while(!q1.empty()||!q2.empty()){// p:整体左端, q:整体右端, r:左段右端, s:右段左端intpq1.empty()?0:q1.front();intqq2.empty()?0:q2.front();intrq1.empty()?0:q1.back();intsq2.empty()?0:q2.back();// 四种可行情况字典序依次减小if(pc[p]s){// 取左配右段左端ansL;sfR;q1.pop_front();q2.pop_back();}elseif(pc[p]r){// 取左配左段右端ansL;sfL;q1.pop_front();q1.pop_back();}elseif(qc[q]r){// 取右配左段右端ansR;sfL;q2.pop_front();q1.pop_back();}elseif(qc[q]s){// 取右配右段左端ansR;sfR;q2.pop_front();q2.pop_back();}elsereturnfalse;}reverse(sf.begin(),sf.end());anssf;coutans\n;returntrue;}intmain(){ios::sync_with_stdio(false);cin.tie(0);cinT;while(T--){cinm;nm*2;// 初始化位置数组for(inti1;im;i)b[i]0;for(inti1;in;i){cina[i];if(b[a[i]]){c[b[a[i]]]i;c[i]b[a[i]];}else{b[a[i]]i;}}// 先尝试第一步取左再尝试第一步取右if(!slv(L)!slv(R))cout-1\n;}return0;}专栏推荐信奥赛C提高组csp-s初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13125089.html各种学习资料助力大家一站式学习和提升#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 点击跳转信奥赛C提高组csp-s初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13125089.html3、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;}