题意转化过来就是,你需要将原序列拆分成尽可能少的形如 LR....RLR 或者 RL....LRL 子序列,最终的答案就是子序列数 $-1$ 。

首先令 AB 表示 A 为子序列开头,B 为子序列结尾的子序列,上面的分别是 LRRL 子序列。

需要注意的是,假设只存在 LRRL 子序列,那么它们如何拼接成答案?这个时候只需要一个 RR 或者一个 LL 即可,没有的话就凑一个出来。

找到一个 LR 和一个 RL ,并且规定 RL 的结尾在 LR 的后面,那么可以将 RL 的结尾的 L 删除从而使得其变成 RR ,再将这个 L 放到 LR 后面,这样变成了 LL

#include <vector>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define ins push_back
#define del pop_back

const int N=1e5+5;
int n,Inv_cnt;
char str[N];
vector <int> End[2],Inv[N],ID[4];

inline void solve() {
    if(ID[2].size()+ID[3].size()) return void();
    if(!ID[0].size()||!ID[1].size()) return void();
    int a=ID[0].back(),b=ID[1].back(),x=Inv[a].back(),y=Inv[b].back();
    (x>y)?(Inv[b].ins(x),Inv[a].del()):(Inv[a].ins(y),Inv[b].del());
    ID[0].del(),ID[1].del(),ID[2].ins(a),ID[3].ins(b);
}

inline void print(int id) {for(auto num:Inv[id]) printf("%d ",num);}
inline void Print(int id) {while(!ID[id].empty()) print(ID[id].back()),ID[id].del();}
int main() {
    scanf("%s\n",str+1),n=strlen(str+1);
    for(int i=1;i<=n;++i) {
        int now=(bool)(str[i]=='R'),Inv_id;
        if(!End[now^1].size()) End[now^1].ins(++Inv_cnt);
        Inv_id=End[now^1].back();
        Inv[Inv_id].ins(i),End[now].ins(Inv_id),End[now^1].del();
    }
    for(int i=1;i<=Inv_cnt;++i)
        ID[(str[Inv[i].front()]==str[Inv[i].back()])*2+(str[Inv[i].front()]=='R')].ins(i);
    solve();
    printf("%d\n",Inv_cnt-1);
    int _1=ID[2].size(),_2=ID[3].size();
    if(_2) Print(1),Print(3),Print(0),Print(2);
    else Print(0),Print(2),Print(1);
    return 0;
}

代码超级短,调了我将近一个小时,\tuu

分类: 文章

Qiuly

QAQ

0 条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注