关键词：
题目描述
在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[4]={2,4,5,7}; const int C2[7]={0,1,2,3,5,6,7}; const int how[8][7]={ 0,0,0,0,0,0,0,//不按 0,0,0,1,1,1,0,//按 2.4 0,0,1,0,1,0,1,//按 3 0,0,1,1,0,1,1,//按 1.4 0,1,0,0,1,0,0,//按 4 0,1,0,1,0,1,0,//按 2 0,1,1,0,0,0,1,//按 3.4 0,1,1,1,1,1,1}; int N,C; int Light[102]; bool tmp [102]; int cntl,cntc; int li[102]; int lc[102]; bool can,now[7]={1,1,1,1,1,1,1}; void open(int n) { for(int i=1;i<7;i++) tmp[i]^=how[n][i]; } void work(int step) { int cnt; if(step==1) cnt=3; else if(step==2) cnt=6; else cnt=7; for(int i=cnt;i>=0;i--) { memset(tmp,1,sizeof(tmp)); if(cnt==3) open(C1[i]); else if(cnt==6) open(C2[i]); else open(i); bool note=1; for(int i=1;i<=cntl;i++) if(tmp[(li[i]-1)%6+1]==0) { note=0;break; } for(int i=1;i<=cntc;i++) if(tmp[(lc[i]-1)%6+1]==1) { note=0;break; } if(note) { for(int i=1;i<=N;i++) printf("%d",tmp[(i-1)%6+1]); printf(" "); can=1; } } } int main() { scanf("%d",&N); scanf("%d",&C); int c; while(11101001) { scanf("%d",&c); if(c==-1)break; li[++cntl]=c; } while(1010011010) { scanf("%d",&c); if(c==-1)break; lc[++cntc]=c; } if(C==0) { if(cntc) puts("IMPOSSIBLE"); else for(int i=1;i<=N;i++) printf("%d",1); return 0; } work(C); if(!can) puts("IMPOSSIBLE"); return 0; }
usaco2.2partylamps
四种开关，n盏灯，1：改变所有灯状态，2：改变奇数灯状态，3：改变偶数灯状态，4：改变3k+1灯状态给你按开关的总次数c和部分灯限制条件（开或关），一开始都是开着的。（$cleq10000,nleq100$）我直接考虑每个开关按了奇数次或... 查看详情
usaco2.2partylamps高能等效+规律枚举
题在这：https://www.luogu.org/problem/show?pid=1468#sub按钮1：当按下此按钮，将改变所有的灯：本来亮着的灯就熄灭，本来是关着的灯被点亮。按钮2：当按下此按钮，将改变所有奇数号的灯。按钮3：当按下此按钮，将改变所有偶数号的... 查看详情
luogup1821[usaco07feb]银牛派对silvercowparty
P1821[USACO07FEB]银牛派对SilverCowParty题目描述OnecowfromeachofNfarms(1≤N≤1000)convenientlynumbered1..Nisgoingtoattendthebigcowpartytobeheldatfarm#X(1≤X≤N).AtotalofM(1≤M≤100,000)unidirection 查看详情
luogup1821[usaco07feb]银牛派对silvercowparty
题目描述OnecowfromeachofNfarms(1≤N≤1000)convenientlynumbered1..Nisgoingtoattendthebigcowpartytobeheldatfarm#X(1≤X≤N).AtotalofM(1≤M≤100,000)unidirectional(one-wayroadsconnectspairsoffarms 查看详情
usaco2.2.4生日派对灯（最近写题碰到的，虽然知道现在写这个有点晚了）
经过分析，他看似很多的开灯的方法其实合并起来就只有八个。首先，一个开关在执行的时候只能按一次（因为你就算按了两次就相当于一次也没有按）。当一个都不按的时候 当然就只有一种：不按。当按一下的时候：很明... 查看详情
题解$luogup2962$-双向广搜-异或高斯消元(代码片段)
luoguP2962题目描述节日宴会上,我们有(N)盏彩色灯,他们分别从(1)到(N)被标上号码。有(M)条边连接着这些灯,当按下某一盏灯的开关的时候,这盏灯本身以及所有和这盏灯有边相连的灯的开关状态都会发生改变。最开始所有灯都是被关... 查看详情
luogup2622关灯问题ii(代码片段)
luogup2622关灯问题II题目描述现有n盏灯，以及m个按钮。每个按钮可以同时控制这n盏灯——按下了第i个按钮，对于所有的灯都有一个效果。按下i按钮对于第j盏灯，是下面3中效果之一：如果a[i][j]为1，那么当这盏灯开了的时候，把... 查看详情
bzoj1468:tree
Description真·树,问距离不大于(k)的点对个数.Sol点分治.同上.Code/**************************************************************Problem:1468User:BeiYuLanguage:C++Result:AcceptedTime:832msMemory:3804kb************ 查看详情
[bzoj1468]tree
传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=1468TreeTimeLimit: 10Sec MemoryLimit: 64MBSubmit: 1517 Solved: 812[Submit][Status][Discuss]Description给你一棵 查看详情
luogup1663山二分答案/实数域bycellur925(代码片段)
题目传送门现在要在山上的某个部位装一盏灯，使得这座山的任何一个部位都能够被看到。给出最小的y坐标，如图的+号处就是y坐标最小的安装灯的地方。 这个题嘛...今年省选前学姐来我们（破烂）的机房串门的时候提到了... 查看详情
bzoj1468tree(点分治模板)
1468:TreeTimeLimit: 10Sec MemoryLimit: 64MBSubmit: 1527 Solved: 818[Submit][Status][Discuss]Description给你一棵TREE,以及这棵树上边的距离.问有多少对点它们两者间的距离小于等于KInputN（n&l 查看详情
[bzoj1468]tree
[BZOJ1468]Tree试题描述给你一棵TREE,以及这棵树上边的距离.问有多少对点它们两者间的距离小于等于K输入N（n<=40000）接下来n-1行边描述管道，按照题目中写的输入接下来是k输出一行，有多少对点之间的距离小于等于k输入示例7161... 查看详情
[joyoi1468]清理垃圾-dp
题目限制时间限制内存限制评测方式题目来源1000ms131072KiB标准比较器Local题目背景聚会结束，留下许多垃圾。Candy：“好多垃圾啊，飘飘乎居士，我们一起处理垃圾吧！”题目描述 Candy家里总共有n个垃圾等... 查看详情
[luogup1220]关路灯（dp）
传送门 如果去关某一个灯，那么途中经过的灯都能关闭，那么就是连续一段区间，区间DP。f[i][j][0]表示关完i,j这个区间且在i这个位置f[i][j][1]表示关完i,j这个区间且在j这个位置 代码#include<cstdio>#include<cstring>#inclu... 查看详情
bzoj.1468.tree(点分治)
题目链接BZOJ1468POJ1741题意:计算树上距离<=K的点对数我们知道树上一条路径要么经过根节点，要么在同一棵子树中。于是对一个点x我们可以这样统计:计算出所有点到它的距离dep[]，排序后可以O(n)求得<=K的点对数量。但画个图... 查看详情
[bzoj1468][poj1741]tree
[BZOJ1468][POJ1741]Tree <题意概括>给定一棵树,求有多少对满足两两距离不超过k的点对(u,v) <做法>典型的点分治题目找出当前树的重心计算该顶点到其子树中每个顶点的路径长度使用双指针法统计满足条件的路径条数... 查看详情
[bzoj1468][poj1741]tree_点分治
Treebzoj-1468poj-1741 题目大意：给你一颗n个点的树，求树上所有路径边权和不大于m的路径条数。 注释：$1\len\le4\cdot10^4$，$1\lem\le10^9$。 想法：GXZlegend给高一将点分治，去听了之后的第一道模板题。 ... 查看详情
bzoj1468:tree点分治
十分巧妙的一种数据结构Code:#include<bits/stdc++.h>#defineN400010#definesetIO(s)freopen(s".in","r",stdin)usingnamespacestd;intto[N<<1],head[N<<1],nex[N<<1],val[N<<1];intf[N],root,m,d 查看详情