NOIP2015
T1跳石头
二分，没啥好说的，不知道为啥(n=0,k=0)的特殊数据会错。
T2子串
(f[i][j][p][0/1])表示(a)串到第(i)个字符，(b)串匹配到第(j)个字符，一共划分成(p)部分，第(i)个字符用((1))没用((0))的方案数。
(if(a[i]==b[j]))
(f[i][j][p][0]=f[i-1][j][p][0]+f[i-1][j][p][1])
(f[i][j][p][1]=f[i-1][j-1][p][1]+f[i-1][j-1][p-1][0]+f[i-1][j-1][p-1][1])
....感觉和代码一样了啊，不写了
#include<iostream>
#include<cstdio>
#include<cstring>
#define mod 1000000007
using namespace std;
const int N = 1005;
int n,m,k,f[2][205][205][2];
char a[N],b[N];
int val=1;
inline int read()
{
int ans=0,w=1;
char c=getchar();
while((c<'0'||c>'9')&&c!='-') c=getchar();
if(c=='-') { w=-1; c=getchar(); }
while(c>='0'&&c<='9')
{ ans=ans*10+c-'0'; c=getchar(); }
return ans*w;
}
int main()
{
freopen("substring.in","r",stdin);
freopen("substring.out","w",stdout);
n=read(); m=read(); k=read();
scanf("%s%s",a+1,b+1);
f[0][0][0][0]=f[1][0][0][0]=1;
for(int i=1;i<=n;i++,val^=1)
for(int j=1;j<=m;j++)
for(int p=1;p<=k;p++)
{
if(a[i]==b[j])
{
f[val][j][p][0]=(f[val^1][j][p][0]+f[val^1][j][p][1])%mod;
f[val][j][p][1]=(f[val^1][j-1][p][1]+(f[val^1][j-1][p-1][1]+f[val^1][j-1][p-1][0])%mod)%mod;
}
else
{
f[val][j][p][0]=(f[val^1][j][p][0]+f[val^1][j][p][1])%mod;
f[val][j][p][1]=0;
}
}
printf("%d
",f[n&1][m][k][0]+f[n&1][m][k][1]);
return 0;
}
T3运输计划
思路：最大中最小（最小中最大），百分之90可以二分。二分一个最长的时间(k)。这样就转化成了可行性问题。
关键是(check)函数怎么写。
用到了树上差分的知识。其中有一个很巧妙地合并方法：按构建顺序编个号，按这个编号的顺序由大到小向上合并，即保证先合并了深度深的点，又好写。
继续说(check),对于长度大于(k)的路径，用每条路径修改差分数组，记录一下他们的最大值(maxx)和条数(cnt)。在所有的路径中，只要有一条路径(i)被这(cnt)条路径都经过，并且(maxx-val[i]<=k),就(return) (true)。否则(return) (false)。
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int N = 300005;
int n,m,head[N],tot,id[N],f[N][21],dep[N],lc[N];
int val[N],dis[N],sum[N],u[N],v[N],len[N],cnt;
struct edge{
int node,next,data;
}e[N<<1];
inline int read()
{
int ans=0,w=1;
char c=getchar();
while((c<'0'||c>'9')&&c!='-') c=getchar();
if(c=='-') { w=-1; c=getchar(); }
while(c>='0'&&c<='9')
{ ans=ans*10+c-'0'; c=getchar(); }
return ans*w;
}
void add(int x,int y,int z)
{
e[++tot].node=y; e[tot].next=head[x];
e[tot].data=z; head[x]=tot;
}
void dfs(int u,int fa)
{
dep[u]=dep[fa]+1;
f[u][0]=fa;
id[++cnt]=u;
for(int i=head[u];i;i=e[i].next)
{
int v=e[i].node;
if(v==fa) continue;
dis[v]=dis[u]+e[i].data;
val[v]=e[i].data;
dfs(v,u);
}
}
void work()
{
for(int i=1;i<=18;i++)
for(int j=1;j<=n;j++)
f[j][i]=f[f[j][i-1]][i-1];
}
int lca(int x,int y)
{
if(dep[x]<dep[y]) swap(x,y);
for(int i=18;i>=0;i--)
if(dep[f[x][i]]>=dep[y])
x=f[x][i];
if(x==y) return x;
for(int i=18;i>=0;i--)
if(f[x][i]!=f[y][i])
x=f[x][i],y=f[y][i];
return f[x][0];
}
bool check(int k)
{
for(int i=1;i<=n;i++) sum[i]=0;
int maxx=0,tmp=0;
for(int i=1;i<=m;i++)
if(len[i]>k)
{
++tmp;
++sum[u[i]]; ++sum[v[i]];
sum[lc[i]]-=2;
maxx=max(maxx,len[i]);
}
for(int i=n;i>=0;i--)
sum[f[id[i]][0]]+=sum[id[i]];
for(int i=1;i<=n;i++)
if(sum[i]>=tmp&&maxx-val[i]<=k)
return true;
return false;
}
int main()
{
freopen("transport.in","r",stdin);
freopen("transport.out","w",stdout);
n=read(); m=read();
int x,y,z;
for(int i=1;i<n;i++)
{
x=read(); y=read(); z=read();
add(x,y,z); add(y,x,z);
}
dfs(1,0);
work();
int l=0,r=0,ans;
for(int i=1;i<=m;i++)
{
u[i]=read(); v[i]=read();
lc[i]=lca(u[i],v[i]);
len[i]=dis[u[i]]+dis[v[i]]-2*dis[lc[i]];
r=max(r,len[i]);
}
while(l<=r)
{
int mid=(l+r)>>1;
if(check(mid)) ans=mid,r=mid-1;
else l=mid+1;
}
printf("%d
",ans);
return 0;
}