【题解】牛客小白月赛44题解
深渊水妖
https://ac.nowcoder.com/acm/contest/11221/A
写在前面的话
这场比赛相比预期的小白月赛难度略高,可能是因为没内测的原因,确实是一个失误
A 深渊水妖
知识点:模拟,排序
对标cf难度:1200
先把所有上升区间找出来,然后输出等于 最大值的那些区间。
坑点:容易读错题,读成 的最大值。
吐槽:作为小白月赛的签到题太难了啊。
参考代码:
#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
知识点:数学
不难发现,改乘法为加法后,相当于每个数和另一个数位上的数相加,所以会加(对方的数位)那么多次。
因此最后的答案就是
建议使用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
个人认为本题难度适合作为小白月赛压轴题。
本题要求树上有多少个起点和终点均为黑点的路径。
答案显然是 ,其中cnt是黑点的数量。
至于黑点数量怎么求,按照二分图染色的方式dfs一下即可。
注:本人在比赛过程中做复杂了,用以下的方式通过的本题:
-
对于每个点 ,先求出它子树中黑点的数量为
-
分别求出以每个点为根的子树、经过该点的路径数量:若该点为白点,数量为 (因为在以该点的孩子中,任取两个的子树中取点,那么方案数为 )。若该点为黑点,那么方案数为 (除了途径该点的,还有以该点为端点的路径,以及该点本身)。
#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';
}
}