现在有这些按钮:
- 按钮 \(1\):当按下此按钮,将改变所有的灯:本来亮着的灯就熄灭,本来是关着的灯被点亮;
- 按钮 \(2\):当按下此按钮,将改变所有奇数号的灯;
- 按钮 \(3\):当按下此按钮,将改变所有偶数号的灯;
- 按钮 \(4\):当按下此按钮,将改变所有序号是 \(3k+1 \ (k \in [0,+\infty) \cap \mathbb Z)\) 的灯。例如:\(1,4,7,10 \dots\)。
同时告诉你 \(n\) 的大小,以及按按钮的次数 \(c\) 和某些点的状态,求最后有几种情况。
题解
注意到只有 \(0,1\) 两种状态,考虑使用 \(bitset\)。
bitset
可以看作是一个二进制数,且支持以下几种操作:
reset()
清零一个 \(bitset\),及将其中每一位设置为 \(0\)。
set()
将 \(bitset\) 的每一位设置为 \(1\)。
test(i)
返回 \(bitset\) 内第 \(i\) 位的值(从零开始,其实像数组一样直接用下标访问也可以)
any()
返回 \(bitset\) 内是否有元素的值为 \(1\)。
none()
与any()
相对,如果元素全部为 \(0\) 则返回 \(1\),否则返回 \(0\)。
count()
计算 \(bitset\) 内元素值为 \(1\) 的元素个数(求 \(0\) 的个数直接用长度减去它就好了)。
flip()
将 \(bitset\) 内的所有元素翻转,相当于按位取反(也就是 \(\sim\))。
好的以上就是 \(bitset\) 的所有操作。
\(bitset\) 的每一位只占一个 \(bit\),空间比桶更优。
实现所有按钮
现在让我们回到题目,根据题意以下就是所有按钮的实现:
点击查看代码
bitset<100> bottom1(bitset<100> b){b.flip();return b;
}
bitset<100> bottom2(bitset<100> b){for(int i=1;i<=n;i+=2){b.flip(i-1);}return b;
}
bitset<100> bottom3(bitset<100> b){for(int i=2;i<=n;i+=2){b.flip(i-1);}return b;
}
bitset<100> bottom4(bitset<100> b){for(int i=0;3*i+1<=n;i++){b.flip(3*i);}return b;
}
为了判定最后的结果是否符合要求,我们需要下面这个函数,而答案要从小到大排序,我们还需要一个大小比较函数(\(bitset\) 不能直接比较):
点击查看代码
bool cmp(bitset<100> A , bitset<100> B){for(int i=0;i<100;i++){if(A[i]<B[i])return true;if(A[i]>B[i])return false;}return false;
}
bool check(bitset<100> tmp){for(int i=0;i<n;i++){if(tmp[i]==0&&light[i+1]==1)return false;if(tmp[i]==1&&light[i+1]==-1)return false;}return true;
}
每个按钮的性质
注意到任意一个按钮按两次就相当于没按,白白浪费了两次按按钮的机会(看作总共 \(c\) 次)。
手玩一下(假设总共 \(10\) 个灯,操作序列:\(bottom1,bottom2,bottom1\)):
初始状态:1111111111
bottom1:0000000000
bottom2:1010101010
bottom1:0101010101
而把两个 \(bottom1\) 抵消之后的操作:
初始状态:1111111111
bottom2:0101010101
结果完全一致,证明的我们的假设是对的。
解法
现在就很好解了,列出每个按钮最多一次的所有可能操作序列,然后判断 \(c\) 减去这个次数是否为 \(2\) 的倍数,如果可以,说明这个有可能是答案之一。
主函数部分:
点击查看代码
if(c%2==0){if(check(first))ans[++len] = first;}if(c>=1&&(c-1)%2==0){if(check(bottom1(first)))ans[++len] = bottom1(first);if(check(bottom2(first)))ans[++len] = bottom2(first);if(check(bottom3(first)))ans[++len] = bottom3(first);if(check(bottom4(first)))ans[++len] = bottom4(first);}if(c>=2&&(c-2)%2==0){if(check(bottom1(bottom2(first))))ans[++len] = bottom1(bottom2(first));if(check(bottom1(bottom3(first))))ans[++len] = bottom1(bottom3(first));if(check(bottom1(bottom4(first))))ans[++len] = bottom1(bottom4(first));if(check(bottom2(bottom3(first))))ans[++len] = bottom2(bottom3(first));if(check(bottom2(bottom4(first))))ans[++len] = bottom2(bottom4(first));if(check(bottom3(bottom4(first))))ans[++len] = bottom3(bottom4(first));}if(c>=3&&(c-3)%2==0){if(check(bottom1(bottom2(bottom3(first)))))ans[++len] = bottom1(bottom2(bottom3(first)));if(check(bottom1(bottom2(bottom4(first)))))ans[++len] = bottom1(bottom2(bottom4(first)));if(check(bottom1(bottom3(bottom4(first)))))ans[++len] = bottom1(bottom3(bottom4(first)));if(check(bottom2(bottom3(bottom4(first)))))ans[++len] = bottom2(bottom3(bottom4(first)));}if(c>=4&&(c-4)%2==0){if(check(bottom1(bottom2(bottom3(bottom4(first))))))ans[++len] = bottom1(bottom2(bottom3(bottom4(first))));}sort(ans+1,ans+len+1,cmp);for(int i=1;i<=len;i++){for(int j=0;j<n;j++)cout << ans[i][j];cout << "\n";}if(len==0)cout << "IMPOSSIBLE";