xmlns="http://www.w3.org/2000/svg"

style="display:

none;">

2021信奥赛C++提高组csp-s复赛真题及题解：回文

/>

题目描述

给定正整数n

nn和整数序列a

a_1,

n}a

style="height:

0.05em;">1​

style="height:

0.15em;">,a

style="height:

0.05em;">2​

style="height:

0.15em;">,…,a

style="height:

0.05em;">2n​

style="height:

0.15em;">，在这2

n2n个数中，1

\ldots,

n1,2,…,n分别各出现恰好2

22次。

现在进行2

n2n次操作，目标是创建一个长度同样为2

n2n的序列b

b_1,

n}b

style="height:

0.05em;">1​

style="height:

0.15em;">,b

style="height:

0.05em;">2​

style="height:

0.15em;">,…,b

style="height:

0.05em;">2n​

style="height:

0.15em;">，初始时b

bb为空序列，每次可以进行以下两种操作之一：

1. 将序列a

   aa的开头元素加到b

   bb的末尾，并从a

   aa中移除。

2. 将序列a

   aa的末尾元素加到b

   bb的末尾，并从a

   aa中移除。

我们的目的是让b

bb成为一个回文数列，即令其满足对所有1

\le

n1≤i≤n，有b

=

i}b

style="height:

0.05em;">i​

style="height:

0.15em;">=b

style="height:

0.05em;">2n+1−i​

style="height:

0.2083em;">。

请你判断该目的是否能达成，如果可以，请输出字典序最小的操作方案，具体在【输出格式】中说明。

输入格式

每个测试点包含多组测试数据。

输入的第一行，包含一个整数T

style="margin-right:

0.1389em;">T，表示测试数据的组数。

对于每组测试数据：

第一行，包含一个正整数n

nn。

/>第二行，包含2

n2n个用空格隔开的整数a

a_1,

n}a

style="height:

0.05em;">1​

style="height:

0.15em;">,a

style="height:

0.05em;">2​

style="height:

0.15em;">,…,a

style="height:

0.05em;">2n​

style="height:

0.15em;">。

输出格式

对每组测试数据输出一行答案。

如果无法生成出回文数列，输出一行-1，否则输出一行一个长度为2

n2n的、由字符L或R构成的字符串（不含空格），其中L表示移除开头元素的操作

2。

你需要输出所有方案对应的字符串中字典序最小的一个。

字典序的比较规则如下：长度均为2

n2n的字符串s

s_{1

n}s

style="height:

0.05em;">1∼2n​

style="height:

0.15em;">比t

t_{1

n}t

style="height:

0.05em;">1∼2n​

style="height:

0.15em;">字典序小，当且仅当存在下标1

\le

n1≤

style="margin-right:

0.0315em;">k≤2n使得对于每个1

<

k1≤i<

style="margin-right:

0.0315em;">k有s

=

t_is

style="height:

0.05em;">i​

style="height:

0.15em;">=t

style="height:

0.05em;">i​

style="height:

0.15em;">且s

<

t_ks

style="height:

0.0315em;">k​

style="height:

0.15em;"><t

style="height:

0.0315em;">k​

style="height:

0.15em;">。

输入输出样例

1

输入

-1

说明/提示

【样例解释

#1】

在第一组数据中，生成的的b

bb数列是[

[4,

4][4,5,3,1,2,2,1,3,5,4]，可以看出这是一个回文数列。

另一种可能的操作方案是LRRLLRRRRR，但比答案方案的字典序要大。

【数据范围】

令∑

\sum

0em;">∑n表示所有T

style="margin-right:

0.1389em;">T组测试数据中n

nn的和。

对所有测试点保证1

100

1001≤

style="margin-right:

0.1389em;">T≤100，1

\le

{10}^51≤n,

style="position:

0em;">∑n≤5×10

style="height:

0.05em;">5。

特殊性质：如果我们每次删除a

aa中两个相邻且相等的数，存在一种方式将序列删空（例如a

=

1]a=[1,2,2,1]）。

思路分析

1. 数据结构
   • a[1..2n]：原始输入序列。

   • b[x]：数值x首次出现的位置，用于构建配对关系。

   • c[i]：位置i的配对位置（满足a[i]==a[c[i]]且c[c[i]]==i）。

   • q1,q2：双端队列，分别存储左段和右段的下标。
     • q1保持原序，q2逆序存储，便于同时从两端访问。

2. 核心函数slv(ch)
   • 第一步：根据ch确定第一次操作方向，并找到配对位置o

     =

     c[st]。

   • 区间划分：剩余下标分为左段[l,

     r2]，分别按顺序推入q1和按逆序推入q2。

   • 贪心构造前半部分（n步）：
     • 每一步从整体左端

       (p)

       取出一个下标，并移除其配对下标（位于r或s）。

     • 按字典序由小到大的顺序检查四种合法情况：
       1. 取左端，配对右段左端

          当前操作L，配对取出方向R。

       2. 取左端，配对左段右端

          当前操作L，配对取出方向L。

       3. 取右端，配对左段右端

          当前操作R，配对取出方向L。

       4. 取右端，配对右段左端

          当前操作R，配对取出方向R。

     • 若四种均不满足，当前方案无解。

   • 生成完整操作串：
     • ans记录前半部分的每一步操作（长度n）。

     • sf记录每一步配对元素被取出时的操作方向（长度n，首字符固定L对应最后一步）。

     • 将sf反转后拼接到ans后，得到长度为2n的完整操作序列。

3. 字典序最小保证
   • 先尝试'L'作为第一步，失败后才尝试'R'。

   • 每一步优先尝试取'L'，且'L'时优先匹配右段左端，'R'时优先匹配左段右端。

   • 最后一步固定为'L'（剩余唯一元素时取左字典序更小）。

   • 上述贪心策略确保在所有可行方案中输出字典序最小的操作串。

4. 复杂度
   • 每组数据仅需一次线性扫描建立配对关系，以及线性次的队列操作。

   • 总复杂度O(∑n)，在∑n

     5×10^5的限制下可轻松通过洛谷所有测试点。

代码实现

#include<bits/stdc++.h>usingnamespacestd;constintN=1000005;intT,n,m;inta[N],b[N],c[N];//
a:原数组,
c:配对位置boolslv(charch){deque<int>q1,q2;//
q1:左段(原序),
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:整体左端,
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;}

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"##########
一站式掌握信奥赛知识!
##########";cout<<"#############
冲刺信奥赛拿奖!
#############";cout<<"######
######";return0;}

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