2014
02-17

Lamp

There are several switches and lamps in the room, however, the connections between them are very complicated. One lamp may be controlled by several switches, and one switch may controls at most two lamps. And what’s more, some connections are reversed by mistake, so it’s possible that some lamp is lighted when its corresponding switch is “OFF”!

To make things easier, we number all the lamps from 1 to N, and all the switches 1 to M. For each lamps, we give a list of switches controlling it. For example, for Lamp 1, the list is “1 ON 3 OFF 9 ON”, that means Lamp 1 will be lighted if the Switch 1 is at the “ON” state OR the Switch 3 is “OFF” OR the Switch 9 is “ON”.

Now you are requested to turn on or off the switches to make all the lamps lighted.

There are several test cases in the input. The first line of each test case contains N and M (1 <= N,M <= 500), then N lines follow, each indicating one lamp. Each line begins with a number K, indicating the number of switches controlling this lamp, then K pairs of “x ON” or “x OFF” follow.

There are several test cases in the input. The first line of each test case contains N and M (1 <= N,M <= 500), then N lines follow, each indicating one lamp. Each line begins with a number K, indicating the number of switches controlling this lamp, then K pairs of “x ON” or “x OFF” follow.

2 2
2 1 ON 2 ON
1 1 OFF
2 1
1 1 ON
1 1 OFF

OFF ON
-1

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>

int flag;
struct Node{
int a;
int b;
int num;
int val;
}tree[888888];

int pos[200005];
int val[200005];
int temp[200005];

void Buildtree(int i,int a,int b)
{
tree[i].a=a;
tree[i].b=b;
tree[i].num=b-a+1;
if(a==b)
return;
int mid=(a+b)>>1;
Buildtree(i<<1,a,mid);
Buildtree(i<<1|1,mid+1,b);
}

void update(int i,int pos,int val)
{
tree[i].num--;
if(tree[i].a==tree[i].b)
{
tree[i].val=val;
//	printf("i==%d__val==%d\n",i,tree[i].val);
return;
}
if(pos<tree[i<<1].num)
update(i<<1,pos,val);
else
update(i<<1|1,pos-tree[i<<1].num,val);
}

void getnum(int i)
{
if(tree[i].a==tree[i].b)
{
temp[flag++]=tree[i].val;
//printf("i===%d_____val===%d\n",i,tree[i].val);
return;
}
getnum(i<<1);
getnum(i<<1|1);
}

int main()
{
int N;
while(scanf("%d",&N)!=EOF)
{
Buildtree(1,1,N);
for(int i=1;i<=N;i++)
{
scanf("%d%d",&pos[i],&val[i]);
}
//	for(i=1;i<=10;i++)
//	{
//		printf("i==%d___a==%d___b=%d____num=%d___cal==%d\n",i,tree[i].a,tree[i].b,tree[i].num,tree[i].val);
//	}
for(i=N;i>0;i--)
{
update(1,pos[i],val[i]);
}
flag=0;
getnum(1);
for(i=0;i<N;i++)
{
printf(i==N-1?"%d\n":"%d ",temp[i]);
}
}
return 0;
}

1. 约瑟夫也用说这么长……很成熟的一个问题了，分治的方法解起来o(n)就可以了，有兴趣可以看看具体数学的第一章，关于约瑟夫问题推导出了一系列的结论，很漂亮

2. 有两个重复的话结果是正确的，但解法不够严谨，后面重复的覆盖掉前面的，由于题目数据限制也比较严，所以能提交通过。已更新算法

3. 题目需要求解的是最小值，而且没有考虑可能存在环，比如
0 0 0 0 0
1 1 1 1 0
1 0 0 0 0
1 0 1 0 1
1 0 0 0 0
会陷入死循环