[USACO][Section 2.2][枚举] Party Lamps

题目大意：

给出一排灯，4个按钮，每个按钮可以使特定位置的灯改变状态。规定操作数c和目标状态，输出c次操作后所有符合目标状态的状态。

思路：

利用深搜按操作次数枚举4^c个状态。

代码：

/*
ID: lujunda1
LANG: C++
PROG: lamps
*/
#include
#include
#include
#include
using namespace std;
int n,c,total;
bool on[102],off[102];
//on[]、off[]用于记录目标状态。 
map mark;
//对状态进行标记，避免重复搜索。 
struct point 
//对用结构体对状态进行封装，便于利用qsort排序。
{
    char arry[102];
}res[16]; 
int cmp(const void* m,const void* n)
//qsort的排序函数。 
{
    return strcmp((*(point*)m).arry+1,(*(point*)n).arry+1);
    //注意下标是从1开始的，而不是0。 
}
void input()
//输入 
{
    scanf("%d%d",&n,&c);
    if(c>4)
        c=c%2?3:4;
        //注意对C的处理，当c>4时，必然会出现同一按钮按多次的情况。 
    for(int i=0;i<102;i++)
        on[i]=off[i]=false;
    int t;
    while(~scanf("%d",&t)&&t!=-1)
        on[t]=true;
    while(~scanf("%d",&t)&&t!=-1)
        off[t]=true;
}
void output()
//输出 
{
    if(!total)
    {
        printf("IMPOSSIBLE\n");
        return;
    }
    qsort(res,total,sizeof(res[0]),cmp);
    for(int i=0;i

发表回复取消回复