USACO 2.2.4 Party Lamps 派對燈

相當繁瑣的窮舉題,容易超時。我花了大半天才寫出來,用了位運算優化和減縮開關次數c才過全了。

先分析算法:窮舉每一種按開關的可能。 但計數器C(0<=C<=10000),簡單窮舉肯定會超時。

根據題上所給的開關規則可以發現任何一個開關按兩下等於不按。這一點決定了可以減縮按c的次數。

  • 當(0<=C<=4)時,簡單窮舉,不改變C。
  • 當(5<=C<=10000)時,窮舉C=4,C=3各一次。

分析存儲結構: 題 中所給N(10<=N<=100),窮舉最大可能性(不優化)就是2^100。用數組1..100存儲不方便,因爲每次傳值都要複製100 次。所以我用了位運算存儲:用4個unsigned long int (無符號32位長整型)存儲每一位燈開關情況,4*32=128位,最大可以存儲 128位,滿足最大100位(其實N值還可以更大,越大越能體現位運算的高效性)。

以下運算可以返回二進制a的第從右數第b位數字,要理解。 ((a&(1<<(b-1)))>>(b-1))&1

/*
ID: cmykrgb1
PROG: lamps
LANG: C++
*/
#include <stdio.h>

typedef struct
{
    unsigned long int s[4];
} psi;

FILE *fi,*fo;
int n,c,u;
int k[101],g[101],ck,cg,tch[4],lr;
psi r[20],pmax;
int toc[5];

int gw(psi&amp; p,int w)  //返回p從右數第w位
{
    int k=(w-1)/32;
    w-=32*k;
    return ((p.s[k]&amp;(1&lt;&lt;(w-1)))&gt;&gt;(w-1))&amp;1;
}

void sw(psi&amp; p,int w) //取反p從右數第w位(開關燈)
{
    int k=(w-1)/32;
    if (!gw(p,w))
        p.s[k]+=1&lt;&lt;(w-1-32*k);
    else
        p.s[k]-=1&lt;&lt;(w-1-32*k);
}

void cpy(psi&amp; k,psi&amp; p) //複製數位
{
    int i;
    for (i=0;i&lt;=u;i++)
        k.s[i]=p.s[i];
}

int sm(psi&amp; a,psi&amp; b) //判等
{
    int i;
    for (i=u;i&gt;=0;i--)
        if (a.s[i]!=b.s[i]) return 0;
    return 1;

}

int cun(psi&amp; p) //判重
{
    int i;
    for (i=1;i&lt;=lr;i++)
        if (sm(p,r[i]))
            return 1;
    return 0;
}

void print(psi&amp; p) //輸出
{
    int i;
    for (i=1;i&lt;=n;i++)
        putc(gw(p,i)+48,fo);
    putc('n',fo);
}

void check(psi&amp; p) //判斷是否符合規則
{
    int j;
    for (j=1;j&lt;=ck;j++)
        if (!gw(p,k[j]))
            return;
    for (j=1;j&lt;=cg;j++)
        if (gw(p,g[j]))
            return;
    if (!cun(p))
    {
        cpy(r[++lr],p);
    }
}

void push(psi p,int c) //窮舉
{
    if (c==0)
    {
        check(p);
        return;
    }
    int i;
    psi tp;
    //變換1
    if (toc[1]&lt;2)
    {
        for (i=0;i&lt;=u;i++) tp.s[i]=p.s[i]; //reset tp

        for (i=0;i&lt;=u;i++)
            tp.s[i]=-tp.s[i]-1;
        toc[1]++;
        push(tp,c-1);
        toc[1]--;
    }
    //變換2
    if (toc[2]&lt;2)
    {
        for (i=0;i&lt;=u;i++) tp.s[i]=p.s[i]; //reset tp

        for (i=1;i&lt;=n;i+=2)
            sw(tp,i);
        toc[2]++;
        push(tp,c-1);
        toc[2]--;
    }
    //變換3
    if (toc[3]&lt;2)
    {
        for (i=0;i&lt;=u;i++) tp.s[i]=p.s[i]; //reset tp

        for (i=1;i&lt;=n;i+=2)
            sw(tp,i);
        toc[3]++;
        push(tp,c-1);
        toc[3]--;
    }
    //變換4
    if (toc[4]&lt;2)
    {
        for (i=0;i&lt;=u;i++) tp.s[i]=p.s[i]; //reset tp

        for (i=1;i&lt;=n;i+=3)
            sw(tp,i);
        toc[4]++;
        push(tp,c-1);
        toc[4]--;
    }
}

void sp(psi&amp; a,psi &amp;b) //交換
{
    psi c;
    cpy(c,a);
    cpy(a,b);
    cpy(b,c);
}

int small(psi&amp; a,psi &amp;b) //比較大小
{
    int i;
    int ka,kb;
    for (i=1;i&lt;=n;i++)
    {
        ka=gw(a,i);
        kb=gw(b,i);
        if (ka<kb)>
            return 1;
        else
            if (kb<ka)>
                return 0;
    }
}

void st(void) //排序
{
    int i,j,k;
    psi rmin;
    for (i=1;i&lt;=lr-1;i++)
    {
        cpy(rmin,pmax);
        for (j=i+1;j&lt;=lr;j++)
        {
            if (small(r[j],rmin))
            {
                cpy(rmin,r[j]);
                k=j;
            }
        }
        if (small(r[k],r[i]))
            sp(r[i],r[k]);
    }
}

int main(void) //主函數
{
    int i;
    fi=fopen("lamps.in","r");
    fo=fopen("lamps.out","w");
    fscanf(fi,"%dn%dn",&amp;n,&amp;c);
    u=(n-1)/32;
    do
    {
        fscanf(fi,"%d",&amp;k[++ck]);
    }
    while (k[ck]!=-1);
    ck--;
    do
    {
        fscanf(fi,"%d",&amp;g[++cg]);
    }
    while (g[cg]!=-1);
    cg--;
    fclose(fi);
    if (c&gt;4)
    {
        c=4;
        pmax.s[0]=pmax.s[1]=pmax.s[2]=pmax.s[3]=4294967295;
        push(pmax,c);
        c=3;
        pmax.s[0]=pmax.s[1]=pmax.s[2]=pmax.s[3]=4294967295;
        push(pmax,c);
    }
    else
    {
        pmax.s[0]=pmax.s[1]=pmax.s[2]=pmax.s[3]=4294967295;
        push(pmax,c);
    }
    st();
    if (lr==0) fprintf(fo,"IMPOSSIBLEn");
    for (i=1;i&lt;=lr;i++)
        print(r[i]);
    fclose(fo);
    return 0;
}

相關日誌