首页 > ACM题库 > HDU-杭电 > HDU 2828-Lamp-线段树-[解题报告]HOJ
2014
02-17

HDU 2828-Lamp-线段树-[解题报告]HOJ

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;
}

 

解题参考:http://blog.csdn.net/aledavvv/article/details/7837076


  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
    会陷入死循环