思维题 找规律分类讨论
如果不找规律暴力枚举的话存在2^100的复杂度
对于这种按灯题目大概率都存在以下规律
1.按两次等于没按可以抵消
2.某个灯的状态与按灯顺序无关,只取决于按灯方案对灯状态改变的次数
由以上规律我们可以知道,按灯方案最终可以被简化成 最多按了4次,且每次各不相同
(否则会存在可以自身相互抵消的两个按键操作)
本题由于按键特殊可以发现1+3——>2 1+2——>3 2+3——>1
那么最终方案又可以被简化成 最多按了3次,且如果按了两次其中一次一定存在4
至此,我们的方案的枚举复杂度就降至了2^3——>8
通过枚举这8中方案就能找到所有可能出现的灯的状态,然后通过与一直条件进行相容性判断
如果不符合数据要求,则说明不能是该状态.
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int state[8][6]={
{1,1,1,1,1,1}, //0 都不按
{0,0,0,0,0,0}, //1 只按1
{1,0,1,0,1,0}, //2 只按2
{0,1,0,1,0,1}, //3 只按3
{0,1,1,0,1,1}, //4 只按4
{1,0,0,1,0,0}, //5 1与4(与顺序无关先按4或者先按1都无所谓)
{0,0,1,1,1,0}, //6 2与4
{1,1,0,0,0,1} //7 3与4
};
vector<int> on;
vector<int> off;
int n,c;
bool cmp(int a,int b)
{
for(int i=0;i<6;i++)
{
if(state[a][i]!=state[b][i])
return state[a][i]<state[b][i];
}
return false;
}
bool check(int s[6])
{
for(int i=0;i<on.size();i++)
{
int t=on[i];
if(!s[t%6]) return false;
}
for(int i=0;i<off.size();i++)
{
int t=off[i];
if(s[t%6]) return false;
}
return true;
}
void work(vector<int> ids)
{
sort(ids.begin(),ids.end(),cmp);
bool flag=false;
for(int i=0;i<ids.size();i++)
{
auto t=state[ids[i]];
if(check(t))
{
flag=true;
for(int i=0;i<n;i++) cout<<t[i%6];
cout<<endl;
}
}
if(!flag) cout<<"IMPOSSIBLE"<<endl;
}
int main()
{
cin>>n>>c;
int x;
while(cin>>x,x!=-1) on.push_back(x-1);//输入的坐标从1~n为了方便%操作,将坐标映射到0~n-1
while(cin>>x,x!=-1) off.push_back(x-1);
if(c==0) work({0});
else if(c==1) work({1,2,3,4});
else if(c==2) work({0,1,2,3,5,6,7});
else work({0,1,2,3,4,5,6,7});
}