牛客小白月赛27题解

B、乐***对

题意：给出n个人，将这些人分为若干个组，每个人对应的一个值a[i]，表示这个人所在队伍的人数只要有a[i]个人才可以，问最多可以组成多少个队伍？若不能组成队伍，则输出-1.
思路：我们考虑贪心的算法，我们令dp[i]表示当前到i的时候我们可以组成的最多的队伍数量。那么，我们可以直到，当我们到达i的时候，我们要考虑将i分到哪个组里面，我们可以将它们与i-1组成一组，如果i>=a[i]的话，我们也可以让[i-a[i]+1,i]这些组成一组，所以我们可以得到状态转移方程： $dp[i]=max\left\{ \begin{aligned} dp[i-1 ]& & \\ dp[i-a[i]]+1& & i>=a[i] \end{aligned} \right.$
所以我们直接进行一个dp即可。
代码：

#include<bits/stdc++.h> 
using namespace std;
int a[100010],dp[100010];
int ans=0;
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    sort(a+1,a+1+n);
    if(n<a[n]){
        cout<<"-1"<<endl;
        return 0;
    }
    for(int i=1;i<=n;i++){
        if(i>=a[i])  ans=dp[i-a[i]]+1;
        dp[i]=max(ans,dp[i-1]);
    }
    cout<<ans<<endl;
    return 0;
}

D、巅峰对决

题意：给出一个序列，保证序列中每个数字都是不一样的，要求对序列进行单点修改和区间查询，查询区间里面的序列知否可以重新组成一个连续的序列。
思路：一个线段树板子题，可惜比赛时没注意看清题目，我们看到对于每次查询，我们确保我们序列里面的数字都是不同的，那么我们只要查询当前访问序列的最大和最小值，，然后与区间长度进行比较即可判断出来，这样，问题就转化为单点修改+区间查询最大和最小值了。
代码：

#include<bits/stdc++.h> 
using namespace std;
const int N=100010;
int tree1[N<<2],tree2[N<<2];
int a[N],n,q;
void build(int node,int l,int r){
    if(l==r){
        tree1[node]=tree2[node]=a[l];
        return;
    }
    int mid=(l+r)>>1,left_node=2*node,right_node=2*node+1;
    build(left_node,l,mid);
    build(right_node,mid+1,r);
    tree1[node]=min(tree1[left_node],tree1[right_node]);
    tree2[node]=max(tree2[left_node],tree2[right_node]);
}
void update(int node,int l,int r,int x,int val){
    if(l==r){
        a[x]=val;
        tree1[node]=tree2[node]=val;
        return;
    }
    int mid=(l+r)>>1,left_node=2*node,right_node=2*node+1;
    if(x<=mid&&x>=l) update(left_node,l,mid,x,val);
    else update(right_node,mid+1,r,x,val);
    tree1[node]=min(tree1[left_node],tree1[right_node]);
    tree2[node]=max(tree2[left_node],tree2[right_node]);
}
int query_mi(int node,int l,int r,int x,int y){
    if(y>=r&&x<=l)  return tree1[node];
    if(l==r)  return tree1[node];
    int mid=(l+r)>>1,left_node=node*2,right_node=node*2+1;
    int ans=1e9+7;
    if(x<=mid)  ans=min(ans,query_mi(left_node,l,mid,x,y));
    if(y>mid)  ans=min(ans,query_mi(right_node,mid+1,r,x,y));
    return ans;
}
int query_mx(int node,int l,int r,int x,int y){
    if(y>=r&&x<=l) return tree2[node];
    if(l==r)  return tree2[node];
    int mid=(l+r)>>1,left_node=node*2,right_node=node*2+1;
    int ans=-1;
    if(x<=mid)  ans=max(ans,query_mx(left_node,l,mid,x,y));
    if(y>mid)  ans=max(ans,query_mx(right_node,mid+1,r,x,y));
    return ans;
}
int main(){
    cin>>n>>q;
    for(int i=1;i<=n;i++)  cin>>a[i];
    build(1,1,n);
    while(q--){
        int op,x,y;
        cin>>op>>x>>y;
        if(op==1){
            update(1,1,n,x,y);
        }else{
            int ans=query_mx(1,1,n,x,y)-query_mi(1,1,n,x,y)+1;
            if(y-x+1==ans)  cout<<"YES"<<endl;
            else  cout<<"NO"<<endl;
        }
    }
    return 0;
}

E、使徒袭来

题意：给三个数的乘积，求出这三个数的和最小。
思路：数学问题，考察基本不等式。 $(a+b+c)_{min}=3(abc)^\frac{1}{3}$
代码：

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

F、核弹剑仙

题意：给出若干个比较，保证在这些比较合法的前提下，输出比每个武器更优的数量。
思路：我们先根据比较来进行建图，如果a优于b的话，我们可以建一条从从b到a的边。然后对于每个点从这该点开始进行一个dfs，即可求出我们的答案
代码：

#include<bits/stdc++.h>
using namespace std;
const int N=10010;
int n,m,tot,sum;
int head[N],ver[N],nxt[N];
bool vis[N];
void add(int x,int y){
    ver[++tot]=y;
    nxt[tot]=head[x],head[x]=tot;
}
void dfs(int x){
    sum++,vis[x]=true;
    for(int i=head[x];i;i=nxt[i]){
        int y=ver[i];
        if(vis[y])  continue;
        dfs(y);
    }
}
int main(){
    cin>>n>>m; 
    while(m--){
        int a,b;
        cin>>a>>b;
        add(b,a);
    }
    for(int i=1;i<=n;i++){
        sum=-1;
        memset(vis,false,sizeof(vis));
        dfs(i);
        cout<<sum<<endl;
    }
    cout<<endl;
    return 0;
}

G、虚空之力

题意：给出一个字符串，对于k，i，n，g可以对答案贡献1，对于k，i，n，g，i，n，g可以为答案贡献2.问答案最大为多少？
思路：一个很显然的贪心，我们肯定要有限满足kinging的情况，只需记录下这些字符的个数然后进行一个合理的分配即可。
代码：

#include<bits/stdc++.h> 
using namespace std;
int main(){
    map<int,int> mp;
    int n;
    cin>>n;
    string s;
    cin>>s;
    for(int i=0;i<n;i++){
        mp[s[i]]++;
    }
    int ans=0;
    while(1){
        if(mp['k']==0||mp['i']==0||mp['n']==0||mp['g']==0)  break;
        else{
            if(mp['i']>1&&mp['n']>1&&mp['g']>1){
                ans+=2;
                mp['i']-=2,mp['n']-=2,mp['g']-=2;
                mp['k']--;
            }
            else{
                ans++;
                mp['k']--;
                mp['i']--,mp['n']--,mp['g']--;
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}

H、社团游戏

题意：给出一个矩阵，找出满足矩阵里面每种字符不超过k个的最大矩阵，输出它的边长。
思路：哈希+二分。我们用num[i][j][k]表示i这个字符在矩阵行1-j，列为1-k的矩阵里面的个数，然后我们在二分答案的时候我们只需要比较是否超过k个即可，这里你也要对二维的哈希有个熟悉的了解。
代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,k;
int num[30][520][520];
char a[520][520];
bool judge(int x,int y,int mid){
    for(int i=1;i<=26;i++){
        int tx=x+mid-1,ty=y+mid-1;
        int sum=num[i][tx][ty]-num[i][x-1][ty]-num[i][tx][y-1]+num[i][x-1][y-1];
        if(sum>k)  return false;
    }
    return true;
}
int main(){
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++) cin>>a[i][j];
    }
    for(int k=1;k<=26;k++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                num[k][i][j]=num[k][i-1][j]+num[k][i][j-1]+(a[i][j]-'a'+1==k)-num[k][i-1][j-1];
            }
        }
    }
    int l,r,mid;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            l=0,r=min(n-i+1,m-j+1);
            int ans=0;
            while(l<=r){
                mid=(l+r)>>1;
            //    cout<<"mid:"<<mid<<endl;
                if(judge(i,j,mid)){
                    l=mid+1;
                    ans=mid;
                }
                else r=mid-1;
            }
            cout<<ans;
            if(j<m)  cout<<" ";
        }
        cout<<endl;
    }
    return 0;
}

I、名作之壁

题意：给你n个数字，第i个数字a[i]表示名作之壁第i天的销量。若某段区间[l,r]中最大值和最小值之差大于k，则称该区间为畅销区间。请问一共有多少个区间为畅销区间？
思路：既然是要对区间内的最大和最小值进行操作的话，我们可以用一个单调队列来对序列进行一个最大和最小值的维护，我们可以枚举每个区间的右端点，如果此时的r是一个畅销区间的话，那么直接对答案的贡献就是n-i+1,因为我们区间的右端点进行一个移动的话，当左端点不动的时候，我们可以知道这个区间里面的最大值肯定是大于等于[l,r]之间的最大值得，然后最小值同理一定是小于等于[l,r]之间的最小值的，那么区间里面的最大与最小值的差一定是大于等于k的，故得证！
代码：

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9;
typedef long long ll;
int n,k,b,c;
int a[10000010],q1[10000010],q2[10000010];
int f1=0,f2=0,r1=0,r2=0;  
//f1,r1用来维护区间最小值，f2,r2用来维护区间最大值 
int main(){
    cin>>n>>k;
    cin>>a[0]>>b>>c;
    ll ans=0;
    for(int l=1,r=1;r<=n;r++){
        a[r]=((ll)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++;
        }
    }
    cout<<ans<<endl;
    return 0;
}

J、逃跑路线

题意：求出一个数组里面的所有数字& $(2^1-1)$ & $(2^2-1)$ & $(2^3-1)$ ... $(2^n-1)$ $最后所得的值。
思路：这个如果对二进制比较熟悉的话应该很好理解，我们知道上面公式后面&下来之后就是1，所以我们只要对数组里面的最低的和判断一下奇偶性就行了。
代码：

#include<bits/stdc++.h> 
using namespace std;
int main(){
    int n;
    cin>>n;
    int ans=0;
    while(n--){
        string a;
        cin>>a;
        int len=a.size();
        ans+=(a[len-1]-'0');
    }
    if(ans&1)  cout<<"1"<<endl;
    else  cout<<"0"<<endl;
    return 0;
}