总之就是 | CSP-S2 2021 （部分）题解

2023-11-18 12:44:28

同步发布于hriver2.github.io

「启」

因为觉得场上很不甘心，所以就把自己场上看过的前三题写了出来。

T4 没有写，因为觉得不是我的能力范围之内的（

但是总体上来说今年的题好像简单的比去年简单（？），难的也比去年简单（？），但是总体难度好像难一点，再加上暴力分比去年少，所以分数线低（？）

反正去年的贪吃蛇我是一点想法都没有，今年 T4 还是有点想法的（

以下代码均使用缺省源 V5.2.

「A」廊桥分配

总的来说这道题真的不难，自己场上的做法和正解只是一个循环的区别，但是场上光想着先把能打的暴力全打了就没把这道题继续往下想。

要写这个的时候，觉得应当测一下官方数据，没想到居然 \(A\) 第一个点挂了，于是改的时候又重新修了一下码风。

「A」思路简述

首先先是场上的 \(O(n^2\log n)\) 的暴力做法。

思路非常的简单，先排序，然后枚举分配的时间，然后里面枚举飞机，每次将应当飞走的飞机从堆中弹出，然后让当前的飞机到编号最小的廊桥停下。

考场代码太丑了，我也懒得修就不放了。

但是这样显然是过不了的，于是考虑优化。首先可以想到的是这样贪心绝对是没问题的，所以我们考虑如何让这个过程的复杂度降低。

仔细分析一下，其实我们可以把两种飞机分开预处理，最后再将对应的答案合并。于是我们就要对于每种飞机处理出分配 \(0\) 到 \(n\) 个廊桥的方案，为了优化复杂度我们肯定不能再傻傻的枚举。

根据刚才我们的贪心策略，我们每次放飞机的时候都是要找到编号最小的廊桥把放进去，所以我们可以把可用廊桥的编号扔到一个小根堆里面，然后每次被使用的时候和占用这个廊桥的飞机一起扔到另外一个堆里面，这样我们处理的复杂度就降为了 \(O(n \log n).\)

「A」Code

template<typename J>
I J Hmax(const J &x,const J &y) 
{
    Heriko x>y?x:y;
}

template<typename J>
I J Hmin(const J &x,const J &y)
{
    Heriko x<y?x:y;
}

CI MXX(1e5+1);

int n,m1,m2,coa[MXX],cob[MXX],ans;

struct Plane
{
    int l,r;

    I bool operator < (const Plane &co) const 
    {
        Heriko (l==co.l)?(r<co.r):(l<co.l);
    }
}

a1[MXX],a2[MXX];

priority_queue<int> id;

priority_queue< pair<int,int> > q;

S main()
{
    Files();

    fr(n),fr(m1),fr(m2);

    for(int i(1);i<=m1;++i)
        fr(a1[i].l),fr(a1[i].r);

    for(int i(1);i<=m2;++i)
        fr(a2[i].l),fr(a2[i].r);

    sort(a1+1,a1+1+m1);
    sort(a2+1,a2+1+m2);

    for(int i(1);i<=n;++i)
        id.push(-i);

    for(int i(1);i<=m1;++i)
    {
        while(q.size() and -q.top().first<a1[i].l)
            id.push(-q.top().second),q.pop();

        if(id.size()) 
        {
            q.push(make_pair(-a1[i].r,-id.top()));
            ++coa[-id.top()];id.pop();
        }
    }

    for(int i(1);i<=n;++i)
        coa[i]+=coa[i-1];

    while(id.size())
        id.pop();

    while(q.size())
        q.pop();

    for(int i(1);i<=n;++i)
        id.push(-i);

    for(int i(1);i<=m2;++i)
    {
        while(q.size() and -q.top().first<a2[i].l)
            id.push(-q.top().second),q.pop();

        if(id.size())
        {
            q.push(make_pair(-a2[i].r,-id.top()));
            ++cob[-id.top()];id.pop();
        }
    }

    for(int i(1);i<=n;++i)
        cob[i]+=cob[i-1];

    for(int i(0);i<=n;++i)
        ans=Hmax(ans,coa[i]+cob[n-i]);

    fw(ans,1);

    Heriko Deltana;
}

「B」括号序列

感觉是一道恶心的题，然后场上写了三个小时挂了，最后写的暴力也挂了，然后提交样例还 CE 了，Bad.

「B」思路简述

暴力就不说了，\(O(3^n)\) 的暴搜，下面的内容主要参考了I_am_Accepted 的题解。

看到数据范围之后，我们心中大约有了一个比较常规的复杂度：\(O(n^3)\)，而这是一个比较正常的区间 DP 的复杂度，所以我们就先正常的设状态和转移。

设 \(f(l,r)\) 表示 \([l,r]\) 为合法序列且 \(l\) 和 \(r\) 匹配的方案数，而 \(g(l,r)\) 表示不匹配的数量，这样就能避免重复计算的情况，最终的答案显然为 \(f(1,n)+g(1,n)\)。同时因为我们最多有 \(k\) 个 *，为了后面方便使用，可以在最初用 \(O(n^2)\) 的时间预处理出来。

而在转移之前还需要特判一些状态：

  • 当端点为符号未确定且不能成为括号的时候，跳过；

  • 当当前区间的长度为 \(2\) 的时候，\(f(l,r)=1\)，跳过。

然后就是转移，首先是 \(f:\)

  • \((S): f(l,r)+=[co(l+1,r)].\)

  • \((A): f(l,r)+=f(l+1,r-1)+g(l+1,r-1).\)

  • \((SA): f(l,r)+=\sum_{i=1}^k(f(l+i+1,r-1)+g(l+i+1,r-1))\times[co(l+1,l+i)].\)

  • \((AS): f(l,r)+=\sum_{i=1}^k(f(l+1,r-i-1)+g(l+1,r-i-1))\times[co(r-i,r-1)].\)

然后是 \(g:\)

  • \(ASB / AB: g(l,r)+=\sum\limits_{l<i<j<r,j-i-1\le k}(f(l,i)+g(l,i)\times f(i,r))[co(i+1,j-1)].\)

然而这个转移是 \(O(n^4)\) 的，所以考虑优化这个的复杂度，发现 \(i\) 每次增减 \(1\)，\(j\) 的变化是 \(O(1)\) 的，可控，所以我们可以先预处理出来合法的下一个转移对象，然后就优化成了 \(O(n^2+n^3)=O(n^3).\)

「B」Code

template<typename J>
I J Hmax(const J &x,const J &y) 
{
    Heriko x>y?x:y;
}

template<typename J>
I J Hmin(const J &x,const J &y)
{
    Heriko x<y?x:y;
}

CI MXX(501),MOD(1e9+7);

int n,k,nex[MXX];

LL f[MXX][MXX],g[MXX][MXX];

bitset<MXX> co[MXX];

char s[MXX];

S main()
{
    Files();

    fr(n),fr(k);
    scanf("%s",s+1);

    for(int i(1);i<=n;++i)
    {
        if(s[i]!='*' and s[i]!='?')
            continue;

        co[i][i]=1;

        for(int j(i+1);j<=n;++j)
            if(s[j]=='*' or s[j]=='?')
                co[i][j]=1;
            else
                break;
    }

    for(int len(2);len<=n;++len)
    {
        for(int l(1),r;l<=n-len+1;++l)
        {
            r=len+l-1;f[l][r]=g[l][r]=0;

            if((s[l]!='(' and s[l]!='?') or (s[r]!=')' and s[r]!='?'))
                continue;

            if(l+1==r)
            {
                (f[l][r]+=1)%=MOD;
                
                continue;
            }

            /*----F----*/

            if(r-l-1<=k and co[l+1][r-1])
                (f[l][r]+=1)%=MOD;

            (f[l][r]+=f[l+1][r-1]+g[l+1][r-1])%=MOD;

            for(int i(l+1);i<=Hmin(l+k,r-2);++i)
                if(co[l+1][i])
                    (f[l][r]+=f[i+1][r-1]+g[i+1][r-1])%=MOD;

            for(int i(r-1);i>=Hmax(l+2,r-k);--i)
                if(co[i][r-1])
                    (f[l][r]+=f[l+1][i-1]+g[l+1][i-1])%=MOD;

            /*----G----*/

            LL tmp(0);

            for(int i(l+1);i<r-1;++i)
            {
                if(tmp<=i)
                    tmp=i+1;

                while(tmp<r-1 and (s[tmp]=='?' or s[tmp]=='*'))
                    ++tmp;

                nex[i]=Hmin((LL)i+k+1,tmp);
            }

            tmp=0;

            for(int i(l+2);i<=nex[l+1];++i)
                (tmp+=f[i][r])%=MOD;

            (g[l][r]+=((f[l][l+1]+g[l][l+1])%MOD*tmp))%=MOD;

            for(int i(l+2);i<r-1;++i)
            {
                (tmp+=MOD-f[i][r])%=MOD;

                for(int j(nex[i-1]+1);j<=nex[i];++j)
                    (tmp+=f[j][r])%=MOD;

                (g[l][r]+=((f[l][i]+g[l][i])%MOD*tmp))%=MOD;
            }
        }
    }

    fw((f[1][n]+g[1][n]+MOD)%MOD,1);

    Heriko Deltana;
}

「C」回文

多测没清空的痛啊，暴力分都没了……

「C」思路简述

实际上，因为要构成回文串，所以当我们在进行第 \(i\) 步操作的时候，就能知道 \(2n-i+1\) 次操作取出的数应当和其相同。

然后又因为每次只能从两段取数，所以原来的序列就被分为了两个连续的部分，于是就考虑用两个 deque 去维护从左端取出的数和从右端取出的数。

然后就有以下四种情况（因为要最优的方案，所以已经按照字典序排序）:

  • \(L\) 的头尾相同，则第 \(i\) 次操作为 \(L\)，第 \(2n-i+1\) 次为 \(L.\)

  • \(L\) 的头和 \(R\) 的头相同，则第 \(i\) 次操作为 \(L\)，第 \(2n-i+1\) 次为 \(R.\)

  • \(R\) 的尾和 \(L\) 的尾相同，则第 \(i\) 次操作为 \(R\)，第 \(2n-i+1\) 次为 \(L.\)

  • \(R\) 的头尾相同，则第 \(i\) 次操作为 \(R\)，第 \(2n-i+1\) 次为 \(R.\)

按照最优的策略先从左端开始跑一边再从右端开始跑一边，如果两次都不能构成就说明无解。

「C」Code

CI MXX(1e6+4);

int n,m,a[MXX];

char ans[MXX];

deque<int> l,r;

I void Solve()
{
    /*----Start At L----*/

    l.clear();
    r.clear();
    l.push_back(a[1]);
    l.push_back(a[2]);

    for(int i(3);i<=m;++i)
        if(l.front()!=l.back())
            l.push_back(a[i]);
        else
            r.push_back(a[i]);

    int flg(0),cnt(0);

    while(cnt<n)
    {
        if(flg)
            break;

        flg=1;

        if(l.size()>1 and l.front()==l.back())
        {
            flg=0;
            ans[++cnt]='L',ans[m-cnt+1]='L';
            l.pop_front();
            l.pop_back();

            continue;
        }

        if(l.size() and r.size() and l.front()==r.front())
        {
            flg=0;
            ans[++cnt]='L',ans[m-cnt+1]='R';
            l.pop_front();
            r.pop_front();

            continue;
        }

        if(l.size() and r.size() and l.back()==r.back())
        {
            flg=0;
            ans[++cnt]='R',ans[m-cnt+1]='L';
            l.pop_back();
            r.pop_back();

            continue;
        }

        if(r.size()>1 and r.front()==r.back())
        {
            flg=0;
            ans[++cnt]='R',ans[m-cnt+1]='R';
            r.pop_front();
            r.pop_back();

            continue;
        }
    }

    if(!flg)
    {
        for(int i(1);i<=m;++i)
            putchar(ans[i]);

        puts("");

        Heriko;
    }

    /*----Start At R----*/

    l.clear();
    r.clear();
    r.push_front(a[m]);
    r.push_front(a[m-1]);

    for(int i(m-2);i;--i)
        if(r.front()!=r.back())
            r.push_front(a[i]);
        else
            l.push_front(a[i]);

    l.push_back(r.front());
    r.pop_front();

    flg=cnt=0;

    while(cnt<n)
    {
        if(flg)
        {
            puts("-1");

            Heriko;
        }

        flg=1;

        if(l.size()>1 and l.front()==l.back())
        {
            flg=0;
            ans[++cnt]='L',ans[m-cnt+1]='L';
            l.pop_front();
            l.pop_back();

            continue;
        }

        if(l.size() and r.size() and l.front()==r.front())
        {
            flg=0;
            ans[++cnt]='L',ans[m-cnt+1]='R';
            l.pop_front();
            r.pop_front();

            continue;
        }

        if(l.size() and r.size() and l.back()==r.back())
        {
            flg=0;
            ans[++cnt]='R',ans[m-cnt+1]='L';
            l.pop_back();
            r.pop_back();

            continue;
        }

        if(r.size()>1 and r.front()==r.back())
        {
            flg=0;
            ans[++cnt]='R',ans[m-cnt+1]='R';
            r.pop_front();
            r.pop_back();

            continue;
        }
    }

    for(int i(1);i<=m;++i)
        putchar(ans[i]);

    puts("");
}

S main()
{
    Files();

    int T;fr(T);

    while(T--)
    {
        fr(n);m=n*2;

        for(int i(1);i<=m;++i)
            fr(a[i]);

        Solve();
    }

    Heriko Deltana;
}

「结」

算是完成了自己的心愿吧（

\[NOIP2021 RP++. \]

上一篇：问题描述： abccba是一个特殊的字符串，正读反读都能读通的，这叫做回文字符串。 输入一个字符串判断是不是回文


下一篇：leetcode【栈与队列—简单】 232. 栈实现队列