牛客小白月赛27题解

A:巨木之森
首先这题的路径我们发现除了最后到达的点以外，其他每条边都要遍历两次（因为最后不回来了）
然后我们会尽量贪心的走最远的点，然后有一个关于直径的性质，距离一个点最远的点一定是直径的两个端点，因此我们求出直径，然后在树上倍增lca选下距离，选出最优的
最后我们sort一遍能选就选，取最多的就可以了！
代码：

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=1e5+5;
struct Edge{int to,w,nxt;}e[N<<1];
int n,fst[N],tote,dep[N],fa[N][21],pos,ru,rv,ans;LL dis[N],m,totw,ma,d[N],now;
void adde(int u,int v,int w){e[++tote]=(Edge){v,w,fst[u]};fst[u]=tote;}
int lca(int u,int v){
    if(dep[u]<dep[v])swap(u,v);
    for(int i=20;~i;i--)if(dep[fa[u][i]]>=dep[v])u=fa[u][i];
    if(u==v)return u;
    for(int i=20;~i;i--)if(fa[u][i]!=fa[v][i])u=fa[u][i],v=fa[v][i];
    return fa[u][0];
}
LL calcdis(int u,int v){return dis[u]+dis[v]-(dis[lca(u,v)]<<1LL);    }
void dfs(int u,int f){
    dep[u]=dep[f]+1;fa[u][0]=f;
    for(int i=1;i<=20;i++)fa[u][i]=fa[fa[u][i-1]][i-1];
    for(int i=fst[u],v,w;i;i=e[i].nxt){
        v=e[i].to;w=e[i].w;
        if(v!=f)dis[v]=dis[u]+(LL)w,dfs(v,u);
    }
}
int main(){
    scanf("%d%lld",&n,&m);
    for(int i=1,u,v,w;i<n;i++)scanf("%d%d%d",&u,&v,&w),adde(u,v,w),adde(v,u,w),totw+=(LL)w;
    dfs(1,0);
    for(int i=1;i<=n;i++){
        LL nowd=calcdis(1,i);
        if(nowd>ma)ma=nowd,pos=i;
    }
    ru=pos;ma=pos=0;
    for(int i=1;i<=n;i++){
        LL nowd=calcdis(ru,i);
        if(nowd>ma)ma=nowd,pos=i;
    }
    rv=pos;
    for(int i=1;i<=n;i++)d[i]=(totw<<1LL)-max(calcdis(ru,i),calcdis(rv,i));
    sort(d+1,d+n+1);
    for(int i=1;i<=n;i++)if((now+=d[i])<=m)ans=i;
    printf("%d\n",ans);
    return 0;
}

B:乐***对
当初做这个题的时候naive了，以为扫一遍就行了，结果还没去想反例，一直以为自己题目读错了
后来发现这个4 4 4 4 4 1类似的就可以体现一下
然后大概是一个偏序dp，关于a[i+1]+i的限制的dp，然后我们用树状数组优化一下就可以
代码：

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=4e5+5,Inf=1e9;
int n,a[N],ans,dp[N],ma[N];
void rel(int &x,int y){x=x>y?x:y;}
int lowbit(int x){return x&-x;}
void change(int x,int y){for(int i=x;i<N;i+=lowbit(i))rel(ma[i],y);}
int askma(int x){int res=-Inf;for(int i=x;i;i-=lowbit(i))rel(res,ma[i]);return res;}
bool cmp(int a,int b){return a>b;}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    sort(a+1,a+n+1,cmp);
    if(a[1]>n){puts("-1");return 0;}
    memset(ma,-0x3f,sizeof(ma));change(a[1],0);
    for(int i=1;i<=n;i++)dp[i]=askma(i)+1,change(a[i+1]+i,dp[i]),ans=max(ans,dp[i]);
    printf("%d\n",ans);
    return 0;
}

C:光玉小镇
经典的trick，我们发现关键点不多，然后我们可以针对这些关键点分别跑最短路
然后对于这些关键点我们考虑枚举它们的顺序就可以了，可以dfs，但是会tle，我们状压一下就可以了
注意一些细节，和这题要开long long，作者这题的代码都用了LL替换了int，可能有点丑见谅！

#include<bits/stdc++.h>
#define LL long long
#define pii pair<LL,LL>
using namespace std;
const LL N=205,S=(1<<17),Inf=1e18;
const LL dx[]={1,0,-1,0},dy[]={0,1,0,-1};
LL n,m,tim,now,px[20],py[20],dp[S][20],dis[N][N],rd[20][20],ans=Inf;
bool vis[N][N];char mp[N][N];
void rel(LL &x,LL y){x=x<y?x:y;}
signed main(){
    scanf("%lld%lld%lld",&n,&m,&tim);
    for(LL i=1;i<=n;i++)scanf("%s",mp[i]+1);
    for(LL i=1;i<=n;i++)for(LL j=1;j<=m;j++)if(mp[i][j]=='S')px[now]=i,py[now]=j,now++;
    for(LL i=1;i<=n;i++)for(LL j=1;j<=m;j++)if(mp[i][j]=='T')px[now]=i,py[now]=j,now++;
    memset(rd,-1,sizeof(rd));
    for(LL t=0;t<now;t++){
        queue<pii>que;while(!que.empty())que.pop();
        memset(vis,false,sizeof(vis));
        que.push(pii(px[t],py[t]));dis[px[t]][py[t]]=0;vis[px[t]][py[t]]=true;
        while(!que.empty()){
            LL x=que.front().first,y=que.front().second;que.pop();
            for(LL i=0,nx,ny;i<4;i++){
                nx=x+dx[i];ny=y+dy[i];
                if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&mp[nx][ny]!='#'&&!vis[nx][ny])vis[nx][ny]=true,dis[nx][ny]=dis[x][y]+1,que.push(pii(nx,ny));
            }
        }
        for(LL i=0;i<now;i++)if(vis[px[i]][py[i]])rd[t][i]=dis[px[i]][py[i]];
    }
    //for(LL i=0;i<2;i++)for(LL j=0;j<2;j++)printf("%d %d %d\n",i,j,rd[i][j]);
    for(LL s=0;s<S;s++)for(LL lst=0;lst<20;lst++)dp[s][lst]=Inf;
    dp[1][0]=0;
    for(LL s=1;s<(1<<now);s++)for(LL lst=0;lst<now;lst++)if(dp[s][lst]<Inf){
        for(LL i=0;i<now;i++)if(!(s&(1<<i))&&rd[lst][i]!=-1)
            rel(dp[s^(1<<i)][i],dp[s][lst]+rd[lst][i]+(i?tim:0));
    }
    for(LL lst=0;lst<now;lst++)if(rd[lst][0]!=-1)rel(ans,dp[(1<<now)-1][lst]+rd[lst][0]);
    if(ans>=Inf)puts("-1");else printf("%lld\n",ans);
    return 0;
}

D:巅峰对决
注意一个重要的性质，每个数都不相同，然后我们发现要满足题目要求的性质，那就是要l~r是连续的，每个数都出现一次，由于互不相同这个条件，我们可以直接区间取min和max，判断即可！
我们成功地将此题转化为了我们熟悉的线段树区间操作的裸题
代码：

#define LL long long
using namespace std;
const int N=1e5+5,Inf=1e9;
int n,q,a[N],mi[N<<2],ma[N<<2];
void update(int rt){mi[rt]=min(mi[rt<<1],mi[rt<<1|1]);ma[rt]=max(ma[rt<<1],ma[rt<<1|1]);}
void build(int rt,int l,int r){
    if(l==r){mi[rt]=ma[rt]=a[l];return;}
    int mid=(l+r)>>1;
    build(rt<<1,l,mid);build(rt<<1|1,mid+1,r);
    update(rt);
}
void change(int rt,int l,int r,int x,int y){
    if(l==r){mi[rt]=ma[rt]=y;return;}
    int mid=(l+r)>>1;
    (x<=mid)?change(rt<<1,l,mid,x,y):change(rt<<1|1,mid+1,r,x,y);
    update(rt);
}
int askmi(int rt,int l,int r,int L,int R){
    if(L<=l&&r<=R)return mi[rt];
    int mid=(l+r)>>1,res=Inf;
    if(L<=mid)res=min(res,askmi(rt<<1,l,mid,L,R));
    if(R>mid)res=min(res,askmi(rt<<1|1,mid+1,r,L,R));
    return res;
}
int askma(int rt,int l,int r,int L,int R){
    if(L<=l&&r<=R)return ma[rt];
    int mid=(l+r)>>1,res=0;
    if(L<=mid)res=max(res,askma(rt<<1,l,mid,L,R));
    if(R>mid)res=max(res,askma(rt<<1|1,mid+1,r,L,R));
    return res;
}
int main(){
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    build(1,1,n);
    while(q--){
        int opt,x,y;scanf("%d%d%d",&opt,&x,&y);
        if(opt==1)change(1,1,n,x,y);
        else{
            if(askma(1,1,n,x,y)-askmi(1,1,n,x,y)==y-x)puts("YES");else puts("NO");
        }
    }
    return 0;
}

E:使徒袭来
我们要是和最低，希望这三个数要尽量均衡，这里相同最好！
然后我们去个三分之一次方就好了，用下pow函数！
（可以借助根号理解）
代码：

#include<bits/stdc++.h>
#define LL long long
using namespace std;
int main(){
    double n;
    scanf("%lf",&n);
    printf("%.3lf\n",3.0*pow(n,1/3.0));
    return 0;
}

F:核弹剑仙
我们把彼此之间的关系拿来建图，然后发现图的规模不大，我们针对每个关键点暴力bfs即可！
代码：

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=1e3+5;
struct Edge{int to,nxt;}e[N<<1];
int n,m,fst[N],tote;bool usd[N];
void adde(int u,int v){e[++tote]=(Edge){v,fst[u]};fst[u]=tote;}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1,u,v;i<=m;i++)scanf("%d%d",&u,&v),adde(v,u);
    for(int i=1,res;i<=n;i++){
        queue<int>que;while(!que.empty())que.pop();
        for(int j=1;j<=n;j++)usd[j]=false;
        res=0;usd[i]=true;que.push(i);
        while(!que.empty()){
            int u=que.front();que.pop();
            for(int i=fst[u],v;i;i=e[i].nxt)if(!usd[v=e[i].to])usd[v]=true,que.push(v);
        }
        for(int j=1;j<=n;j++)if(j!=i&&usd[j])res++;
        printf("%d\n",res);
    }
    return 0;
}

G:虚空之力
一共只有两种操作，我们发现只需要枚举一种操作的使用次数，然后另外一种操作次数尽量取最优就是当前可以组成的个数
然后把所有这些算出来的取max就可以了！
代码：

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=1e7+5;
int n,cntk,cnti,cntn,cntg,ans;char str[N];
int main(){
    scanf("%d",&n);scanf("%s",str+1);
    for(int i=1;i<=n;i++){
        if(str[i]=='k')cntk++;
        if(str[i]=='i')cnti++;
        if(str[i]=='n')cntn++;
        if(str[i]=='g')cntg++;
    }
    for(int i=0,nowk,nowi,nown,nowg,now;i<=n;i++){
        nowk=cntk-i;nowi=cnti-(i<<1);nown=cntn-(i<<1);nowg=cntg-(i<<1);now=min(min(nowk,nowi),min(nown,nowg));
        //printf("%d %d %d %d %d\n",i,nowk,nowi,nown,nowg);
        if(now>=0)ans=max(ans,(i<<1)+now);
    }
    printf("%d\n",ans);
    return 0;
}

H:社团游戏
我们只需要枚举左上角，然后下面的要求是满足单调性的，即是可二分的，我们只需要二分大小就可以了！
然后我们要求的就是针对每个字母求一个二维前缀和，因为判断的时候要用二维前缀和快速求出矩阵内某个字母的的个数！
代码：

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=505;
int n,m,lim,a[N][N],sum[26][N][N];char str[N];
int main(){
    scanf("%d%d%d",&n,&m,&lim);
    for(int i=1;i<=n;i++){
        scanf("%s",str+1);
        for(int j=1;j<=m;j++)a[i][j]=str[j]-'a';
    }
    for(int k=0;k<26;k++)for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)sum[k][i][j]=sum[k][i-1][j]+sum[k][i][j-1]-sum[k][i-1][j-1]+(a[i][j]==k);
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){
        int now=1;
        for(int l=10,tmp;~l;l--){
            tmp=now+(1<<l);bool fl=true;
            if(i+tmp-1>n||j+tmp-1>m)continue;
            for(int k=0;k<26;k++)if(sum[k][i+tmp-1][j+tmp-1]-sum[k][i-1][j+tmp-1]-sum[k][i+tmp-1][j-1]+sum[k][i-1][j-1]>lim){fl=false;break;}
            if(fl)now=tmp;
        }
        printf("%d%c",now," \n"[j==m]);
    }
    return 0;
}

I:名作之壁
这场最有意思的一道题，我们钦定一个点让它分别成为最大值最小值，然后之前的如果满足差大于那个指定值，就代表右端点到n，左端点从1到当前的队头都是满足条件的，我们记录一个pre代表可以满足条件的区间到(1~pre[i],i)都是可以的，我们要两次单调队列更新这个pre数组就可以
发现这么多个点一定可能成为一个最大值和最小值因此一定会被扫过一次，所以这个正确性可以证明！
代码：

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=1e7+5,P=1e9;
int n,k,a[N],sb,sc,hd,tl,que[N],pre[N],now;LL ans;
int main(){
    scanf("%d%d%d%d%d",&n,&k,&a[0],&sb,&sc);
    for(int i=1;i<=n;i++)a[i]=((LL)a[i-1]*sb+sc)%P;
    memset(pre,-1,sizeof(pre));now=-1;
    for(int i=1;i<=n;i++){
        while(hd<=tl&&a[que[hd]]<a[i]-k)now=max(now,que[hd]),hd++;
        pre[i]=max(pre[i],now);
        while(hd<=tl&&a[que[tl]]>=a[i])tl--;que[++tl]=i;
    }
    hd=1;tl=0;now=-1;
    for(int i=1;i<=n;i++){
        while(hd<=tl&&a[que[hd]]>a[i]+k)now=max(now,que[hd]),hd++;
        pre[i]=max(pre[i],now);
        while(hd<=tl&&a[que[tl]]<=a[i])tl--;que[++tl]=i;
    }
    for(int i=1;i<=n;i++)if(pre[i]!=-1)ans+=(LL)pre[i];
    printf("%lld\n",ans);
    return 0;
}

J:逃跑路线
我们发现是&操作，而且这个数是1，那么结果只会是0或者1，因此我们只需要判断这个结果的奇偶性，取字符串末尾相加即可！
代码：

#include<bits/stdc++.h>
#define LL long long
using namespace std;
int ans;char str[10005];
int main(){
    int T;scanf("%d",&T);
    while(T--)scanf("%s",str+1),ans+=str[strlen(str+1)]-'0';
    printf("%d\n",ans&1);
    return 0;
}