B一个大神的做法。。。更普遍的做法是打表。。

有一个3*3的机场，里面有一些飞机，飞机的颜色有B和G两种，飞机只能在(0,0)处起飞，飞机可以往上下左右的空白处移动。

问这些飞机一共可以组成多少种不同的起飞颜色序列。

。。。。

如果不考虑30000组case，那么可以直接O(n!)枚举起飞顺序，然后判定可不可行，最后再计算有多少种不同的颜色序列。

现在预处理这个：can[sta][x][y]表示当前地图状态为sta（2进制串，0表示没有飞机，1表示有飞机）时那些地方和(0,0)联通。

那么判定的时候就可以直接判断了。

但是交上去还是TLE。

于是又把可行的起飞顺序给暴力预处理出来了，arr[sta][]表示当前初始状态为sta的时候的所有起飞顺序（最坏情况只有1344种）。

然后就可以降到O(cas*1344)了。

交上去果然还是TLE。

没辙，再预处理一下当前初始状态为sta，且每辆飞机的颜色状态为col的时候有多少种不同答案。

预处理大概2^8*3*3+2^8*2^8*1344*8这么多。

每组数据可以做到O(1)。

#include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;const int step[4][2] = {
    {
    0,1},{
    0,-1},{
    1,0},{-1,0}};bool can[256][3][3];char g[3][3];void DFS(int sta,int x,int y){    can[sta][x][y] = true;    for (int i = 0; i < 4; i++)    {        int tx = x+step[i][0];        int ty = y+step[i][1];        if (tx < 0 || tx > 2 || ty < 0 || ty > 2)   continue;        if (g[tx][ty] == '#')            can[sta][tx][ty] = true;        else        {            if (can[sta][tx][ty] == false)                DFS(sta,tx,ty);        }    }}int arr[2000][10],arrlen[2000],arrtot;int tmp[10];void DFS2(int ful,int sta,int tot){    if (sta == 0)    {        int id = arrtot;        arrlen[id] = tot;        for (int i = 0; i < tot; i++)            arr[id][i] = tmp[i];        arrtot++;        return;    }    for (int i = 0; i < 3; i++)        for (int j = 0; j < 3; j++)            if (((sta>>(i*3+j-1))&1) == 1)                if (can[sta][i][j] == true)                {                    tmp[tot] = i*3+j-1;                    DFS2(ful,sta-(1<<(i*3+j-1)),tot+1);                }}bool flag[256];int res[256][256];int tid[8];void Gao(){    memset(can,false,sizeof(can));    for (int i = 0; i < (1<<8); i++)    {        g[0][0] = '.';        for (int x = 0; x < 3; x++)            for (int y = 0; y < 3; y++)                if (x != 0 || y != 0)                {                    if (((i>>(x*3+y-1))&1) == 1)                        g[x][y] = '#';                    else                        g[x][y] = '.';                }        DFS(i,0,0);    }    memset(res,0,sizeof(res));    for (int i = 0; i < (1<<8); i++)    {        arrtot = 0;        DFS2(i,i,0);        int ttid = 0;        for (int x = 0; x < 3; x++)            for (int y = 0; y < 3; y++)                if (x != 0 || y != 0)                    if (((i>>(x*3+y-1))&1) == 1)                        tid[x*3+y-1] = ttid++;        int len = arrlen[0];        for (int j = 0; j < (1<
          
           >tid[arr[k][q]])&1) == 1)                        v = (v<<1)|1;                    else                        v = v<<1;                if (flag[v] == false)                    res[i][j]++;                flag[v] = true;            }            /*if (j == 0 || j == (1<
           
            = 0; x--) for (int y = 2; y >= 0; y--) if (x != 0 || y != 0) { if (mp[x][y] == '*') sta = sta<<1; else sta = (sta<<1)|1; } int col = 0; for (int x = 2; x >= 0; x--) for (int y = 2; y >= 0; y--) if (x != 0 || y != 0) { if (mp[x][y] == 'G') col = col<<1; else if (mp[x][y] == 'B') col = (col<<1)|1; } printf("Case %d: %d\n",++cas,res[sta][col]); } return 0; }
           
          
         
        
       
      

还有一种。。定义一个状态s，表示飞机场上对应的格子有无飞机（不管颜色），总共有2^9种状态，如果对与s，我们选择一个和起飞点直接连通的有飞机的格子，并把其置0，得到状态ss，那么s和ss连一条有向边。然后就可以利用这个状态转移图直接dfs了。

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;struct edge{    int v,p;    edge(){}    edge(int v,int p):v(v),p(p){}};vector
         
           G[256];int dx[]={
   0,1,0,-1},    dy[]={
   1,0,-1,0};int mat[5][5],vis[5][5],flag[1<<8],ans;void predfs(int s,int x,int y){    vis[x][y]=1;    if(mat[x][y]==2){        int v=s,p=(x-1)*3+y-1;        v^=(1<<(8-p));        G[s].push_back(edge(v,p));        return;    }    for(int i=0;i<4;i++){        int tx=x+dx[i],ty=y+dy[i];        if(mat[tx][ty]&&!vis[tx][ty])            predfs(s,tx,ty);    }}void dfs(int s,int color){    if(!s){
   if(!flag[color]) flag[color]=1,ans++;return;}    for(int i=0;i
          
           >=1; memset(vis,0,sizeof(vis)); predfs(s,1,1); } int cas=0; char str[3][5]; while(scanf("%s%s%s",str[0],str[1],str[2])+1){ int s=0; for(int i=0;i<3;i++) for(int j=0;j<3;j++){ mat[i+1][j+1]=(str[i][j]=='*'?1:(str[i][j]=='B'?2:3)); s=s*2+(str[i][j]!='*'); } ans=0; memset(flag,0,sizeof(flag)); dfs(s,0); printf("Case %d: %d\n",++cas,ans); } return 0;}
          
         
        
       
      
     

 

D

给定n种颜色的石头，每种颜色有si颗，同种颜色的石头不区分。问能构成多少种不同的石头序列（不同的序列是指：1.石头数不同；2.石头数相同，至少一个位置的石头颜色不同）　　dp[ i ][ j ]表示：考虑前i种石头构成的长度为j的序列的个数。　　转台转移方程：　　　　dp[ i ][ j ] = dp[ i-1 ][ j ];   //未放入第i种颜色的石头　　　　for  k := 1 ~ min( j , s[ i ] ) //放入k个第i种颜色的石头　　　　　　dp[ i ][ j ] += dp[ i-1 ][ j - k ] * C[ j ][ k ]; 　　　其中C[ n ][ m ]表示组合数。

#include
     
      #include
      
       #include
       
        #include
        
         #define ll  long long#define mod  1000000007using namespace std;long long dp[110][10010],s[110],c[10010][110],n;void init(long long n,long long m){    long long i,j;    memset(c,0,sizeof(c));    for(i=0;i<=m;i++)c[0][i]=c[1][i]=1;    for(i=0;i<=m;i++)c[i][i]=1;    for(i=0;i<=n;i++)c[i][0]=1;    for(i=1;i<=n;i++)    {        for(j=1;j<=m;j++)        {            if(i!=j)            c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;        }    }}void DP(){    memset(dp,0,sizeof(dp)); long long t=s[1],m; for(int i=1; i<=n; i++)   dp[i][0]=1; for(int j=1; j<=s[1]; j++)      dp[1][j]=1; for(int i=2; i<=n; i++){    t+=s[i]; for(int j=1; j<=t; j++){     m=min((ll)j,s[i]);     dp[i][j]=dp[i-1][j]; for(int k=1; k<=m; k++){    dp[i][j]+=dp[i-1][j-k]*c[j][k];     dp[i][j]%=mod;   }  } }}int main(){    init(10000,100);    long long l=0,i,j,k,len,h,ans;    while(scanf("%lld",&n)!=EOF)    {        l++;        h=0;        for(i=1;i<=n;i++){scanf("%lld",&s[i]);h+=s[i];};         DP();        ans=0;        for(j=1;j<=h;j++)        {            ans+=dp[n][j];            ans%=mod;        }        printf("Case %lld: %lld\n",l,ans);        //cout<
         
          <
         
        
       
      
     

E 数位dp吧，只不过写起来有点繁琐，先预处理一下会好很多。把每一位都预处理出min和max，表示这一位的数只能从min到max，比如问号就是0-9。并且对于位数不够字符串，把高位补成0。然后dp[i][j]表示从低到高至第i位并进位为j的时候的方案数。最后答案为dp[n][0]。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #define ll long longusing namespace std;int n;int d[3][20],u[3][20];ll dp[20][2];void init(string s){    string a,b,c;    int i,j;    memset(d,0,sizeof(d));    memset(u,0,sizeof(u));    for(i=0;s[i]!='+';i++);    for(j=0;s[j]!='=';j++);    a=s.substr(0,i);    b=s.substr(i+1,j-i-1);    c=s.substr(j+1,s.size()-j-1);    reverse(a.begin(),a.end());    reverse(b.begin(),b.end());    reverse(c.begin(),c.end());        n=max(a.size(),max(b.size(),c.size()));        for(i=0;i
          
           1&&a[a.size()-1]=='?') d[0][a.size()-1]=1; for(i=0;i
           
            1&&b[b.size()-1]=='?') d[1][b.size()-1]=1; for(i=0;i
            
             1&&c[c.size()-1]=='?') d[2][c.size()-1]=1;}void gao(){ memset(dp,0,sizeof(dp)); dp[0][0]=1; for(int i=0;i
             
              =d[2][i]&&t<=u[2][i]) dp[i+1][tt]+=dp[i][j]; } }}int main(){ int cas=0; string s; while(cin>>s){ init(s); gao(); printf("Case %d: %lld\n",++cas,dp[n][0]); } return 0;}
             
            
           
          
         
        
       
      
     

F和I都可以用神题形容了。。

F:7k+:

首先看奇度点个数。

如果有4个，那么两条边必然四个端点为这四个点。枚举判断即可。

如果有2个，令这两个点为left和right。

对于所有存在边(x, left)和(x, right)的x，删掉这两条边。

在删除后的图中，对于所有在原图中存在边(x, left)和(x, right)的x，如果

(1) x与left连通   或

(2) x与right连通  或

(3) x与某个点y连通，且原图中存在边(y, left)和(y, right)

那么如果存在一个z，使得原图中删除(z, left)和(z, right)是合法的，那么，原图中删除(x, left)和(x, right)也是合法的，且合法的x只有这三种情况。

取最小的边对((x, left), (x, right))，判断是否可行即可。

 

如果奇点个数是其他情况，都无解。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #define N 200009using namespace std;int n,m;int a[N],b[N],d[N];int tf[N],vis[N],fa[N];typedef pair
          
            PII;typedef pair
           
            
             ,int > PPI;int find(int a){ return fa[a]==a?a:fa[a]=find(fa[a]);}bool union_set(int a,int b){ a=find(a),b=find(b); if(a==b) return false; fa[a]=b; return true;}bool check(){ int c=n-1; for(int i=1;i<=n;i++) fa[i]=i; for(int i=m;i;i--) if(!tf[i]) c-=union_set(a[i],b[i]); return !c;}int main(){ int cas=0; while(scanf("%d%d",&n,&m)+1){ printf("Case %d: ",++cas); memset(tf,0,sizeof(tf)); memset(d,0,sizeof(d)); memset(vis,0,sizeof(vis)); for(int i=1;i<=m;i++){ scanf("%d%d",a+i,b+i); d[a[i]]^=1; d[b[i]]^=1; } if(!check()){puts("NO");continue;} vector
             
               odd; for(int i=1;i<=n;i++) if(d[i]) odd.push_back(i); if(!odd.size()||odd.size()>4){puts("NO");continue;} if(odd.size()==2) { int u=odd[0],v=odd[1]; for(int i=1;i<=m;i++){ if(a[i]==u) vis[b[i]]=i; else if(b[i]==u) vis[a[i]]=i; } vector
              
                del; for(int i=1;i<=m;i++){ if(a[i]==v&&vis[b[i]]){ tf[i]=tf[vis[b[i]]]=1; del.push_back(PPI(PII(min(i,vis[b[i]]),max(i,vis[b[i]])),b[i])); } else if(b[i]==v&&vis[a[i]]){ tf[i]=tf[vis[a[i]]]=1; del.push_back(PPI(PII(min(i,vis[a[i]]),max(i,vis[a[i]])),a[i])); } } check(); sort(del.begin(),del.end()); memset(vis,0,sizeof(vis)); for(int i=0;i
               

v; for(int i=1;i<=m;i++) if(d[a[i]]&&d[b[i]]) v.push_back(i); sort(v.begin(),v.end()); int ok=0,e1,e2; for(int i=0;!ok&&i