CSP-S2 T3思路

· · 个人记录

好像初二没人会啊……

在这里给一个过了大样例的思路。

我们无论如何要不先选最左边的数，要不就选最右边的数。

例如样例一，有如下数列：

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

如果我们第一步选择最左边的 4，那么在第四位的 4 就一定要最后取出才能满足条件，因此，在它左边的所有数字，都只能通过 L 操作取出，而右边的操作只能有 R 操作取出。

那么考虑在这样的情况下是否能够成功。现在我们有两个数列，被中间的 4 分开。我们还是每次只能取左边数列的最左端或右边数列的最右端。

当我们在第 i 此选择之后，那么要保证那个数字是第 n-i+1 个被选择的，我瞎想了一个四指针的方法：存储左数列的左端点与右端点加一 j_1 、存储右数列的右端点与左端点加一 j_2，而每次看左数列的左端点 i_1 与右数列的右端点 i_2，是否有 a_{i_1} = a_{j_1} 或 a_{i_1} = a_{j_2} 如果有成功的就加入操作字符串，并且将取 j 的操作反向加入一个字符串，如果没有就看 i_2。最终如果都不可行就直接退出，否则返回两个字符串的组合就可以。

我不会做B呜呜呜呜呜呜呜呜呜呜TAT

code:

#include<bits/stdc++.h>
using namespace std;
const int MAXN=5e5+5;
int t,n,arr[MAXN*2],l[MAXN],r[MAXN];
int l1,l2,r1,r2;
string ans,nya,ret;
string check1() {
    ans="L",nya="L";
    l1=2,r1=2*n,l2=r[arr[1]],r2=r[arr[1]];
    int cnt=n-1;
    while(cnt--) {
        if(r[arr[l1]]==l2-1) {
            ans+="L";
            nya+="L";
            ++l1;--l2;
            continue;
        }
        if(r[arr[l1]]==r2+1) {
            ans+="L";
            nya+="R";
            ++l1;++r2;
            continue;
        }
        if(l[arr[r1]]==l2-1) {
            ans+="R";
            nya+="L";
            --r1;--l2;
            continue;
        }
        if(l[arr[r1]]==r2+1) {
            ans+="R";
            nya+="R";
            --r1;++r2;
            continue;
        }
        return "fuck";
    }
    for(int i=n-1;i>=0;--i) ans+=nya[i];
    return ans;
}
string check2() {
    ans="R",nya="L";
    l1=1,r1=2*n-1,l2=l[arr[2*n]],r2=l[arr[2*n]];
    int cnt=n-1;
    while(cnt--) {
        if(r[arr[l1]]==l2-1) {
            ans+="L";
            nya+="L";
            ++l1;--l2;
            continue;
        }
        if(r[arr[l1]]==r2+1) {
            ans+="L";
            nya+="R";
            ++l1;++r2;
            continue;
        }
        if(l[arr[r1]]==l2-1) {
            ans+="R";
            nya+="L";
            --r1;--l2;
            continue;
        }
        if(l[arr[r1]]==r2+1) {
            ans+="R";
            nya+="R";
            --r1;++r2;
            continue;
        }
        return "fuck";
    }
    for(int i=n-1;i>=0;--i) ans+=nya[i];
    return ans;
}
int main() {
    freopen("palin.in","r",stdin);
    freopen("palin.out","w",stdout);
    scanf("%d",&t);
    while(t--) {
        scanf("%d",&n);
        for(int i=1;i<=2*n;++i) {
            scanf("%d",&arr[i]);
            l[arr[i]]=r[arr[i]];
            r[arr[i]]=i;
        }
        string ret=check1();
        if(ret!="fuck") cout<<ret<<endl;
        else {
            ret=check2();
            if(ret!="fuck") cout<<ret<<endl;
            else printf("-1\n");
        }
    }
    return 0;
}
/*
4 18 2 9 9 19 10 6 8 7 14 20 5 4 1 13 17 18 12 15 11 2 16 3 3 16 11 15 12 19 17 10 13 1 5 6 20 14 7 8
x x            o o o o o  o  o o o o  o  o                                    x x  x  x x x x  x  x x
*/