T1 跳石头
二分即可
#include<bits/stdc++.h>
using namespace std;
int n,m,d,l,r,mid,ans,a[100000];
bool judge(int x){
int tot=0,i=0,now=0;
while (i<n+1) {
i++;
if(a[i]-a[now]<x) tot++;
else now=i;
}
return tot<=m;
}
int main(){
freopen("stone.in","r",stdin);
freopen("stone.out","w",stdout);
cin>>d>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
a[n+1]=d,l=1,r=d;
while(l<=r){
mid=(l+r)/2;
if (judge(mid)){
ans=mid;
l=mid+1;
}
else r=mid-1;
}
cout<<ans;
return 0;
}
T2 子串
DP。我觉得和背包的思路挺像的一道题。用f1[i][j][k]表示两串分别到a[i]，b[j]，且a[i]必须使用时，用了k个子串的方案数。f2[i][j][k]表示无论用不用当前字符(A[i])时的方案数总和。那么转移方程就显而易见了：
f1[i][j][k]=f1[i-1][j-1][k-1]+f2[i-1][j-1][k]
f2[i][j][k]=f2[i][j][k]+f[i][j][k]
我们发现i这个维度是可以滚动的，于是就节省了一维空间
#include<bits/stdc++.h>
using namespace std;
int mod=1000000007;
char a[1001],b[201];
int n,m,k1,y,ans,f1[1001][200],f2[201][201];
int main(){
//freopen("substring.in","r",stdin);
//freopen("substring.out","w",stdout);
cin>>n>>m>>k1;
cin>>a>>b;
f1[0][0]=f2[0][0]=1;
for (int i=1; i<=n; i++)
for (int j=m; j>=1; j--)
for (int k=1; k<=k1; k++)
{
if (a[i-1]!=b[j-1]) {f1[j][k]=0; continue;}
f1[j][k]=(f1[j-1][k]%mod+f2[j-1][k-1]%mod)%mod;
f2[j][k]=(f2[j][k]%mod+f1[j][k]%mod)%mod;
}
printf("%d",f2[m][k1]);
return 0;
}
T3 运输计划
先Tarjan求m对点的lca，然后二分答案，把所有大于二分的答案的路径记录，判断有没有一条边被所有大于二分的答案的路径所重复，如果有，那么这条边必须大于等于最大的路径减二分的答案，如果上述两个条件都符合那么这个二分的答案就是合法的，细节参考代码。如果TLE加个快读即可。
#include<cstdio>
#include<vector>
#include<algorithm>
#include<cstdlib>
#include<cstring>
using namespace std;
typedef pair<int,int>PP;
struct node{
int to,dist,nu;
};
struct P{
int a,b,c;
};
int q[300002],n,m,hh[300002],ans[300002],anss[300002],lca[300002],h[300002],fa[300002],left,right,mid,f[300002];
P y[300002];
bool fl[300002];
vector<node>s[300002];
vector<PP>t[300002];
int find(int x){
if (fa[x]==x)return x;
else return fa[x]=find(fa[x]);
}
void dfs(int x,int tt){
anss[x]=tt;fa[x]=x;
for (int i=0;i<s[x].size();i++)
if (!fa[s[x][i].to])
{
h[s[x][i].to]=s[x][i].nu;
dfs(s[x][i].to,tt+s[x][i].dist);
fa[s[x][i].to]=find(x);
}
for (int i=0;i<t[x].size();i++)
if (fa[t[x][i].first])lca[t[x][i].second]=find(t[x][i].first);
}
void dfs(int x){//c++支持重载函数
for (int i=0;i<s[x].size();i++)
if (!fl[s[x][i].to])
{
fl[s[x][i].to]=1;
dfs(s[x][i].to);
f[h[x]]+=f[h[s[x][i].to]];
}
}
bool pd(int x){
int t=0,u,maxn=0;
memset(f,0,sizeof(f));
memset(fl,0,sizeof(fl));
for (int i=0;i<m;i++)
if (ans[i]>x){maxn=max(ans[i],maxn);q[t++]=i;}
if (!t)return true;
for (int i=0;i<t;i++)
{
u=q[i];
f[h[y[u].a]]++;//这条边+1
f[h[y[u].b]]++;//这条边+1
f[h[lca[u]]]-=2;//这条边-2，因为这条边虽然计算了两次，实际上一次都没有走到
}
dfs(1);
for (int i=1;i<n;i++)
if (f[i]==t && hh[i]>=maxn-x)return true;
return false;
}
int main()
{
scanf("%d%d",&n,&m);
int u,v,w,sum=0;
for (int i=1;i<n;i++)
{
scanf("%d%d%d",&u,&v,&w);sum+=w;
hh[i]=w;node g;
g.to=v;g.dist=w;g.nu=i;
s[u].push_back(g);
g.to=u;
s[v].push_back(g);
}
for (int i=0;i<m;i++)
{
scanf("%d%d",&y[i].a,&y[i].b);
t[y[i].a].push_back(PP(y[i].b,i));
t[y[i].b].push_back(PP(y[i].a,i));
}
dfs(1,0);
for (int i=0;i<m;i++)
ans[i]=anss[y[i].a]+anss[y[i].b]-2*anss[lca[i]];//a到b的距离等于1到a的距离+1到b的距离-1到lca(a,b)的距离
left=0;right=sum;
while(left<right)//二分答案
{
mid=(left+right)/2;
if (pd(mid))right=mid;
else left=mid+1;
}
printf("%d",right);
return 0;
}
