Codeforces Round #835(div4) A~G题解

前言

也是好久没有打div4了，上一次还是半年前的第二场cf比赛，记得当时过了3题，非常开心。这一次过了5个题，D题调试时间太久，导致F题最后没时间调试了。总之还不错。
Codeforces Round #835(div4)补题链接

A. Medium Number 签到

题意：给你三个数，求中位数。
Acwing周赛原题，写个数组，排序一下，然后输出中间即可。

#include<bits/stdc++.h>
using namespace std;
int main()
{int T;cin>>T;while(T--){int a[3];cin>>a[0]>>a[1]>>a[2];sort(a,a+3);cout<<a[1]<<endl;}return 0;
}

B Atilla’s Favorite Problem 签到

题意：给你一个字符串，找到ASCII码最大的字符。输出字母表中的位置。
思路：直接暴力扫一遍，更新最大值即可，记得下标需要+1。
代码：

#include<bits/stdc++.h>
using namespace std;
int main()
{int T;cin>>T;while(T--){int n;cin>>n;string s;cin>>s;int ans=0;for(int i=0;i<n;i++){ans=max(ans,s[i]-'a'+1);}cout<<ans<<endl;}return 0;
}

C. Advantage 签到

题意：给定一串序列，求出每个序列与除他以外最大的值得差值。
思路：求出最大值和次大值。对于不等于最大值的，直接用它减去最大值，反之，减去次大值。
最大值和次大值可以维护，我就直接备份了一个数组，然后直接排序求了。
代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int a[N],b[N];
int main()
{int T;cin>>T;while(T--){int n;cin>>n;for(int i=0;i<n;i++){cin>>a[i];b[i]=a[i];}sort(b,b+n);for(int i=0;i<n;i++){if(a[i]!=b[n-1]) cout<<a[i]-b[n-1]<<" ";else cout<<a[i]-b[n-2]<<" ";}cout<<endl;}return 0;
}

D. Challenging Valleys 思维

题意：如果一段序列只存在一段“谷”，那么输出“Yes”，否则输出“No”。所谓“谷”，要么首段上升，要么尾端下降，或者先下降，在上升。
思路：因为只能有一个“谷”出现，我们发现，如果序列上升了，那么就必须一直上升，否则就会存在多个“谷”。（因为你上升了然后又下降，只有两种情况，一种一直下降到最后，那么就会有首端和尾端两个谷，不满足题意，如果你上升下降后面又上升，那么就有首段一个谷，下降上升又一个谷，两个谷，不满足题意）
代码：

#include<bits/stdc++.h>
using namespace std;
const int N =2e5+10;
int a[N];
int main(){int T;cin>>T;while(T--){int n;cin>>n;for(int i=0;i<n;i++) cin>>a[i];bool flg=0;//表示是否已经上升过bool ans=0;for(int i=1;i<n;i++){if(a[i]>a[i-1]) flg=1;if(flg&&a[i]<a[i-1]) {ans=1;break;}}if(ans) puts("No");else puts("Yes");}return 0;
}

E. Binary Inversions 思维+贪心

题意：给你一个只含0和1的数组，你有一次机会把一个数反转（0变为1,1变为0），让你求出各种操作后逆序对的最大值。
思路：因为数组比较特殊，只含0和1，那么逆序对数量就等于，每个1后面0的数量之和。这里可以贪心，如果要使逆序对最大，那么我们可以把第一个0改为1，或者把最后一个1改为0，最后计算原本的逆序对，三个取最大值即可。
写一个求解逆序对函数，倒着统计0的个数，如果遇到1，那么这个1的逆序对数就是当前0的数量，总逆序对，求个和就好。记得开long long。
代码：

#include<bits/stdc++.h>
using namespace std;
const int N =2e5+10;
typedef long long LL;
LL a[N],cnt[N];
int n;
LL Reverse_pair(){memset(cnt,0,sizeof cnt);//数组初始化LL res=0,num=0;for(int i=n;i>=1;i--){if(!a[i]) num++;else cnt[i]=num;}for(int i=1;i<=n;i++){res+=cnt[i];}return res;
}
int main(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);int T;cin>>T;while(T--){cin>>n;bool flg=0;int f0=0,l1=0;//维护第一个0和最后一个1的下标for(int i=1;i<=n;i++) {cin>>a[i];if(!flg&&!a[i]) {f0=i;flg=1;}if(a[i]) l1=i;}LL b=Reverse_pair();a[f0]=1;//第一个0变为1LL c=Reverse_pair();a[f0]=0;//还原a[l1]=0; //最后一个1变为0LL d=Reverse_pair();cout<<max({b,c,d})<<endl;}return 0;
}

F. Quests 前缀和+二分

题意：给你n个任务，每个任务做完，会给你ai的奖励，任务做完后k天就不能再做这个任务，给你c和d，让你求出能够在d天内，奖励达到c的最大k值。
分析：因为我们需要尽快达到c，所以每次先做奖励最多的任务，所以需要排个序，二分答案，mid为一个周期，一个周期之后就可以在做奖励最多的任务。所以check函数就写当前的奖励是否大于等于c即可。
代码：

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
typedef long long LL;
LL a[N],sum[N];
LL n,c,d;
bool check(LL mid){LL res=sum[min(mid+1,n)]*(d/(mid+1))+sum[min(n,d%(mid+1))];return res>=c;
}
int main(){int T;cin>>T;while(T--){cin>>n>>c>>d;for(int i=1;i<=n;i++) cin>>a[i];sort(a+1,a+n+1,greater<int>());memset(sum,0,sizeof sum);for(int i=1;i<=n;i++) sum[i]=sum[i-1]+a[i];LL l=-1,r=d+1;while(l<r){LL mid=(l+r+1)>>1;if(check(mid)) l=mid;else r=mid-1;}if(l==-1) puts("Impossible");else if(l==d+1) puts("Infinity");else cout<<l<<endl;}
}

G. SlavicG’s Favorite Problem 图论+搜索+思维

题意：给你一棵带边权的树，给定起点a和终点b，刚开始的分数是0，每次经过一条边，分数就等于当前分数异或上该边的边权，要求你最后到大b时，分数要为0，你在图中有一次可以传送的机会，你可以传送到任意结点，求是否可以满足要求。
思路：根据异或的性质，两个相同的分数异或，结果为0，所以我们可以从起点搜索一遍，记录下经过每一条边当前的分数。在从终点相同方式搜索一遍，如果遇到了相同的分数，那么我们可以到达一个相同的节点，然后传送到另一个值相等的节点，再走到b即可满足条件，否则，无法满足条件。
代码：多组数据，记得做好中间变量初始化操作。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10,M=2*N;
int h[N],e[M],ne[M],w[M],idx;
int n,a,b;
bool st[N];
bool flg;
map<int,int> mp;
void add(int a,int b,int c){e[idx]=b;w[idx]=c;ne[idx]=h[a];h[a]=idx++;
}
void init(){//变量初始化idx=0;flg=0;memset(h,-1,sizeof h);memset(e,0,sizeof e);memset(ne,0,sizeof ne);  memset(w,0,sizeof w);memset(st,0,sizeof st);mp.clear();
}
void dfs(int u,int cur){mp[cur]=1;st[u]=true;for(int i=h[u];~i;i=ne[i]){int j=e[i];if(st[j]) continue;if(j==b) continue;dfs(j,cur^w[i]);}
}
void dfs1(int u,int cur){st[u]=true;for(int i=h[u];~i;i=ne[i]){int j=e[i];if(st[j]) continue;dfs1(j,cur^w[i]);if(flg) return;if(mp[cur^w[i]]) flg=1;}
}
int main(){int T;cin>>T;while(T--){cin>>n>>a>>b;init();n--;while(n--){int a,b,c;cin>>a>>b>>c;add(a,b,c);add(b,a,c);}dfs(a,0);memset(st,0,sizeof st);dfs1(b,0);if(flg) puts("YES");else puts("NO");}
}