interestingLSY 的博客

interestingLSY 的博客

USACO Training 6.1.1 Postal Vans 题解

posted on 2017-12-17 17:04:55 | under 题解 |

USACO Training 6.1.1 Postal Vans 题解

描述

给定一个4行n列的网格,询问有多少条路径满足从左上角格点出发,经过每个格点仅一次,并回到左上角的个点(类似哈密顿回路)

算法:

插头dp(不知道插头dp是啥的可以先看我的另一篇博文:“插头dp 从懵逼到懵逼”)

代码:

    #include <bits/stdc++.h>
    #define vc vector
    #define pb push_back
    #define ll long long
    #define _tp template
    #define _tyn typename
    #define sint short int
    #define ull unsigned ll
    #define uint unsigned int
    #define B cout << "BreakPoint" << endl;
    #define ms(_data) memset(_data,0,sizeof(_data))
    #define fin(_filename) freopen(_filename,"r",stdin)
    #define fout(_filename) freopen(_filename,"w",stdout)
    #define msn(_data,_num) memset(_data,_num,sizeof(_data))
    #define fastio ios_base::sync_with_stdio(false);cin.tie(0);
    using namespace std;
    _tp<_tyn T>void mymax( T &_a , T _b ){ if( _a < _b ) _a = _b; }
    _tp<_tyn T>void mymin( T &_a , T _b ){ if( _a > _b ) _a = _b; }
    void print(int _x){printf("%d\n",_x);}
    void print(ll _x){printf("%I64d ",_x);}
    _tp<_tyn T>void print( T _a[] , int _s , int _t ){
        for( int i = _s ; i <= _t ; i++ )
            cout << _a[i] << " ";
           cout << endl;
    }
    #define il inline
    struct InputReader{
        static const int bs = 1000000;
        char buf[bs];
        int p;
        il InputReader():p(bs) {}
        il void flush(){
            p = 0;
            fread(buf, 1, bs, stdin);
        }
        il char c(){
            if(p >= bs) flush();
            return buf[p++];
        }
        int getnum(){
            char ch = c();
            while( ch < '0'  ||  ch > '9' ) ch = c();
            return (int)(ch-'0');
        }
        il int operator() (){
            int ans = 0;
            char ch = c();
            int fu = 1;
            while( ch < '0'  ||  ch > '9' ){
                if( ch == '-' ) fu = -1;
                ch = c();
            }
            while( ch >= '0'  &&  ch <= '9' ){
                ans *= 10;
                ans += ch-'0';
                ch = c();
            }
            return ans * fu;
        }
        ll readll(){
            ll ans = 0LL;
            char ch = getnum()+'0';
            while( ch >= '0'  &&  ch <= '9' ){
                ans *= 10LL;
                ans += ch-'0';
                ch = c();
            }
            return ans;
        }
        char specialread(){
            char ch = c();
            while( ch < 'a'  ||  ch > 'z' ) ch = c();
            return ch;
        }
    }in;
    il void read( int &x ){
        x = in();
    }
    il void read( int &x, int &y ){
        x = in(); y = in();
    }
    il void read( int &x1 , int &x2 , int &x3 ){
        x1 = in(); x2 = in(); x3 = in();
    }
    il void read( int &x1 , int &x2 , int &x3 , int &x4 ){
        x1 = in(); x2 = in(); x3 = in(); x4 = in();
    }
    /////////////////////////////////////////////////////////////////////
    /////////////////////////////////////////////////////////////////////
    int n;
    struct S{
        int mask;
        S(){ mask = 0; }
        S( int mk ){ mask = mk; }
        int bit( int x ){
            return ( mask >> ((x-1)<<1) ) & 3;
        }
        void set( int x , int y ){
            int newmask = 0;
            for( int i = 5 ; i >= 1 ; i-- ){
                newmask <<= 2;
                if( i != x ) newmask |= bit(i);
                else newmask |= y;
            }
            mask = newmask;
        }
        void print(){
            //cout << bitset<8>(mask) << endl;
            for( int i = 1 ; i <= 5 ; i++ ){
                if( bit(i) == 0 ) cout << "_";
                if( bit(i) == 1 ) cout << "(";
                if( bit(i) == 2 ) cout << ")";
                if( bit(i) == 3 ) cout << "#";
                //cout << bit(i) << endl;
            }
            cout << endl;
        }
        int operator[] ( int x ){
            return bit(x);
        }
        int findpos( int x , int type ){
            for( int i = x+1 ; i <= 5 ; i++ )
                if( bit(i) == type )
                    return i;
            cerr << "\n\n\nError in findpos" << endl;
            print();
            cerr << x << "  " << type << endl << endl << endl << endl;
            exit(0);
        }
        int rfindpos( int x , int type ){
            for( int i = x-1 ; i >= 1 ; i-- )
                if( bit(i) == type )
                    return i;
            cerr << "\n\n\nError in rfindpos" << endl;
            print();
            cerr << x << "  " << type << endl << endl << endl << endl;
            exit(0);
        }
    };
    #define MAXMASK 1030
    #define MAXN 1010
    struct Bignum{
        vc<sint> dat;
        Bignum(){}
        Bignum( int x ){
            while(x){
                sint nowbit = x % 10;
                dat.pb(nowbit);
                x /= 10;
            }
            //reverse(dat.begin(),dat.end());
        }
        void tui(){
            while( dat.size() > 1  &&  dat[dat.size()-1] == 0 )
                dat.pop_back();
        }
        void jinwei(){
            for( uint i = 0 ; i < dat.size() ; i++ ){
                if( dat[i] >= 10 ){
                    if( i == dat.size()-1 ) dat.pb( dat[i]/10 );
                    else dat[i+1] += dat[i]/10;
                    dat[i] %= 10;
                }
            }
        }
        void print() const{
            for( int i = dat.size()-1 ; i >= 0 ; i-- )
                printf("%d",dat[i]);
            printf("\n");
        }
    };
    void bplus( Bignum &a , Bignum b ){
        //cout << "[Plus]\n";
        //a.print();
        //b.print();
        a.dat.resize( max( a.dat.size() , b.dat.size() )+1 );
        for( uint i = 0 ; i < min(a.dat.size(),b.dat.size()) ; i++ ){
            a.dat[i] += b.dat[i];
        }
        a.jinwei();
        a.tui();
    }
    Bignum dp[100][6][MAXMASK];
    void solve(){
        dp[1][1][1023] = Bignum(1);
        bool now = 0 , nxt;
        for( int y = 1 ; y <= n ; y++ ){
            now ^= 1;
            nxt = now ^ 1;
            //cout << y << "   " << nxt << " " << now << endl;
            for( int x = 1 ; x <= 5 ; x++ ){
                for( int sx = 1 ; sx < MAXMASK ; sx++ ){
                    if( dp[now][x][sx].dat.empty() ) continue;
                    S s(sx);
                    if( x > 4 ){
                        S news = S(s.mask<<2);
                        news.set(1,3);
                        bplus(dp[nxt][1][news.mask],dp[now][x][sx]);
                        dp[now][x][sx].dat.clear();
                        continue;
                    }
                    //cout << "Dfs at " << y << ' ' << x << "   ";
                    //s.print();
                    int l = s[x];
                    int u = s[x+1];
                    S news = s;
                    //printf("l: %d  u: %d\n",l,u);
                    if( l == 3  &&  u == 3 ){
                        if( x == 4  ||  y == n ){
                            continue;
                        }
                        news.set(x,1);
                        news.set(x+1,2);
                        bplus( dp[now][x+1][news.mask] , dp[now][x][sx] );
                        dp[now][x][sx].dat.clear();
                        continue;
                    }else
                    if( l != 3  &&  u != 3 ){
                        news.set(x,3);
                        news.set(x+1,3);
                        if( l == u ){
                            if( l == 1 ){    // ( (
                                //cout << y << " " << x << endl;
                                int pos = news.findpos(x,2);
                                news.set(pos,1);
                            }else{            // ) )
                                int pos = news.rfindpos(x,1);
                                news.set(pos,2);
                            }
                        }else{
                            if( l == 1  &&  u == 2 ){
                                if( y != n  ||  x != 4 ){
                                    //cout << "Op 2 Banned" << endl;
                                    dp[now][x][sx].dat.clear();
                                    continue;
                                }
                            }
                        }
                        bplus(dp[now][x+1][news.mask],dp[now][x][sx]);
                        dp[now][x][sx] = 0;
                        continue;
                    }else{
                        Bignum tans = 0;
                        if( l != 3 ){
                            if( y != n ) bplus(dp[now][x+1][sx],dp[now][x][sx]);
                            if( x != 4 ){
                                news.set(x,3);
                                news.set(x+1,l);
                                bplus(dp[now][x+1][news.mask],dp[now][x][sx]);
                            }
                        }else{
                            if( y != n ){
                                news.set(x,u);
                                news.set(x+1,3);
                                bplus(dp[now][x+1][news.mask],dp[now][x][sx]);
                            }
                            if( x != 4 ){
                                bplus(dp[now][x+1][sx],dp[now][x][sx]);
                            }
                        }
                        dp[now][x][sx].dat.clear();
                    }
                }
            }
        }
    }
    void init(){
        for( int i = 0 ; i <= 1 ; i++ )
            for( int j = 1 ; j <= 5 ; j++ )
                for( int k = 1 ; k < MAXMASK ; k++ )
                    dp[i][j][k].dat.clear();
    }
    int main(){
        fin("vans.in");
        fout("vans.out");
        read(n);
        init();
        solve();
        Bignum ans = dp[(n+1)&1][1][1023];
        bplus(ans,ans);
        ans.print();
        return 0;
    }