T1:队长快跑

基本思路：

离散化·DP·数据结构优化DP

这三个我都没想到。。。。气死。

定义状态数组：\(c[i][j]\)表示在i时最小的a值是j时可以摧毁的最多的水晶数。

那么状态转移方程就是：

c[i][j]=max(c[i-1][a[i]+1],c[i-1][a[i]+2],......,c[i-1][maxn])+1,if(a[i]>b[i]),这时还要同时更新c[i-1][j]（j\(\in(b[i],a[i]]\)）

c[i][j]=max(c[i-1][b[i]+1],c[i-1][b[i]+2],......,c[i-1][maxn])+1,if(a[i]<=b[i])

我来解释下为什么这么转移：

首先可以明确的一点是，c[i][a[i]]只能由c[i-1][a[i]+1->maxn]转移来，因为如果转移的j比a[i]小，那么转移来的情况就不是以a[i]为最小值了。

加一是将当前点纳入

当a[i]<=b[i]时，我解释下什么是b[i]+1而不是a[i]+1，因为题目要求是之前的a比现在的b大，所以这么转移才合法

当a[i]>b[i]时，在b[i]~a[i]的范围内,c[i-1]是可以将当前点纳入的，所以要给他们集体加一，c[i][a[i]的转移就很好理解了

直接转移时间复杂度是\(O(n^{3})\)，考虑优化,我们可以将第二维放在线段树上，对应的叶子维护对应a值情况的值，一棵线段树从头用到尾，记录的是当前的情况，就可以\(O(nlogn)\)转移了。

上代码：

#include<bits/stdc++.h>

using namespace std;

namespace STD

{

    #define ll long long

    #define rr register

    inline int max(int x,int y){return x>y?x:y;}

	//伤心往事：

	//这里的max原本用的是#define函数，然后TLE了

	//后来小马告诉我，#define函数会重复调用，T到起飞

	//所以改成了inline

    const int SIZE=100002;

    int n;

    int a[SIZE],b[SIZE];

    int c[SIZE<<1];

    int read()

    {

        rr int x_read=0,y_read=1;

        rr int c_read=getchar();

        while(c_read<'0'||c_read>'9')

        {

            if(c_read=='-') y_read=-1;

            c_read=getchar();

        }

        while(c_read<='9'&&c_read>='0')

        {

            x_read=(x_read*10)+(c_read^48);

            c_read=getchar();

        }

        return x_read*y_read;

    }

    int lazy[SIZE<<3],maxn[SIZE<<3];

    void push_down(int id)

    {

        if(!lazy[id]) return;

        lazy[id<<1]+=lazy[id],lazy[id<<1|1]+=lazy[id];

        maxn[id<<1]+=lazy[id],maxn[id<<1|1]+=lazy[id];

        lazy[id]=0;

        return;

    }

    void add(int id,int l,int r,int st,int en,int val)

    {

        if(st<=l&&r<=en){maxn[id]+=val,lazy[id]+=val;return;}

        int mid=(l+r)>>1;

        push_down(id);

        if(st<=mid) add(id<<1,l,mid,st,en,val);

        if(mid<en) add(id<<1|1,mid+1,r,st,en,val);

        maxn[id]=max(maxn[id<<1],maxn[id<<1|1]);

    }

    void change(int id,int l,int r,int pos,int val)

    {

        if(l==r){maxn[id]=max(maxn[id],val);return;}

        int mid=(l+r)>>1;

        push_down(id);

        if(pos<=mid) change(id<<1,l,mid,pos,val);

        else change(id<<1|1,mid+1,r,pos,val);

        maxn[id]=max(maxn[id<<1],maxn[id<<1|1]);

    }

    int query(int id,int l,int r,int st,int en)

    {

        if(st<=l&&r<=en) return maxn[id];

        int mid=(l+r)>>1;

        int ret=INT_MIN;

        push_down(id);

        if(st<=mid) ret=max(ret,query(id<<1,l,mid,st,en));

        if(mid<en) ret=max(ret,query(id<<1|1,mid+1,r,st,en));

        return ret;

    }

};

using namespace STD;

int main()

{

    n=read();

    for(rr int i=1;i<=n;i++)

    {

        a[i]=read(),b[i]=read();

        c[++c[0]]=a[i],c[++c[0]]=b[i];

    }

    sort(c+1,c+1+c[0]);

    int cnt=unique(c+1,c+1+c[0])-c-1;

    for(rr int i=1;i<=n;i++)

    {

        a[i]=lower_bound(c+1,c+1+cnt,a[i])-c;

        b[i]=lower_bound(c+1,c+1+cnt,b[i])-c;

    }

    int val;

    for(rr int i=1;i<=n;i++)

    {

        if((a[i]<=b[i])&&(b[i]+1<=cnt))

        {

            val=query(1,1,cnt,b[i]+1,cnt)+1;

            change(1,1,cnt,a[i],val);

        }

        if(a[i]>b[i])

        {

            add(1,1,cnt,b[i]+1,a[i],1);

			//注意要先add后change,因为change后的树现在的情况了

			//而add是给之前的情况add

            if(a[i]+1<=cnt)

            {

                val=query(1,1,cnt,a[i]+1,cnt)+1;

                change(1,1,cnt,a[i],val);

            }

        }

    }

    printf("%d",maxn[1]);

}

T2:影魔

由于要用到可持久化线段树，我们没学，先鸽掉。

T3:抛硬币

基本思路：

一个简单的小DP。

定义状态数组：\(c[i][j]\)表示在i位置长度为j的本质不同的子序列的个数。

很容易想出方程\(c[i][j]=c[i-1][j-1]+c[i-1][j]\)c[i-1][j-1]是新形成了这么多串，c[i-1][j]是继承之前已经形成了的串、

但是一看样例，事情并不简单，有的字母重复出现，就会导致序列算重，因此要记录每个字母上一次出想的位置last。

最终的方程是：

\[c[i][j]=c[i-1][j-1]+c[i-1][j]-c[last-1][j-1]
\]

上代码：

#include<bits/stdc++.h>

using namespace std;

namespace STD

{

    #define ll long long

    #define rr register

    const int SIZE=3001;

    const int mod=998244353;

    int l;

    char s[SIZE];

    int c[SIZE][SIZE];

    int last[29];

    int read()

    {

        rr int x_read=0,y_read=1;

        rr char c_read=getchar();

        while(c_read<'0'||c_read>'9')

        {

            if(c_read=='-') y_read=-1;

            c_read=getchar();

        }

        while(c_read<='9'&&c_read>='0')

        {

            x_read=(x_read*10)+(c_read^48);

            c_read=getchar();

        }

        return x_read*y_read;

    }

};

using namespace STD;

int main()

{

    int x=scanf("%s",s+1);

    int len=strlen(s+1);

    l=read();

    c[1][1]=1;

    for(rr int i=0;i<=len;i++) c[i][0]=1;

    last[s[1]-'a'+1]=1;

    for(rr int i=2;i<=len;i++)

    {

        for(rr int j=1;j<=l;j++)

        {

            if(j>i) break;

            if(last[s[i]-'a'+1])

                c[i][j]=((c[i-1][j]+c[i-1][j-1])%mod-c[last[s[i]-'a'+1]-1][j-1]+mod)%mod;

            else

                c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;

        }

        last[s[i]-'a'+1]=i;

    }

    printf("%d",c[len][l]);

}

巴特西

NOIP模拟14「队长快跑·影魔·抛硬币」

T1:队长快跑

基本思路：

T2:影魔

T3:抛硬币

基本思路：

最新文章

热门文章