P1468 派对灯 Party Lamps
我们来分析一下对灯的操作
1.对所有灯的,这时吧所有灯看成一个整体
2.奇偶数的操作,这时可以把每两个数看成一个循环节
3.对3X+ 1的操作,这时可以把每三个数看成一个循环节
显而易见的,我们把序列看成6个一组的循环节,便能模拟整个序列。
用笔画一下,我们发现将这个含六个元素的序列进行变换最终只会有八种结果,那么我们只需要判断一下最后这八种结果
最后是否符合题意要求就行了(至于他是怎么变换的我们不用管)
以上就是在题解区找到的解释,其实说得很好,希望原作者 fastle 见谅。
#include<bits/stdc++.h>
using namespace std;
const int N = 1e3+;
int One[N],Zero[N],cnt1,cnt2;
int n,C;
int a[N][];
string S[];
char s[N];
void Init(){
for(int i=;i<N;i++){
for(int j=;j<=;j++){
a[i][j] = ;
}
}
}
inline bool check( int No ){
int cnt = ;
for(int i=;i<;i++){
if( (No & (<<i)) == (<<i) )
cnt++;
}
bool F = (cnt<=C) ;
for(int i=;i<cnt1;i++){
if( a[One[i]][No] != ) F = false;
}
for(int i=;i<cnt2;i++){
if( a[Zero[i]][No] != ) F = false;
}
return F;
}
int main()
{
ios_base :: sync_with_stdio();
cin.tie(NULL) , cout.tie(NULL);
Init();
cin>>n>>C;
while( cin>>One[cnt1++] ){
if(One[cnt1-]==-){
cnt1--; break;
}
}
while( cin>>Zero[cnt2++] ){
if(Zero[cnt2-]==-){
cnt2--; break;
}
}
/*
for(int i=0;i<cnt1;i++){
printf("%d%c",One[i],i==cnt1-1?'\n':' ');
}
for(int i=0;i<cnt2;i++){
printf("%d%c",Zero[i],i==cnt2-1?'\n':' ');
}
*/
for(int i=;i<=;i++){
if( i & ){
for(int j=;j<=n;j++){
a[j][i] = a[j][i] ^ ;
}
}
if( (i>>) & ){
for(int j=;j<=n;j+=){
a[j][i] = a[j][i] ^ ;
}
}
if( (i>>) & ){
for(int j=;j<=n;j+=){
a[j][i] = a[j][i] ^ ;
}
}
if( (i>>) & ){
for(int j=;j<=n;j+=){
a[j][i] = a[j][i] ^ ;
}
}
}
int cnt = ; for(int j=;j<=;j++){
if( check(j) ) {
for(int i = ; i <= n; i++){
s[i-] = a[i][j] + '';
}
s[n] = '\0';
S[cnt++] = s;
}
}
if( cnt == ){
cout<<"IMPOSSIBLE"<<endl;
}else{
sort(S,S+cnt);
cnt = unique(S,S+cnt)-S;
for(int i = ; i < cnt ; i++ ){
cout<<S[i]<<endl;
}
}
return ;
}