牛客练习赛51（部分题解）

太过爱你忘了你带给我的痛 2024-04-18 14:06 57阅读 0赞

# 牛客练习赛51（部分题解） #

ps:菜鸡一枚，纯属供自己复习所用，如有错误还望指出

[A：abc][A_abc]

感觉题目应该说明下的，开始乍一看题目，还以为是kmp，原来题目中的子串不是我们所常规中的子串，而是子序列（我是这么理解的）  
然后耽误会时间，由于是个签到题，所以不会设很难，  
但是还是WA了一发，本想着就只有1e5，但是子串却可能远不止如此，加了long long 就过了

#include<cstdio>
    #include<algorithm>
    #include<iostream>
    #include<cstring>
    #define ll long long
    using namespace std;
    const int maxn=100010;
    ll dp[5];
    char str[maxn];
    int main()
    {
        
        scanf("%s",str);
        int len=strlen(str);
        memset(dp,0,sizeof(dp));
        for(int i=0;i<len;i++)
        {
        
            dp[3]=dp[3]+(str[i]=='c')*dp[2];
            dp[2]=dp[2]+(str[i]=='b')*dp[1];
            dp[1]=dp[1]+(str[i]=='a');
        }
        printf("%lld\n",dp[3]);
        return 0;
    }

[B：子串查询][B]

这题真的没懂，最开始尝试套A题的模板，然后TLE，后面想了下，不如暴力试试，感觉也就是遍历一遍啊，但是还是TLE了  
看题解还是看的我有点迷茫

**设nex\[i\]\[j\]表示s串中第i后面第一个字符为(j+‘a’)的位置(0<=j<26),规定s串的下标从1开始,如果不存在这样的位置则nex\[i\]\[j\]=-1。对于每次查询，按顺序枚举串t的所有字符，每次优先匹配可以匹配的最小位置进行贪心。更正式的说，最开始我们设now=0,每次枚举到串t的位置i，我们使得now=nex\[now\]\[t\[i\]-‘a’\],如果中途now=-1了，说明串t不是s的子串，否则串t是s的子串。因此我们可以用一个队列辅助来求出nex数组，就可以在线性时间内解决这道题。**

于是找个题解敲了下：

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<iostream>
    #include<queue>
    using namespace std;
    const int maxn=100010;
    int n,k,Next[maxn][26];
    char s[maxn];
    char t[55];
    queue<int>q[26];
    int main()
    {
        
        scanf("%d%d",&n,&k);
        scanf("%s",s+1);
        for(int i=1;i<=n;i++)
            q[s[i]-'a'].push(i);
        for(int j=0;j<26;j++)
        {
        
            if(!q[j].empty())
                Next[0][j]=q[j].front();
            else
                Next[0][j]=-1;
        }
        for(int i=1;i<=n;i++)
        {
        
            q[s[i]-'a'].pop();
            for(int j=0;j<26;j++)
            {
        
                if(!q[j].empty())
                    Next[i][j]=q[j].front();
                else
                    Next[i][j]=-1;
            }
        }
        while(k--)
        {
        
            scanf("%s",t+1);
            int now=0;
            int flag=0;
            for(int i=1;t[i]!='\0';i++)
            {
        
                now=Next[now][t[i]-'a'];
                if(now==-1)
                {
        
                    flag=1;
                    break;
                }
            }
            if(flag==1)
                printf("NO\n");
            else
                printf("YES\n");
        }
        return 0;
    }

[C：勾股定理][C]

C题不想说话，一道这么简单的题都没能A出来，开始就是一顿操作猛如虎，结果TLE。。。。  
看完题解后发现，打下表就会发现规律啊：  
1、**如果n为奇数：c-b=1;**  
接着由勾股定理就可以求得**c=(n^2+1)/2**  
2、**如果n为偶数：c-b=2;**  
接着由勾股定理就可以求得**c=(n^2+4)/4**

于是就非常简单了：  
瞬间把时间复杂度拉到了线性

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<iostream>
    #define ll long long
    using namespace std;
    int main()
    {
        
        ll n,b,c;
        scanf("%lld",&n);
        if(n<=2)
            printf("-1\n");
        else
        {
        
            if(n%2==1)
            {
        
                c=(n*n+1)/2;
                b=c-1;
            }
            else
            {
        
                c=(n*n+4)/4;
                b=c-2;
            }
            printf("%lld %lld\n",b,c);
        }
        return 0;
    }

[D：羊吃草][D]

可能唯一能说下的就是D题了，当时可能很多人都去做前面三题去了，没看D题，刚看会题，就让我和poj的奶牛问题了，越来越觉得就是一个**二分图最大匹配**的板子题

给出奶牛问题的题解链接：[https://blog.csdn.net/boliu147258/article/details/99961614][https_blog.csdn.net_boliu147258_article_details_99961614]

那题是奶牛和牛栏  
这题变为了羊和时间，可能二分图构建那会有点麻烦，但是也不是太麻烦，于是找出我的模板，一顿操作，样例一过立马交了  
成功一A，虽然是个水题

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<iostream>
    using namespace std;
    int mp[410][410];
    int Line[410];
    int vis[410];
    int a[410],b[410];
    int l,r;
    int Find(int i)
    {
        
        for(int j=l;j<=r;j++)
        {
        
            if(mp[i][j]==1&&vis[j]==0)
            {
        
                vis[j]=1;
                if(Line[j]==0||Find(Line[j])==1)
                {
        
                    Line[j]=i;
                    return 1;
                }
            }
        }
        return 0;
    }
    int main()
    {
        
        int n,q;
        scanf("%d%d",&n,&q);
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        for(int i=1;i<=n;i++)
            scanf("%d",&b[i]);
        while(q--)
        {
        
            memset(vis,0,sizeof(vis));
            memset(Line,0,sizeof(Line));
            memset(mp,0,sizeof(mp));
            scanf("%d%d",&l,&r);
            for(int i=1;i<=n;i++)
            {
        
                if(l<=a[i]&&r>=b[i])
                {
        
                    for(int j=a[i];j<=b[i];j++)
                    {
        
                        mp[i][j]=1;
                    }
                }
                else if(l>=a[i]&&r>=b[i])
                {
        
                    for(int j=l;j<=b[i];j++)
                    {
        
                        mp[i][j]=1;
                    }
                }
                else if(l<=a[i]&&r<=b[i])
                {
        
                    for(int j=a[i];j<=r;j++)
                    {
        
                        mp[i][j]=1;
                    }
                }
                else if(l>=a[i]&&r<=b[i])
                {
        
                    for(int j=l;j<=r;j++)
                    {
        
                        mp[i][j]=1;
                    }
                }
            }
            int cnt=0;
            for(int i=1;i<=n;i++)
            {
        
                memset(vis,0,sizeof(vis));
                if(Find(i)==1)
                    cnt++;
            }
            printf("%d\n",cnt);
        }
        return 0;
    }

感觉自己没有以前那么菜了，虽然还是个只会做两题的菜鸟，慢慢来吧，今天下午的网络赛又打自闭了，没 A几题不说，还搞得现在好困

[A_abc]: https://ac.nowcoder.com/acm/contest/1083/A
[B]: https://ac.nowcoder.com/acm/contest/1083/B
[C]: https://ac.nowcoder.com/acm/contest/1083/C
[D]: https://ac.nowcoder.com/acm/contest/1083/D
[https_blog.csdn.net_boliu147258_article_details_99961614]: https://blog.csdn.net/boliu147258/article/details/99961614