纵有疾风起
人生不言弃

usaco 2.2 lamps…今天下午颇没状态…

/*
    ID:chenjiong
    PROG:lamps
    LANG:C++
*/

#include <stdio.h>
#include <string.h>
#include <algorithm>

using namespace std;

int N;
int lamp[7] = {
   1,1,1,1,1,1,1};
int C;

int cnt_on;
int on[7];
int cnt_off;
int off[7];

bool vis[7];

typedef struct {
    int lamp[7];
    int val;
}S;

int cnt;
S ans[16];

int w[7] =  {
   0,32,16,8,4,2,1};

void push1()
{
    int i;
    for ( i = 1; i <= 6; i++)
        lamp[i] = 1 - lamp[i];
}

void push2()
{
    int i;
    for ( i = 1; i <= 6; i += 2)
        lamp[i] = 1 - lamp[i];
}

void push3()
{
    int i;
    for ( i = 2; i <= 6; i += 2)
        lamp[i] = 1 - lamp[i];
}

void push4()
{
    int i;
    for ( i = 1; i <= 6; i += 3)
        lamp[i] = 1 - lamp[i];
}

void push(int No)
{
    switch ( No )
    {
        case 1 : push1(); break;
        case 2 : push2(); break;
        case 3 : push3(); break;
        case 4 : push4(); break;
    }
}

int cal()
{
    int i;
    int sum = 0;
    for ( i = 1; i <= 6; i++)
        sum += lamp[i] * w[i];
    return sum;
}

bool is_ok()
{
    int i;
    for ( i = 0; i < cnt_on; i++)
        if ( lamp[on[i]] == 0 )
            return false;
    for ( i = 0; i < cnt_off; i++)
        if ( lamp[off[i]] == 1 )
            return false;
    return true;
}

int times;

void dfs(int cur)
{
    if ( cur == 5 )
    {
        if ( C - times >= 0 && ( C - times ) % 2 == 0 && is_ok() )
        {
            int i;
            for ( i = 1; i <= 6; i++)
                ans[cnt].lamp[i] = lamp[i];
            ans[cnt++].val = cal();
        }
        return;
    }

    push(cur);
    times++;
    dfs(cur + 1);
    push(cur);
    times--;
    
    dfs(cur + 1);
}

bool cmp(const S& a,const S& b)
{
    return a.val < b.val;
}
            
int main()
{
    freopen("lamps.in","r",stdin);
    freopen("lamps.out","w",stdout);

    scanf("%d",&N);
    scanf("%d",&C);

    int a;
    cnt_on = 0;
    while ( scanf("%d",&a) == 1 )
    {
        if ( a == -1 )
            break;
        int p = a - a / 6 * 6;
        if ( !vis[p] )
        {
            vis[p] = true;
            on[cnt_on++] = p;
        }
    }

    cnt_off = 0;
    while ( scanf("%d",&a) == 1 )
    {
        if ( a == -1 )
            break;
        int p = a - a / 6 * 6;
        if ( !vis[p] )
        {
            vis[p] = true;
            off[cnt_off++] = p;
        }
    }

    times = 0;
    dfs(1);

    if ( cnt == 0 )
    {
        printf("IMPOSSIBLE\n");
        return 0;
    }
    
    sort(ans,ans + cnt,cmp);

    int i,j,k;
    int pre = -1;
    for ( i = 0; i < cnt; i++)
    {
        if ( ans[i].val != pre )
        {
            pre = ans[i].val;
            for ( j = 1; j <= N / 6; j++)
                for ( k = 1; k <= 6; k++)
                    printf("%d",ans[i].lamp[k]);
            int tmp = N % 6;
            for ( k = 1; k <= tmp; k++)
                printf("%d",ans[i].lamp[k]);
            printf("\n");
        }
    }

    return 0;
}

 

转载于:https://www.cnblogs.com/jiongjiong-mengmeng/archive/2012/11/03/2752896.html

原文链接:https://blog.csdn.net/weixin_30342827/article/details/96639880

本站声明:网站内容来源于网络,如有侵权,请联系我们,我们将及时处理。

未经允许不得转载:起风网 » usaco 2.2 lamps…今天下午颇没状态…

分享到: 生成海报
avatar

评论 抢沙发

评论前必须登录!

立即登录   注册

切换注册

登录

忘记密码 ?

切换登录

注册

我们将发送一封验证邮件至你的邮箱, 请正确填写以完成账号注册和激活