2022年5月5日模拟赛题解与总结(ABC237)

总结

初一第一，竞赛班第二

还可以，为了照顾提高班来的四个同学放了四个水题，可惜他们做的不是很理想，希望他们下次可以获得满意的成绩

这次做的其实是 AtCoder ABC237

A.Not Overflow

一道水题，C++11直接判断即可

有好多同学没开C++11，默哀默哀，希望大家下次不要再出锅了

#include <bits/stdc++.h>

using namespace std;

long long n, l = -2147483648, r = 2147483647;

int main() {

    scanf("%lld", &n);

    if (l <= n && n <= r) {

        printf("Yes");

    } else {

        printf("No");

    }

}

Code From 彬彬

B.Matrix Transposition

很简单，但是需要用到以前被老师骂的一种打法

数据中\(h,w<100000\),总不能开\(100000*100000\)吧...

所以用多少开多少

见代码

#include <bits/stdc++.h>

using namespace std;

long long n,m,x;

int main()

{

    cin>>n>>m;

    long long a[n+5][m+5];//数据问题，这样开比较保险

    memset(a,0,sizeof(a));

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

    {

        for(int j=1;j<=m;j++)

        {

            cin>>a[i][j];

        }

    }

    for(int i=1;i<=m;i++)

    {

        for(int j=1;j<=n;j++)

        {

            cout<<a[j][i]<<' ';

        }

        cout<<endl;

    }

}

C.kasaka

先看前后各有多少a,如果后面少于前面，那就不行

为什么？

如果后面少于前面，那我们不能在后面补

反之，我们可以在前面补a

如果没判掉，就看除去头尾a的部分是否回文

#include <bits/stdc++.h>

using namespace std;

string x,y;//STL的字符串

long long t,w,len;

int main()

{

    cin>>x;

    y=x;//这里，不初始化长度就会越界

    len=x.size();

    while(x[t]=='a')t++;

    while(x[len-w-1]=='a')w++;

    if(w<t)

    {

        cout<<"No"<<endl;

    }

    else

    {

        for(int i=t;i<=len-w-1;i++)

        {

            y[i-t]=x[i];

        }//突然想到可以用strstr

        for(int i=0;i<len-t-w;i++)//判回文

        {

            if(y[i]!=y[len-t-w-i-1])

            {

                cout<<"No"<<endl;

                return 0;

            }

        }

        cout<<"Yes"<<endl;

    }

}

D.LR insertion

显然是一道链表，利用链表原理，可以优化成\(O(n)\)

关于链表的介绍详见我的超级黑历史

这里我是手写的

#include <bits/stdc++.h>

using namespace std;

struct node {

    int l,r;

}a[1000005];

long long n,t;

char c;

int main()

{

    a[0].l=-1;

    a[0].r=-1;

    cin>>n;

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

    {

        cin>>c;

        if(c=='L')

        {

            a[i].l=a[i-1].l;

            a[a[i-1].l].r=i;

            a[i-1].l=i;

            a[i].r=i-1;

            if(a[i].l==-1)

            {

                t=i;

            }

        }

        else

        {

            a[i].r=a[i-1].r;

            a[a[i-1].r].l=i;

            a[i-1].r=i;

            a[i].l=i-1;

        }

    }

    cout<<t<<' ';

    for(int i=t;i!=-1;i=a[i].r)

    {

        if(a[i].r!=-1)cout<<a[i].r<<' ';

    }

}

以上是做出来的

以下是骗分的

E.Skiing

这道题是一道最长路，我打的SPFA只有98分，正解果然又是堆优化dij

98分代码

#include<bits/stdc++.h>

using namespace std;

struct node

{

    long long to,w,next;

}a[1000005];

long long n,m,t,x,y,h[200005],b[200005],ans,f[200005];

void add(long long x,long long y)

{

    t++;

    a[t].to=y;

    a[t].w=b[x]-b[y];

    if(a[t].w<0)

    {

        a[t].w*=2;

    }

    a[t].next=h[x];

    h[x]=t;

}

queue<long long>q;

int main(){

    cin>>n>>m;

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

        scanf("%lld",&b[i]);

        f[i]=-1e14;

    }

    for(int i=1;i<=m;i++){

        scanf("%lld%lld",&x,&y);

        add(y,x);

        add(x,y);

    }

    q.push(1);

    f[1]=0;

    while(!q.empty())

    {

        long long t=q.front();

        q.pop();

        for(int i=h[t];i;i=a[i].next)

        {

            if(f[t]+a[i].w>f[a[i].to])

            {

                f[a[i].to]=f[t]+a[i].w;

                q.push(a[i].to);

            }

        }

    }

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

    {

        if(f[i]>ans)ans=f[i];

    }

    cout<<ans;

}

一顿欺负 DeepSeaSpray，又问了问教练，终于看懂了正解dij是怎么搞的

去问 DeepSeaSpray ，不要问我

监督#include<bits/stdc++.h>

using namespace std;

struct node

{

    long long to,w,next;

}a[1000005];

long long n,m,t,x,y,h[200005],b[200005],ans,dis[200005];

void add(long long x,long long y,long long z)

{

    t++;

    a[t].to=y;

    a[t].w=z;

    a[t].next=h[x];

    h[x]=t;

}

struct nd{

    long long x,dis;

    bool operator <(const nd &xx)const

    {

        return dis>xx.dis;

    }

    nd(long long xx,long long xdis){

        x=xx;

        dis=xdis;

    }

};

priority_queue<nd>p;

int main(){

    cin>>n>>m;

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

        scanf("%lld",&b[i]);

    }

    for(int i=1;i<=m;i++){

        scanf("%lld%lld",&x,&y);

        if(b[x]>b[y])add(y,x,b[x]-b[y]),add(x,y,0);

        else add(x,y,b[y]-b[x]),add(y,x,0);

    }

    p.push(nd(1,0));

    memset(dis,127,sizeof(dis));

    dis[1]=0;

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

    {

    //    cout<<t<<endl;

        long long t=p.top().x;

        p.pop();

        for(int j=h[t];j;j=a[j].next)

        {

       //     cout<<a[j].to<<' '<<a[j].w<<endl;

            if(dis[t]+a[j].w<dis[a[j].to])

            {

                dis[a[j].to]=dis[t]+a[j].w;

                p.push(nd(a[j].to,dis[a[j].to]));

            }

        }

    }

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

    {

        ans=max(ans,b[1]-b[i]-dis[i]);

    }

    cout<<ans;

}

F.|LIS| = 3

考场dfs，只有8分

发现就是一个简单DP

设\(f_{i,x,y,z}\)表示前\(i\)个数构成的LIS中，长度为1的LIS结尾最小是\(x\),长度为2的是\(y\),长度为\(3\)的是为\(z\)

如果你知道\(O(nlog_n)\)的LIS做法的话你应该知道满足\(x<y<z\)

所以只要枚举第\(i+1\)个数时令其小于\(z\)就可以保证不会出现长度为\(x(3 < x)\)的LIS,

#include<bits/stdc++.h>

using namespace std;

long long n,m,f[1005][15][15][15],ans;

int main()

{

    cin>>n>>m;

    f[0][m+1][m+1][m+1]=1;

    for(int i=0;i<n;i++)

    {

        for(int x=1;x<=m+1;x++)

        {

            for(int y=1;y<=m+1;y++)

            {

                for(int z=1;z<=m+1;z++)

                {

                    for(int j=1;j<=m;j++)

                    {

                        if(j<=x)

                        {

                            f[i+1][j][y][z]+=f[i][x][y][z];

                            f[i+1][j][y][z]%=998244353;

                        }

                        else if(j<=y)

                        {

                            f[i+1][x][j][z]+=f[i][x][y][z];

                            f[i+1][x][j][z]%=998244353;

                        }

                        else if(j<=z)

                        {

                            f[i+1][x][y][j]+=f[i][x][y][z];

                            f[i+1][x][y][j]%=998244353;

                        }

                    }

                }

            }

        }

    }

    for(int i=1;i<=m;i++)

    {

        for(int j=i+1;j<=m;j++)

        {

            for(int k=j+1;k<=m;k++)

            {

                ans+=f[n][i][j][k];

                ans%=998244353;

            }

        }

    }

    cout<<ans;

}

我觉得很好理解，所以不讲了

G.Range Sort Query

直接sort六十分走起

#include<bits/stdc++.h>

using namespace std;

long long n,q,x,c,l,r,a[1000005];

bool cmp(long long x,long long y) {

    return x>y;

}

int main()

{

    cin>>n>>q>>x;

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

    {

        cin>>a[i];

        if(a[i]==x)a[i]=1;

        else if(a[i]>x)a[i]=2;

        else a[i]=0;

    }

    for(int i=1;i<=q;i++)

    {

        cin>>c>>l>>r;

        if(c==1)

        {

            sort(a+l,a+r+1);

        }

        else

        {

            sort(a+l,a+r+1,cmp);

        }

    }

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

    {

        if(a[i]==1)

        {

            cout<<i;

            return 0;

        }

    }

}

后来听说是bt线段树，就不怎么想打了