Switches（暴力模拟题）

admin管理员组

文章数量:1582725

Switches

题目描述
In the control panel of an enormous amphitheatre, there are N switches, numbered from 1 to N, that control the M light bulbs of the place, which are numbered from 1 to M. Note that the number of switches and light bulbs is not necessarily the same and this happens because each switch is associated not to a single light bulb, but to a set of light bulbs. When a switch is activated, each one of the bulbs associated to it is toggled. If the bulb is lit, then it will be switched off, otherwise it will be switched on.

Some bulbs are lit initially and the janitor in charge of the amphitheatre has to switch off all them. He started trying to press the switches randomly, but as soon as he figured out that it wouldn’t necessarily work, he decided to follow a fixed strategy. He will trigger the switches 1,2,3,…,N,1,2,3,… in other words, every time after triggering the switch number N, he resumes the procedure from the switch number 1. He intends to keep pressing switches by the given strategy until all bulbs are switched off at the same time (in that moment he stops pressing the switches). Will his strategy work?

Given the bulbs which are initially lit and the sets of lamps associated to each switch, your program should compute the number of times the janitor will press switches. If by following the given strategy the janitor is never able to switch off all the lamps at the same time, your program should print -1.
输入
The first line contains two integers N and M (1≤N,M≤1000) representing, respectively, the number of switches and the number of light bulbs. The second line contains an integer L (1≤L≤M) followed by distinct integers Xi (1≤Xi≤M), representing the bulbs that are lit in the first place. Each of the following N rows contains an integer Ki (1≤Ki≤M) followed by Ki distinct integers Yi (1≤Yi≤M), representing the bulbs attached to switch i (1≤i≤N).
输出
Your program must print a single line containing an integer representing the number of times the janitor will press the switches by following the strategy described, until all the lights were off at the same time. If that never happens, print -1.
样例输入
6 3
2 1 3
3 1 2 3
2 1 3
2 1 2
2 2 3
1 2
3 1 2 3
样例输出
5

题意：
样例解读：给你6个开关，3个灯泡
第一行 2个灯亮着 即1号灯和3号灯亮着
借来六行，代表从1到6这六个开关分别可以控制的灯
3 1 2 3，代表1号开关，可以同时控制三个灯 1 2 3号
以此类推…
每按下一个开关，亮着的灯会灭，灭的灯会亮，问知道按多少次开关，可以让所有的灯熄灭，可以循环按。如果熄灭不掉，则输出-1.

思路：
直接模拟，用结构体存储，模拟亮不亮时用类似于桶排序的思想。

代码：

#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
int a[1010];
int n,m,l,ans=0;
struct node
{
	int id,ll;
	int c[1010];
}q[1010];
int fun(int u)
{
	for(int i=1;i<=q[u].ll;i++){
		if(a[q[u].c[i]]==0) a[q[u].c[i]]=1;
		else a[q[u].c[i]]=0;
	}
}
int main()
{
	cin>>n>>m;
	cin>>l;
	for(int i=1;i<=l;i++){
		int x;
		cin>>x;
		a[x]=1;
	}
	for(int i=1;i<=n;i++){
		cin>>q[i].ll;
		for(int j=1;j<=q[i].ll;j++) cin>>q[i].c[j];
	}
	int i=1;
	for(i=1;i<=n;i++){
		fun(i);ans++;
		int k=1;
		for(k=1;k<=m;k++){
			if(a[k]!=0) break;
		}
		if(k>m){
			cout<<ans;
			return 0;
		}
	}
	i=1;
	for(i=1;i<=n;i++){
		fun(i);ans++;
		int k=1;
		for(k=1;k<=m;k++){
			if(a[k]!=0) break;
		}
		if(k>m){
			cout<<ans;
			return 0;
		}
	}
	if(i>n){
		cout<<-1;
		return 0;
	}
	return 0;
}

本文标签： 模拟题暴力Switches