hihocoder 1233 Boxes

素颜马尾好姑娘i 2022-08-08 16:47 102阅读 0赞

打表  
通过最终排序好的情况直接bfs得到合法状态的，状压的时候有多种方法。  
第一种是最直接的，因为只有7个数，每个位置上最多也只可能是7个数，所以你用一个数组表示每一位有哪些块，然后用一个long long状压出你这个状态的情况，用map标记判重。  
这样的复杂度会稍微大一些，可能不能直接在线打表，所以你大一个表再交上去。我们的比赛的时候程序大概88kb，杭电上就会挂了。

第二种是用n进制状压，用一个数组表示，第i块在第sav\[i\]个坑里。这样可以直接用数组判重，复杂度会小一些。可以直接在线打表。

#include<cstdio>
    #include<cstring>
    #include<cmath>
    #include<vector>
    #include<queue>
    #include<algorithm>
    #include<iostream>
    using namespace std;
    #define clr(a,b) memset(a,b,sizeof(a))
    const int INF=~(1<<(sizeof(int )*8-1))-100000;
    typedef long long ll;
    typedef pair<int,int > P;
    #define MOD 1000000007
    int vis[1000000],ans[10][1000000];
    
    queue<P> q;
    void decode(int state,int len,int *pl)
    {
        for(int i=1;i<=len;i++)
        {
            pl[i]=state%len+1;
            state/=len;
        }
    }
    
    int encode(int *pl,int len)
    {
        int ret=0;
        for(int i=len;i>=1;i--)
        {
            ret*=len;
            ret+=pl[i]-1;
        }
        return ret;
    }
    
    int sav[10],temp[10];
    int bfs(int len)
    {
        while(!q.empty())   q.pop();
        for(int i=1;i<=len;i++)
        {
            sav[i]=i;
        }
        int state=encode(sav,len);
        vis[state]=1;
        q.push(make_pair(state,0));
        int d=0;
        int tot=0;
        int have[10];
        int up=1;
        for(int i=1;i<=len;i++) up*=i;
        while(!q.empty() && tot!=up)
        {
            P cnt=q.front();
            q.pop();
            state=cnt.first;
            ans[len][state]=cnt.second;
            decode(state,len,sav);
            int flag=1;
            memset(have,0,sizeof have);
            for(int i=1;i<=len;i++)
                if(!have[sav[i]])
                    have[sav[i]]=1;
                else
                {
                    flag=0;
                    break;
                }
            if(flag)
            {
                cout<<"ma[";
                for(int i=1;i<=len;i++)
                printf("%d",sav[i]);
                cout<<"]=";
                cout<<ans[len][state]<<";";
                tot++;
            }
    
            for(int i=1;i<=len;i++)
                temp[i]=len+1;
            for(int i=len;i>=1;i--)
            {
                temp[sav[i]]=i;
            }
            for(int i=1;i<=len;i++)
            if(temp[i]<=len)
            {
                if(i-1>=1&&temp[i]<temp[i-1])
                {
                    sav[temp[i]]=i-1;
                    state=encode(sav,len);
                    if(!vis[state])
                    {
                        vis[state]=1;
                        q.push(make_pair(state,cnt.second+1));
                    }
                    sav[temp[i]]=i;
                }
                if(i+1<=len&&temp[i]<temp[i+1])
                {
                    sav[temp[i]]=i+1;
                    state=encode(sav,len);
                    if(!vis[state])
                    {
                        vis[state]=1;
                        q.push(make_pair(state,cnt.second+1));
                    }
                    sav[temp[i]]=i;
                }
            }
        }
    }
    
    int have[10];
    int main()
    {
        freopen("data.txt","w",stdout);
        for(int i=3;i<=7;i++)
        {
            memset(vis,0,sizeof(vis));
            bfs(i);
            cout<<endl;
        }
    }