codeforces gym101482 D Digi Comp II 拓朴+规律

https://vjudge.net/problem/Gym-101482D

题目大意：给出$m$个开关的初始状态$L、R$，以及这个开关左侧连接的开关编号和右侧连接的开关编号，$1$号开关为起点，$0$号开关为终点，$n$个球依次从起点滚下，当经过一个开关时，会走向其状态对应的开关，同时翻转该状态。请输出最终$m$个开关的状态。

思路：先找一波规律，显然当有$n$个球经过开关$u$时，通过$n$的奇偶性以及$u$的初始状态很容易得到最终的状态。而且会有$n/2+n\&1$个球经过它初始状态指向的开关，有$n/2$个球经过另一个状态的开关。那么这就给了我们启发，以拓朴序的方式进行递推，就可以得到每个开关的最终状态。注意坑点一，不一定只有起点$1$的入度为$0$。坑点二，有些开关的$L、R$对应的编号是相同的，入队的时候要注意。

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define eps 1e-10
#define pr pair<int,int>
using namespace std;
typedef long long ll;const int maxn=5e5+5;ll n;
int m;
int ind[maxn],l[maxn],r[maxn],ans[maxn];
ll val[maxn];
char s[maxn][2];
queue<int> q;int main()
{scanf("%lld%d",&n,&m);for(int i=1;i<=m;i++){scanf("%s%d%d",s[i],&l[i],&r[i]);++ind[l[i]],++ind[r[i]];}for(int i=1;i<=m;i++)if(!ind[i])q.push(i);val[1]=n;int u;while(!q.empty()){u=q.front();q.pop();ans[u]=val[u]&1;if(s[u][0]=='L'){val[l[u]]+=val[u]-(val[u]>>1);val[r[u]]+=val[u]>>1;}else{val[r[u]]+=val[u]-(val[u]>>1);val[l[u]]+=val[u]>>1;}if(--ind[l[u]]==0)q.push(l[u]);if(--ind[r[u]]==0)q.push(r[u]);}for(int i=1;i<=m;i++){if(ans[i])printf("%c",s[i][0]=='L'?'R':'L');elseprintf("%c",s[i][0]);}return 0;
}