牛客小白月赛36

牛客小白月赛36

A 好哥哥

题意

给定一段合法括号序列和元钱，合法括号序列的定义如下：
1.是合法的括号序列。
2.若字符串是合法的括号序列，那么(A)也是合法的括号序列。
3.若字符串A,B是合法的括号序列，那么AB也是合法的括号序列。
我们设定表示第对括号的层数，即：它前面有多少未匹配的左括号。同时规定一对括号A是另一对括号B的好哥哥，当且仅当且括号A在括号B内。
如果当前位于一对括号Q，每次可以花费1元跳到：
1.它的任意一个好哥哥。
2.一对括号X，要求X的好哥哥是Q。
假如一开始位于第一对括号，请问最多可以经过多少对不重复的括号？

Solution

对括号序列建树，找到最长链，其余部分可以随便跑，代价是。根据能否跑完最长链计算答案。

代码
#include<bits/stdc++.h>
using namespace std;
int n,m;
char s[20000005];
int main()
{
    scanf("%d%d",&m,&n);
    scanf("%s",s);
    int maxn=0;
    int cnt=0;
    int l=0;
    for(int i=0;i<2*m;i++)
    {
        if(s[i]=='(')
        {
            cnt++;
            l++;
        }
        else
            l--;
        if(l==0)break;
        maxn=max(maxn,l);
    }
    int ans=0;
    if(n+1<maxn)ans=n+1;
    else ans=min(cnt,maxn+(n-maxn+1)/2);
    printf("%d",ans);
    return 0;
}

B 最短串

题意

给定a，b两个串，要求找到最短的字符串s，其子串既包含a，也包含b，其中

Solution

通过数据范围5e3可知，这题可以暴力寻找以下四种情况(后两种情况选其一，即要么a是b的子串，要么b是a的子串)。
1、a的前缀和b的后缀相同，其相同的最大长度
2、a的后缀和b的前缀相同，其相同的最大长度
3、a是b的子串
4、b是a的子串

代码
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define ls i<<1
#define rs i<<1|1
typedef long long ll;
typedef pair<int,int>P;
char a[5005],b[5005];
int main()
{
    scanf("%s%s",a,b);
    int n=strlen(a);
    int m=strlen(b);
    int maxn=0;
    for(int i=1;i<=min(n,m);i++)
    {
        bool flag=true;
        for(int j=0;j<i;j++)
        {
            if(a[j]=='?'||b[m-i+j]=='?')continue;
            if(a[j]!=b[m-i+j])
            {
                flag=false;
                break;
            }
        }
        if(flag)
        {
            maxn=max(i,maxn);
            continue;
        }
        flag=true;
        for(int j=0;j<i;j++)
        {
            if(b[j]=='?'||a[n-i+j]=='?')continue;
            if(b[j]!=a[n-i+j])
            {
                flag=false;
                break;
            }
        }
        if(flag)maxn=max(i,maxn);
    }
    if(n>m)
    {
        for(int i=0;i+m-1<n;i++)
        {
            bool flag=true;
            for(int j=0;j<m;j++)
            {
                if(a[i+j]=='?'||b[j]=='?')continue;
                if(a[i+j]!=b[j])
                {
                    flag=false;
                    break;
                }
            }
            if(flag)
            {
                maxn=max(m,maxn);
                break;
            }
        }
    }
    else
    {
        for(int i=0;i+n-1<m;i++)
        {
            bool flag=true;
            for(int j=0;j<n;j++)
            {
                if(b[i+j]=='?'||a[j]=='?')continue;
                if(b[i+j]!=a[j])
                {
                    flag=false;
                    break;
                }
            }
            if(flag)
            {
                maxn=max(n,maxn);
                break;
            }
        }
    }
    printf("%d",n+m-maxn);
    return 0;
}

C 杨辉三角

题意

为杨辉三角中第n行提取出来的数，
求，答案对取模，其中

Solution
代码
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define ls i<<1
#define rs i<<1|1
typedef long long ll;
typedef pair<int,int>P;
const int mod=99824353;
int fpow(ll x,ll ti)
{
    ll ans=1;
    while(ti)
    {
        if(ti&1)ans=ans*x%mod;
        x=x*x%mod;
        ti>>=1;
    }
    return ans;
}
ll n;
int main()
{
    scanf("%lld",&n);
    n--;
    if(n==0)return 0*printf("0");
    else if(n==1)return 0*printf("1");
    ll res=(n%mod)*((n+1)%mod)%mod*fpow(2,n-2)%mod;
    printf("%lld",res);
    return 0;
}

D 哥三好

题意

三个人分别有元钱，他们经常去网吧，去一次网吧，其中一人一次性买三个人的单，网吧的电脑分为三种价位100元，150元，250元每晚/人，每次都会定三台相同价位的电脑，现在问有多少种请客方案，请客顺序不同算不同方案，最终答案对1e9+7取模，其中

Solution

从数据范围来看，请一次客有300,450,750三种选择，因此可以先把都除以150，然后暴力背包就行了。最后枚举剩下的钱把多有答案累加起来。

代码
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int a,b,c;
int dp[300][300][300];
int main()
{
    cin>>a>>b>>c;
    a/=150;b/=150;c/=150;
    dp[0][0][0]=1;
    for(int j=0;j<=a;j++)
    {
        for(int k=0;k<=b;k++)
        {
            for(int w=0;w<=c;w++)
            {
                if(dp[j][k][w])
                {
                    dp[j+2][k][w]=(dp[j+2][k][w]+dp[j][k][w])%mod;
                    dp[j][k+2][w]=(dp[j][k+2][w]+dp[j][k][w])%mod;
                    dp[j][k][w+2]=(dp[j][k][w+2]+dp[j][k][w])%mod;

                    dp[j+3][k][w]=(dp[j+3][k][w]+dp[j][k][w])%mod;
                    dp[j][k+3][w]=(dp[j][k+3][w]+dp[j][k][w])%mod;
                    dp[j][k][w+3]=(dp[j][k][w+3]+dp[j][k][w])%mod;

                    dp[j+5][k][w]=(dp[j+5][k][w]+dp[j][k][w])%mod;
                    dp[j][k+5][w]=(dp[j][k+5][w]+dp[j][k][w])%mod;
                    dp[j][k][w+5]=(dp[j][k][w+5]+dp[j][k][w])%mod;
                }
            }
        }
    }
    int res=0;
    for(int i=0;i<=1;i++)
    {
        for(int j=0;j<=1;j++)
        {
            for(int k=0;k<=1;k++)
            {
                if(a-i>=0&&b-j>=0&&c-k>=0)
                res=(res+dp[a-i][b-j][c-k])%mod;
            }
        }
    }
    printf("%d",res);
    return 0;
}

E 皇城PK

题意

有名选手会进行次比赛，每次比赛不会出现平局的情况，只会有一个胜者。视胜者选手的实例比败者的实例强，如果出现选手A打败选手B，选手B打败选手C，选手C打败选手A，则视为他们的实例全部相同。
问按现在已有的比赛结果，有多少个选手可能获得冠军（如果两个人实力一样，则都不能获得冠军）。
其中

Solution

把败者标记一下，只要有一次失败，则一定不可能成为冠军，最后统计未标记的人有多少个。

代码
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define ls i<<1
#define rs i<<1|1
typedef long long ll;
typedef pair<int,int>P;
const int mod=1e9+7;
int n,m;
int vis[100005];
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        vis[b]=1;
    }
    int num=0;
    for(int i=1;i<=n;i++)
    {
        if(vis[i])continue;
        num++;
    }
    printf("%d",num);
    return 0;
}

F 象棋

题意

给定的期盼，全部摆满炮，视所有炮都不属于同一阵营，他们之间可以相互攻击且不能不进行攻击直接移动。请问经历若干次攻击，直到不能攻击后，最少能剩余多少个炮。

Solution

首先要知道象棋中炮的攻击规则，炮只能攻击所在行或列里面隔着一个炮的炮
通过这个性质可以知道攻击完后最多剩下两行，最多剩下两列，因此答案就是

代码
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define ls i<<1
#define rs i<<1|1
typedef long long ll;
typedef pair<int,int>P;
const int mod=1e9+7;
int t;
ll n,m;
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%lld%lld",&n,&m);
        n=min(2ll,n);
        m=min(2ll,m);
        printf("%lld\n",n*m);
    }
    return 0;
}

G 永不言弃

题意

有个关卡，对于每个关卡有两种通过方式。小沙的初始属性为，当角色的属性大于关卡的最高上限时，能强行通过该关卡，或者拥有通过该关卡的必过道具（并不是消耗品）。每个关卡通过后可能会开启一个或多个后置关卡，但每个关卡开启也需要若干个前置关卡，只有前置关卡全部通过后，才能开启该关卡。tips：除了一号关卡，如果一个关卡没有任何前置关卡，那么该关卡无法永远开启。
每个关卡只能玩一次，并且通过后能增强小沙角色的属性，也会给一个必过道具。目前小沙能否将这个游戏打通。

Solution

拓扑排序+优先队列
用两个队列模拟一下过程，从第一个关卡开始打，如果属性大于该后置关卡上限，或者有必过道具，那么就能通过该后置关卡，获得其道具，把这个关卡的编号放到另一个队列中，如果当前关卡还有没有通过的后置关卡，那么该关卡的编号也要放到另一个队列中，操作完这个队列后再对另一个队列进行相同的操作，当整个队列中没有关卡再能通过时（如果能通过则能进行下一次另一个队列的模拟），跳出循环。

代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
ll s;
int vis[50005];
int pre[50005];
int a[50005];
int b[50005];
int c[50005];
int d[50005];
vector<int>e[50005];
int main()
{
    scanf("%d%lld",&n,&s);
    for(int i=1;i<=n;i++)scanf("%d%d",&a[i],&b[i]);
    for(int i=1;i<=n;i++)scanf("%d%d",&c[i],&d[i]);
    for(int i=1;i<=n;i++)
    {
        int k;scanf("%d",&k);
        for(int j=0;j<k;j++)
        {
            int x;scanf("%d",&x);
            e[i].push_back(x);
            pre[x]++;
        }
    }
    queue<int>q[5];
    int id=0;
    int res=0;
    if(s>=a[1])
    {
        res++;
        q[0].push(1);
        vis[d[1]]=1;
        s+=c[1];
     }
    while(true)
    {
        bool flag=true;
        while(!q[id].empty())
        {
            int now=q[id].front();q[id].pop();
            bool ff=true;
            for(int i=0;i<e[now].size();i++)
            {
                if(e[now][i]==-1)continue;
                int x=e[now][i];
                //cout<<x<<endl;
                if(vis[b[x]]||s>=a[x])
                {
                    s+=c[x];
                    vis[d[x]]=1;
                    e[now][i]=-1;
                    pre[x]--;
                    if(pre[x]==0)
                    {
                        q[id^1].push(x);
                        res++;
                    }
                    flag=false;
                }else ff=false;
            }
            if(!ff)q[id^1].push(now);
        }
        if(flag)break;
        id^=1;
    }
    //cout<<res<<endl;
    if(res==n)printf("Yes");
    else printf("No");
}

H 卷王之王

题意

有个数字，第个数字为，次操作，每次操作给出一个数字，将所有值小于等于的数字都加上,当次操作完成后，按顺序输出这个数字。
其中

Solution

据说正解可以用优先队列模拟，把的部分剪枝掉。
这边是通过线段树+剪枝通过的。
记录一下区间最小值，如果区间最小值大于，那么该区间就不用加上，直接返回就可以了。
再记录一下区间最大值，如果区间最大值小于等于，那么说明该区间的数都可以加上，加上后返回即可。

代码
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define ls i<<1
#define rs i<<1|1
typedef long long ll;
typedef pair<int,int>P;
int n,m;
int a[100005];
ll res[100005];
struct node
{
    int l,r;
    ll minn;
    ll maxn;
    ll lazy;
    ll x;
}tree[100005*4];
void push_up(int i)
{
    tree[i].minn=min(tree[ls].minn,tree[rs].minn);
    tree[i].maxn=max(tree[ls].maxn,tree[rs].maxn);
}
void build(int i,int l,int r)
{
    tree[i].l=l;
    tree[i].r=r;
    tree[i].lazy=0;
    if(l==r)
    {
        tree[i].x=a[l];
        tree[i].maxn=a[l];
        tree[i].minn=a[l];
        return;
    }
    int mid=(l+r)/2;
    build(ls,l,mid);
    build(rs,mid+1,r);
    push_up(i);
}
void push_down(int i)
{
    if(tree[i].l==tree[i].r)return;
    tree[ls].lazy+=tree[i].lazy;
    tree[rs].lazy+=tree[i].lazy;
    tree[ls].maxn+=tree[i].lazy;
    tree[rs].maxn+=tree[i].lazy;
    tree[ls].minn+=tree[i].lazy;
    tree[rs].minn+=tree[i].lazy;
    tree[i].lazy=0;
}
void update(int i,ll val)
{
    if(tree[i].minn>val)return;
    if(tree[i].maxn<=val)
    {
        tree[i].lazy+=val;
        tree[i].maxn+=val;
        tree[i].minn+=val;
        return ;
    }
    if(tree[i].l==tree[i].r)return;
    push_down(i);
    update(ls,val);
    update(rs,val);
    push_up(i);
}
void query(int i)
{
    push_down(i);
    if(tree[i].l==tree[i].r)
    {
        int id=tree[i].l;
        res[id]=tree[i].maxn;
        return ;
    }
    query(ls);
    query(rs);
    push_up(i);
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    build(1,1,n);
    while(m--)
    {
        int x;scanf("%d",&x);
        update(1,x);
    }
    query(1);
    for(int i=1;i<=n;i++)printf("%lld ",res[i]);
    return 0;
}

I 四面楚歌

题意

一个的区域，每块格子有以下几种类型：
.：表示为空地
1：表示为敌兵，不许通过，敌兵不会移动
0：表示为我方士兵
我方士兵只能上/下/左/右移动，问有多少个士兵能移出边界

Solution

要知道每个士兵能不能突围，正着思考需要知道每个我方士兵能否到达边界，这样无疑会tle，但是反着思考（0，0）点能到达多少个我方士兵，通过bfs就能找到多少士兵能够突围。

代码
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define ls i<<1
#define rs i<<1|1
typedef long long ll;
typedef pair<int,int>P;
const int mod=1e9+7;
int n,m;
char s[1005][1005];
int dx[]={1,-1,0,0},dy[]={0,0,1,-1};
queue<P>q;
int d[1005][1005];
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%s",s[i]+1);
    memset(d,INF,sizeof(d));
    d[0][0]=0;
    q.push(P(0,0));
    int res=0;
    while(!q.empty())
    {
        P p=q.front();q.pop();
        for(int i=0;i<4;i++)
        {
            int x=dx[i]+p.first;
            int y=dy[i]+p.second;
            if(x<0||x>n+1||y<0||y>m+1)continue;
            if(d[x][y]!=INF||s[x][y]=='1')continue;
            d[x][y]=0;
            if(s[x][y]=='0')
            {
                //cout<< x<<' '<<y<<endl;
                s[x][y]='.';
                res++;
            }
            q.push(P(x,y));
        }
    }
    printf("%d",res);
    return 0;
}

J 科学幻想

题意

长度为的字符串，有个指令，指令有以下两种：
1：将第个字符修改为
2：判断区间的字符串与区间的字符串是否勉强相等。
勉强相等指的是长度相等，对应位置上最多有一个位置的字符不同。

Solution

1.对于修改字符，可以线段树进行单点修改字符
2.对于字符串是否勉强相等，先判断两个区间长度是否相等，如果相等则二分对hash值进行判断：
左边部分相同，则可以向右缩小区间
左边部分不相同，右边部分相同，则可向左缩小区间
左边部分和右边部分都不相同，则说明这两个区间不勉强相等

代码
#include <bits/stdc++.h>
#define ls i<<1
#define rs i<<1|1
using namespace std;
typedef long long ll;
const int P=131;
const int mod=1e9+7;
int n,m;
char s[100005];
int p[100005];
struct node
{
    int l,r;
    int x;
}tree[400000+5];
void push_up(int i)
{
    int len=tree[rs].r-tree[rs].l+1;
    tree[i].x=(1ll*tree[ls].x*p[len]%mod+tree[rs].x)%mod;
}
void build(int i,int l,int r)
{
    tree[i].l=l;
    tree[i].r=r;
    if(tree[i].l==tree[i].r)
    {
        tree[i].x=s[l]-'a';
        return ;
    }
    int mid=(l+r)/2;
    build(ls,l,mid);
    build(rs,mid+1,r);
    push_up(i);
}
void update(int i,int l,int val)
{
    if(tree[i].l==l&&tree[i].r==l)
    {
        tree[i].x=val;
        return ;
    }
    int mid=(tree[i].l+tree[i].r)/2;
    if(mid>=l)update(ls,l,val);
    if(mid<l)update(rs,l,val);
    push_up(i);
}
node query(int i,int l,int r)
{
    if(l>r)return tree[i];
    if(l<=tree[i].l&&tree[i].r<=r)
    {
        return tree[i];
    }
    int mid=(tree[i].l+tree[i].r)/2;
    if(l<=mid&&r>mid)
    {
        node a=query(ls,l,r);
        node b=query(rs,l,r);
        a.r=b.r;
        a.x=(1ll*a.x*p[b.r-b.l+1]%mod+b.x)%mod;
        return a;
    }
    else if(l<=mid)return query(ls,l,r);
    else if(r>mid)return query(rs,l,r);
}
bool solve(int l1,int r1,int l2,int r2)
{
    if((r2-l2)!=(r1-l1))return false;
    int l=0,r=r2-l2;
    while(l<=r)
    {
        int mid=(l+r)/2;
        int lsum1=query(1,l1,l1+mid).x;
        int lsum2=query(1,l2,l2+mid).x;
        if(lsum1==lsum2)
        {
            l=mid+1;
            continue;
        }
        int rsum1=query(1,l1+mid+1,r1).x;
        int rsum2=query(1,l2+mid+1,r2).x;
        if(rsum1==rsum2)
        {
            r=mid-1;
            continue;
        }
        return false;
    }
    return true;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    cin>>(s+1);
    p[0]=1;
    for(int i=1;i<=n;i++)p[i]=1ll*p[i-1]*P%mod;
    //scanf("%d%d",&n,&m);
    //scanf("%s",s+1);
    build(1,1,n);
    while(m--)
    {
        int op;//scanf("%d",&op);
        cin>>op;
        if(op==1)
        {
            int x;char ch[5];
            cin>>x>>ch;
            //scanf("%d%s",&x,ch);
            update(1,x,ch[0]-'a');
        }
        else
        {
            int l1,l2,r1,r2;
            cin>>l1>>r1>>l2>>r2;
            //scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
            if(solve(l1,r1,l2,r2))cout<<"YES\n";//printf("YES\n");
            else cout<<"NO\n";//printf("NO\n");
        }
    }
    return 0;
}
全部评论

相关推荐

11-22 22:26
门头沟学院 前端工程师
糕手的秋招总结
没人规定0offer就不能写秋招总结吧？😡写出我的经历，让你们看看我至今还是0offer糕手，都做对了些什么🤡🤡🤡糕手思维比较发散，所以写帖子一般废话多了点我尽量来点干货（话说今天恰华莱士给我干窜了。。。）前排提醒，小白向的，您都拿大厂offer或者就是前端大师，糕手可不敢在您面前造次啊🤡🤡🤡1.运气非常重要，如果你做到了这一条，剩下的都是狗屁，没啥要看的了2.简历还是简点好，缩成一页已经是老生常谈了，除非你四五段实习吧。就拿前端举例子，不太建议写TS。刚开始的小白思维都这样，我新学会个技术栈，那一定要写上，证明我的牛x都这么过来的，都懂我从始至终都不太喜欢TS，你可以...
剑与她皆失：当初实习离职的时候想一段实习加上我是java后端转测试，那大厂测试测开offer不得框框拿🤡🤡🤡🤡
点赞 评论 收藏
分享
昨天 10:10
华中科技大学 Java
点赞 评论 收藏
分享
10-28 12:12
东北大学 自动化测试
点赞 评论 收藏
分享
10-11 18:35
中国矿业大学 机械设计师
笑死，我写的吐槽被搬到脉脉了
专心打鱼：互联网搬运工，贴子都要偷
点赞 评论 收藏
分享
11-21 04:39
南昌大学 Java
26届求助：老生常谈了，考研还是就业
26届211本，目前在准备就业，大一大二啥都没学，这学期大三开学才开始学，学的很差，但是通过学校找到了一家中厂下学期开学的实习（难度比普通自己找低很多）。刚开始没想过考研，不想读研卷学历，后来开始考虑，担心吃学历的亏。核心问题就是：我这种情况，工作三年和读研比哪个以后发展更好，或者差不多。看牛客上还是大部分是研究生能拿到很好的offer，但社招应该也不看牛客，不知道到底是什么情况，求求过来人帮帮我吧
scoxty：我大三上才开始系统学习的开发本科够了，早准备早投递
投递牛客等公司10个岗位 > 如果能重来，就业or读研你选哪个？ 你会选择考研还是直接就业
点赞 评论 收藏
分享
点赞 收藏 评论
分享

全站热榜

正在热议
# 25届秋招总结 #
279235次浏览 2418人参与
# 如果实习可以转正，你会不会放弃秋招 #
206106次浏览 2807人参与
# 北方华创开奖 #
24550次浏览 263人参与
# 地方国企笔面经互助 #
3271次浏览 7人参与
# 学历or实习经历，哪个更重要 #
47496次浏览 368人参与
# 选完offer后，你后悔学本专业吗 #
16718次浏览 120人参与
# 如何一边实习一边秋招 #
989182次浏览 12623人参与
# 软开人，秋招你打算投哪些公司呢 #
41669次浏览 534人参与
# 数据人的面试交流地 #
436334次浏览 7812人参与
# 0offer是寒冬太冷还是我太菜 #
892939次浏览 7965人参与
# 得物求职进展汇总 #
64896次浏览 674人参与
# 求职遇到的搞笑事件 #
69016次浏览 571人参与
# 你觉得专业和学校哪个对薪资影响最大 #
28944次浏览 215人参与
# 查收我的offer竞争力报告 #
21282次浏览 263人参与
# 你最想要的公司福利是？ #
43504次浏览 161人参与
# 没有实习经历，还有机会进大厂吗 #
809035次浏览 13886人参与
# 来聊聊机械薪资天花板是哪家 #
67512次浏览 460人参与
# 当你面对裁员会如何？ #
26529次浏览 156人参与
# 一觉醒来，我觉醒了超级打工人系统 #
3644次浏览 38人参与
# 应届生被毁约被毁意向了怎么办 #
28849次浏览 247人参与
# 面试体验感最好的是哪家？ #
84195次浏览 822人参与
牛客网
牛客企业服务