2020-08-22 22:33 已编辑中南大学 C++

关注

【题解】牛客小白月赛27

前面的碎碎念：
首先要特别感谢Hewitt，Amori，henry_y三位大佬对本场比赛所有题目测试所提供的意见！
本场比赛大部分题目均由经典套路改编，相信对初学者提升自己会提供一些帮助。不过对于经验丰富的选手，本套题目可能会略显无聊，没有提供更有趣的题目，在此也是对那些选手说一声抱歉QAQ。

题目难度预估：
简单：E/G/J
中等：B/D/F/H
困难：A/C/I

A-巨木之森

考点：树的直径。
我们求出从每个结点出发，遍历完树上所有结点的最短路程和，然后把这n个最短路程和从小到大排序，找到前缀和小于等于m的最大下标输出即可。那么接下来的问题是如何快速求取这n个最短路程和。
通过贪心考虑得出一个结论，从一个点出发遍历所有结点并最后回到原来的点，则树上所有边都要访问两次。而在这道题中访问到最后一个点立即停下来，那么最短路程和就是走到离出发点最远的那个点停下，即所有边的长度和 $图片说明$ 2-出发点走到离它最远点的距离。
而由于有多个出发点，我们利用树的直径的性质，也就是在树上任意一点的最远点一定是树的直径的端点，于是我们只需求出任意一条树的直径，那么这条直径的2个端点一定有一个是每个点的最远点。因此我们从任意一点DFS，找到树的直径的一个端点，从该端点再DFS，找到树的直径的另一个端点。利用DFS，我们可以得到两个Dis数组，Dis1[i]和Dis2[i]分别表示从树的直径的两个端点到i号结点的距离。利用这两个数组，我们就可以求出每个结点到最远点的距离，从而求出从每个结点出发遍历完树上所有结点的最短路程和。
时间复杂度：O(n $图片说明$ log(n))。

标程：

#include<bits/stdc++.h>
using namespace std;

struct node
{
    long long x,h;
}Q[100005];
vector<int>R[100005],W[100005];
long long m,t,s=0,Dis[2][100005],T[100005];
bool V[100005];
void BFS(int sx,bool a)
{
    long long i,j,x,h,f=0,r=1;
    memset(V,0,sizeof(V));
    Q[0].h=0,Q[0].x=sx,V[sx]=1;
    while(r!=f)
    {
        x=Q[f].x,h=Q[f++].h;
        Dis[a][x]=h;
        for(i=0;i<R[x].size();i++)
        {
            j=R[x][i];
            if(!V[j])V[j]=1,Q[r].x=j,Q[r++].h=h+W[x][i];
        }
    }
}
int main()
{
    int i,j,k,l,r,n;
    scanf("%d%lld",&n,&m);
    for(i=1;i<n;i++)
    {
        scanf("%d%d%d",&j,&k,&l),s+=l;
        R[j].push_back(k),R[k].push_back(j);
        W[j].push_back(l),W[k].push_back(l);
    }
    BFS(1,0);
    for(t=-1,i=1;i<=n;i++)if(t<Dis[0][i])t=Dis[0][i],l=i;
    BFS(l,0);
    for(t=-1,i=1;i<=n;i++)if(t<Dis[0][i])t=Dis[0][i],r=i;
    BFS(r,1);
    for(i=1;i<=n;i++)T[i]=s*2-max(Dis[0][i],Dis[1][i]);
    sort(T+1,T+1+n);
    for(t=0,i=1;i<=n;i++)
    {
        t+=T[i]; 
        if(t>m)break;
    }
    printf("%d\n",i-1);
    return 0;
}

B-乐***对

考点：动态规划
我们对a数组从小到大排序，设DP[i]为前i个乐手最多能组成DP[i]个乐队，那么有转移方程：
① i<a[i]，DP[i]=0
② i>=a[i]，DP[i]=max(DP[i-a[i]], DP[i-a[i]-1], …,DP[0])+1
所以我们边转移边维护一个前缀max数组，即可线性求出DP[n]。最后看DP[n]是否为0，若为0则输出-1，否则输出DP[n]。
时间复杂度：O(n $图片说明$ log(n))。

标程：

#include<bits/stdc++.h>
using namespace std;

int a[100005],Max[100005]={0};
int main()
{
    int i,n,DP;
    scanf("%d",&n);
    for(i=1;i<=n;i++)scanf("%d",&a[i]);
    sort(a+1,a+1+n);
    for(i=1;i<=n;i++)
    {
        if(i>=a[i])DP=Max[i-a[i]]+1;
        else DP=0;
        Max[i]=max(Max[i-1],DP);
    }
    if(!DP)DP=-1;
    printf("%d\n",DP);
    return 0;
}

C-光玉小镇

考点：搜索+状压DP
首先一个很直白的思想就是单纯的BFS搜索，但是这样要搜索n $图片说明$ m $图片说明$ 2^|T|种状态，其中|T|表示图中电线杆的数量，对于此题肯定是超时无疑了。于是我们考虑把图中的‘S’与‘T’单独抽出来，两两之间BFS建图，其中Dis1[i]表示从家出发到i号电线杆的最短时间，Dis2[i][j]表示从i号电线杆到j号电线杆的最短时间。建图部分的时间复杂度是O(n $图片说明$ m $图片说明$ |T|^2)。
建完图后，有两种做法，第一种做法是DFS暴力枚举|T|!种路线。什么意思呢，比如有3个电线杆a,b,c，那么就有：家→a→b→c→家，家→a→c→b→家，家→b→a→c→家，家→b→c→a→家，家→c→a→b→家，家→c→b→a→家，这样的六种路线。所以我们暴力枚举出|T|!种路线，求出其对应所要花费的时间，然后保存最小值即可。但是可恶的出题人把|T|的最大数量出到了15，O(|T|!)的时间复杂度仍然会超时。因此采取第二种做法状压DP。
我们设DP[i][j]为在状态i时，最后一个修理的是j号电线杆的最短时间。其中状态i表示，若i的二进制形式上第k位为1，则k号电线杆已被修理，否则k号电线杆未被修理。其状态转移方程如下：

for(i=0;i<(1<<|T|);i++)
{
    for(j=0;j<|T|;j++)
    {
        if(((1<<j)&i)==0)continue;
        for(k=0;k<|T|;k++)
        {
            if((1<<k)&i)continue;
            DP[i|1<<k][k]=min(DP[i|1<<k][k],DP[i][j]+Dis2[j][k]);
        }
    }
}

最后我们遍历一遍DP数组，令ans=min(ans, DP[(1<<|T|)-1][i]+|T| $图片说明$ t+Dis1[i])就行了。状压DP部分的时间复杂度是O(2^|T| $图片说明$ |T|^2)。
时间复杂度：O((n $图片说明$ m+2^|T|) $图片说明$ |T|^2)。

标程：

#include<bits/stdc++.h>
using namespace std;

struct node1
{
    int x,y,h;
}Q[40005];
struct node2
{
    int x,y;
}T[20];
int n,m,L=0,dx[]={1,-1,0,0},dy[]={0,0,1,-1};
int Dis1[20],Dis2[20][20],DP[33005][20];
char R[205][205];
bool V[205][205];
int BFS(int sx,int sy,int ex,int ey)
{
    int i,r=1,f=0,x,y,h,X,Y,flag=0;
    memset(V,0,sizeof(V)),V[sx][sy]=1;
    Q[0].x=sx,Q[0].y=sy,Q[0].h=0;
    while(r!=f)
    {
        x=Q[f].x,y=Q[f].y,h=Q[f++].h;
        if(x==ex&&y==ey)
        {
            flag=1;
            break;
        }
        for(i=0;i<4;i++)
        {
            X=x+dx[i],Y=y+dy[i];
            if(X<0||X>=n||Y<0||Y>=m||V[X][Y]||R[X][Y]=='#')continue;
            V[X][Y]=1,Q[r].x=X,Q[r].y=Y,Q[r++].h=h+1;
        }
    }
    if(!flag)h=-1;
    return h;
}
int main()
{
    int i,j,k,sx,sy;
    long long t,ans=1e18;
    scanf("%d%d%lld",&n,&m,&t);
    memset(DP,0x3f,sizeof(DP)); 
    for(i=0;i<n;i++)scanf("%s",R[i]);
    for(i=0;i<n;i++)
    {
        for(j=0;j<m;j++)
        {
            if(R[i][j]=='S')sx=i,sy=j;
            if(R[i][j]=='T')T[L].x=i,T[L++].y=j;
        }
    }
    for(i=0;i<L;i++)
    {
        DP[1<<i][i]=Dis1[i]=BFS(sx,sy,T[i].x,T[i].y);
        if(Dis1[i]==-1){printf("-1\n");return 0;}
    }
    for(i=0;i<L;i++)
        for(j=i+1;j<L;j++)Dis2[i][j]=Dis2[j][i]=BFS(T[i].x,T[i].y,T[j].x,T[j].y);
    for(i=0;i<(1<<L);i++)
    {
        for(j=0;j<L;j++)
        {
            if(((1<<j)&i)==0)continue;
            for(k=0;k<L;k++)
            {
                if((1<<k)&i)continue;
                DP[i|1<<k][k]=min(DP[i|1<<k][k],DP[i][j]+Dis2[j][k]);
            }
        }
    }
    for(i=0;i<L;i++)ans=min(ans,DP[(1<<L)-1][i]+Dis1[i]+L*t);
    printf("%lld\n",ans);
}

D-巅峰对决

考点：线段树
因为数据保证任何时候这n个数字均互不相同，所以利用线段树维护区间最大值和区间最小值，对于每次2类型询问的区间，若区间最大值-区间最小值+1=区间长度，则输出YES，否则输出NO。
时间复杂度：O((n+q) $图片说明$ log(n))。

标程：

#include<bits/stdc++.h>
using namespace std;

int y,MAX,MIN,Max[400005],Min[400005];
void build(int L,int R,int x)
{
    if(L==R)
    {
        scanf("%d",&y);
        Max[x]=Min[x]=y;
        return;
    }
    int M=(L+R)>>1;
    build(L,M,x<<1),build(M+1,R,x<<1|1);
    Max[x]=max(Max[x<<1],Max[x<<1|1]);
    Min[x]=min(Min[x<<1],Min[x<<1|1]);
}
void update(int L,int R,int l,int r,int x)
{
    if(l<=L&&R<=r)
    {
        Max[x]=Min[x]=y;
        return;
    }
    int M=(L+R)>>1;
    if(M>=l)update(L,M,l,r,x<<1);
    if(M<r)update(M+1,R,l,r,x<<1|1);
    Max[x]=max(Max[x<<1],Max[x<<1|1]);
    Min[x]=min(Min[x<<1],Min[x<<1|1]);
}
void search(int L,int R,int l,int r,int x)
{
    if(l<=L&&R<=r)
    {
        MAX=max(MAX,Max[x]),MIN=min(MIN,Min[x]);
        return;
    }
    int M=(L+R)>>1;
    if(M>=l)search(L,M,l,r,x<<1);
    if(M<r)search(M+1,R,l,r,x<<1|1);
}
int main()
{
    int i,n,q,op,x,l,r;
    scanf("%d%d",&n,&q);
    build(1,n,1);
    while(q--)
    {
        scanf("%d",&op);
        if(op==1)scanf("%d%d",&x,&y),update(1,n,x,x,1);
        else
        {
            scanf("%d%d",&l,&r);
            MAX=0,MIN=2e9,search(1,n,l,r,1);
            if(MAX-MIN==r-l)printf("YES\n");
            else printf("NO\n");
        }
    }
    return 0;
}

E-使徒袭来

考点：数学
根据基本不等式，有： $图片说明$ 。因此答案即为 $图片说明$ 。
时间复杂度：O(1)。

标程：

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    scanf("%d",&n);
    printf("%.3lf\n",3*pow(n,1.0/3));
    return 0;
}

F-核弹剑仙

考点：bitset+拓扑排序
我们先根据破坏力强弱关系建图，若a武器破坏力强于b武器破坏力，则a号结点向b号结点连一条有向边。接着对每个结点开一个bitset，第i位为1则表示i号武器破坏力强于本武器。然后开始进行拓扑排序，每次把当前结点的bitset信息转移到下一个节点的bitset上，同时把当前结点编号在下一个节点bitset的相应位置置1，最后输出每个节点bitset上的1的个数即可。
考虑到大家的比赛体验，数据量保证使用set的O((m+n) $图片说明$ n $图片说明$ log(n))做法和未利用bitset优化的O((m+n) $图片说明$ n)做法均可通过此题。
时间复杂度：O((m+n) $图片说明$ n/64)。

标程：

#include<bits/stdc++.h>
using namespace std;

bitset<1005>T[1005];
vector<int>R[1005];
int main()
{
    int i,j,n,m,x,r=0,f=0,Q[1005],in[1005]={0};
    scanf("%d%d",&n,&m);
    while(m--)
    {
        scanf("%d%d",&i,&j);
        R[i].push_back(j),in[j]++;
    }
    for(i=1;i<=n;i++)if(!in[i])Q[r++]=i;
    while(r!=f)
    {
        x=Q[f++];
        for(i=0;i<R[x].size();i++)
        {
            j=R[x][i];
            T[j]|=T[x],T[j][x]=1;
            if(!(--in[j]))Q[r++]=j;
        }
    }
    for(i=1;i<=n;i++)printf("%d\n",T[i].count());
    return 0;
}

G-虚空之力

考点：贪心
很明显我们需要尽量利用第二种方式组合礼炮。遍历字符串求出‘k’ ‘i’ ‘n’ ‘g’四个字符的个数，设t=min(‘i’字符个数，‘n’字符个数，‘g’字符个数)。若‘k’字符个数 $图片说明$ 2小于等于t，则答案为‘k’字符个数 $图片说明$ 2，否则答案为t。
时间复杂度：O(n)。

标程：

#include<bits/stdc++.h>
using namespace std;

char R[10000005];
int main()
{
    int i,n,ans,a=0,b=0,c=0,d=0,t;
    scanf("%d%s",&n,R);
    for(i=0;i<n;i++)
    {
        if(R[i]=='k')a++;
        if(R[i]=='i')b++;
        if(R[i]=='n')c++;
        if(R[i]=='g')d++;
    }
    t=min(b,min(c,d));
    if(2*a>t)ans=t;
    else ans=2*a;
    printf("%d\n",ans);
    return 0;
}

H-社团游戏

考点：二维前缀和+二分
首先我们得知道，对于任意一个小写字母，其正方形边长越长，那么在这个矩阵中找到该字母个数和超过k的正方形的可能性也就越大，因此这个边长具有单调性可以二分。
所以我们对每个小写字母预处理一个二维前缀和，然后枚举左上角，之后二分边长。对于每次二分的边长，我们判断其形成的正方形是否符合任意一类小写字母个数之和不超过k就行了。
时间复杂度：O(26 $图片说明$ n $图片说明$ m $图片说明$ log(min(n,m)))。

标程：

#include<bits/stdc++.h>
using namespace std;

int n,m,k,S[26][505][505]={0};
char R[505][505];
bool judge(int x1,int y1,int x2,int y2)
{
    for(int i=0;i<26;i++)
        if(S[i][x2][y2]-S[i][x1-1][y2]-S[i][x2][y1-1]+S[i][x1-1][y1-1]>k)return 0;
    return 1;
}
int main()
{
    int i,j,l,r,mid,ans;
    scanf("%d%d%d",&n,&m,&k);
    for(i=1;i<=n;i++)scanf("%s",R[i]+1);
    for(l=0;l<26;l++)
        for(i=1;i<=n;i++)
            for(j=1;j<=m;j++)
                S[l][i][j]=S[l][i-1][j]+S[l][i][j-1]-S[l][i-1][j-1]+(R[i][j]==l+'a');
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        {
            for(l=1,r=min(n-i+1,m-j+1);l<=r;)
            {
                mid=(l+r)>>1;
                if(judge(i,j,i+mid-1,j+mid-1))ans=mid,l=mid+1;
                else r=mid-1;
            }
            printf("%d",ans);
            if(j<m)printf(" ");
        }
        printf("\n");
    }
    return 0;
}

I-名作之壁

考点：尺取法+单调队列。
设答案为ans，考虑使用尺取法，用右指针r遍历数组。若[l,r]区间内最大值与最小值之差大于k，则此时对答案的贡献为n-r+1。因为[l,r+1],[l,r+2],…,[l,n]区间的最大值只可能大于等于[l,r]区间的最大值，[l,r+1],[l,r+2],…,[l,n]区间的最小值只可能小于等于[l,r]区间的最小值。因此若[l,r]区间为畅销区间，则[l,r+1],[l,r+2],…,[l,n]区间肯定也都为畅销区间。所以只要[l,r]区间的最大值与最小值之差大于k，我们就令ans+= n-r+1，同时移动左指针，令l++，直到[l,r]区间的最大值与最小值之差小于等于k。
当右指针r遍历完整个数组，我们输出ans即可。至于维护[l,r]区间内的最大值和最小值，我们可以使用两个单调队列来实现。
时间复杂度：O(n)。

标程：

#include<bits/stdc++.h>
using namespace std;

const int mod=1e9;
int r1=0,f1=0,r2=0,f2=0,a[10000005],Q1[10000005],Q2[10000005];
int main()
{
    int n,k,b,c,L,R;
    long long ans=0;
    scanf("%d%d%d%d%d",&n,&k,&a[0],&b,&c);
    for(L=R=1;R<=n;R++)
    {
        a[R]=((long long)a[R-1]*b+c)%mod;
        while(r1>f1&&a[Q1[r1-1]]>=a[R])r1--;
        Q1[r1++]=R;
        while(r2>f2&&a[Q2[r2-1]]<=a[R])r2--;
        Q2[r2++]=R;
        while(a[Q2[f2]]-a[Q1[f1]]>k)
        {
            ans+=n-R+1,L++;
            if(Q1[f1]<L)f1++;
            if(Q2[f2]<L)f2++;
        }
    }
    printf("%lld\n",ans);
    return 0;
}

J-逃跑路线

考点：位运算
首先我们很容易知道(2^1-1)&(2^2-1)&…&(2^n-1)=1，也就是说我们要求这n个数字之和为奇数还是偶数。若一个数字加上偶数，奇偶性不变；若一个数字加上奇数，奇偶性变化，因此我们只需看这n个数字中有多少个奇数就行了。至于判断一个数字是否是奇数，只需看它最后一位是否是奇数。
时间复杂度：O(n $图片说明$ |a[i]|)。

标程：

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int i,n,len,ans=0;
    char R[10005];
    scanf("%d",&n);
    while(n--)
    {
        scanf("%s",R),len=strlen(R);
        if((R[len-1]-'0')&1)ans^=1;
    }
    printf("%d\n",ans);
    return 0;
}

update：B题数据弱了，赛后加强了数据，大家可以重新去提交看看原来的代码是否正确。

全部评论

推荐最新楼层

啊哈2147483647

许昌学院 Java

感觉收获很多，非常感谢，期待奆佬的下一场比赛

3 回复分享

发布于 2020-08-24 13:19

蒜拧孟

电子科技大学中山学院后端工程师

好题，都能学

1 回复分享

发布于 2020-08-23 00:48

今非昔比彡

文远知行_infra_仿真算法工程师

C题为什么分层图最短路假了啊，我想不出啥反例可以hack。

点赞回复分享

发布于 2020-08-23 11:12

Doran_dinosaur

门头沟学院 Java

佬儿，G题数据能给一下吗？或者列举一下bug么？我觉得没问题orz https://ac.nowcoder.com/acm/contest/view-submission?submissionId=44791417

点赞回复分享

发布于 2020-08-23 09:24

zxjyes

中国科学院大学算法工程师

蒟蒻求助，B的转移方程怎么推的？？

点赞回复分享

发布于 2020-08-23 09:03

CoolGuang!

博乐科技_服务端开发工程师

如果I题小于等于k 有什么方法嘛？

点赞回复分享

发布于 2020-08-23 00:42

BHU吴嘉帅

北华大学 C++

B 这个过不去了，或者列举一下bug么？我觉得没问题啊！😂 https://ac.nowcoder.com/acm/contest/view-submission?submissionId=44785459

点赞回复分享

发布于 2020-08-22 23:59

Falcon__

西安交通大学后端工程师

其实A题可以使用动态规划，dp[u][1],dp[u][0]表示，我对于u这个子树，1---我回来，0---我不回来，的最优花费，然后随意一个为root,dfs一遍，再考虑转移(这个很简单，不多说)，然后在进行换根，这里涉及细节，我把代码贴上 https://paste.ubuntu.com/p/TR68YdBMkH/

点赞回复分享

发布于 2020-08-22 23:11