【题解】牛客小白月赛39题解

视频讲解：https://www.bilibili.com/video/BV1oq4y197n5
（有什么想对出题人说的或对题目的讨论可以在评论区发言QAQ）
ps:想看花絮的可以等内测群友补充
出题人的碎碎念：
对本场比赛的预期：
预计：
签到：ABCE
中档：DFGH
由于中档比较多（加上压轴被毙了，所以没有绝对难度的压轴，大佬们AK得比较快QAQ）
A 憧憬：符合预期
B 欢欣：符合预期
C 奋发：低于预期
D 绝望：符合预期
E 迷惘：符合预期
F 孤独：低于预期
G 冷静：高于预期
H 终别：符合预期
AK人数：低于预期
QAQ
整体来说，基本能让大家都有良好的体验感，只是大佬们可能觉得不够痛快QAQ
赛时根据榜的情况及选手反馈添加了一些样例和解释让大家能更好的理解题意QAQ

A 憧憬

考点：简单数学
分类：签到
向量平行：x1y2-x2y1=0，然后O(n^2)枚举即可

#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#define LL long long
using namespace std;
const int INF=0x3f3f3f3f;
int read()
{
   int s=0,bj=0;
   char ch=getchar();
   while(ch<'0'||ch>'9')bj|=(ch=='-'),ch=getchar();
   while(ch>='0'&&ch<='9')s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
   return bj?-s:s;
}
void printnum(int x)
{
    if(x>9)printnum(x/10);
    putchar(x%10^48);
}
void print(int x,char ch)
{
    if(x<0){putchar('-');x=-x;}
    printnum(x);putchar(ch);
}
int n;
struct node{int X1,Y1,X2,Y2;}a[1005];
int nox,noy;
int ans;
int main()
{
    n=read();
    for(int i=1;i<=n;++i)
    {
        a[i].X1=read();a[i].Y1=read();a[i].X2=read();a[i].Y2=read();
    }
    int X1=read(),Y1=read(),X2=read(),Y2=read();
    for(int i=1;i<=n;++i)
    for(int j=i+1;j<=n;++j)
    if((a[i].X2-a[i].X1+a[j].X2-a[j].X1)*(Y2-Y1)==(a[i].Y2-a[i].Y1+a[j].Y2-a[j].Y1)*(X2-X1)){puts("YES");return 0;}
    puts("NO");
    return 0;
}

B 欢欣

考点：模拟
分类：签到
不多说，简单的字符串枚举即可。

#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#define LL long long
using namespace std;
const int INF=0x3f3f3f3f;
int read()
{
   int s=0,bj=0;
   char ch=getchar();
   while(ch<'0'||ch>'9')bj|=(ch=='-'),ch=getchar();
   while(ch>='0'&&ch<='9')s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
   return bj?-s:s;
}
void printnum(int x)
{
    if(x>9)printnum(x/10);
    putchar(x%10^48);
}
void print(int x,char ch)
{
    if(x<0){putchar('-');x=-x;}
    printnum(x);putchar(ch);
}
char ch[1000005];
int main()
{
    scanf("%s",ch+1);
    int len=strlen(ch+1);
    for(int i=1;i<=len-2;++i)
    {
        if(ch[i]=='Q'&&ch[i+1]=='A'&&ch[i+2]=='Q'){print(i,'\n');return 0;}
    }
    return 0;
}

C 奋发

考点：模拟
分类：签到
按照题意模拟即可。
最基础的就是直接上模拟，但这是 的。
思考什么东西可以加速？你会发现两个限制之间一定是存在固定顺序的选择策略的，这个顺序的段数不会超过三段。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int read() {
    int s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
    return s*w;
}
signed main() {
    int n=read()-1,A=read(),B=read(),a,b,ans=min(A,B);
    for(int i=n;i;i--) {
        a=read(),b=read();
        ans+=max(0,min(a,b)-max(A,B)+(A!=B));
        A=a,B=b;
    }cout<<ans<<'\n';
    return 0;
}

D 绝望

考点：任意一个可以支持区间单次修改的东西比如树状数组，set，线段树之类的，基本数论
分类：中档
本题的第个操作显然不是拿来维护的，根据我们的询问内容查找质数个数可知，我们需要分类讨论如下几种情况：
图片说明
为了方便讲解，我将其从上到下称为1~6
1:无论值与操作次数多少，均不会发生变化，需单独讨论
2:为1:可能会出现且所在位置为质数时由非质数变为质数
3:非1：只需在赋初值时判断一下是否为质数即可
4:为，什么都没有发生qwq
5:为1，见情况2
6：：区间内质数个数归零，因为至少乘上了，显然不再为质数
只需将上述情况写清楚即可获得

E 翻转

考点：模拟
分类：签到
直接对于每一个数模拟

从后往前扫描，每扫一位，就将其作为当前新数的最后一位。
正常做法：

#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#define LL long long
using namespace std;
const int INF=0x3f3f3f3f;
int read()
{
   int s=0,bj=0;
   char ch=getchar();
   while(ch<'0'||ch>'9')bj|=(ch=='-'),ch=getchar();
   while(ch>='0'&&ch<='9')s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
   return bj?-s:s;
}
void printnum(int x)
{
    if(x>9)printnum(x/10);
    putchar(x%10^48);
}
void print(int x,char ch)
{
    if(x<0){putchar('-');x=-x;}
    printnum(x);putchar(ch);
}
int T;
LL ans,tmp,no;
int main()
{
    T=read();
    while(T--)
    {
        tmp=read();no=0;
        while(tmp)
        {
            no=(no<<1)|(tmp&1);
            tmp>>=1;
        }
        ans+=no;
    }
    print(no,'\n');
    return 0;
}

也可以用lowbit找到二进制下每个1的相对位置，直接将1插入新数的各个位即可。

复杂度
奇怪：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
long long n,m,a[1000005],QAQ,low,now,la,an;
long long lowbit(long long x){return x&-x;}
int main()
{
    long long i,j;
    scanf("%lld",&n);
    for(i=1;i<=n;++i)scanf("%lld",&a[i]);
    for(i=1;i<=n;++i)
    {
        la=1;
        while(a[i])
        {
            now=lowbit(a[i]);
            QAQ*=now/la;
            QAQ|=1;a[i]^=now;la=now;
        }
        an+=QAQ;
    }
    printf("%lld",an);
    return 0;
}

F 孤独

考点：贪心？
分类：中档
考虑用两条链进行拼凑，对于一个子树分两种情况：一条子树里+其他的和两条子树里，
再对子树里的最优情况分析可得，若为两条子树里，显然是从size最大和次大的儿子的子树中延伸出来，若为一条，则选择size最大的子树，对于每一棵子树，维护最大儿子，次大儿子，第三大儿子，及一条链为子树里时子树中的最大连通块，再在上传时计算即可（语言不易描述，可以结合代码理解），复杂度O（n）

#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#define LL long long
using namespace std;
int read()
{
    int s=0,bj=0;
    char ch=getchar();
    while(ch<'0'||ch>'9')bj|=(ch=='-'),ch=getchar();
    while(ch>='0'&&ch<='9')s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
    return bj?-s:s;
}
void printnum(int x)
{
    if(x>9)printnum(x/10);
    putchar(x%10^48);
}
void print(int x,char ch)
{
    if(x<0){putchar('-');x=-x;}
    printnum(x);putchar(ch);
}
int n;
struct node{int nx,to;}w[2000005];
int h[1000005],cnt,siz[1000005];
void AddEdge(int x,int y)
{
    w[++cnt].to=y;w[cnt].nx=h[x];h[x]=cnt;
    w[++cnt].to=x;w[cnt].nx=h[y];h[y]=cnt;
}
int ans=0x3f3f3f3f;
struct Tree{int fir,sec,thi,ge;}t[1000005];
void dfs(int x,int fa)
{
    int maxx1=0,maxx2=0,maxx3=0;
    siz[x]=1;
    for(int i=h[x];i;i=w[i].nx)
    {
        int y=w[i].to;
        if(y^fa)
        {
            dfs(y,x);siz[x]+=siz[y];
            if(siz[y]>=siz[maxx1]){maxx3=maxx2;maxx2=maxx1;maxx1=y;}
            else if(siz[y]>=siz[maxx2]){maxx3=maxx2;maxx2=y;}
            else if(siz[y]>=siz[maxx3])maxx3=y;
        }
    }
    t[x].fir=maxx1;t[x].sec=maxx2;t[x].thi=maxx3;
    t[x].ge=(siz[x]==1)?0:max(t[t[x].fir].ge,siz[t[x].sec]);
    ans=min(ans,max(max(max(t[t[x].fir].ge,t[t[x].sec].ge),siz[t[x].thi]),n-siz[x]));
    ans=min(ans,max(max(t[t[x].fir].ge,siz[t[x].sec]),n-siz[x]));
}
int main()
{
    n=read();
    for(int i=1;i<n;++i)AddEdge(read(),read());
    dfs(1,0);
    print(max(ans,1),'\n');
    return 0;
}

G 冷静

考点：树状数组
分类：中档
转化题意，会发现求的就是数的最小质因子大于等于 的数个数。

开一个树状数组，从小到大，加入每个数的最小质因子。将询问挂在 上，查询即可。

时间复杂度O(nlogn)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
char __buf[1<<20],*__p1,*__p2;
#define getchar() (__p1==__p2?(__p2=__buf+fread(__p1=__buf,1,1<<20,stdin),__p1==__p2?EOF:*__p1++):*__p1++)
int read() {
    int s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
    return s*w;
}
const int maxn = 1e7+10;
struct info {int n,K,m;}a[3000010];
int pr[670000],s[maxn],q,n,c[maxn],PR[3000010];
void ins(int x) {for(;x<=10000000;x+=x&-x) ++c[x];}
int ask(int x) {int r=0;for(;x;x-=x&-x) r+=c[x];return r;}
void SHAI(int n) {
    for(int i=2;i<=n;i++) {
        if(!s[i]) pr[++pr[0]]=i,s[i]=i;
        for(int j=1;j<=pr[0]&&i*pr[j]<=n&&(s[i*pr[j]]=pr[j]);j++)
            if(i%pr[j]==0) break;
    }
}
signed main() {
    SHAI(1e7),q=read();
    for(int i=1;i<=q;i++) a[i]=(info){read(),read(),i};
    sort(a+1,a+1+q,[](info x,info y){return x.n<y.n;});
    for(int i=1,j=1;i<=q;i++) {
        while(j<a[i].n) ins(s[++j]);
        PR[a[i].m]=a[i].n-1-ask(a[i].K-1);
    }
    for(int i=1;i<=q;i++) cout<<PR[i]<<'\n';
    return 0;
}

H 终别

考点：贪心
分类：中档
首先可以先考虑不使用魔法的情况显然 必然需要被消灭，那么同时对显然比对 造成伤害更优，由此我们可以得到一个从左往右依次计算的算法:假设到 已经清零， 对于 ，那么同时对造成伤害直到被消灭。
对于使用魔法的情况，我们考虑从前往后和从后往前分别计算，分别表示前/后所有都被消灭时的斩击数，这时我们可以枚举使用魔法的位置，并通过预处理的可以O(1)计算代价。
总时间复杂度O(n)

#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#define int long long
using namespace std;
int read()
{
    int s=0,bj=0;
    char ch=getchar();
    while(ch<'0'||ch>'9')bj|=(ch=='-'),ch=getchar();
    while(ch>='0'&&ch<='9')s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
    return bj?-s:s;
}
void printnum(int x)
{
    if(x>9)printnum(x/10);
    putchar(x%10^48);
}
void print(int x,char ch)
{
    if(x<0){putchar('-');x=-x;}
    printnum(x);putchar(ch);
}
int n;
int l[1000005],r[1000005],a[1000005],b[1000005];//l[i]表示把i-1之前清0的代价 
signed main()
{
    n=read();
    for(int i=1;i<=n;++i)a[i]=b[i]=read();
    for(int i=2;i<=n+1;++i)
    {
        l[i]=l[i-1]+a[i-1];
        a[i]=max(0ll,a[i]-a[i-1]);
        a[i+1]=max(0ll,a[i+1]-a[i-1]);
    }
    for(int i=n-1;i>=0;--i)
    {
        r[i]=r[i+1]+b[i+1];
        b[i]=max(0ll,b[i]-b[i+1]);
        b[max(0ll,i-1)]=max(0ll,b[max(0ll,i-1)]-b[i+1]);
    }
    int ans=1e18;
    for(int i=1;i<n;++i)ans=min(ans,l[i]+r[i+1]);
    print(ans,'\n');
    return 0;
}
全部评论
好良心的题 好爽的场
4 回复 分享
发布于 2021-10-22 23:08
如果有些没有讲清楚的地方，可以去B站看红名巨巨playf的讲解https://www.bilibili.com/video/BV1oq4y197n5
1 回复 分享
发布于 2021-10-23 09:37
G题能教一下用平衡树怎么写吗，比赛的时候用平衡树一直wa
点赞 回复 分享
发布于 2021-10-23 00:03
C题能证明下 那个ans 取值的方案吗 看不太懂
点赞 回复 分享
发布于 2021-10-23 09:32
D的代码贴掉了，可以去我博客里面看😥https://blog.nowcoder.net/n/63027c1ddfcb40b59f17b159261fe204
点赞 回复 分享
发布于 2021-10-24 11:16
F题如果有多于3个相等的最大的子树该怎么选？不应该根据dp值大小选吗？感觉单纯比大小转移不一定最优。
点赞 回复 分享
发布于 2021-10-29 16:35

相关推荐

11-21 16:09
杭州电子科技大学 运营
点赞 评论 收藏
分享
11-21 16:49
门头沟学院 Java
点赞 评论 收藏
分享
10-25 16:26
门头沟学院 电力电子工程师
双非硕0offer
已经开始25年高考的第一轮复习了
牛客717484937号：双飞硕没实习挺要命的
点赞 评论 收藏
分享
09-30 20:01
西安石油大学 嵌入式软件工程师
点赞 评论 收藏
分享
22 7 评论
分享

全站热榜

正在热议
# 25届秋招总结 #
324128次浏览 3017人参与
# 上班苦还是上学苦呢？ #
70324次浏览 627人参与
# 百度开奖 #
180979次浏览 1132人参与
# 地方国企笔面经互助 #
4422次浏览 12人参与
# 如果有时光机，你最想去到哪个年纪？ #
20930次浏览 375人参与
# 选完offer后，你后悔学本专业吗 #
21627次浏览 158人参与
# 阿里云管培生offer #
36532次浏览 421人参与
# 我的实习求职记录 #
6068109次浏览 83526人参与
# 如何一边实习一边秋招 #
996100次浏览 12661人参与
# 入职第一天，你准备什么时候下班 #
21520次浏览 144人参与
# 招聘要求与实际实习内容不符怎么办 #
10700次浏览 276人参与
# bilibili求职进展汇总 #
32975次浏览 354人参与
# 许愿池 #
214610次浏览 2534人参与
# 学历or实习经历，哪个更重要 #
53636次浏览 421人参与
# 实习工作，你找得还顺利吗？ #
247609次浏览 2905人参与
# 海康威视求职进展汇总 #
400492次浏览 3408人参与
# 通信硬件薪资爆料 #
608060次浏览 5156人参与
# 携程求职进展汇总 #
135467次浏览 928人参与
# 正在实习的你，几点下班 #
53035次浏览 395人参与
# 工作两年想退休了 #
53007次浏览 672人参与
# 如果再来一次，你还会学硬件吗 #
95129次浏览 1171人参与
# 软件开发薪资爆料 #
2194255次浏览 21884人参与
牛客网
牛客企业服务