牛客小白月赛24总结（补题）

川长思鸟来 2023-05-21 13:50 164阅读 0赞

# 牛客小白月赛24总结（补题） #

### 文章目录 ###

*  牛客小白月赛24总结（补题）
 *   *  前言：
     *  签到题：B、F、G
     *   *  G：
         *  B：
         *  F：
     *  简单题：H、I、J
     *   *  H：
         *  J：
         *  I：
         *  其他：

## 前言： ##

在这立个flag，卸游！卸游！卸游！  
下午刚打完上海大学的网络赛自闭，晚上又继续自闭…  
![在这里插入图片描述][20200419095556871.png]  
后面三题wa到心态爆炸。。。。  
不能再这样搞下去了，不然今年省赛又得打铁了

## 签到题：B、F、G ##

### G： ###

最开始就是看的G题，一看题目觉得应该两分钟内能A出来吧  
可谁知wa了我5发才过…

题意是：n个题目，m单位时间，下面给出n个题目对应的所需要的时间  
首先开始写了个数组存每个题目所需要的时间，然后排个序，用whlie(m)，真的是傻了，如果像每个题目所需要的时间都是0的话，岂不是死循环了

re两发后，立马换成for，然后加了个if(m<=0) break；  
结果又wa了，当然不能<=0啊，应该直接与当前的时间比较  
if(m<a\[i\]) break;  
wa了5发后终于过了

#include<bits/stdc++.h>
    #define lowbit(x) x&(-x)
    #define ll long long
    #define inf 0x3f3f3f3f
    using namespace std;
    const ll mod=1e9+7;
    const int maxn=5e5+10;
    int a[maxn];
    int main(){
        
        int  n;
        ll m;
        scanf("%d%lld",&n,&m);
        for(int i=1;i<=n;i++){
        
            scanf("%d",&a[i]);
        }
        sort(a+1,a+n+1);
        int ans=0;
        for(int i=1;i<=n;i++){
        
            if(m<a[i])
                break;
            m-=a[i];
            ans++;
        }
        printf("%d\n",ans);
        return 0;
    }

### B： ###

接着看B，  
题意：n个人，每个人对应一个能力值a\[i\]，保证选中的人任意两人的能力值之差小于等于k  
直接用一个队列维护一下（滑动窗口）即可，但是还是wa了一发才过，其实想复杂了，可以不开空间模拟能实现，虽然标程给的是滑动窗口做法  
我的代码：

#include<bits/stdc++.h>
    #define lowbit(x) x&(-x)
    #define ll long long
    #define inf 0x3f3f3f3f
    using namespace std;
    const ll mod=1e9+7;
    const int maxn=2e5+10;
    queue<int>q;
    int a[maxn];
    int main(){
        
        int t,n,k;
        scanf("%d",&t);
        while(t--){
        
            while(!q.empty()){
        
                q.pop();
            }
            scanf("%d%d",&n,&k);
            for(int i=1;i<=n;i++){
        
                scanf("%d",&a[i]);
            }
            sort(a+1,a+n+1);
            int ans=1;
            q.push(a[1]);
            int num=a[1];
            for(int i=2;i<=n;i++){
        
                if((a[i]-num)>k){
        
                    while(!q.empty()){
        
                        q.pop();
                    }
                    q.push(a[i]);
                    num=a[i];
                }
                else{
        
                    while((a[i]-q.front())>k){
        
                        q.pop();
                    }
                    q.push(a[i]);
                    num=a[i];
                    if(q.size()>ans){
        
                        ans=q.size();
                    }
                }
            }
            printf("%d\n",ans);
        }
        return 0;
    }

赛后看了别的大佬的代码后，改的：

#include<bits/stdc++.h>
    #define lowbit(x) x&(-x)
    #define ll long long
    #define inf 0x3f3f3f3f
    using namespace std;
    const ll mod=1e9+7;
    const int maxn=2e5+5;
    int t,n,k;
    int a[maxn];
    int main(){
        
        scanf("%d",&t);
        while(t--){
        
            scanf("%d%d",&n,&k);
            for(int i=1;i<=n;i++){
        
                scanf("%d",&a[i]);
            }
            sort(a+1,a+n+1);
            int head=1;
            int ans=0;
            for(int i=2;i<=n;i++){
        
                while(a[i]-a[head]>k){
        
                    head++;
                }
                if((i-head+1)>ans)
                    ans=i-head+1;
            }
            printf("%d\n",ans);
        }
        return 0;
    }

### F： ###

直接按题意模拟即可：  
可算一发过了

#include<bits/stdc++.h>
    #define lowbit(x) x&(-x)
    #define ll long long
    #define inf 0x3f3f3f3f
    using namespace std;
    const ll mod=1e9+7;
    const int maxn=2e5+10;
    string s1,s2;
    int main(){
        
        cin>>s1>>s2;
        if(s1=="elephant"){
        
            if(s2=="elephant"){
        
                printf("tiangou yiwusuoyou\n");
            }
            else if(s2=="tiger"){
        
                printf("tiangou yiwusuoyou\n");
            }
            else if(s2=="cat"){
        
                printf("tiangou yiwusuoyou\n");
            }
            else{
        
                printf("tiangou txdy\n");
            }
        }
        else if(s1=="tiger"){
        
            if(s2=="elephant"){
        
                printf("tiangou txdy\n");
            }
            else if(s2=="tiger"){
        
                printf("tiangou yiwusuoyou\n");
            }
            else if(s2=="cat"){
        
                printf("tiangou yiwusuoyou\n");
            }
            else{
        
                printf("tiangou yiwusuoyou\n");
            }
        }
        else if(s1=="cat"){
        
            if(s2=="elephant"){
        
                printf("tiangou yiwusuoyou\n");
            }
            else if(s2=="tiger"){
        
                printf("tiangou txdy\n");
            }
            else if(s2=="cat"){
        
                printf("tiangou yiwusuoyou\n");
            }
            else{
        
                printf("tiangou yiwusuoyou\n");
            }
        }
        else{
        
            if(s2=="elephant"){
        
                printf("tiangou yiwusuoyou\n");
            }
            else if(s2=="tiger"){
        
                printf("tiangou yiwusuoyou\n");
            }
            else if(s2=="cat"){
        
                printf("tiangou txdy\n");
            }
            else{
        
                printf("tiangou yiwusuoyou\n");
            }
        }
    }

## 简单题：H、I、J ##

### H： ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JvbGl1MTQ3MjU4_size_16_color_FFFFFF_t_70]  
判断是不是有矛盾出现

**敌人的敌人不一定是敌人，好吧，我吐了**  
一直用两个集合维护，wa到吐

换成并查集，可能会发现还是过不了，由于数据较大，需要离散化（吐血）

#include<bits/stdc++.h>
    #define lowbit(x) x&(-x)
    #define ll long long
    #define inf 0x3f3f3f3f
    using namespace std;
    const ll mod=1e9+7;
    const int maxn=1e6+5;
    int t,n;
    struct node{
        
        int u,v,c;
    };
    node a[maxn];  //存关系
    int par[maxn<<1];      //存朋友关系的父亲
    vector<int>ve;     //用来离散化
    int get_par(int u){
        
        if(par[u]!=u){
        
            par[u]=get_par(par[u]);
        }
        return par[u];
    }
    int main(){
        
        scanf("%d",&t);
        while(t--){
        
            ve.clear();
            scanf("%d",&n);
            for(int i=1;i<=2*n;i++){
        
                par[i]=i;
            }
            int par_u,par_v;
            for(int i=1;i<=n;i++){
        
                scanf("%d%d%d",&a[i].u,&a[i].v,&a[i].c);
                ve.push_back(a[i].u),ve.push_back(a[i].v);
            }
            sort(ve.begin(),ve.end());
            //ve.erase(unique(ve.begin(),ve.end()),ve.end());        //去重不去重都可以过
            for(int i=1;i<=n;i++){
        
                a[i].u=lower_bound(ve.begin(),ve.end(),a[i].u)-ve.begin()+1;
                a[i].v=lower_bound(ve.begin(),ve.end(),a[i].v)-ve.begin()+1;
            }
            for(int i=1;i<=n;i++){
        
                if(a[i].c==1){
        
                    par_u=get_par(a[i].u);
                    par_v=get_par(a[i].v);
                    if(par_u!=par_v){
        
                        par[par_v]=par_u;
                    }
                }
            }
            int flag=0;
            for(int i=1;i<=n;i++){
        
                if(a[i].c==0){
        
                    par_u=get_par(a[i].u);
                    par_v=get_par(a[i].v);
                    if(par_u==par_v){
        
                        flag=1;
                        break;
                    }
                }
            }
            if(flag==0){
        
                printf("YES\n");
            }
            else{
        
                printf("NO\n");
            }
        }
        return 0;
    }

### J： ###

正如题解所说：  
![在这里插入图片描述][20200419115542775.png]  
两重循环肯定会超时，于是可以利用前缀和缩短为O(n)  
然额我公式都推出来了，结果还是wa，wa到怀疑人生  
![在这里插入图片描述][20200419120133239.png]  
对比标程，终于给A了，注意减的时候需要加个mod，防止相减变成负数了

#include<bits/stdc++.h>
    #define lowbit(x) x&(-x)
    #define ll long long
    #define inf 0x3f3f3f3f
    using namespace std;
    const ll mod=1e9+7;
    const int maxn=5e5+5;
    ll n;
    ll a[maxn];
    ll sum[maxn];      //前缀和
    int main(){
        
        scanf("%lld",&n);
        ll ans=0;
        sum[0]=0;
        for(ll i=1;i<=n;i++){
        
            scanf("%lld",&a[i]);
            sum[i]=(sum[i-1]+a[i])%mod;
            ans=(ans+a[i]*a[i])%mod;
        }
        ans=((n-1)*ans)%mod;
        for(ll i=1;i<=n;i++){
        
            ans=(ans-2*(sum[i-1]*a[i])%mod+mod)%mod;
        }
        printf("%lld\n",ans);
        return 0;
    }

### I： ###

一道树链剖分的模板题

### 其他： ###

由于比赛的时候其他题都没看，所以待补

[20200419095556871.png]: /images/20230521/0dcd229444e14616bafb20bb8412230b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JvbGl1MTQ3MjU4_size_16_color_FFFFFF_t_70]: /images/20230521/67469a308fbf45aa90730a5b1a99f693.png
[20200419115542775.png]: /images/20230521/9eaf2dd432314ab09776d2c3f6b0c180.png
[20200419120133239.png]: /images/20230521/cf144d775e364ac399777eeb13e30a9f.png