简答题 偏难
#22122

3、回文

3、回文


未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include &lt;bits/stdc++.h&gt; using namespace std; int t, n, l, r, l1, r1; int a[1000010], ton1[1000010], ton[1000010], vis[1000010]; stack&lt;int&gt; q; vector&lt;int&gt; 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 &lt;&lt; k &lt;&lt; " " &lt;&lt; l1 &lt;&lt; " " &lt;&lt; r1 &lt;&lt; " " &lt;&lt; l &lt;&lt; " " &lt;&lt; r &lt;&lt; " " &lt;&lt; q.size() &lt;&lt; endl;     if (k == n / 2) {         for (int i = 0; i &lt;= n / 2 - 1; i++) {             if (q1[i] == 1) {                 cout &lt;&lt; "L";             } else {                 cout &lt;&lt; "R";             }         }         while (!q.empty()) {             int x = q.top();             q.pop();             if (a[l] == x) {                 cout &lt;&lt; "L";                 l++;             } else {                 cout &lt;&lt; "R";                 r--;             }         }         cout &lt;&lt; endl;         return 1;     } else {         // cout &lt;&lt; ton[l1 + 1] &lt;&lt; l - 1 &lt;&lt; ton[l1 + 1] &lt;&lt; r + 1 &lt;&lt; endl;         if (vis[a[l1 + 1]] == 0 &amp;&amp; (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 &amp;&amp; (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 &lt;= n; i++) {             vis[i] = ton1[i] = ton[i] = 0;         }                  for (int i = 1; i &lt;= 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 &lt;= 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 &lt;&lt; -1 &lt;&lt; endl;             }         }     }     return 0; }</pre><p><br/></p>
这道题暂未补解析。