USACO Training 6.1.1 Postal Vans 题解
interestingLSY
2017-12-17 17:04:55
# USACO Training 6.1.1 Postal Vans 题解
## 描述
给定一个4行n列的网格，询问有多少条路径满足从左上角格点出发，经过每个格点仅一次，并回到左上角的个点（类似哈密顿回路）
## 算法：
**插头dp**（不知道插头dp是啥的可以**先看**我的另一篇博文：“插头dp 从懵逼到懵逼”）
## 代码：
```cpp
#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;
}
```