（感觉自己并没有什么写题解的必要啊……做点补充好了，顺便扔代码
D1T1.神奇的幻方
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,a[][];
int main()
{
scanf("%d",&n);
int mid=n/+,x=,y=mid;
a[][mid]=;
for(int i=;i<=n*n;i++)
{
if(x==&&y!=n)x=n,y++;
else if(x!=&&y==n)x--,y=;
else if(x==&&y==n)x++;
else
{
if(a[x-][y+])x++;
else x--,y++;
}
a[x][y]=i;
}
for(int i=;i<=n;i++)
{
for(int j=;j<=n;j++)
printf("%d ",a[i][j]);
printf("\n");
}
return ;
}
D1T2.信息传递
拓扑排序，找到最短环的长度。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=;
int n,to[N],in[N],ans=0x3f3f3f3f;
bool f[N];
int read()
{
int x=,f=;char c=getchar();
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
}
int main()
{
n=read();
for(int i=;i<=n;i++)
to[i]=read(),in[to[i]]++;
for(int i=;i<=n;i++)
if(in[i]==)in[to[i]]--;
for(int i=;i<=n;i++)
{
if(in[i]==||f[i])continue;
int st=i,ed=i,sum=;
f[i]=true;
while(to[ed]!=st)
sum++,ed=to[ed],f[ed]=true;
ans=min(ans,sum+);
}
printf("%d",ans);
return ;
}
D1T3.斗地主
一道真·很不想写的题。留个坑？回来填坑了。
比想象中的好写……其实就是dfs，vijos上的100组数据是真的有意思orz
注意A的转换，以及三带二不能带双王。
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int inf=0x3f3f3f3f;
int T,n,x,y,ans,num[],a[];
int read()
{
int x=,f=;char c=getchar();
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
}
int go()
{
bool f=false;
if(num[]==)f=true;
memset(a,,sizeof(a));
for(int i=;i<=;i++)a[num[i]]++;
int sum=;
while(a[]&&a[]>=)a[]--,a[]-=,f=false,sum++;
while(a[]&&a[]>=)a[]--,a[]-=,sum++;
while(a[]&&a[])a[]--,a[]--,f=false,sum++;
if(f)sum++,a[]--;
while(a[]&&a[])a[]--,a[]--,sum++;
while(a[]&&a[])a[]--,a[]--,sum++;
return sum+a[]+a[]+a[]+a[];
}
void dfs(int step)
{
if(step>=ans)return;
int t=go();
ans=min(ans,t+step);
for(int i=;i<=;i++)
{
int next=i;
while(num[next]>=)next++;
if(next-i>=)
{
for(int j=i+;j<=next-;j++)
{
for(int k=i;k<=j;k++)num[k]-=;
dfs(step+);
for(int k=i;k<=j;k++)num[k]+=;
}
}
}
for(int i=;i<=;i++)
{
int next=i;
while(num[next]>=)next++;
if(next-i>=)
{
for(int j=i+;j<=next-;j++)
{
for(int k=i;k<=j;k++)num[k]-=;
dfs(step+);
for(int k=i;k<=j;k++)num[k]+=;
}
}
}
for(int i=;i<=;i++)
{
int next=i;
while(num[next]>=)next++;
if(next-i>=)
{
for(int j=i+;j<=next-;j++)
{
for(int k=i;k<=j;k++)num[k]--;
dfs(step+);
for(int k=i;k<=j;k++)num[k]++;
}
}
}
}
int main()
{
T=read();n=read();
while(T--)
{
memset(num,,sizeof(num));
for(int i=;i<=n;i++)
{
x=read();y=read();
if(x==)x=;
else if(x)x--;
num[x]++;
}
ans=inf;
dfs();
printf("%d\n",ans);
}
return ;
}
D2T1.跳石头
其实我第一次看到这道题的时候它叫河中跳房子……
先二分出答案，再判断答案是否合法（即需要移走的岩石数是否小于等于M
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int len,n,m,ans,a[];
int read()
{
int x=,f=;char c=getchar();
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
}
bool check(int mid)
{
int base=,num=;
for(int i=;i<=n+;i++)
{
if(a[i]-base<mid)num++;
else base=a[i];
}
return num<=m;
}
int main()
{
len=read();n=read();m=read();
for(int i=;i<=n;i++)a[i]=read();
a[n+]=len;
int l=,r=len;
while(l<=r)
{
int mid=(l+r)>>;
if(check(mid))ans=mid,l=mid+;
else r=mid-;
}
printf("%d",ans);
return ;
}
D2T2.子串
DP状态转移方程及解析详见开头题解（其实只是因为懒
这里提供自己写的一份滚动数组版本的代码。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int modd=;
const int N=;
const int M=;
int n,m,K,f[][M][M],s[][M][M];
char a[N],b[M];
int read()
{
int x=,f=;char c=getchar();
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
}
int main()
{
n=read();m=read();K=read();
scanf("%s%s",a,b);
s[][][]=s[][][]=;
for(int i=;i<=n;i++)
{
int ii=i%;
for(int j=;j<=m;j++)
if(a[i-]==b[j-])
for(int k=;k<=min(j,K);k++)
{
f[ii][j][k]=(s[ii^][j-][k-]+f[ii^][j-][k])%modd;
s[ii][j][k]=(s[ii^][j][k]+f[ii][j][k])%modd;
}
else
for(int k=;k<=min(j,K);k++)
{
f[ii][j][k]=;
s[ii][j][k]=s[ii^][j][k];
}
}
printf("%d",s[n%][m][K]);
return ;
}
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的子树内。然后就很简单明了了吧。
具体实现看代码咯。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=;
int n,m,cnt,a,b,t;
int head[N],fa[N],deep[N],dis[N],x[N][],st[N],ed[N],lca[N],dist[N],sum[N],v[N];
bool f[N];
struct edge{int next,to,w;}e[N];
int read()
{
int x=,f=;char c=getchar();
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
}
void insert(int u,int v,int w)
{
cnt++;e[cnt].to=v;e[cnt].w=w;e[cnt].next=head[u];head[u]=cnt;
}
void dfs(int k)
{
f[k]=true;
for(int i=;(<<i)<=deep[k];i++)
x[k][i]=x[x[k][i-]][i-];
for(int i=head[k];i;i=e[i].next)
{
if(!f[e[i].to])
{
x[e[i].to][]=k;
deep[e[i].to]=deep[k]+;
v[e[i].to]=e[i].w;
dis[e[i].to]=dis[k]+e[i].w;
dfs(e[i].to);
}
}
}
int find(int ri,int rj)
{
if(deep[ri]<deep[rj])swap(ri,rj);
int d=deep[ri]-deep[rj];
for(int i=;(<<i)<=d;i++)
if((<<i)&d)ri=x[ri][i];
if(ri==rj)return ri;
for(int i=;i>=;i--)
if((<<i)<=deep[rj]&&x[ri][i]!=x[rj][i])
ri=x[ri][i],rj=x[rj][i];
return x[ri][];
}
void query(int k)
{
for(int i=head[k];i;i=e[i].next)
if(e[i].to!=x[k][])
{
query(e[i].to);
sum[k]+=sum[e[i].to];
}
}
bool check(int ans)
{
int cntt=,cutt=;
for(int i=;i<=n;i++)sum[i]=;
for(int i=;i<=m;i++)
if(dist[i]>ans)
{
cntt++;cutt=max(cutt,dist[i]-ans);
sum[st[i]]++;sum[ed[i]]++;sum[lca[i]]-=;
}
query();
for(int i=;i<=n;i++)
if(sum[i]==cntt&&v[i]>=cutt)return true;
return false;
}
int main()
{
n=read();m=read();
for(int i=;i<n;i++)
{
a=read();b=read();t=read();
insert(a,b,t);insert(b,a,t);
}
dfs();
for(int i=;i<=m;i++)
{
st[i]=read();ed[i]=read();
lca[i]=find(st[i],ed[i]);
dist[i]=dis[st[i]]+dis[ed[i]]-*dis[lca[i]];
}
int L=,R=;
for(int i=;i<=m;i++)R=max(R,dist[i]);
while(L<=R)
{
int mid=(L+R)>>;
if(check(mid))R=mid-;
else L=mid+;
}
printf("%d\n",L);
return ;
}