WA 了十几发，清醒了之后发现自己是个 sb。
首先肯定贪心选，让每条链尽量长即可。
最后直接跑个欧拉回路即可（两个点的欧拉回路(ˉ▽ˉ；)...）。
分析一下，发现两个点的度数一定满足要求，无非就是是否联通。
那么如果两个点之间没有连边并且两个点都有自环，那么就会不连通。
只需要考虑这种特殊情况就行了。
考虑略微修改一下连边使得图联通
-
拎出两个自环：
...L..R..L...R... .R..L...R..L..... -
这种情况只要改成这样就行了：
.R.L..R..L...R... ....L...R..L..... -
然后，就没有然后了，已经做完了。
代码
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=1e5+10;
int n,cnt[2],nex[N];
int k,ans[N];
char a[N];
int cover(int x,int tag=0){
int s;
for(;x;x=nex[x])if(s=x,tag)ans[++k]=x;
return s;
}
int top,stk[N],deg[2];
vector<pair<int,int> >to[2];
void add(int u,int v,int w){
deg[u]++,deg[v]--;
to[u].push_back({v,w});
}
void dfs(int u){
for(;!to[u].empty();){
int v=to[u].back().first,w=to[u].back().second;
to[u].pop_back();
dfs(v);
stk[++top]=w;
}
}
int main(){
freopen(".in","r",stdin);
//freopen(".out","w",stdout);
scanf("%s",a+1),n=strlen(a+1);
for(int i=1;i<=n;i++)cnt[a[i]=='R']++;
vector<int>L,R;
for(int i=n;i>=1;i--){
if(a[i]=='L'){
if(!R.empty())nex[i]=R.back(),R.pop_back();
L.push_back(i);
}else{
if(!L.empty())nex[i]=L.back(),L.pop_back();
R.push_back(i);
}
}
vector<int>LL,LR,RL,RR;
for(int x:L){
char c=a[cover(x)];
if(c=='L')LL.push_back(x);
else LR.push_back(x);
}
for(int x:R){
char c=a[cover(x)];
if(c=='L')RL.push_back(x);
else RR.push_back(x);
}
if(RR.empty()&&LL.empty()&&!RL.empty()&&!LR.empty()){
int x=LR.back(),y=RL.back();
LR.pop_back(),RL.pop_back();
if(x<y){
RR.push_back(nex[x]);
LL.push_back(x);
nex[x]=y;
}else{
LL.push_back(nex[y]);
RR.push_back(y);
nex[y]=x;
}
}
for(int x:LL)add(0,a[cover(x)]=='L',x);
for(int x:LR)add(0,a[cover(x)]=='L',x);
for(int x:RL)add(1,a[cover(x)]=='L',x);
for(int x:RR)add(1,a[cover(x)]=='L',x);
top=0;
if(deg[0]<deg[1])dfs(1);
else if(deg[0]>deg[1])dfs(0);
else dfs(0),dfs(1);
for(int i=top;i>=1;i--)cover(stk[i],1);
int cnt=0;
for(int i=1;i<n;i++)cnt+=ans[i]>ans[i+1];
printf("%d\n",cnt);
for(int i=1;i<=n;i++)printf("%d ",ans[i]);
for(int i=1;i<n;i++){
if(a[ans[i]]==a[ans[i+1]])assert(0);
}
return 0;
}