ssoj 2279 磁力阵

说不想改最后还是向T1屈服了。。然后就de了一下午Bug。。。

虽然昨天随口扯的有点道理，正解就是迭代加深A星搜索，但实际写起来就十分难受了。

说自己的做法，略鬼畜。

每个正方形的边界上的边、每条边在哪些正方形上，都可以用一个Long Long的二进制串表示。给每个矩形编号，预处理每个矩形对应边的串，每条边对应矩形的串，每个矩形对应矩形（它的所有边对应矩形的并集，之后估价会用）。

然后就直接迭代搜索，存一个串表示现在哪些正方形处理完了，每次找出第一个没处理的正方形，枚举每条边试图处理它。用一个估价函数判断现在有没有必要继续搜：找当前状态所有未处理的正方形，把它的所有边处理掉，遇到一个就res++,若res+cnt>limit 就return 0;

几个坑点，可能只有自己会被坑。。。

1.不用二进制优化会TLE，可能是我写得比较残，T2个点。。

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<cmath>

#include<queue>

#include<vector>

typedef long long LL;

using namespace std;

int T,n,totn,k,x,xx,tot,now,nowok,e[][],sq[][],ok[],tpok[],limit;

void clear() {

    memset(e,,sizeof(e));

    memset(sq,,sizeof(sq));

    memset(ok,,sizeof(ok));

    tot=; nowok=;

}

void link(int ed,int id) {

    e[ed][++e[ed][]]=id;

    sq[id][++sq[id][]]=ed;

}

void pre() {

    totn=;

    for(int i=;i<=n;i++) totn+=i*i;

    for(int k=;k<=n;k++)

    for(int i=;i<=n;i++)

        for(int j=;j<=n;j++)

            if(i+k<=n&&j+k<=n)

             {

                tot++;

                for(int l=;l<=k;l++) {

                    now=(i-)*(*n+)+j+l;

                    link(now,tot);

                    now=(i+k)*(*n+)+j+l;

                    link(now,tot);

                }

                now=n+(i-)*(*n+)+j;

                link(now,tot);

                link(now+k+,tot);

                for(int l=;l<=k;l++) {

                    now+=(*n+);

                    link(now,tot);

                    link(now+k+,tot);

                }

            }

}

int check(int x,int c,int li) {

    memset(tpok,,sizeof(tpok));

    int res=;

    for(int i=;i<=totn;i++)

    if(!ok[i]&&!tpok[i]) {

         res++;

         for(int j=;j<=sq[i][];j++) {

             int u=sq[i][j];

             for(int l=;l<=e[u][];l++)

                 tpok[e[u][l]]=;

         }

    }

    return res;

}

int dfs(int cnt,int no,int lim) {

    if(cnt>lim) return ;

    if(!no) return ;

    int tp[],flag=;

    memset(tp,,sizeof(tp));

    for(int i=;i<=totn;i++) if(flag) break; else {

       if(!ok[i]){

           flag=;

        for(int j=;j<=sq[i][];j++) {

            xx=;   tp[]=;

            x=sq[i][j];

            for(int l=;l<=e[x][];l++) {

               if(!ok[e[x][l]]) {tp[++tp[]]=e[x][l]; xx++;}

               ok[e[x][l]]=;

            }

            if(check(sq[i][j],cnt,lim)+cnt<=lim) {

                if(dfs(cnt+,no-xx,lim)) return ;

            }

            for(int i=;i<=tp[];i++)

                ok[tp[i]]=;

        }

       }

    }

    return ;

}

int main()

{

    freopen("mag.in","r",stdin);

    freopen("mag.out","w",stdout);

    scanf("%d",&T);

    while(T--) {

        scanf("%d%d",&n,&k);

        clear();

        pre();

        for(int i=;i<=k;i++) {

            scanf("%d",&x);

            for(int j=;j<=e[x][];j++) {

                if(!ok[e[x][j]]) nowok++;

                ok[e[x][j]]=;

            }

        }

        for(limit=;limit<=;limit++) {

            if(dfs(,totn-nowok,limit)) {

                printf("%d\n",limit);

                break;

            }

        }

    }

    return ;

}

2.搜索的时候只需要搜当前状态第一个不满足的正方形，因为其他在之后的状态中是可以搜到的，不然会T8个点。。。

3.正方形的编号，因为搜索是按编号搜的，要先编小正方形再编大的。。自行体会。。会T两个点，速度是0.2秒和10.2秒的差距。。。

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<cmath>

#include<queue>

#include<vector>

typedef long long LL;

using namespace std;

int T,n,totn,k,x,xx,now,tot,nowok,sqq[][];

LL e[],sq[],val[],st,limit,N;

void clear() {

    memset(e,,sizeof(e));

    memset(sq,,sizeof(sq));

    memset(sqq,,sizeof(sqq));

    memset(val,,sizeof(val));

    tot=; st=;

}

void link(int ed,int id) {

    e[ed]|=1LL<<(id-);

    sq[id]|=1LL<<(ed-);

    sqq[id][++sqq[id][]]=ed;

}

void pre() {

    totn=;

    for(int i=;i<=n;i++) totn+=i*i;

    N=(1LL<<totn)-;

    for(int k=;k<=n;k++)

        for(int i=;i<=n;i++)

            for(int j=;j<=n;j++)

            if(i+k<=n&&j+k<=n)

             {

                tot++;

                for(int l=;l<=k;l++) {

                    now=(i-)*(*n+)+j+l;

                    link(now,tot);

                    now=(i+k)*(*n+)+j+l;

                    link(now,tot);

                }

                now=n+(i-)*(*n+)+j;

                link(now,tot);

                link(now+k+,tot);

                for(int l=;l<=k;l++) {

                    now+=(*n+);

                    link(now,tot);

                    link(now+k+,tot);

                }

            }

    for(int i=;i<=totn;i++) {

        for(int j=;j<=sqq[i][];j++) {

            val[i]|=e[sqq[i][j]];

        }

    }

}

int check(LL now,int c,int li) {

    int res=;

    for(int i=;i<=totn-;i++) {

        if(!(now&(1LL<<i-))) {

            res++;

            if(res+c>li) return ;

            now|=val[i];

        }

    }

    return res+c<=li;

}

int dfs(int cnt,LL now,int lim) {

    if(cnt>lim) return ;

    if(now==N) return ;

    LL tmp;

    if(!check(now,cnt,lim)) return ;

    int flag=;

    for(int i=;i<=totn;i++) if(flag) break; else{

       if(!(now&(1LL<<i-))){

               flag=; 

               for(int j=;j<=sqq[i][];j++) {

                   tmp=now|e[sqq[i][j]];

                //if(check(tmp,cnt,lim)) {

                if(dfs(cnt+,tmp,lim)) return ;

                //}

               }

       }

    }

    return ;

}

int main()

{

    freopen("mag.in","r",stdin);

    freopen("mag.out","w",stdout);

    scanf("%d",&T);

    while(T--) {

        scanf("%d%d",&n,&k);

        clear();

        pre();

        for(int i=;i<=k;i++) {

            scanf("%d",&x);

            st|=e[x];

        }

        for(limit=;limit<=;limit++) {

            if(dfs(,st,limit)) {

                printf("%d\n",limit);

                break;

            }

        }

    }

    return ;

}

巴特西

ssoj 2279 磁力阵

最新文章

热门文章