luogu P1468 派对灯 Party Lamps
题目描述
在IOI98的节日宴会上,我们有N(10<=N<=100)盏彩色灯,他们分别从1到N被标上号码。 这些灯都连接到四个按钮:
按钮1:当按下此按钮,将改变所有的灯:本来亮着的灯就熄灭,本来是关着的灯被点亮。
按钮2:当按下此按钮,将改变所有奇数号的灯。
按钮3:当按下此按钮,将改变所有偶数号的灯。
按钮4:当按下此按钮,将改变所有序号是3*K+1(K>=0)的灯。例如:1,4,7...
一个计数器C记录按钮被按下的次数。当宴会开始,所有的灯都亮着,此时计数器C为0。
你将得到计数器C(0<=C<=10000)上的数值和经过若干操作后某些灯的状态。写一个程序去找出所有灯最后可能的与所给出信息相符的状态,并且没有重复。
输入输出格式
输入格式:
不会有灯会在输入中出现两次。
第一行: N。
第二行: C最后显示的数值。
第三行: 最后亮着的灯,用一个空格分开,以-1为结束。
第四行: 最后关着的灯,用一个空格分开,以-1为结束。
输出格式:
每一行是所有灯可能的最后状态(没有重复)。每一行有N个字符,第1个字符表示1号灯,最后一个字符表示N号灯。0表示关闭,1表示亮着。这些行必须从小到大排列(看作是二进制数)。
如果没有可能的状态,则输出一行'IMPOSSIBLE'。
输入输出样例
10
1
-1
7 -1
0000000000
0101010101
0110110110
说明
在这个样例中,有三种可能的状态:
所有灯都关着
1,4,7,10号灯关着,2,3,5,6,8,9亮着。
1,3,5,7,9号灯关着,2, 4, 6, 8, 10亮着。
翻译来自NOCOW
USACO 2.2
所有按钮按两次 和 1.2.3三个按钮间的关系之后是和没按一样的 所以实际只有8种情况,所以在cnt=1时 实际只有按1 或2 或 3 或 4四种情况 在cnt=2时 除只按按钮4之外 其余情况均可实现
而当c>2时 都可利用c=1 and c=2 时得出,所以可实现所有情况
利用异或实现操作
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std; const int C1[]={,,,};
const int C2[]={,,,,,,};
const int how[][]={
,,,,,,,//不按
,,,,,,,//按 2.4
,,,,,,,//按 3
,,,,,,,//按 1.4
,,,,,,,//按 4
,,,,,,,//按 2
,,,,,,,//按 3.4
,,,,,,}; int N,C;
int Light[];
bool tmp [];
int cntl,cntc;
int li[];
int lc[];
bool can,now[]={,,,,,,}; void open(int n)
{
for(int i=;i<;i++)
tmp[i]^=how[n][i];
}
void work(int step)
{
int cnt;
if(step==) cnt=;
else if(step==) cnt=;
else cnt=;
for(int i=cnt;i>=;i--)
{
memset(tmp,,sizeof(tmp));
if(cnt==)
open(C1[i]);
else if(cnt==)
open(C2[i]);
else
open(i);
bool note=;
for(int i=;i<=cntl;i++)
if(tmp[(li[i]-)%+]==)
{
note=;break;
}
for(int i=;i<=cntc;i++)
if(tmp[(lc[i]-)%+]==)
{
note=;break;
}
if(note)
{
for(int i=;i<=N;i++)
printf("%d",tmp[(i-)%+]);
printf("\n");
can=;
}
} }
int main()
{
scanf("%d",&N);
scanf("%d",&C);
int c;
while()
{
scanf("%d",&c);
if(c==-)break;
li[++cntl]=c;
}
while()
{
scanf("%d",&c);
if(c==-)break;
lc[++cntc]=c;
}
if(C==)
{
if(cntc)
puts("IMPOSSIBLE");
else
for(int i=;i<=N;i++)
printf("%d",);
return ;
}
work(C);
if(!can)
puts("IMPOSSIBLE");
return ;
}
最新文章
- 安装完ActivePython后Python的Idle窗口打不开也卸载不掉的解决方法
- [LeetCode] Jump Game II(贪婪算法)
- HDU 4614 Vases and Flowers (2013多校2 1004 线段树)
- BZOJ_1036_[ZJOI2008]_树的统计Conut_(树链剖分)
- 话谈c#拷贝
- MVC3+EF4.1学习系列(十)----MVC+EF处理树形结构
- 测者的性能测试手册:快速安装LoadRunner Linux上的Generator
- Docker 安装 MySQL
- day44前端开发2之css基础
- linux 网络管理的三种方式
- gnuplot画折线图
- mysql优化的21条经验(转)
- WINDOWS 下设置单独的java环境
- day 61 pymysql
- POJ 2653 - Pick-up sticks - [枚举+判断线段相交]
- SQL server2008零基础学习
- JSON字符串转换成对象时候 需要有默认构造器 因为这是通过反射创建的 反射是先通过默认构造器创建对象的
- resultMap结果集映射
- Pascal ASCII和文本的转换
- Could not automatically select an Xcode project
热门文章
- 孤荷凌寒自学python第三十九天python 的线程锁Lock
- 孤荷凌寒自学python那些事第一天
- leetcode 174. 地下城游戏 解题报告
- 爬虫:Scrapy11 - Logging
- PHP面向对象 封装与继承
- 【bzoj1927】[Sdoi2010]星际竞速 有上下界费用流
- [SDOI2015][bzoj4518] 征途 [斜率优化dp]
- firefox解决flash崩溃
- linux mint 自动挂载windows的D盘和E盘
- 汕头市队赛 SRM 07 C 整洁的麻将桌