USACO - 2.2.4 - Party Lamps

 

原创文章转载请注明出处

摘要：枚举，三星

一. 题目翻译

1. 描述：

在IOI98的节日宴会上，我们有N(10<=N<=100)盏彩色灯，他们分别从1到N被标上号码。 这些灯都连接到四个按钮：

一个计数器C记录按钮被按下的次数。当宴会开始，所有的灯都亮着，此时计数器C为0。

你将得到计数器C(0<=C<=10000)上的数值和经过若干操作后某些灯的状态。写一个程序去找出所有灯最后可能的与所给出信息相符的状态，并且没有重复。

 

2. 格式：

          INPUT FORMAT:

          (file lamps.in)

          不会有灯会在输入中出现两次。

          第一行: N。

          第二行: C最后显示的数值。

          第三行: 最后亮着的灯,用一个空格分开，以-1为结束。

          第四行: 最后关着的灯,用一个空格分开，以-1为结束。

          OUTPUT FORMAT:

          (file lamps.out)

          每一行是所有灯可能的最后状态(没有重复)。每一行有N个字符，第1个字符表示1号灯，最后一个字符表示N号灯。0表示关闭，1表示亮着。这些行必须从小到大排列（看作是二进制数）。

          如果没有可能的状态，则输出一行'IMPOSSIBLE'。

3. SAMPLE：

          SAMPLE INPUT:

10

1

-1

7 -1

          SAMPLE OUTPUT:

0000000000

0101010101

0110110110

在这个样例中，有三种可能的状态：

所有灯都关着

1,4,7,10号灯关着，2,3,5,6,8,9亮着。

1,3,5,7,9号灯关着，2, 4, 6, 8, 10亮着。

          

二.  题解

1. 题意理解（将问题分析清楚，大致用什么思路）：

这道题目还是暴力枚举，开关按两次以后等于没有按。如果同时按了偶数和奇数按钮等于按了一号按钮，按了一号和偶数等于按了奇数按钮，按了一号和奇数按钮等于按了偶数按钮。

那么无论怎么枚举按钮只可能出现以下8种情况：1.什么都没有按；2.只按了一号按钮；3.只按了奇数按钮；4.只按了偶数按钮；5.只按了3*k+1按钮；6.同时按了一号按钮和3*k+1按钮；7.同时按了奇数按钮和3*k+1按钮；8.同时按了偶数按钮和3*k+1按钮

由于只有以上的8种状态，现在难点就在于如何将这些状态与cnt（按了几次）对应起来。

 分析后，我们可以对cnt做如下分类：1. cnt ==0 ;2.cnt ==1；3.cnt==2 ；4.cnt==3；5.cnt>=4，并且cnt为偶数 ;6.cnt>4，并且cnt为奇数

cnt的前四种情况都比较简单，可以直接模拟出。现在讨论第5种和第6种情况，第5种情况等价于cnt==4的情况（因为最多有四个开关，所以cnt>4的时候一定可以找到两个开关作用两两相消除），第6种情况等价于cnt==3（原理同上）。

按照上面说明的情况，我们只需要对输入的cnt进行判断的，然后将该情况可能产生的亮灯状态与输入的开关灯状态比较，如果满足则输出。

 

2. 具体实现（具体实现过程中出现的问题）：

其他请参考代码注释。

3. 需要注意的细节：

输出要求按照一定的顺序，我们再向zero、one、two这些数组中添加可能亮灯状态时需要按照输出要求的顺序添加，这里要注意一下。

三.  代码

/*
ID:fightin1
LANG:JAVA
TASK:lamps
*/

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Scanner;

public class lamps {
	
	
	public static void main(String[] args) {
		try {
//			Scanner in = new Scanner(System.in);
//			PrintWriter pw = new PrintWriter(System.out);
			Scanner in = new Scanner(new BufferedReader(new FileReader(
			"lamps.in")));
			PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter(
			"lamps.out")));
			int n = in.nextInt();
			int cnt = in.nextInt();
			int[] on = new int[n+1];
			int oncnt = 0;
			for (int a=in.nextInt(),j=1;a!=-1;a=in.nextInt()){
				on[j++] = a;
				oncnt ++;
			}
			int[] off = new int[n+1];
			int offcnt = 0;
			for (int a=in.nextInt(),j=1;a!=-1;a=in.nextInt()){
				off[j++] = a;
				offcnt ++;
			}

			HashSet<Integer> onInit = new HashSet<Integer>(); //000000

			HashSet<Integer> onAll = new HashSet<Integer>();  
			HashSet<Integer> onOdd = new HashSet<Integer>();
			HashSet<Integer> onEven = new HashSet<Integer>();
			HashSet<Integer> on3 = new HashSet<Integer>();

			HashSet<Integer> onSame = new HashSet<Integer>();
			HashSet<Integer> on3All = new HashSet<Integer>();
			HashSet<Integer> on3Odd = new HashSet<Integer>();
			HashSet<Integer> on3Even = new HashSet<Integer>();
			
			
			for (int i=1;i<n+1;i++){
				onAll.add(i);
				if (i%2 == 0){
					onEven.add(i);
					on3Even.add(i);
				} else {
					onOdd.add(i);
					on3Odd.add(i);
				}
				if ((i-1)%3 == 0){
					on3.add(i);
					on3Odd.add(i);
					on3Even.add(i);
					if (i%2 == 0){
						on3Even.remove(i);
					} else {
						on3Odd.remove(i);
					}
				} else {
					on3All.add(i);
				}
			}

			ArrayList<HashSet<Integer>> zero = new ArrayList<HashSet<Integer>>();
			zero.add(new HashSet<Integer>());

			ArrayList<HashSet<Integer>> one = new ArrayList<HashSet<Integer>>();
			one.add(onAll);
			one.add(onOdd);
			one.add(on3);
			one.add(onEven);

			ArrayList<HashSet<Integer>> two = new ArrayList<HashSet<Integer>>();
			two.add(onAll);
			two.add(onOdd);
			two.add(on3Even);
			two.add(on3All);
			two.add(onEven);
			two.add(on3Odd);
			two.add(onSame);

			ArrayList<HashSet<Integer>> three = new ArrayList<HashSet<Integer>>();
			three.add(onAll);
			three.add(on3Even);
			three.add(onOdd);
			three.add(on3);
			three.add(onEven);
			three.add(on3Odd);
			

			ArrayList<HashSet<Integer>> fourEven = new ArrayList<HashSet<Integer>>();
			fourEven.add(onAll);
			fourEven.add(on3Even);
			fourEven.add(onOdd);
			fourEven.add(on3);
			fourEven.add(on3All);
			fourEven.add(onEven);
			fourEven.add(on3Odd);
			fourEven.add(onSame);
			

			ArrayList<HashSet<Integer>> fourOdd = three;
			
			ArrayList<HashSet<Integer>> result = new ArrayList<HashSet<Integer>>();
			ArrayList<HashSet<Integer>> temp;
			if (cnt == 0){
				temp = zero;
			} else if (cnt == 1){
				temp = one;
			} else if (cnt == 2){
				temp = two;
			} else if (cnt == 3){
				temp = three;
			} else if ((cnt-4)%2==1){
				temp = fourOdd;
			} else {
				temp = fourEven;
			}
			for (int i=0;i<temp.size();i++){
				HashSet<Integer> tempReslut = temp.get(i);
				boolean found = true;
				for (int j=1;j<=oncnt;j++){
					if (tempReslut.contains(on[j])){
						found = false;
						break;
					} 
				}
				for (int j=1;j<=offcnt&&found;j++){
					if (!tempReslut.contains(off[j])){
						found = false;
						break;
					}
				}
				if(found){
					result.add(tempReslut);
				}
			}
			
//			if (cnt != 0)	
//			{	if (cnt%2 == 0){
//					for (int i=0;i<even.size();i++){
//						HashSet<Integer> temp = even.get(i);
//						boolean found = true;
//						for (int j=1;j<=oncnt;j++){
//							if (temp.contains(on[j])){
//								found = false;
//								break;
//							} 
//						}
//						for (int j=1;j<=offcnt&&found;j++){
//							if (!temp.contains(off[j])){
//								found = false;
//								break;
//							}
//						}
//						if(found){
//							result.add(temp);
//						}
//					}
//				}else {
//					for (int i=0;i<odd.size();i++){
//						HashSet<Integer> temp = odd.get(i);
//						boolean found = true;
//						for (int j=1;j<=oncnt;j++){
//							if (temp.contains(on[j])){
//								found = false;
//								break;
//							} 
//						}
//						for (int j=1;j<=offcnt&&found;j++){
//							if (!temp.contains(off[j])){
//								found = false;
//								break;
//							}
//						}
//						if(found){
//							result.add(temp);
//						}
//					}
//				}
//			}else {
//				HashSet<Integer> temp = onInit;
//				boolean found = true;
//				for (int j=1;j<=oncnt;j++){
//					if (temp.contains(on[j])){
//						found = false;
//						break;
//					} 
//				}
//				for (int j=1;j<=offcnt&&found;j++){
//					if (!temp.contains(off[j])){
//						found = false;
//						break;
//					}
//				}
//				if(found){
//					result.add(temp);
//				}
//			}
			
			if (result.size() ==0){
				pw.println("IMPOSSIBLE");
			} else {
				for (int i=0;i<result.size();i++){
					HashSet<Integer> tempPrint = result.get(i);
					for (int j=1;j<n+1;j++){
						if(tempPrint.contains(j)){
							pw.print(0);
						}else {
							pw.print(1);
						}
					}
					pw.println();
				}
			}
			
			pw.close();
		} catch (Exception e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		
	}
}