2012-C17-team5

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

Rank 2，被上交的 JB + SJB + GXX 队踩了，其实这个排名已经相当不错了

附：1008 代码，懒得说明了，有问题直接问我吧
{{{
#include <cstdio>
#include <queue>
#include <cstring>
#include <cassert>
#include <map>
#include <algorithm>
using namespace std;

typedef pair<int,int> PII;
const int SIZE = 12, INF = 1000000007;

map<int,int> idx;
int at[41836],w;
int go[41836][12];
int ty[41836][12];
int pt[41836][12];
int dp[2][37][41836];
queue<PII> qu[2];

inline int get(int mask, int i){
    return (mask>>(i+i))&3;
}

inline void set(int& mask, int i, int v){
    mask&=~(3<<(i+i));
    mask|=  v<<(i+i);
}

inline void relax(int now, int k, int s, int cnt){
    if(k>w || s==41835) return;
    if(~dp[now][k][s]){
        dp[now][k][s]+=cnt;
        if(dp[now][k][s]>=INF) dp[now][k][s]-=INF;
    }else{
        dp[now][k][s]=cnt;
        qu[now].push(PII(k,s));
    }
}

void build(int mask){
    if(idx.count(mask)) return;
    at[idx.size()]=mask;
    idx.insert(PII(mask,idx.size()));
    for(int i=0;i<=SIZE;i++) if(!get(mask,i))
    for(int j=i+1;j<=SIZE;j++){
        if(get(mask,j)) break;
        build(1<<(i+i)|2<<(j+j)|mask);
    }
}

void init(){
    build(0);
    for(int i=0;i<SIZE;i++) go[41835][i]=pt[41835][i]=41835;
    for(int s=0;s<41835;s++){
        for(int i=0;i<SIZE;i++){
            int mask=at[s],z=0;
            int x=get(mask,i);
            int y=get(mask,i+1);
            for(int o=i+1;o<=SIZE;o++) z|=get(mask,o);
            pt[s][i]=z?41835:idx[mask<<2];
            if(x==1 && y==2){
                int cnt=0,v[]={0,+1,-1};
                for(int o=0;o<i;o++) cnt+=v[get(mask,o)];
                if(cnt&1){
                    go[s][i]=41835;
                }else{
                    set(mask,i,0);
                    set(mask,i+1,0);
                    go[s][i]=idx[mask];
                    ty[s][i]=1;
                }
            }else if(x==2 && y==1){
                set(mask,i,0);
                set(mask,i+1,0);
                go[s][i]=idx[mask];
            }else if(x==1 && y==1){
                int cnt=1,v[]={0,+1,-1},o=i+1;
                while(cnt) cnt+=v[get(mask,++o)];
                set(mask,o,1);
                set(mask,i,0);
                set(mask,i+1,0);
                go[s][i]=idx[mask];
            }else if(x==2 && y==2){
                int cnt=1,v[]={0,-1,+1},o=i;
                while(cnt) cnt+=v[get(mask,--o)];
                set(mask,o,2);
                set(mask,i,0);
                set(mask,i+1,0);
                go[s][i]=idx[mask];
            }else if(x){
                set(mask,i,0);
                set(mask,i+1,x);
                go[s][i]=idx[mask];
                ty[s][i]=2;
            }else if(y){
                set(mask,i,y);
                set(mask,i+1,0);
                go[s][i]=idx[mask];
                ty[s][i]=2;
            }else{
                set(mask,i,1);
                set(mask,i+1,2);
                go[s][i]=idx[mask];
                ty[s][i]=4;
            }
        }
    }
}

int main(){
    init();
    int cs;
    scanf("%d",&cs);
    while(cs--){
        char a[15][15];
        int n,m,now=1,ans=0;
        scanf("%d%d%d",&n,&m,&w);
        memset(dp,-1,sizeof(dp));
        qu[0]=qu[1]=queue<PII>();
        qu[0].push(PII(0,0));
        dp[0][0][0]=1;
        for(int i=0;i<n;i++) scanf("%s",a[i]);
        if(w>=37){ puts("0");continue; }
        for(int i=0;i<n;i++) for(int j=0;j<m;j++){
            int h=((n-i)*m-j+1)/4+3;
#define BEGIN   while(qu[ans].size()){              \
                    int k=qu[ans].front().first;    \
                    int s=qu[ans].front().second;   \
                    int cnt=dp[ans][k][s];          \
                    dp[ans][k][s]=-1;               \
                    qu[ans].pop();                  \
                    if(!cnt || k+h<w) continue;
#define END     }
            if(j+1==m){
                if(a[i][j]=='*') BEGIN
                    if(ty[s][j]==4) relax(now,k,pt[s][j],cnt);
                END else BEGIN
                    if(ty[s][j]==2) relax(now,k,pt[s][j],cnt);
                    relax(now,k+(ty[s][j]&1),pt[go[s][j]][j],cnt);
                END
            }else{
                if(a[i][j]=='*') BEGIN
                    if(ty[s][j]==4) relax(now,k,s,cnt);
                END else BEGIN
                    if(ty[s][j]==2) relax(now,k,s,cnt);
                    relax(now,k+(ty[s][j]&1),go[s][j],cnt);
                END
            }
            swap(now,ans);
        }
        printf("%d\n",max(dp[ans][w][0],0));
    }
}
}}}

Rank 2，被上交的 JB + SJB + GXX 队踩了，其实这个排名已经相当不错了

附：1008 代码，懒得说明了，有问题直接问我吧

#include <cstdio>
#include <queue>
#include <cstring>
#include <cassert>
#include <map>
#include <algorithm>
using namespace std;
typedef pair<int,int> PII;
const int SIZE = 12, INF = 1000000007;
map<int,int> idx;
int at[41836],w;
int go[41836][12];
int ty[41836][12];
int pt[41836][12];
int dp[2][37][41836];
queue<PII> qu[2];
inline int get(int mask, int i){
    return (mask>>(i+i))&3;
}
inline void set(int& mask, int i, int v){
    mask&=~(3<<(i+i));
    mask|=  v<<(i+i);
}
inline void relax(int now, int k, int s, int cnt){
    if(k>w || s==41835) return;
    if(~dp[now][k][s]){
        dp[now][k][s]+=cnt;
        if(dp[now][k][s]>=INF) dp[now][k][s]-=INF;
    }else{
        dp[now][k][s]=cnt;
        qu[now].push(PII(k,s));
    }
}
void build(int mask){
    if(idx.count(mask)) return;
    at[idx.size()]=mask;
    idx.insert(PII(mask,idx.size()));
    for(int i=0;i<=SIZE;i++) if(!get(mask,i))
    for(int j=i+1;j<=SIZE;j++){
        if(get(mask,j)) break;
        build(1<<(i+i)|2<<(j+j)|mask);
    }
}
void init(){
    build(0);
    for(int i=0;i<SIZE;i++) go[41835][i]=pt[41835][i]=41835;
    for(int s=0;s<41835;s++){
        for(int i=0;i<SIZE;i++){
            int mask=at[s],z=0;
            int x=get(mask,i);
            int y=get(mask,i+1);
            for(int o=i+1;o<=SIZE;o++) z|=get(mask,o);
            pt[s][i]=z?41835:idx[mask<<2];
            if(x==1 && y==2){
                int cnt=0,v[]={0,+1,-1};
                for(int o=0;o<i;o++) cnt+=v[get(mask,o)];
                if(cnt&1){
                    go[s][i]=41835;
                }else{
                    set(mask,i,0);
                    set(mask,i+1,0);
                    go[s][i]=idx[mask];
                    ty[s][i]=1;
                }
            }else if(x==2 && y==1){
                set(mask,i,0);
                set(mask,i+1,0);
                go[s][i]=idx[mask];
            }else if(x==1 && y==1){
                int cnt=1,v[]={0,+1,-1},o=i+1;
                while(cnt) cnt+=v[get(mask,++o)];
                set(mask,o,1);
                set(mask,i,0);
                set(mask,i+1,0);
                go[s][i]=idx[mask];
            }else if(x==2 && y==2){
                int cnt=1,v[]={0,-1,+1},o=i;
                while(cnt) cnt+=v[get(mask,--o)];
                set(mask,o,2);
                set(mask,i,0);
                set(mask,i+1,0);
                go[s][i]=idx[mask];
            }else if(x){
                set(mask,i,0);
                set(mask,i+1,x);
                go[s][i]=idx[mask];
                ty[s][i]=2;
            }else if(y){
                set(mask,i,y);
                set(mask,i+1,0);
                go[s][i]=idx[mask];
                ty[s][i]=2;
            }else{
                set(mask,i,1);
                set(mask,i+1,2);
                go[s][i]=idx[mask];
                ty[s][i]=4;
            }
        }
    }
}
int main(){
    init();
    int cs;
    scanf("%d",&cs);
    while(cs--){
        char a[15][15];
        int n,m,now=1,ans=0;
        scanf("%d%d%d",&n,&m,&w);
        memset(dp,-1,sizeof(dp));
        qu[0]=qu[1]=queue<PII>();
        qu[0].push(PII(0,0));
        dp[0][0][0]=1;
        for(int i=0;i<n;i++) scanf("%s",a[i]);
        if(w>=37){ puts("0");continue; }
        for(int i=0;i<n;i++) for(int j=0;j<m;j++){
            int h=((n-i)*m-j+1)/4+3;
#define BEGIN   while(qu[ans].size()){              \
                    int k=qu[ans].front().first;    \
                    int s=qu[ans].front().second;   \
                    int cnt=dp[ans][k][s];          \
                    dp[ans][k][s]=-1;               \
                    qu[ans].pop();                  \
                    if(!cnt || k+h<w) continue;
#define END     }
            if(j+1==m){
                if(a[i][j]=='*') BEGIN
                    if(ty[s][j]==4) relax(now,k,pt[s][j],cnt);
                END else BEGIN
                    if(ty[s][j]==2) relax(now,k,pt[s][j],cnt);
                    relax(now,k+(ty[s][j]&1),pt[go[s][j]][j],cnt);
                END
            }else{
                if(a[i][j]=='*') BEGIN
                    if(ty[s][j]==4) relax(now,k,s,cnt);
                END else BEGIN
                    if(ty[s][j]==2) relax(now,k,s,cnt);
                    relax(now,k+(ty[s][j]&1),go[s][j],cnt);
                END
            }
            swap(now,ans);
        }
        printf("%d\n",max(dp[ans][w][0],0));
    }
}