2021信奥赛C++提高组csp-s复赛真题及题解：回文
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=b2n+1−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表示移除开头元素的操作 1，R表示操作 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≤i<k有s i = t i s_i = t_isi=ti且s k < t k s_k < t_ksk<tk。
输入输出样例 1
输入 1
2 5 4 1 2 4 5 3 1 2 3 5 3 3 2 1 2 1 3输出 1
LRRLLRRRRL -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≤100，1 ≤ 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∼7 | 10 1010 | 10 1010 | 50 5050 | 无 |
| 8 ∼ 10 8 \sim 108∼10 | 100 100100 | 20 2020 | 1000 10001000 | 无 |
| 11 ∼ 12 11 \sim 1211∼12 | 100 100100 | 100 100100 | 1000 10001000 | 无 |
| 13 ∼ 15 13 \sim 1513∼15 | 100 100100 | 1000 10001000 | 25000 2500025000 | 无 |
| 16 ∼ 17 16 \sim 1716∼17 | 1 11 | 5 × 10 5 5 \times {10}^55×105 | 5 × 10 5 5 \times {10}^55×105 | 无 |
| 18 ∼ 20 18 \sim 2018∼20 | 100 100100 | 5 × 10 5 5 \times {10}^55×105 | 5 × 10 5 5 \times {10}^55×105 | 有 |
| 21 ∼ 25 21 \sim 2521∼25 | 100 100100 | 5 × 10 5 5 \times {10}^55×105 | 5 × 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的限制下可轻松通过洛谷所有测试点。
代码实现
#include<bits/stdc++.h>usingnamespacestd;constintN=1000005;intT,n,m;inta[N],b[N],c[N];// a:原数组, b:值首次出现位置, c:配对位置boolslv(charch){deque<int>q1,q2;// q1:左段(原序), q2:右段(逆序)string ans,sf;// ans:前半操作, sf:后半操作(待反转)ans=ch;sf="L";// 最后一步强制取左into;// 与第一次取出的数配对的位置if(ch=='L'){o=c[1];for(inti=2;i<o;++i)q1.push_back(i);for(inti=n;i>o;--i)q2.push_back(i);}else{o=c[n];for(inti=1;i<o;++i)q1.push_back(i);for(inti=n-1;i>o;--i)q2.push_back(i);}while(!q1.empty()||!q2.empty()){// p:整体左端, q:整体右端, r:左段右端, s:右段左端intp=q1.empty()?0:q1.front();intq=q2.empty()?0:q2.front();intr=q1.empty()?0:q1.back();ints=q2.empty()?0:q2.back();// 四种可行情况，字典序依次减小if(p&&c[p]==s){// 取左，配右段左端ans+='L';sf+='R';q1.pop_front();q2.pop_back();}elseif(p&&c[p]==r){// 取左，配左段右端ans+='L';sf+='L';q1.pop_front();q1.pop_back();}elseif(q&&c[q]==r){// 取右，配左段右端ans+='R';sf+='L';q2.pop_front();q1.pop_back();}elseif(q&&c[q]==s){// 取右，配右段左端ans+='R';sf+='R';q2.pop_front();q2.pop_back();}elsereturnfalse;}reverse(sf.begin(),sf.end());ans+=sf;cout<<ans<<'\n';returntrue;}intmain(){ios::sync_with_stdio(false);cin.tie(0);cin>>T;while(T--){cin>>m;n=m*2;// 初始化位置数组for(inti=1;i<=m;++i)b[i]=0;for(inti=1;i<=n;++i){cin>>a[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
各种学习资料，助力大家一站式学习和提升！！！
#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 点击跳转
信奥赛C++提高组csp-s初赛&复赛真题题解（持续更新）
https://blog.csdn.net/weixin_66461496/category_13125089.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;}