一道二分答案裸题，一道dp，一道各种裸题的混合（树上差分+二分答案+LCA）
stone:
二分查找裸题啊:
int check(int x)
{
int cnt=,last=;
for(int i=;i<=n;i++)
if(a[i]-a[last]<x) cnt++;//已经是最小值了，所以没有比他更小的，有更小的就要移开
else last=i;//推起走
if(cnt>m) return ;
return ;
} void find(int l,int r)
{
while(l<=r)
{
int mid=(l+r)>>;
if(check(mid))
{
ans=max(ans,mid);
l=mid+;//二分查找满足单调性，既然它满足，那么比它大的也可能满足，就往大的去推（比较是找最大值）
}
else r=mid-;
}
}
int main()
{
scanf("%d%d%d",&len,&n,&m);
for(int i=;i<=n;i++)
scanf("%d",&a[i]);
find(,len);
printf("%d",ans);
return ;
}
substring:
DP：考虑当前匹配成功与否
这种两个串一个一个挨着去找的有没有LIS,LCS的感觉——>大佬们就想到了dp（然而自己没有
状态
首先我们考虑设计状态。我们发现，为了保证无后效性的一位一位往后推，我们需要记录当前推到aa串的哪一个位置了；接着还有记录匹配了bb串的那几个字符。因为是按照原串顺序，所以相当于是即匹配bb的前几个字符。有这些还不够，我们还要记录划分了几个子串。最后，为了便于转移，我们还要标记一维0/1状态，表示aa串中的第ii个字符是否选入。
这样，我们就设计好了状态。我们记f_{i,j,p,v}fi,j,p,v表示到aa串的第ii个位置为止使用pp个子串匹配bb串前jj位字符且第ii个位置选或不选（vv）的方案数。
转移
设计好状态，不会转移怎么行。我们分情况考虑。
-
当a_i=b_jai=bj时：
f_{i,j,p,0}fi,j,p,0：由于这位不选，所以就是前面一位选和不选方案数之和，即f_{i,j,p,0}=f_{i-1,j,p,0}+f_{i-1,j,p,1}fi,j,p,0=fi−1,j,p,0+fi−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}fi,j,p,1=fi−1,j−1,p,1+fi−1,j−1,p−1,0+fi−1,j−1,p−1,1.
-
当a_i\ne b_jai≠bj时：
不选情况同上，即f_{i,j,p,0}=f_{i-1,j,p,0}+f_{i-1,j,p,1}fi,j,p,0=fi−1,j,p,0+fi−1,j,p,1.
由于选不了，自然就是00，即f_{i,j,p,1}=0fi,j,p,1=0.
优化空间
如果你读完状态设计之后又稍微思考就会发现，空间可能较大。空间不够怎么办？在luogu还好说，如果真的在NOIP，应该是不敢开1000\times200\times200\times2=8\times10^71000×200×200×2=8×107的数组吧。所以我们观察转移方程，发现每次转移只用到了前一位！于是我们把第一维很愉快地滚掉了。这样，空间复杂度就保证是O(mk)O(mk)了。那么时间呢？时间是O(n\cdot mk)O(n⋅mk)，但是时间不像空间，这个复杂度是可以接受的。于是，完整算法就结束了。
#pragma GCC optimize (2)
#include<bits/stdc++.h>
#define mod 1000000007
using namespace std;
typedef long long ll;
int n,m,k;
int a[],b[];
char aa[],bb[];
ll f[][][][]; int main()
{
cin>>n>>m>>k;
scanf("%s",aa);
scanf("%s",bb);
if(n<m)
{
printf("0\n");
return ;
}
for(int i=;i<n;++i) a[i+]=aa[i]-;
for(int i=;i<m;++i) b[i+]=bb[i]-;
f[][][][]=f[][][][]=;
for(int i=;i<=n;++i)
{
for(int j=;j<=m;++j)
{
for(int c=;c<=k;++c)
{
if(a[i]==b[j])
{
f[i%][j][c][]=(f[(i+)%][j][c][]+f[(i+)%][j][c][])%mod;
f[i%][j][c][]=(f[(i+)%][j-][c][]+f[(i+)%][j-][c-][]+f[(i+)%][j-][c-][])%mod;
}
else
{
f[i%][j][c][]=(f[(i+)%][j][c][]+f[(i+)%][j][c][])%mod;
f[i%][j][c][]=;
}
}
}
}
cout<<(f[n%][m][k][]+f[n%][m][k][])%mod<<endl;
return ;
}
为了避免&1，^1的麻烦用%2
1s极限：1e8