自动搬运

查看原文

来自洛谷，原作者为

	Orzalpha 会的只会一点，不会的一点不会。

搬运于2025-08-24 21:25:25，当前版本为作者最后更新于2019-02-17 09:02:45，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

其实这道题掌握了规律就很简单。

规律如下：

规律一：对于任意c，总能转化为c≤2时的某种状态。

首先，给出公理。

公理1：按钮的顺序不决定状态。打个例子，12和21得到的状态是相同的。

公理2：同一个按钮按两次等于没按。打个例子，121与2得到的状态是相同的。

公理3：按钮123满足任意两个等于第三个。打个例子，12得到的状态与3是相同的。

通过以上三个公理，可以得到如下推论：

推论1：对于任意c＞4，所得到的状态总是与c≤4中的某种不重复序列的状态相同。证明：对于c＞4的按钮序列中，由抽屉原理得必然有一个按钮至少按了两次，就可以抵消掉。打个例子，12343→124。

推论2：对于任意2＜c≤4的不重复序列，所得到的状态总是与c≤2中的某种状态相同。证明：对于2＜c≤4的不重复序列，4出现的次数总是小于等于1，即至少有2个123中的按钮。由公理2与公理3得，任意2＜c≤4的不重复序列总是与c≤2的某种序列等效。打个例子，1234→114→4。

至此，我们可以得出最终的结论，即规律一：对于任意c，总能转化为c≤2时的某种状态。

规律二：当c≤2时，分别出现如下状态。

当c=0时，0；

当c=1时，1，2，3，4；

当c=2时，0，1(23)，2(13)，3(12)，14，24，34；

另外，由规律一，当c＞2时，有可能取到c≤2时的所有情况，即0，1，2，3，4，14，24，34。

规律三：无论哪种状态，循环节总为6。

因此，根据这三个规律，就可以用常量表存出所有c的情况，只需要挨个检验即可。

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int h[9][7]= {{},
	{0,0,0,0,0,0}, //1
	{0,0,0,1,1,1}, //34
	{1,0,1,0,1,0}, //2
	{1,0,1,1,0,1}, //4
	{0,1,0,0,1,0}, //14
	{0,1,0,1,0,1}, //3
	{1,1,1,0,0,0}, //24
	{1,1,1,1,1,1}  //0
};
int n,c,on[101],off[101];
inline void work(int w[9])
{
	int flag=1;
	for(int k=1; k<=w[0]; k++)
	{
		int tag=0;
		for(int i=1; i<=on[0]; i++)
			if(!h[w[k]][on[i]%6])
			{tag=1;break;}
		if(tag) continue;
		for(int i=1; i<=off[0]; i++)
			if(h[w[k]][off[i]%6])
			{tag=1;break;}
		if(tag) continue;
		flag=0;
		for(int i=1; i<=n; i++)
			printf("%d",h[w[k]][i%6]);
		printf("\n");
	}
	if(flag) printf("IMPOSSIBLE");
	exit(0);
}
int main()
{
	int tmp;
	scanf("%d%d",&n,&c);
	while(1)
	{
		scanf("%d",&tmp);
		if(tmp==-1) break;
		on[++on[0]]=tmp;
	}
	while(1)
	{
		scanf("%d",&tmp);
		if(tmp==-1) break;
		off[++off[0]]=tmp;
	}
	if(c==0)
	{int w[9]={1,8};work(w);}
	if(c==1)
	{int w[9]= {4,1,3,4,6};work(w);}
	if(c==2)
	{int w[9]= {7,1,2,3,5,6,7,8};work(w);}
	if(c>2)
	{int w[9]= {8,1,2,3,4,5,6,7,8};work(w);}
	return 0;
}