I1. Kevin and Puzzle (Easy Version) 题解

题目回顾

给定长度为 $n$、仅由 $\text{L}/\text{R}$ 组成的字符串 $s$，构造非负整数数组 $a$ 满足：

1. 若 $s_i=\text{L}$，则 $a_i = c(1,i-1)$（数组前 $i-1$ 个元素的不同数个数）；
2. 若 $s_i=\text{R}$，则 $a_i = c(i+1,n)$（数组后 $n-i$ 个元素的不同数个数）；
3. 无法构造则输出 $-1$。

核心思路

1. 关键结论：字符串合法性判定

这是解题的核心前提，直接决定是否存在合法数组： 对字符串做对称位置检查（$i$ 和 $n-i+1$）：

• 若出现对称对 $\boldsymbol{(R,L)}$，且此前已经出现过相同的对称对 → 字符串非法，输出 $-1$；
• 其余情况均合法，可以构造数组。

直观理解：合法字符串的结构必须是 左侧连续 $\text{L}$ + 右侧连续 $\text{R}$，禁止出现交叉的 $\text{RL}$ 对称结构。

2. 构造策略：双指针递归构造

合法后，用从两端向中间收缩的双指针递归构造数组：

• 定义 $solve(l,r,k)$：处理区间 $[l,r]$，当前赋值基数为 $k$，返回构造的最大数值；
• 按两端字符 $s[l],s[r]$ 的组合分情况赋值，保证数组满足题目要求；
• 赋值规则：用递增的数字构造，天然保证「不同元素个数」符合 $c(l,r)$ 的定义。

代码逐段解析

全局变量

#include<bits/stdc++.h>
#define int long long
using namespace std;
int t,n,a[200005];  // a：答案数组，t：测试用例数，n：字符串长度
string s;           // 输入字符串（下标从1开始）

递归构造函数：solve(l, r, k)

核心构造逻辑，分4种情况处理对称两端：

int solve(int l,int r,int k){
    if(l>r) return k-1;        // 区间空，返回上一级基数
    if(l==r){a[l]=k;return k;} // 单个元素，直接赋值k
    
    // 情况1：左L、右R → 两端同赋k，向内收缩，k+1
    if(s[l]=='L'&&s[r]=='R'){
        a[l]=a[r]=k;
        return solve(l+1,r-1,k+1);
    }
    // 情况2：左L、右L → 左赋k，右递归+1
    if(s[l]=='L'&&s[r]=='L'){
        a[l]=k;
        a[r]=solve(l+1,r-1,k+1)+1;
        return a[r];
    }
    // 情况3：左R、右R → 右赋k，左递归+1
    if(s[l]=='R'&&s[r]=='R'){
        a[r]=k;
        a[l]=solve(l+1,r-1,k+1)+1;
        return a[l];
    }
    // 情况4：非法情况（合法字符串不会走到这里）
    for(int i=l;i<=r;i++)a[i]=k+1;
    return k+1;
}

主函数：合法性检查 + 构造输出

signed main(){
    cin>>t;
    while(t--){
        cin>>n>>s;
        s=" "+s; // 下标转为1开始，方便对称处理
        int flag=0; // 合法性标记：0=无相同对称对，1=有相同对，2=非法
        
        // 对称检查：i 和 n-i+1
        for(int i=1;i<=n/2;i++){
            if(s[i]==s[n-i+1]) flag=1; // 出现相同对称对
            // 出现(R,L)对称对 + 此前有相同对 → 非法
            if(s[i]=='R'&&s[n-i+1]=='L'){
                flag=2;
                break;
            }
        }
        
        if(flag==2){ // 非法，输出-1
            cout<<"-1\n";
            continue;
        }
        
        solve(1,n,0); // 合法，递归构造数组
        // 输出答案
        for(int i=1;i<=n;i++)cout<<a[i]<<" ";
        cout<<"\n";
    }
}

样例验证

样例输入1

3
LLR

1. 对称检查：合法；
2. 递归构造：$solve(1,3,0)$ → 输出 0 1 0，与样例一致。

样例输入3

4
RRLR

1. 对称检查：出现非法 $\text{(R,L)}$ 对称对；
2. 输出 -1，与样例一致。

样例输入4

5
LLRLR

1. 对称检查：合法；
2. 构造输出 0 1 2 3 0，与样例一致。

复杂度分析

1. 时间复杂度：$O(\sum n)$

   • 合法性检查：$O(n)$；
   • 递归构造：双指针仅遍历数组一次，$O(n)$；
   • 总复杂度满足题目约束（$\sum n \le 2\times10^5$）。

2. 空间复杂度：$O(n)$

   • 存储数组 $a$ 和字符串，递归深度为 $O(n/2)$（评测机栈空间可支持）。

总结

1. 先判合法性：通过对称检查快速排除非法字符串；
2. 再构造数组：用两端向中间收缩的递归，按字符组合分情况赋值；
3. 构造的数组天然满足题目要求，是简洁高效的正解。