【题解】Walking! 贪心, 堆 CF578E —Qiuly

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

首先令 AB 表示 A 为子序列开头，B 为子序列结尾的子序列，上面的分别是 LR 和 RL 子序列。

需要注意的是，假设只存在 LR 和 RL 子序列，那么它们如何拼接成答案？这个时候只需要一个 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