UVALive 6953Digi Comp II（搜寻）

UVALive 6953Digi Comp II（搜索）

题意：

   m个开关，n个球。每个开关有两个状态，左或右，左则滚到左边，右则滚到右边。每滚一个球状态则反转一次。问最后每个开关的状态是怎样的。

解题：

  因为球数实在太多（10^18），一个一个模拟果断不行，而开关的最后状态只取决于滚过的球数和初始状态。故我决定n个球一起传，然而，因为有些节点可能后面才扫到，而它的子节点已经把球传下去了，没考虑到这一点，wa了一次。改了之后，因为递归重复过多，TLE了。又改成队列，RE了。又优化下，从下往上算，还是RE。最后，才知道，原来可以用in数组来记录每个节点的入度，只有当该节点入度减为0后，才把该节点push到队列。

坑点：

1.L,R可以相同，处理需注意。

2.入度为0的点，不只1一个。其他节点也可以入度为0。（这是有影响的哦！）

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;


bool status[500005],LR;
long long int amount[500005];
long long int n,x,y;
int m,a,b,lft[500005],rght[500005],tmp,in[500005],L,R;
char c;
queue <int> cal;
int main()
{
	while(~scanf("%lld%d",&n,&m))
	{
		memset(status,0,sizeof(status));
		memset(amount,0,sizeof(amount));
		memset(in,0,sizeof(in));
		memset(lft,0,sizeof(lft));
		memset(rght,0,sizeof(rght));
		getchar();
		amount[1]=n;
		for(int i=1;i<=m;i++)
		{
			scanf("%c %d %d",&c,&a,&b);
			getchar();
			lft[i]=a;
			rght[i]=b;
			if(c=='L')
				status[i]=1;
			in[a]++;
			in[b]++;
		}
		for(int i=1;i<=m;i++)
		{
			if(in[i]==0)
				cal.push(i);
		}
		while(!cal.empty())
		{
           tmp=cal.front();
		   cal.pop();
		   L=lft[tmp];
		   R=rght[tmp];
		   if(L||R)
		   {
		     x=(amount[tmp]+1)/2;
		     y=amount[tmp]-x;
		     if(status[tmp])
		     {
			   amount[L]+=x;
			   amount[R]+=y;
		     }
		     else
		     {
			   amount[L]+=y;
			   amount[R]+=x;
		     }
		     in[L]--;
		     in[R]--;
		   if(L==R)
		   {
			   if(L&&in[L]==0)
                 cal.push(L);
		   }
		   else
		   {
			   if(in[L]==0&&L)
		         cal.push(L);
		       if(in[R]==0&&R)
		         cal.push(R);
			}
		  }
		}
		for(int i=1;i<=m;i++)
		{
			if(amount[i]%2)status[i]=!status[i];
			if(status[i])printf("L");
			else printf("R");
		}
		printf("\n");
	}
	return 0;
}