简答题
偏难
#22122
3、回文
3、回文


答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include <bits/stdc++.h>
using namespace std;
int t, n, l, r, l1, r1;
int a[1000010], ton1[1000010], ton[1000010], vis[1000010];
stack<int> q;
vector<int> q1;
int read() {
int asd = 0, qwe = 1;
char zxc;
while (!isdigit(zxc = getchar())) {
if (zxc == '-') {
qwe = -1;
}
}
while (isdigit(zxc)) {
asd = asd * 10 + zxc - '0';
zxc = getchar();
}
return asd * qwe;
}
int dfs(int k) {
// cout << k << " " << l1 << " " << r1 << " " << l << " " << r << " " << q.size() << endl;
if (k == n / 2) {
for (int i = 0; i <= n / 2 - 1; i++) {
if (q1[i] == 1) {
cout << "L";
} else {
cout << "R";
}
}
while (!q.empty()) {
int x = q.top();
q.pop();
if (a[l] == x) {
cout << "L";
l++;
} else {
cout << "R";
r--;
}
}
cout << endl;
return 1;
} else {
// cout << ton[l1 + 1] << l - 1 << ton[l1 + 1] << r + 1 << endl;
if (vis[a[l1 + 1]] == 0 && (ton[l1 + 1] == l - 1 || ton[l1 + 1] == r + 1)) {
l1++;
if (ton[l1] == l - 1) {
l--;
} else {
r++;
}
q1.push_back(1);
q.push(a[l1]);
vis[a[l1]] = 1;
return dfs(k + 1);
} else if (vis[a[r1 - 1]] == 0 && (ton[r1 - 1] == l - 1 || ton[r1 - 1] == r + 1)) {
r1--;
if (a[ton[r1]] == a[l - 1]) {
l--;
} else {
r++;
}
q1.push_back(2);
q.push(a[r1]);
vis[a[r1]] = 1;
return dfs(k + 1);
} else {
return 0;
}
}
}
int main() {
// freopen("palin.in" , "r" , stdin);
// freopen("palin.out" , "w" , stdout);
t = read();
while (t--) {
n = read() * 2;
l1 = 0;
r1 = n + 1;
while (!q.empty()) {
q.pop();
}
q1.clear();
for (int i = 1; i <= n; i++) {
vis[i] = ton1[i] = ton[i] = 0;
}
for (int i = 1; i <= n; i++) {
a[i] = read();
if (ton1[a[i]]) {
ton[i] = ton1[a[i]];
ton[ton1[a[i]]] = i;
} else {
ton1[a[i]] = i;
}
}
// 第一种尝试:从左侧开始
vis[a[++l1]] = 1;
l = r = ton[l1];
q1.push_back(1);
q.push(a[l1]);
if (dfs(1) == 0) {
// 重置状态,尝试从右侧开始
for (int i = 1; i <= n; i++) {
vis[i] = 0;
}
q1.clear();
l1 = 0;
r1 = n + 1;
while (!q.empty()) {
q.pop();
}
vis[a[--r1]] = 1;
l = r = ton[r1];
q1.push_back(2);
q.push(a[r1]);
if (dfs(1) == 0) {
cout << -1 << endl;
}
}
}
return 0;
}</pre><p><br/></p>
这道题暂未补解析。