纠错
2026-07-03 20:25:15
发布于：广东
一、总体结论
你当前代码相比最初版本，已经修复了部分明显越界问题，例如：
string ans(2 * n, '?');
int l = 1, r = 2 * n;
但是程序仍然不能 AC。
根本原因不是某个判断符号写错，而是算法模型错误：
你仍然把剩余序列当成一个连续区间
[l, r]来维护，但本题在第一次确定首尾相同元素后，中间剩余部分会被切成两个独立区间，必须维护[l1, r1]和[l2, r2]两段。
因此，这份代码不是简单改几个边界条件就能通过的，核心的 solve 函数需要改成双区间模型。
二、已经修好的问题
1. string ans 越界问题已修复
旧代码中：
string ans;
ans[n - 1] = 'L';
这是严重越界，因为空字符串不能直接访问下标。
你现在改成：
string ans(2 * n, '?');
这是正确的。
2. 初始区间范围部分修复
旧代码中：
int l = 0, r = n - 1;
这是错的，因为数组是从 1 到 2n 存储的。
你现在改成：
int l = 1, r = 2 * n;
至少数组边界方向是对的。
但是注意：即使这里改成了 1 ~ 2n，仍然不能解决核心问题，因为剩余元素不能只用一个 [l, r] 表示。
三、当前代码的核心错误
错误 1：只维护一个区间 [l, r]
你当前代码的主要逻辑是：
int l = 1, r = 2 * n;
然后每次根据 l 和 r 取元素。
但是本题正确模型不是这样的。
以第一次取 L 为例：
假设序列为：
[1, 2, 1, 2]
第一次取走左端 1 后，另一个 1 在位置 3。为了让最终序列是回文，这个位置 3 的 1 必须留到最后取。
因此剩下的中间部分不是一个连续区间，而是两个区间：
[2, 2] 和 [4, 4]
也就是说，正确状态应该是：
l1 = 2, r1 = 2;
l2 = 4, r2 = 4;
但你的代码仍然维护成：
l = 2, r = 4;
这样会把位置 3 也当成普通的中间元素参与后续操作，这是错误的。
错误 2：fpos(lst) 思路不适合本题
你现在使用：
int lv = fpos(lst) - 1, rv = lv + 2;
也就是根据上一次取的位置 lst，找到它的另一个相同元素的位置，再看这个位置左右两侧。
这个思路看起来像是在“围绕匹配点扩展”，但它不符合本题的删除过程。
本题每一步真实能选择的元素，只可能来自当前剩余部分的四个端点：
a[l1], a[r1], a[l2], a[r2]
所以正确代码应该枚举四种情况：
a[l1] == a[r1] // 前面取 L，后面取 L
a[l1] == a[l2] // 前面取 L，后面取 R
a[r2] == a[r1] // 前面取 R，后面取 L
a[r2] == a[l2] // 前面取 R，后面取 R
而不是每次通过 fpos(lst) 找另一个位置。
错误 3：会把同一个元素和自己配对
你当前代码中有：
if(l <= lv && a[l] == a[lv])
这里允许 l == lv。
这会导致同一个位置被当成两个元素使用。
例如：
1
2
1 2 1 2
第一次取 L 后：
lst = 1
fpos(lst) = 3
lv = 2
l = 2
于是判断：
l <= lv
a[l] == a[lv]
变成：
2 <= 2
a[2] == a[2]
这个条件成立，但实际上是在让位置 2 的元素和自己配对，这是不合法的。
类似问题还出现在其他判断中，例如：
rv < r
l <= lv
这些边界判断都不是本题正确模型下的判断方式。
四、最小反例
当前代码在下面数据上会出错：
1
2
1 2 1 2
正确答案可以是：
LLRL
对应过程：
原序列：[1, 2, 1, 2]
L -> 1
L -> 2
R -> 2
L -> 1
得到 b = [1, 2, 2, 1]
这是合法回文。
但你的代码会错误地构造出类似：
LLLL
对应过程：
L -> 1
L -> 2
L -> 1
L -> 2
得到 b = [1, 2, 1, 2]
这不是回文。
这说明当前模型会错误地使用原本应该留到最后的那个匹配元素。
五、正确模型应该是什么
本题的关键是：
第一次取的元素决定最后一次必须取哪个元素。
因为最终 b 是回文，所以：
b[1] == b[2n]
如果第一次取的是左端 a[1]，那么最后一个数必须是另一个 a[1]。
设另一个 a[1] 的位置为 p，那么中间剩余部分被切成：
[2, p - 1] 和 [p + 1, 2n]
如果第一次取的是右端 a[2n]，设另一个 a[2n] 的位置为 p，那么中间剩余部分被切成：
[1, p - 1] 和 [p + 1, 2n - 1]
所以 solve 函数必须维护四个端点：
int l1, r1, l2, r2;
而不是：
int l, r;
六、正确的四种转移
每一轮要同时确定答案的前面一位和后面一位。
也就是同时填：
ans[i]
ans[j]
其中：
j = 2 * n - 1 - i;
当前能选择的位置来自两个区间的四个端点。
四种情况分别是：
情况 1：前面取 L，后面取 L
a[l1] == a[r1]
操作：
ans[i] = 'L';
ans[j] = 'L';
l1++;
r1--;
情况 2：前面取 L，后面取 R
a[l1] == a[l2]
操作：
ans[i] = 'L';
ans[j] = 'R';
l1++;
l2++;
情况 3：前面取 R，后面取 L
a[r2] == a[r1]
操作：
ans[i] = 'R';
ans[j] = 'L';
r2--;
r1--;
情况 4：前面取 R，后面取 R
a[r2] == a[l2]
操作：
ans[i] = 'R';
ans[j] = 'R';
r2--;
l2++;
七、为什么先尝试 L，再尝试 R
题目要求输出字典序最小的方案。
因为：
'L' < 'R'
所以应当先尝试第一次操作为 L 的方案。
如果 check('L') 成功，直接输出它。
只有当 check('L') 失败时，才尝试 check('R')。
也就是：
string ans = check('L');
if(ans.empty()) ans = check('R');
这个策略是正确的。
八、当前代码的其他风险
局部数组过大，可能爆栈
你现在每组数据里写：
int a[N]{};
int fir[N]{}, sec[N]{};
又因为你写了：
#define int long long
所以每个数组大约占：
1e6 * 8 = 8MB
三个数组大约是：
24MB
而且这些数组是局部变量，放在栈上，容易爆栈。
建议改成：
vector<int> a(2 * n + 1);
vector<int> fir(n + 1), sec(n + 1);
因为题目保证数字只在 1 ~ n 之间，所以 fir 和 sec 只需要开到 n + 1。
九、针对你当前代码的修改建议
不建议继续修补这一套逻辑：
int l, r;
int lst;
fpos(lst);
这套模型本身不适合本题。
建议直接把 solve 函数改成双区间版本。
核心结构如下：
auto check = [&](char first) -> string {
int m = 2 * n;
string ans(m, '?');
int l1, r1, l2, r2;
if(first == 'L') {
int p = fpos(1);
ans[0] = 'L';
ans[m - 1] = 'L';
l1 = 2;
r1 = p - 1;
l2 = p + 1;
r2 = m;
} else {
int p = fpos(m);
ans[0] = 'R';
ans[m - 1] = 'L';
l1 = 1;
r1 = p - 1;
l2 = p + 1;
r2 = m - 1;
}
for(int i = 1; i < n; i++) {
int j = m - 1 - i;
if(l1 < r1 && a[l1] == a[r1]) {
ans[i] = 'L';
ans[j] = 'L';
l1++;
r1--;
}
else if(l1 <= r1 && l2 <= r2 && a[l1] == a[l2]) {
ans[i] = 'L';
ans[j] = 'R';
l1++;
l2++;
}
else if(l2 <= r2 && l1 <= r1 && a[r2] == a[r1]) {
ans[i] = 'R';
ans[j] = 'L';
r2--;
r1--;
}
else if(l2 < r2 && a[r2] == a[l2]) {
ans[i] = 'R';
ans[j] = 'R';
r2--;
l2++;
}
else {
return "";
}
}
return ans;
};
注意这里的 fpos 应该是传入位置，返回同值的另一个位置：
auto fpos = [&](int pos) {
int val = a[pos];
if(fir[val] == pos) return sec[val];
return fir[val];
};
十、最终结论
你的当前版本主要问题不是语法，也不是简单越界，而是：
单区间维护方式错误。
本题第一次取走一个数后，它的另一个相同数必须作为最后一个数保留，因此原序列会被切成两个区间。
所以正确做法必须是：
维护 l1, r1, l2, r2 四个端点。
而不是：
维护 l, r 和 lst。
因此，当前代码继续沿着 fpos(lst) 方向修，很难修对。应该直接改成双区间模型。
这里空空如也
有帮助，赞一个