【题解】牛客小白月赛44题解

写在前面的话

这场比赛相比预期的小白月赛难度略高，可能是因为没内测的原因，确实是一个失误

A 深渊水妖

知识点：模拟，排序

对标cf难度：1200

先把所有上升区间找出来，然后输出等于 $a[r]-a[l]a[r]-a[l]$ 最大值的那些区间。

坑点：容易读错题，读成 $r-lr-l$ 的最大值。

吐槽：作为小白月赛的签到题太难了啊。

参考代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int mod=1e9+7;
int a[101010];
struct node
{
    int l,r,val;
    node(int l,int r,int val):l(l),r(r),val(val){}
};
bool cmp(node a,node b){
    if(a.val!=b.val)return a.val>b.val;
    return a.l<b.l;
}
int main(){
    ios::sync_with_stdio(false);cin.tie(0);
    int n,i,j,k,t,_=1;
    cin>>_;
    while(_--){
        cin>>n;
        for(i=1;i<=n;i++)cin>>a[i];
        vector<node>p;
        int l=1;
        for(i=2;i<=n;i++){
            if(a[i]<a[i-1]){
                p.push_back(node(l,i-1,a[i-1]-a[l]));
                l=i;
            }
        }
        p.push_back(node(l,n,a[n]-a[l]));
        sort(p.begin(),p.end(),cmp);
        for(i=0;i<p.size();i++){
            if(p[i].val==p[0].val)cout<<p[i].l<<" "<<p[i].r<<" ";
        }
        cout<<'\n';
        
    }
}

B 顽皮恶魔

知识点：字符串，枚举

对标cf难度：1000

真正的签到题。找到所有周围没胡萝卜的植物即可。

坑点：如果用普通的字符串读入方式，需要注意下标是从0开始的。

参考代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int mod=1e9+7;
string a[1111];
int main(){
    ios::sync_with_stdio(false);cin.tie(0);
    int n,m,i,j,k,t,_=1;
    cin>>_;
    while(_--){
        cin>>n>>m;
        for(i=0;i<n;i++)cin>>a[i];
        for(i=0;i<n;i++){
            for(j=0;j<m;j++){
                if(a[i][j]=='P'){
                    for(k=-1;k<=1;k++){
                        for(t=-1;t<=1;t++){
                            int x=i+k,y=j+t;
                            if(x>=0&&x<n&&y>=0&&y<m&&a[x][y]=='*')a[i][j]='t';
                        }
                    }
                }
            }
        }
        int res=0;
        for(i=0;i<n;i++){
            for(j=0;j<m;j++)res+=a[i][j]=='P';
        }
        cout<<res<<'\n';
    }
}

C 绝命沙虫

对标cf难度：1300

知识点：模拟

题目怎么说就怎么做。模拟每次充值和返现的过程即可。

坑点：double精度问题，解决方法是加一个特别小的数然后向下取整（强转int）

参考代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int mod=1e9+7;
int a[101010];
int main(){
    ios::sync_with_stdio(false);cin.tie(0);
    int n,i,j,k,t,_=1;
    cin>>_;
    while(_--){
        double m;
        cin>>n>>m;
        long long r,g;
        long long res=0;
        while(n>0){
            r=n*100,g=min(10000,(int)(n*100*(m-0.99999999999999)));
            res+=r/10+g/10;
            n=r/200;
        }
        cout<<res<<'\n';
    }
}

D 丛林木马

对标cf难度：1500

知识点：数学

不难发现，改乘法为加法后，相当于每个数和另一个数位上的数相加，所以会加（对方的数位）那么多次。

因此最后的答案就是 $a\ast (b\mathrm{的}\mathrm{数}\mathrm{位}\mathrm{数})+b\ast (a\mathrm{的}\mathrm{数}\mathrm{位}\mathrm{数})a*(b的数位数)\; +\; b*(a的数位数)$

建议使用python通过此题，可以避免高精度（滑稽

参考代码（：

t=int(input())
for i in range(t):
    a,b=input().split()
    m=min(len(a),len(b))
    print((int(a)*len(b)+int(b)*len(a))%998244353)

E 变异蛮牛

知识点：树形dp，dfs

对标cf难度：1600

个人认为本题难度适合作为小白月赛压轴题。

本题要求树上有多少个起点和终点均为黑点的路径。

答案显然是 $C_{cnt}^{2}C\_\{cnt\}^2$，其中cnt是黑点的数量。

至于黑点数量怎么求，按照二分图染色的方式dfs一下即可。

注：本人在比赛过程中做复杂了，用以下的方式通过的本题：

1. 对于每个点 $xx$，先求出它子树中黑点的数量为 $dp[x]dp[x]$

2. 分别求出以每个点为根的子树、经过该点的路径数量：若该点为白点，数量为 ${\sum }_{i=1}^m{\sum }_{j=i+1}^{m}dp[i]\ast dp[j]\backslash sum\_\{i=1\}^\{m\}\backslash sum\_\{j=i+1\}^\{m\}dp[i]*dp[j]$（因为在以该点的孩子中，任取两个的子树中取点，那么方案数为 $dp[i]\ast dp[j]dp[i]*dp[j]$ ）。若该点为黑点，那么方案数为 ${\sum }_{i=1}^m{\sum }_{j=i+1}^{m}dp[i]\ast dp[j]+{\sum }_{i=1}^{m}dp[i]+1\backslash sum\_\{i=1\}^\{m\}\backslash sum\_\{j=i+1\}^\{m\}dp[i]*dp[j]+\backslash sum\_\{i=1\}^\{m\}dp[i]+1$（除了途径该点的，还有以该点为端点的路径，以及该点本身）。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
long long mod=1e9+7,dp[201010],p[201010];
vector<int>g[201010];
int dfs(int x,int pr,int d){
    int sum=d;
    p[x]=d;
    for(int i=0;i<g[x].size();i++){
        if(g[x][i]!=pr)sum+=dfs(g[x][i],x,1-d);
    }
    return dp[x]=sum;
}
long long res=0;
void cal(int x,int pr){
    res+=p[x];
    long long temp=0;
    for(int i=0;i<g[x].size();i++){
        if(g[x][i]!=pr){
            //if(x==1)cout<<g[x][i]<<" "<<dp[g[x][i]]<<'\n';
            res+=dp[g[x][i]]*temp;
            temp+=dp[g[x][i]];
            res+=p[x]*dp[g[x][i]];
            cal(g[x][i],x);
        }
    }
}
int main(){
    ios::sync_with_stdio(false);cin.tie(0);
    int n,m,i,j,k,t,_=1;
    cin>>_;
    while(_--){
        cin>>n;
        for(i=1;i<=n;i++)g[i].clear(),dp[i]=0,p[i]=0;
        for(i=1;i<n;i++){
            int x,y;
            cin>>x>>y;
            g[x].push_back(y);
            g[y].push_back(x);
        }
        dfs(1,-1,1);
        res=0;
        cal(1,-1);
        cout<<res<<'\n';
        //cout<<dp[1]*(dp[1]+1)/2<<'\n';     //直接输出这句话也可以通过。
    }
}

F 幽暗统领

对标cf难度：2000

知识点：树，贪心

思路：

显然，如果最长链不超过所有点数的一半，那么所有的点都可以成为重心。

如果最长链超过了sum的一半，那么重心一定落在最长链上。求出有效的左右端点位置即可。

具体推导我是通过找规律找到的，附一张草稿纸（

参考代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int mod=1e9+7;
long long a[101010];
int main(){
    ios::sync_with_stdio(false);cin.tie(0);
    int n,m,i,j,k,t,_=1;
    cin>>_;
    while(_--){
        cin>>n;
        long long sum=0,ma=0,res=0;
        for(i=0;i<n;i++)cin>>a[i],sum+=a[i],ma=max(ma,a[i]);
        //sort(a,a+n);
        long long yu=sum-ma;
        //如果一个最大值不超过其他点的总和，那么所有点全部都可以是重心
        if(ma<=yu){cout<<sum<<'\n';continue;}
        //否则只计算最长链，找到中间合法部分（小+余≥大）
        long long l=(ma-yu+1)/2,r=ma+1-l;
        cout<<r-l+1<<'\n';
    }
}