【题解】牛客小白月赛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 奋发

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

#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$ 个操作显然不是拿来维护的，根据我们的询问内容查找质数个数可知，我们需要分类讨论如下几种情况：
图片说明
为了方便讲解，我将其从上到下称为1~6
1:无论 $x$ 值与操作次数多少， $a_i$ 均不会发生变化，需单独讨论
2: $a_i$ 为1:可能会出现 $x=1$ 且所在位置 $i$ 为质数时由非质数变为质数
3: $a_i$ 非1：只需在赋初值时判断一下是否为质数即可
4: $x$ 为 $0$ ，什么都没有发生qwq
5: $x$ 为1，见情况2
6： $x>1$ ：区间内质数个数归零，因为至少乘上了 $i^x$ ，显然不再为质数
只需将上述情况写清楚即可获得 $AC$

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插入新数的各个位即可。

复杂度 $O(nlogn)$
奇怪：

#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 冷静

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

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

时间复杂度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 终别

考点：贪心
分类：中档
首先可以先考虑不使用魔法的情况显然 $a_1$ 必然需要被消灭，那么同时对 $a_1,a_2,a_3$ 显然比对造成伤害更优，由此我们可以得到一个从左往右依次计算的算法:假设 $a_{1}$ 到 $a_{i-1}$ 已经清零，对于 $a_i$ ，那么同时对 $a_i,a_{i+1},a_{i+2}$ 造成伤害直到 $a_i$ 被消灭。
对于使用魔法的情况，我们考虑从前往后和从后往前分别计算， $l_i,r_i$ 分别表示 $i$ 前/后所有都被消灭时的斩击数，这时我们可以枚举使用魔法的位置，并通过预处理的 $l_i,r_i$ 可以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;
}