题解 P1468 【派对灯 Party Lamps】
其他题解已经把思路说明得十分详细了，这篇题解就 着重说明一下 对数据巧(tou)妙(lan)的处理技巧。
- 思路：看到这个数据范围发现暴力显然是不可以的，于是可以往记忆化或者简化模拟的方面去想。
然后经(you)思(ti)考(jie)可得如下性质：
- 以6为循环节，超过直接取模修改
- 对于
C=3 ，即可取完所有情况，且超过可以通过各种方法转换至C=3 （譬如连按两下任意按钮，或者通过按1,2,3 浪费次数）。
于是可以往只判断前6个字符和压缩开关次数<=3 次，使其在常数范围内即可得解。
-
那么如何处理本题数据呢？
我们可以通过打表将已知数据全部表示出来，使用时直接调用即可。
(我凭本事打的表怎么能说偷懒！）
首先理一下我们已经可以知道哪些东西：
- 草稿纸上画出的
C=1,C=2,C=3 的所有可能出现的情况map[i][j] （重复的或可替代的不算） - 根据输入数据得出的1~6循环节内各位置的开关灯情况
a[i] 。 -
其中1,3我们均可以直接打表出来：
int a[10],map[8][8]={} //已按照字典序(1表示开灯，2表示关灯）
{0,2,2,2,2,2,2},
//c=1,2,3
{0,2,2,1,1,1,2},
//c=2,3
{0,2,1,2,1,2,1},
//c=1,2,3
{0,2,1,1,2,1,1},
//c=1,3
{0,1,2,2,1,2,2},
//..2,3
{0,1,2,1,2,1,2},
//..1,2,3
{0,1,1,2,2,2,1},
//..2,3
{0,1,1,1,1,1,1}
//..2,3
};
bool f,f2,go[4][10]={ //i表示当前的c,j表示与上表对应的开关灯情况
{0,0,0,0,0,0,0,0},
{1,0,1,1,0,1,0,0},
{1,1,1,0,1,1,1,1},
{1,1,1,1,1,1,1,1}
};
别看这么长，全是草稿纸扫一眼的问题，手速快的人1分钟就可以敲完。
其次2号表我们读入中即可处理，至此题目已经做完一半，而我们才刚刚读入处理完。_(:з」∠)
- 主程序
得出3张表后，我们对8种情况一一判断，枚举表中数据和输入数据是否相符，并在go数组内判断当前c是否包含此情况。
于是主程序一共两个函数，不到十行：
bool equal(int x) //若输入数据存在当前位置信息就判断与map是否相符
{
for (int i=1;i<=6;i++)
if (map[x][i]!=a[i]&&a[i]) return 0;
return 1;
}
void check(int c)
{
for (int i=0;i<=7;i++)
if (equal(i)&&go[c][i]) print(i); //打印
}- 细节
- 一开始忘记考虑
c=0 的情况，又懒得修改三张表了，于是直接最后特判了一下。。 -
- 打完之后发现也有八十多行，但是大部分都是特判和打表，实际长度是真的少。
于是上我丑陋的代码：
#include <iostream>
using namespace std;
int n,c;
int a[10],map[8][8]={ //按照字典序
{0,2,2,2,2,2,2},
//1,2,3
{0,2,2,1,1,1,2},
//2,3
{0,2,1,2,1,2,1},
//1,2,3
{0,2,1,1,2,1,1},
//1,3
{0,1,2,2,1,2,2},
//2,3
{0,1,2,1,2,1,2},
//1,2,3
{0,1,1,2,2,2,1},
//2,3
{0,1,1,1,1,1,1}
//2,3
};
bool f,f2,go[4][10]={
{0,0,0,0,0,0,0,0},
{1,0,1,1,0,1,0,0},
{1,1,1,0,1,1,1,1},
{1,1,1,1,1,1,1,1}
};
//打表
void print(int i)
{
f2=1;
for (int j=1;j<=n;j++)
cout<<(map[i][(j%6!=0)?j%6:6]!=2)?1:0;
cout<<endl;
}
bool equal(int x)
{
for (int i=1;i<=6;i++)
if (map[x][i]!=a[i]&&a[i]) return 0;
return 1;
}
void check(int c)
{
for (int i=0;i<=7;i++)
if (equal(i)&&go[c][i]) print(i);
}
int main()
{
cin>>n>>c; if (c>3) c=3;
for (int i=1,p=0;i<=n;) {
cin>>p;
if (p!=-1) {
if (!c) f=1; //特判
int kp=(p%6!=0)?p%6:6; a[kp]=1;
} else break;
}
for (int i=1,p=0;i<=n;f) {
cin>>p;
if (p!=-1) {
if (!c) f=1; //特判
int kp=(p%6!=0)?p%6:6;
if (!a[kp]) a[kp]=2; else f=1;
} else break;
}
//读入处理
if (f){
cout<<"IMPOSSIBLE"<<endl; return 0;
}
check(c);
if (!c) { //特判
for (int i=1;i<=n;i++) cout<<1; return 0;
}
if (!f2) cout<<"IMPOSSIBLE"<<endl;
return 0;
}