求助S组T3
  • 板块灌水区
  • 楼主L_S_C
  • 当前回复0
  • 已保存回复0
  • 发布时间2021/10/24 18:48
  • 上次更新2023/11/4 02:23:11
查看原帖
求助S组T3
187850
L_S_C楼主2021/10/24 18:48
#include<bits/stdc++.h>
using namespace std;
long long n, arr[1000010], t;
struct node{
    string s;
}ans[1000010];
bool cmt(node x, node y){
    return x.s < y.s;
}
string solve1(long long x){
    long long l1 = 1, r1 = 2 * n + 1, l2 = x, r2 = x;
    string str1 = "L", str2 = "L";
    for(int i = 1; i < n; i++){
        if(arr[l1 + 1] == arr[l2 - 1] && l1 + 1 != l2 - 1){
            str1 = str1 + "L";
            str2 = "L" + str2;
            l1++;
            l2--;
//          cout << 1;
        }
        else if(arr[l1 + 1] == arr[r2 + 1] && l1 + 1 != l2 && r2 + 1 != r1){
            str1 = str1 + "L";
            str2 = "R" + str2;
            l1++;
            r2++;
//          cout << 2;
        }
        else if(arr[r1 - 1] == arr[l2 - 1] && r1 - 1 != r2 && l2 - 1 != r1){
            str1 = str1 + "R";
            str2 = "L" + str2;
            r1--;
            l2--;
//          cout << 3;
        }
        else if(arr[r1 - 1] == arr[r2 + 1] && r2 + 1 != r1 - 1){
            str1 = str1 + "R";
            str2 = "R" + str2;
            r1--;
            r2++;
//          cout << 4;
        }
        else return "";
    }
    return str1 + str2;
}
string solve2(long long x){
    long long l1 = 2, r1 = 2 * n, l2 = x, r2 = x;
    string str1 = "R", str2 = "L";
    for(int i = 1; i < n; i++){
        if(arr[l1 + 1] == arr[l2 - 1] && l1 + 1 != l2 - 1){
            str1 = str1 + "L";
            str2 = "L" + str2;
            l1++;
            l2--;
        }
        else if(arr[l1 + 1] == arr[r2 + 1] && l1 + 1 != l2 && r2 + 1 != r1){
            str1 = str1 + "L";
            str2 = "R" + str2;
            l1++;
            r2++;
        }
        else if(arr[r1 - 1] == arr[l2 - 1] && r1 - 1 != r2 && l2 - 1 != r1){
            str1 = str1 + "R";
            str2 = "L" + str2;
            r1--;
            l2--;
        }
        else if(arr[r1 - 1] == arr[r2 + 1] && r2 + 1 != r1 - 1){
            str1 = str1 + "R";
            str2 = "R" + str2;
            r1--;
            r2++;
        }
        else return "";
    }
}
int main(){
//  freopen("palin.in", "r", stdin);
//  freopen("palin.out", "w", stdout);
    cin >> t;
    while(t--){
        scanf("%lld", &n);
        for(int i = 1; i <= 2 * n; i++){
            scanf("%lld", &arr[i]);
        }
        long long tot = 0;
        string tmp;
        for(int i = 2 * n; i >= 2; i--){
            if(arr[i] == arr[1])tmp = solve1(i);
            if(tmp != ""){
                ans[++tot].s = tmp;
            }
        }
        for(int i = 2 * n - 1; i >= 1; i--){
            if(arr[i] == arr[n * 2])tmp = solve2(i);
            if(tmp != ""){
                ans[++tot].s = tmp;
            }
        }
        if(tot){
            sort(ans + 1, ans + tot + 1, cmt);
            cout << ans[1].s<<'\n';
        }
        if(!tot){
            cout << -1 << '\n';
        }
    }
    return 0;
}
//2
//5 
//4 1 2 4 5 3 1 2 3 5
//3
//3 2 1 2 1 3
//1
//20
//5 20 6 12 13 18 9 17 2 7 7 18 1 11 10 15 4 6 17 19 14 10 14 13 1 16 8 3 12 8 19 20 4 16 5 3 9 2 15 11
2021/10/24 18:48
加载中...