提高组noip2015

一道二分答案裸题，一道dp，一道各种裸题的混合（树上差分+二分答案+LCA）

stone:

二分查找裸题啊:

int check(int x)
{
    int cnt=0,last=0;
    for(int i=1;i<=n;i++)
    if(a[i]-a[last]<x) cnt++;//已经是最小值了，所以没有比他更小的，有更小的就要移开
    else last=i;//推起走
    if(cnt>m) return 0;
    return 1;
}

void find(int l,int r)
{
    while(l<=r)
    {
        int mid=(l+r)>>1;
        if(check(mid)) 
        {
            ans=max(ans,mid);
            l=mid+1;//二分查找满足单调性，既然它满足，那么比它大的也可能满足，就往大的去推（比较是找最大值）
        }
        else r=mid-1;
    }
}
int main()
{
    scanf("%d%d%d",&len,&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    find(0,len);
    printf("%d",ans);
    return 0;
}

substring:

DP：考虑当前匹配成功与否

这种两个串一个一个挨着去找的有没有LIS,LCS的感觉——>大佬们就想到了dp（然而自己没有

状态

首先我们考虑设计状态。我们发现，为了保证无后效性的一位一位往后推，我们需要记录当前推到

这样，我们就设计好了状态。我们记 $f_{i,j,p,v}fi,j,p,v表示到aa串的第ii个位置为止使用pp个子串匹配bb串前jj位字符且第ii个位置选或不选（vv）的方案数。$

转移

设计好状态，不会转移怎么行。我们分情况考虑。

当 $a_i=b_jai=bj时：$
1. $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。$
2. 容易得到 $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 e b_jai≠bj时：$
1. 不选情况同上，即 $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.$
2. 由于选不了，自然就是 $00，即f_{i,j,p,1}=0fi,j,p,1=0.$

优化空间

如果你读完状态设计之后又稍微思考就会发现，空间可能较大。空间不够怎么办？在luogu还好说，如果真的在NOIP，应该是不敢开 $imes10^71000×200×200×2=8×107的数组吧。所以我们观察转移方程，发现每次转移只用到了前一位！于是我们把第一维很愉快地滚掉了。这样，空间复杂度就保证是O(mk)O(mk)了。那么时间呢？时间是O(ncdot 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[2005],b[2005];
char aa[2005],bb[2005];
ll f[2][205][205][2];


int main()
{
    cin>>n>>m>>k;
    scanf("%s",aa);
    scanf("%s",bb);
    if(n<m)
    {
        printf("0
");
        return 0;
    }
    for(int i=0;i<n;++i) a[i+1]=aa[i]-96;
    for(int i=0;i<m;++i) b[i+1]=bb[i]-96;
    f[1][0][0][0]=f[0][0][0][0]=1;
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=m;++j)
        {
            for(int c=1;c<=k;++c)
            {
                if(a[i]==b[j])
                {
                    f[i%2][j][c][0]=(f[(i+1)%2][j][c][0]+f[(i+1)%2][j][c][1])%mod;
                    f[i%2][j][c][1]=(f[(i+1)%2][j-1][c][1]+f[(i+1)%2][j-1][c-1][1]+f[(i+1)%2][j-1][c-1][0])%mod;
                }
                else
                {
                    f[i%2][j][c][0]=(f[(i+1)%2][j][c][0]+f[(i+1)%2][j][c][1])%mod;
                    f[i%2][j][c][1]=0;
                }
            }
        }
    }
    cout<<(f[n%2][m][k][1]+f[n%2][m][k][0])%mod<<endl;
    return 0;
}

为了避免&1，^1的麻烦用%2

1s极限：1e8