先扔一份写的超级详细的题解。         

（感觉自己并没有什么写题解的必要啊……做点补充好了，顺便扔代码

D1T1.神奇的幻方

1 #include
      
        2 #include
       
         3 #include
        
          4 using namespace std; 5 int n,a[41][41]; 6 int main() 7 { 8     scanf("%d",&n); 9     int mid=n/2+1,x=1,y=mid;10     a[1][mid]=1;11     for(int i=2;i<=n*n;i++)12     {13         if(x==1&&y!=n)x=n,y++;14         else if(x!=1&&y==n)x--,y=1;15         else if(x==1&&y==n)x++;16         else17         {18             if(a[x-1][y+1])x++;19             else x--,y++;20         }21         a[x][y]=i;22     }23     for(int i=1;i<=n;i++)24     {25         for(int j=1;j<=n;j++)26             printf("%d ",a[i][j]);27         printf("\n");28     }29     return 0;30 }
        
       
      

D1T2.信息传递

拓扑排序，找到最短环的长度。

1 #include
      
        2 #include
       
         3 #include
        
          4 using namespace std; 5 const int N=200050; 6 int n,to[N],in[N],ans=0x3f3f3f3f; 7 bool f[N]; 8 int read() 9 {10     int x=0,f=1;char c=getchar();11     while(c<'0'||c>'9'){
    if(c=='-')f=-1;c=getchar();}12     while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}13     return x*f;14 }15 int main()16 {17     n=read();18     for(int i=1;i<=n;i++)19         to[i]=read(),in[to[i]]++;20     for(int i=1;i<=n;i++)21         if(in[i]==0)in[to[i]]--;22     for(int i=1;i<=n;i++)23     {24         if(in[i]==0||f[i])continue;25         int st=i,ed=i,sum=0;26         f[i]=true;27         while(to[ed]!=st)28             sum++,ed=to[ed],f[ed]=true;29         ans=min(ans,sum+1); 30     }31     printf("%d",ans); 32     return 0;33 }
        
       
      

D1T3.斗地主

一道真·很不想写的题。留个坑？回来填坑了。

比想象中的好写……其实就是dfs，vijos上的100组数据是真的有意思orz

注意A的转换，以及三带二不能带双王。

1 #include
      
        2 #include
       
         3 #include
        
          4 using namespace std; 5 const int inf=0x3f3f3f3f; 6 int T,n,x,y,ans,num[20],a[5];  7 int read() 8 { 9     int x=0,f=1;char c=getchar();10     while(c<'0'||c>'9'){
    if(c=='-')f=-1;c=getchar();}11     while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}12     return x*f;13 }14 int go()15 {16     bool f=false;17     if(num[0]==2)f=true;18     memset(a,0,sizeof(a));19     for(int i=0;i<=13;i++)a[num[i]]++;20     int sum=0;21     while(a[4]&&a[2]>=2)a[4]--,a[2]-=2,f=false,sum++;22     while(a[4]&&a[1]>=2)a[4]--,a[1]-=2,sum++;23     while(a[4]&&a[2])a[4]--,a[2]--,f=false,sum++;24     if(f)sum++,a[2]--;25     while(a[3]&&a[2])a[3]--,a[2]--,sum++;26     while(a[3]&&a[1])a[3]--,a[1]--,sum++;27     return sum+a[1]+a[2]+a[3]+a[4];28 }29 void dfs(int step)30 {31     if(step>=ans)return;32     int t=go();33     ans=min(ans,t+step);34     for(int i=2;i<=13;i++)35     {36         int next=i;37         while(num[next]>=3)next++;38         if(next-i>=2)39         {40             for(int j=i+1;j<=next-1;j++)41             {42                 for(int k=i;k<=j;k++)num[k]-=3;43                 dfs(step+1);44                 for(int k=i;k<=j;k++)num[k]+=3;45             }46         }47     }48     for(int i=2;i<=13;i++)49     {50         int next=i;51         while(num[next]>=2)next++;52         if(next-i>=3)53         {54             for(int j=i+2;j<=next-1;j++)55             {56                 for(int k=i;k<=j;k++)num[k]-=2;57                 dfs(step+1);58                 for(int k=i;k<=j;k++)num[k]+=2;59             }60         }61     }62     for(int i=2;i<=13;i++)63     {64         int next=i;65         while(num[next]>=1)next++;66         if(next-i>=5)67         {68             for(int j=i+4;j<=next-1;j++)69             {70                 for(int k=i;k<=j;k++)num[k]--;71                 dfs(step+1);72                 for(int k=i;k<=j;k++)num[k]++;73             }74         }75     }76 }77 int main()78 {79     T=read();n=read();80     while(T--)81     {82         memset(num,0,sizeof(num));83         for(int i=1;i<=n;i++)84         {85             x=read();y=read();86             if(x==1)x=13;87             else if(x)x--; 88             num[x]++;89         }90         ans=inf;91         dfs(0);92         printf("%d\n",ans);93     }94     return 0;95 }
        
       
      

D2T1.跳石头

其实我第一次看到这道题的时候它叫河中跳房子……

先二分出答案，再判断答案是否合法（即需要移走的岩石数是否小于等于M

1 #include
      
        2 #include
       
         3 #include
        
          4 using namespace std; 5 int len,n,m,ans,a[50010]; 6 int read() 7 { 8     int x=0,f=1;char c=getchar(); 9     while(c<'0'||c>'9'){
    if(c=='-')f=-1;c=getchar();}10     while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}11     return x*f;12 }13 bool check(int mid)14 {15     int base=0,num=0;16     for(int i=1;i<=n+1;i++)17     {18         if(a[i]-base
         
          >1;32         if(check(mid))ans=mid,l=mid+1;33         else r=mid-1; 34     }35     printf("%d",ans);36     return 0;37 }
         
        
       
      

D2T2.子串

DP状态转移方程及解析详见开头题解（其实只是因为懒

这里提供自己写的一份滚动数组版本的代码。

1 #include
      
        2 #include
       
         3 #include
        
          4 using namespace std; 5 const int modd=1000000007; 6 const int N=1005; 7 const int M=205; 8 int n,m,K,f[2][M][M],s[2][M][M]; 9 char a[N],b[M];10 int read()11 {12     int x=0,f=1;char c=getchar();13     while(c<'0'||c>'9'){
    if(c=='-')f=-1;c=getchar();}14     while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}15     return x*f;16 }17 int main()18 {19     n=read();m=read();K=read();20     scanf("%s%s",a,b);21     s[0][0][0]=s[1][0][0]=1;22     for(int i=1;i<=n;i++)23     {24         int ii=i%2;25         for(int j=1;j<=m;j++)26             if(a[i-1]==b[j-1])27                 for(int k=1;k<=min(j,K);k++)28                 {29                     f[ii][j][k]=(s[ii^1][j-1][k-1]+f[ii^1][j-1][k])%modd;30                     s[ii][j][k]=(s[ii^1][j][k]+f[ii][j][k])%modd;31                 }32             else33                 for(int k=1;k<=min(j,K);k++)34                 {35                     f[ii][j][k]=0;36                     s[ii][j][k]=s[ii^1][j][k];37                 }38     }39     printf("%d",s[n%2][m][K]);40     return 0;41 }
        
       
      

D2T3.运输计划

我们的大体思路依然是二分答案 → 判断是否合法。

首先，建树，dfs一发。因为我们后面需要树上倍增求最近公共祖先，所以要把一些会用到的信息先处理好。

需要特别注意的是，我们用v[i]代表结点i与其父亲结点的连边的权值。

然后，我们把每个运输计划起点、终点的LCA以及路径长度先预处理出来。

对于二分出来的每个ans，我们可能需要将一条边边权赋为0来使所有方案的路径长度都小于或等于ans。倘若ans合法，则这条边满足以下条件：位于所有路径长度大于ans的计划的路径交集里，且权值大于路径长度最长的那条边-ans的值。否则ans不合法。

我们选择用sum数组维护树上前缀和来求交集，sum[i]代表结点i与其父亲结点的连边在所有路径长度大于ans的计划中出现的次数。若sum[i]=路径长度大于ans的计划的数量，则结点i与其父亲结点的连边在交集里。二分答案之后的判定过程为：O（m）扫一遍方案，对于所有路径长度大于我们二分出来的ans的方案，起点、终点sum+1，他们的LCAsum-2，然后再求前缀和。至于为什么要这么做……画图易得：如果结点i与其父亲结点的连边在方案x中，则方案x的起点或终点有且只有一个在结点i的子树内。然后就很简单明了了吧。

具体实现看代码咯。

1 #include
      
        2 #include
       
         3 #include
        
          4 using namespace std; 5 const int N=700010; 6 int n,m,cnt,a,b,t; 7 int head[N],fa[N],deep[N],dis[N],x[N][20],st[N],ed[N],lca[N],dist[N],sum[N],v[N]; 8 bool f[N]; 9 struct edge{
    int next,to,w;}e[N];10 int read()11 {12     int x=0,f=1;char c=getchar();13     while(c<'0'||c>'9'){
    if(c=='-')f=-1;c=getchar();}14     while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}15     return x*f;16 }17 void insert(int u,int v,int w)18 {19     cnt++;e[cnt].to=v;e[cnt].w=w;e[cnt].next=head[u];head[u]=cnt;20 }21 void dfs(int k)22 {23     f[k]=true;24     for(int i=1;(1<
         
          <=deep[k];i++)25         x[k][i]=x[x[k][i-1]][i-1];26     for(int i=head[k];i;i=e[i].next)27     {28         if(!f[e[i].to])29         {30             x[e[i].to][0]=k;31             deep[e[i].to]=deep[k]+1; 32             v[e[i].to]=e[i].w;33             dis[e[i].to]=dis[k]+e[i].w;34             dfs(e[i].to);35         }36     }37 }38 int find(int ri,int rj)39 {40     if(deep[ri]
          
           =0;i--)46         if((1<
           
            <=deep[rj]&&x[ri][i]!=x[rj][i])47 ri=x[ri][i],rj=x[rj][i];48 return x[ri][0];49 }50 void query(int k)51 {52 for(int i=head[k];i;i=e[i].next)53 if(e[i].to!=x[k][0])54 {55 query(e[i].to);56 sum[k]+=sum[e[i].to];57 }58 }59 bool check(int ans)60 {61 int cntt=0,cutt=0;62 for(int i=1;i<=n;i++)sum[i]=0;63 for(int i=1;i<=m;i++)64 if(dist[i]>ans)65 {66 cntt++;cutt=max(cutt,dist[i]-ans);67 sum[st[i]]++;sum[ed[i]]++;sum[lca[i]]-=2;68 }69 query(1);70 for(int i=1;i<=n;i++)71 if(sum[i]==cntt&&v[i]>=cutt)return true;72 return false;73 }74 int main()75 {76 n=read();m=read();77 for(int i=1;i
            
             >1;94 if(check(mid))R=mid-1;95 else L=mid+1;96 }97 printf("%d\n",L);98 return 0;99 }