提高组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:

这种两个串一个一个挨着去找的有没有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)的方案数。


转移

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

  1. 当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​.

  2. 当a_i\ne 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,应该是不敢开1000\times200\times200\times2=8\times10^71000×200×200×2=8×107的数组吧。所以我们观察转移方程,发现每次转移只用到了前一位!于是我们把第一维很愉快地滚掉了。这样,空间复杂度就保证是O(mk)O(mk)了。那么时间呢?时间是O(n\cdot mk)O(n⋅mk),但是时间不像空间,这个复杂度是可以接受的。于是,完整算法就结束了。

#include<cstdio>
#include<cstring>
const int MAXN=1010;
const int MAXM=210;
const int MOD=(int)(1e9)+7;
int f[2][MAXM][MAXM][2];
char a[MAXN],b[MAXM];
int n,m,k;bool val=1;

void dp(){
    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][0]+f[val^1][j-1][p-1][1])%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;
                }
            }
}

int main(){
    scanf("%d%d%d",&n,&m,&k);
    scanf("%s%s",a+1,b+1);
    dp();
    printf("%d\n",(f[n&1][m][k][0]+f[n&1][m][k][1])%MOD);
    return 0;
}

 

 

 

上一篇:JS中 reduce() 的用法


下一篇:Leetcode 25 Reverse Nodes in k-Group