牛客小白月赛112

A

• 给定三个数a,b,c,a放在天平一侧，判断有没有方法使得天平平衡

思路

• 瞪眼题
• 能平衡的无非5种情况，a=b,a=c,a=b+c,a+b=c,a+c=b,判断即可

代码

#include<bits/stdc++.h>
using namespace std;
int main(){
    long long a,b,w;
    scanf("%lld%lld%lld",&a,&b,&w);
    if(a==w||b==w||a+b==w||a+w==b||b+w==a){
        printf("Yes\n");
    }else{
        printf("No\n");
    }
    return 0;
}

B

• 给定一个长度为n的数组，如果有元素满足,则记为一座山峰，山峰高度为 ，判断最高的山峰高度是多少，如果没有山峰则输出-1

思路

• 直接模拟即可

代码

#include<bits/stdc++.h>
using namespace std;
long long a[202020];
int main(){
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
    }
    long long ans=-1;
    for(int i=2;i<=n-1;i++){
        if(a[i]>a[i+1]&&a[i]>a[i-1]){
            ans=max(a[i]-(a[i-1]+a[i+1])/2,ans);
        }
    }
    printf("%lld",ans);
}

C

• 有n球和m桶，每桶装够k个就会清零，判断将所有球投入桶后，总和为q

思路

• 依题意，想凑够q个，痛的容量一定得够，即

• 此外，因为消除一定是消除k个，所以

• 注意检验同余使用不要用

  因为，前推后恒成立，后推前需要满足

代码

#include<bits/stdc++.h>
using namespace std;
int main(){
    int t;
    long long n,m,k,q;
    scanf("%d",&t);
    while(t--){
        scanf("%lld%lld%lld%lld",&n,&m,&k,&q);
        if(q>m*(k-1)) printf("No\n");
        else if((n-q)%k!=0)printf("No\n");
        else printf("Yes\n");
    }
    
    return 0;
}

D

• 给一个无根树选根，使得其叉数最小，如果同叉数，输出最小序号

思路

• 对于一个无根树，观察可得，选择作为跟的点的度数会直接成为他的叉数，其余点的度数减一后变为叉数（因为要和父节点相连）
• 贪心考虑，我们希望度数最大的被减一，其它的减不减都不会超过最大的，所以选择不是最大且序号最小的节点作为根节点即可

代码

#include<bits/stdc++.h>
using namespace std;
int degree[202020];
int main(){
    int n;
    scanf("%d",&n);
    for(int i=1;i<n;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        degree[u]++;
        degree[v]++;
    }
    int lar=-1;
    for(int i=1;i<=n;i++){
        lar=max(lar,degree[i]);
    }
    int root=-1;
//     for(int i=1;i<=n;i++)printf("%d ",degree[i]);
//     printf("\n%d",lar);
    for(int i=1;i<=n;i++){
        if(degree[i]!=lar){
            root=i;
            break;
        }
    }
    if(root==-1){
        printf("1 1");
    }else{
        printf("%d %d",lar-1,root);
    }
    return 0;
}