A:颜色问题
题目：http://ch.ezoj.tk/contest/CH%20Round%20%2358%20-%20OrzCC杯noip模拟赛day2/颜色问题
题解：算一下每个仆人到它的目的地的时间取max即可
代码：
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<string>
#define inf 1000000000
#define maxn 1500000
#define maxm 500+100
#define eps 1e-10
#define ll long long
#define pa pair<int,int>
#define for0(i,n) for(int i=0;i<=(n);i++)
#define for1(i,n) for(int i=1;i<=(n);i++)
#define for2(i,x,y) for(int i=(x);i<=(y);i++)
#define for3(i,x,y) for(int i=(x);i>=(y);i--)
#define mod 1000000007
using namespace std;
inline int read()
{
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=*x+ch-'';ch=getchar();}
return x*f;
}
int n,f[maxn],head[maxn];
struct edge{int go,next;}e[maxn];
int main()
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
n=read();
for1(i,n)
{
int x=read();
e[i].go=i;e[i].next=head[x];head[x]=i;
f[i]=inf;
}
for1(i,n)
{
int x=read();
for(int j=head[x];j;j=e[j].next)
{
int y=e[j].go;
if(y>=i)f[y]=min(f[y],y-i+);else f[y]=min(f[y],n-i+y+);
}
}
int ans=;
for1(i,n)ans=max(ans,f[e[i].go]);
printf("%d\n",ans==inf?-:ans);
return ;
}
B：树的问题
题目：http://ch.ezoj.tk/contest/CH%20Round%20%2358%20-%20OrzCC杯noip模拟赛day2/树的问题
题解：如果x和y的LCA不是其中任意一个，那么答案显然是s[x]+s[y]，画一下图就知道
否则不妨设LCA(x,y)=x，则ans=n-（s[son[x]]-s[y]) 其中son[x]是 x 走向 y的第一个点，画一下图就可以知道。。。
而son[x]不能dfs求，只要把y倍增上去即可。需要思考一下。
具体看代码
代码：
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<string>
#define inf 1000000000
#define maxn 300000
#define maxm 500+100
#define eps 1e-10
#define ll long long
#define pa pair<int,int>
#define for0(i,n) for(int i=0;i<=(n);i++)
#define for1(i,n) for(int i=1;i<=(n);i++)
#define for2(i,x,y) for(int i=(x);i<=(y);i++)
#define for3(i,x,y) for(int i=(x);i>=(y);i--)
#define mod 1000000007
using namespace std;
inline int read()
{
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=*x+ch-'';ch=getchar();}
return x*f;
}
int n,m,head[maxn],tot,fa[maxn],s[maxn],f[maxn][],dep[maxn];
struct edge{int go,next;}e[*maxn];
inline void insert(int x,int y)
{
e[++tot].go=y;e[tot].next=head[x];head[x]=tot;
e[++tot].go=x;e[tot].next=head[y];head[y]=tot;
}
void dfs(int x)
{
s[x]=;
for1(i,)
if((<<i)<=dep[x])f[x][i]=f[f[x][i-]][i-];
else break;
for(int i=head[x],y;i;i=e[i].next)
if(!dep[y=e[i].go])
{
dep[y]=dep[x]+;
f[y][]=x;
dfs(y);
s[x]+=s[y];
}
}
bool lca(int x,int y)
{
int ans=;
if(dep[x]<dep[y])swap(x,y);
int t=dep[x]-dep[y];
for0(i,)
if(t&(<<i))x=f[x][i];
return x==y;
}
int main()
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
n=read();m=read();
for1(i,n-)insert(read(),read());
dep[]=;
dfs();
while(m--)
{
int x=read(),y=read();
if(dep[x]>dep[y])swap(x,y);
if(!lca(x,y))printf("%d\n",s[x]+s[y]);
else
{
int t=dep[y]-dep[x]-,w=y;
for0(i,)if(t&(<<i))w=f[w][i];
printf("%d\n",n-(s[w]-s[y]));
}
}
return ;
}
C:比赛问题
题目：http://ch.ezoj.tk/contest/CH%20Round%20%2358%20-%20OrzCC杯noip模拟赛day2/比赛问题
题解：刚开始把题看简单了，直接一个n*m*k*k的DP。。。还感叹怎么这么水。。。
后来发现这k*k个方格的状态是有后效性的T_T
然后发现好像可以状压得70，但我感觉我写不出来或者写出来调不出来，然后就交了错误的程序弃疗了。。。
最后居然有40QAQ
代码：
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<string>
#define inf 1000000000
#define maxn 150
#define maxm 500+100
#define eps 1e-10
#define ll long long
#define pa pair<int,int>
#define for0(i,n) for(int i=0;i<=(n);i++)
#define for1(i,n) for(int i=1;i<=(n);i++)
#define for2(i,x,y) for(int i=(x);i<=(y);i++)
#define for3(i,x,y) for(int i=(x);i>=(y);i--)
#define mod 1000000007
using namespace std;
inline int read()
{
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=*x+ch-'';ch=getchar();}
return x*f;
}
int n,m,k,x,y,xx,yy,f[maxn][maxn];
bool a[maxn][maxn],b[maxn][maxn];
int main()
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
n=read();m=read();k=read();x=read();y=read();xx=read();yy=read();
for1(i,k)for1(j,k)
{
char ch=' ';
while(ch!=''&&ch!='')ch=getchar();
a[i][j]=ch=='';
}
for1(i,n)for1(j,m)
{
char ch=' ';
while(ch!='B'&&ch!='W')ch=getchar();
b[i][j]=ch=='W';
}
memset(f,,sizeof(f));
f[x][y]=;
for1(i,k)
for1(j,k)
if(a[i][j]&&b[x+i-][y+j-])f[x][y]++;
for2(i,x,xx)
for2(j,y,yy)
if(i!=x||j!=y)
{
int tmp=;
for1(ii,k-)
for1(jj,k)
if(a[ii][jj]&&!a[ii+][jj]&&b[i+ii-][j+jj-])tmp++;
for1(jj,k)if(a[k][jj]&&b[i+k-][j+jj-])tmp++;
f[i][j]=min(f[i][j],f[i-][j]+tmp);
tmp=;
for1(ii,k)
for1(jj,k-)
if(a[ii][jj]&&!a[ii][jj+]&&b[i+ii-][j+jj-])tmp++;
for1(ii,k)if(a[ii][k]&&b[i+ii-][j+k-])tmp++;
f[i][j]=min(f[i][j],f[i][j-]+tmp);
//cout<<i<<' '<<j<<' '<<f[i][j]<<endl;
}
printf("%d\n",f[xx][yy]);
return ;
}