http://poj.org/problem?id=1176
| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions: 4023 | Accepted: 1386 |
Description
1 to N. The lamps are connected to four buttons:
button 1 -- when this button is pressed, all the lamps change their state: those that are ON are turned OFF and those that are OFF are turned ON.
button 2 -- changes the state of all the odd numbered lamps.
button 3 -- changes the state of all the even numbered lamps.
button 4 -- changes the state of the lamps whose number is of the form 3K+1 (with K >= 0), i.e., 1,4,7,...
There is a counter C which records the total number of button presses.
When the party starts, all the lamps are ON and the counter C is set to zero.
You are given the value of counter C and information on the final state of some of the lamps. Write a program to determine all the possible final configurations of the N lamps that are consistent with the given information, without repetitions.
Input
The first line contains the number N and the second line the final value of counter C. The third line lists the lamp numbers you are informed to be ON in the final configuration, separated by one space and terminated by the integer -1. The fourth line lists the lamp numbers you are informed to be OFF in the final configuration, separated by one space and terminated by the integer -1.
The parameters N and C are constrained by:
10 <= N <= 100
1 <= C <= 10000
The number of lamps you are informed to be ON, in the final configuration, is less than or equal to 2.The number of lamps you are informed to be OFF, in the final configuration, is less than or equal to 2.
Output
Sample Input
10
1
-1
7 -1
Sample Output
0000000000
0101010101
0110110110
分析：
题意：对于一串彩灯，提供四种改变彩灯状态（ON<=>OFF）的操作：a.改变所有彩灯状态；b.改变奇数彩灯状态；c.改变偶数彩灯状态；d.改变3k+1号彩灯状态（1,4,7,10...）。
给定彩灯数目，操作次数，和对于某几个彩灯必须为ON、某几个彩灯必须为OFF的要求，问经过给定次数的操作，最终能达到的满足要求的状态有多少种，输出所有满足要求的彩灯状态。
原题中操作次数是1<=C<=10000的，如果以此为搜索深度，时间复杂度相当可观。
转换思路：
当按第一种操作时 ：奇偶全变
当按第二种操作时 ：奇数全变
当按第三种操作时 ：偶数全变
当按第四种操作时 ：3K + 1 全变（1 ， 4 ，7 ， 10 ， 13 ， 16 ， 。。。97 ，100）。
四种情况的最小公倍数为 8 ，即是周期为 8 ，打表可得：
string s[8]={
"0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000",
"1010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010",
"0101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101",
"0110110110110110110110110110110110110110110110110110110110110110110110110110110110110110110110110110",
"1001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001",
"1100011100011100011100011100011100011100011100011100011100011100011100011100011100011100011100011101",
"0011100011100011100011100011100011100011100011100011100011100011100011100011100011100011100011100011",
"1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111"
};
1，当只按键一次出现的状态有：1,2,3,4
2，当按键二次则出现的状态有：1,2,3,5,6,7,8
3，当按键三次或三次以上全部状态可以出现。
AC代码：
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int N,C;
int v1[],v2[];
int cmp(const void *a,const void *b)
{
if(*(string*)a>*(string*)b)
return ;
else return ;
} int main()
{
//freopen("input.txt","r",stdin);
string result[];
int temp,i,i1(),i2(),j,id();
string s[]={
"",
"",
"",
"",
"",
"",
"",
""
}; cin>>N>>C;
cin>>temp;
while(temp!=-)
{
v1[i1++]=temp-;
cin>>temp;
}
cin>>temp;
while(temp!=-)
{
v2[i2++]=temp-;
cin>>temp;
}
if(C==)
{
for(i=;i<N;i++)
cout<<s[][i];
cout<<endl;
}//c=0
else if(C>=)
{
for(i=;i<;i++)
{
if(i==)
{
if(C==) continue;
}
if(i== || i== || i== || i==)
{
if(C<) continue;
}
for(j=;j<i1;j++)
{
temp=v1[j];
if(s[i][temp]!='') break;
}
if(j==i1)
{
for(j=;j<i2;j++)
{
temp=v2[j];
if(s[i][temp]!='') break;
}
if(j==i2)
{
result[id]=s[i];
id++;
}
}
}//for
qsort(result,id,sizeof(string),cmp);
for(i=;i<id;i++)
{
for(j=;j<N;j++)
cout<<result[i][j];
cout<<endl;
}
}//if return ; }