题解：洛谷 P7915 [CSP-S 2021] 回文

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。

欢迎大家订阅我的专栏：算法题解：C++与Python实现！

附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总

【题目来源】

洛谷：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为空序列，每次可以进行以下两种操作之一：

1. 将序列a aa的开头元素加到b bb的末尾，并从a aa中移除。
2. 将序列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​。

【输入样例】

2 5 4 1 2 4 5 3 1 2 3 5 3 3 2 1 2 1 3

【输出样例】

LRRLLRRRRL -1

【算法标签】

#普及+# #贪心#

【代码详解】

// 28分#include<bits/stdc++.h>usingnamespacestd;constintN=1005;// 最大数组大小inta[N];// 原始数组，存储输入的2n个数字intb[N];// 中间数组，用于存储当前构造的序列intt,n;// t: 测试用例数量, n: 原题中的n，但数组大小是2ncharc[N];// 操作序列，记录每一步是'L'还是'R'boolflag;// 标记是否已找到合法序列// 检查当前构造的序列b是否是回文序列boolcheck(){// 从两端向中间比较for(inti=1,j=2*n;i<j;i++,j--){if(b[i]!=b[j])// 如果对应位置不相等{returnfalse;// 不是回文}}returntrue;// 是回文}// 深度优先搜索函数// left: 当前剩余数字的左边界（在数组a中的下标）// right: 当前剩余数字的右边界（在数组a中的下标）// top: 当前构造序列b的下一个位置voiddfs(intleft,intright,inttop){if(flag)// 如果已经找到合法序列，直接返回{return;}// 递归终止条件：所有数字都已使用if(left>right){// 检查当前构造的序列b是否是回文序列if(check()){// 如果找到合法序列，设置标记为trueflag=true;// 输出操作序列for(inti=1;i<=2*n;i++){cout<<c[i];}cout<<endl;}return;// 返回上一层递归}// 分支1：从剩余数字的左侧取数字b[top]=a[left];// 将a[left]放入构造序列c[top]='L';// 记录操作为'L'（从左侧取）dfs(left+1,right,top+1);// 递归处理剩余数字// 分支2：从剩余数字的右侧取数字b[top]=a[right];// 将a[right]放入构造序列c[top]='R';// 记录操作为'R'（从右侧取）dfs(left,right-1,top+1);// 递归处理剩余数字}intmain(){// 输入测试用例数量cin>>t;// 处理每个测试用例while(t--){// 输入n（但实际有2n个数字）cin>>n;// 初始化标记flag=false;// 输入2n个数字for(inti=1;i<=2*n;i++){cin>>a[i];}// 开始深度优先搜索dfs(1,2*n,1);// 如果没有找到合法序列，输出-1if(!flag){cout<<-1<<endl;}}return0;}

// 100分解法#include<bits/stdc++.h>usingnamespacestd;constintN=1000005;// 最大数组大小inta[N];// 原始数组，存储输入的2n个数字intb[N];// 构造的回文数组intc[N];// 第一组数字intd[N];// 第二组数字charans[N];// 记录操作序列，L表示从左侧取，R表示从右侧取intt,n;// t: 测试用例数量, n: 原题中的n，但实际数组大小为2nboolflag,flag2=true;// flag: 局部标记, flag2: 全局标记，表示是否找到解// 主处理函数// type: 处理类型，1表示从左侧第一个数字开始，2表示从右侧最后一个数字开始voidfunc(inttype){intx;// 关键数字，用于分割数组ints=0;// 计数器，用于跟踪关键数字的出现次数intj=0;// 数组c的指针intk=0;// 数组d的指针// 数组指针初始化intbhead=1;// 构造数组b的左指针intbtail=2*n;// 构造数组b的右指针intchead=1;// 数组c的左指针intctail;// 数组c的右指针intdhead=1;// 数组d的左指针intdtail;// 数组d的右指针// 根据type进行不同的初始分割if(type==1)// 从左侧第一个数字开始{x=a[1];// 关键数字是第一个数字for(inti=1;i<=2*n;i++){if(s<2)// 在遇到第二个x之前，放入数组c{c[++j]=a[i];}else// 遇到第二个x之后，放入数组d{d[++k]=a[i];}if(a[i]==x)// 统计关键数字出现次数{s++;}}}else// 从右侧最后一个数字开始{x=a[2*n];// 关键数字是最后一个数字for(inti=1;i<=2*n;i++){if(s<1)// 在遇到第一个x之前，放入数组c{c[++j]=a[i];}else// 遇到第一个x之后，放入数组d{d[++k]=a[i];}if(a[i]==x)// 统计关键数字出现次数{s++;}}}ctail=j;// 数组c的右边界dtail=k;// 数组d的右边界// 构造回文序列的核心循环while(bhead<btail){flag=true;// 标记本轮是否成功匹配// 情况1：数组c两端相等if(chead<ctail&&c[chead]==c[ctail]){b[bhead]=c[chead];b[btail]=c[ctail];ans[bhead]='L';// 从左侧取ans[btail]='L';// 从左侧取chead++;ctail--;bhead++;btail--;flag=false;// 成功匹配}// 情况2：数组d两端相等elseif(dhead<dtail&&d[dhead]==d[dtail]){b[bhead]=d[dhead];b[btail]=d[dtail];ans[bhead]='R';// 从右侧取ans[btail]='R';// 从右侧取dhead++;dtail--;bhead++;btail--;flag=false;// 成功匹配}// 情况3：数组c的左侧和数组d的左侧相等elseif(c[chead]==d[dhead]){b[bhead]=c[chead];b[btail]=d[dhead];ans[bhead]='L';// 从左侧取ans[btail]='R';// 从右侧取chead++;dhead++;bhead++;btail--;flag=false;// 成功匹配}// 情况4：数组c的右侧和数组d的右侧相等elseif(c[ctail]==d[dtail]){b[bhead]=c[ctail];b[btail]=d[dtail];ans[bhead]='R';// 从右侧取ans[btail]='L';// 从左侧取ctail--;dtail--;bhead++;btail--;flag=false;// 成功匹配}// 如果四种情况都不满足，说明无法构造回文if(flag){flag2=false;// 标记失败return;// 直接返回}}}intmain(){// 输入测试用例数量cin>>t;// 处理每个测试用例while(t--){cin>>n;flag2=true;// 重置成功标记// 输入2n个数字for(inti=1;i<=2*n;i++){scanf("%d",&a[i]);}// 清空数组memset(b,0,sizeof(b));memset(c,0,sizeof(c));memset(d,0,sizeof(d));// 尝试第一种分割方式（从左侧开始）func(1);if(flag2)// 如果成功{for(inti=1;i<=2*n;i++){cout<<ans[i];}cout<<endl;continue;// 处理下一个测试用例}// 清空数组memset(b,0,sizeof(b));memset(c,0,sizeof(c));memset(d,0,sizeof(d));flag2=true;// 重置标记// 尝试第二种分割方式（从右侧开始）func(2);if(flag2)// 如果成功{for(inti=1;i<=2*n;i++){cout<<ans[i];}cout<<endl;continue;// 处理下一个测试用例}// 两种方式都失败，输出-1cout<<-1<<endl;}return0;}

【运行结果】

2 5 4 1 2 4 5 3 1 2 3 5 3 3 2 1 2 1 3 LRRLLRRRRL -1