当前位置：首页 > news >正文

打卡信奥刷题（3170）用C++实现信奥题 P7915 [CSP-S 2021] 回文

news 2026/7/7 16:55:16

P7915 [CSP-S 2021] 回文

题目描述

给定正整数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

输入输出样例 #2

输入 #2

见附件中的 palin/palin2.in

输出 #2

见附件中的 palin/palin2.ans

说明/提示

【样例解释 #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]）。

【hack 数据提供】
@潜在了H2O下面。

C++实现

#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;constintmo=1e9+7;inlineintread(){charch=getchar();intx=0,f=1;while(!isdigit(ch))f=(ch=='-'?-1:f),ch=getchar();while(isdigit(ch))x=(x<<3)+(x<<1)+ch-'0',ch=getchar();returnx*f;}constintN=5e5+5;intn,L[N],R[N],a[2*N],b[2*N];charans[2*N];booldoit(intlst,intLi,intRi){if(Li==2)ans[1]='L';elseans[1]='R';intl=lst,r=lst,st=2,ed=2*n-1;for(inti=1;i<n;i++){if(R[a[Li]]==l-1)l--,Li++,ans[st++]='L',ans[ed--]='L';elseif(R[a[Li]]==r+1)r++,Li++,ans[st++]='L',ans[ed--]='R';elseif(L[a[Ri]]==l-1)l--,Ri--,ans[st++]='R',ans[ed--]='L';elseif(L[a[Ri]]==r+1)r++,Ri--,ans[st++]='R',ans[ed--]='R';elsereturn0;}ans[2*n]='L';printf("%s\n",ans+1);return1;}voidsolve(){memset(L,0,sizeof(L));memset(R,0,sizeof(R));memset(b,0,sizeof(0));memset(ans,0,sizeof(ans));n=read();for(inti=1;i<=2*n;i++)a[i]=read(),L[a[i]]?R[a[i]]=i:L[a[i]]=i;if(doit(R[a[1]],2,2*n))return;if(doit(L[a[2*n]],1,2*n-1))return;puts("-1");return;}signedmain(){intT=read();while(T--)solve();return0;}