牛客小白月赛36

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

Solution

对括号序列建树，找到最长链，其余部分可以随便跑，代价是 $2\times (节点数-1)$ 。根据能否跑完最长链计算答案。

代码

#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，其中 $|a|\leq5000，|b|\leq5000$

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 杨辉三角

题意

$a_i$ 为杨辉三角中第n行提取出来的数， $i\in[0,n-1]$
求 $\sum_{i=0}^{n-1}i^2\times a[i]$ ，答案对 $99824353$ 取模，其中 $n\leq10^{18}$

Solution

$\sum_{i=0}^{n-1}i^2\times a[i] \\ =\sum_{i=0}^{n-1} i^2 \times (_{\ \ \ i}^{n-1}) \\ =\sum_{i=0}^{n-1}i^2\times \frac{(n-1)!}{i!(n-i-1)!} \\ =\sum_{i=0}^{n-1}i^2\times \frac{(n-1)\times(n-2)!}{i\times(i-1)!(n-i-1)!} \\ =(n-1)\sum_{i=0}^{n-2}i\times \frac{(n-2)!}{(i-1)!(n-i-1)!} \\ =(n-1)\sum_{i=0}^{n-2}[(i-1)+1]\frac{(n-2)!}{(i-1)!(n-i-1)!} \\ =(n-1)(\sum_{i=0}^{n-2}(i-1)\frac{(n-2)!}{(i-1)!(n-i-1)!}+\sum_{i=0}^{n-2}\frac{(n-2)!}{(i-1)!(n-i-1)!}) \\ =(n-1)(\sum_{i=0}^{n-2}(i-1)\frac{(n-2)\times(n-3)!}{(i-1)\times(i-2)!(n-i-1)!}+2^{n-2}) \\ =(n-1)((n-2)\sum_{i=0}^{n-3}\frac{(n-3)!}{(i-2)!(n-i-1)!}+2^{n-2}) \\ =(n-1)((n-2)2^{n-3}+2^{n-2}) \\ =(n-1)(n\times 2^{n-3}-2\times2^{n-3}+2^{n-2}) \\ =(n-1)\times n \times 2^{n-3}$

代码

#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 哥三好

题意

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

Solution

从数据范围来看，请一次客有300,450,750三种选择，因此可以先把 $a,b,c$ 都除以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

题意

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

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 象棋

题意

给定 $n\times m$ 的期盼，全部摆满炮，视所有炮都不属于同一阵营，他们之间可以相互攻击且不能不进行攻击直接移动。请问经历若干次攻击，直到不能攻击后，最少能剩余多少个炮。 $T组样例，n\leq10^{18},m\leq10^{18}$

Solution

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

代码

#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 永不言弃

题意

有 $n$ 个关卡，对于每个关卡有两种通过方式。小沙的初始属性为 $s$ ，当角色的属性大于关卡的最高上限时，能强行通过该关卡，或者拥有通过该关卡的必过道具（并不是消耗品）。每个关卡通过后可能会开启一个或多个后置关卡，但每个关卡开启也需要若干个前置关卡，只有前置关卡全部通过后，才能开启该关卡。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 卷王之王

题意

有 $n$ 个数字，第 $i$ 个数字为 $a[i]$ ， $m$ 次操作，每次操作给出一个数字 $x$ ，将所有值小于等于 $x$ 的数字都加上 $x$ ,当 $m$ 次操作完成后，按顺序输出这 $n$ 个数字。
其中 $n\leq10^5,m\leq10^5,a[i]\leq10^9,x\leq10^9$

Solution

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

代码

#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 四面楚歌

题意

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

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 科学幻想

题意

长度为 $n$ 的字符串，有 $m$ 个指令，指令有以下两种：
1：将第 $x$ 个字符修改为 $y$
2：判断 $[l1,r1]$ 区间的字符串与 $[l2,r2]$ 区间的字符串是否勉强相等。
勉强相等指的是长度相等，对应位置上最多有一个位置的字符不同。

Solution

1.对于修改字符，可以线段树 $log(n)$ 进行单点修改字符
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;
}