本文主要是介绍Codeforces Round 936 (Div. 2)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
A - Median of an Array
直接进行排序，从后面往前遍历到中位数的位置，在此期间如果有数等于中位数，就将修改次数增加1.
#include "bits/stdc++.h"
using namespace std;#define int long long
#define endl '\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0);
#define all(x) x.begin(),x.end()
#define pi pair<int,int>
#define vi vector<int>void solve()
{int n;cin>>n;vi a(n);for (int i=0;i<n;i++){cin>>a[i];}sort(a.begin(),a.end());int pos=n/2;if(n%2==0){pos--;}int ans=0;for (int i=n-1;i>=0;i--){if(a[i]==a[pos]){ans++;}if(i==pos){break;}}cout<<ans<<endl;}
signed main()
{IOSint t;cin>>t;while(t--){solve();}
}B - Maximum Sum
先找找到最大子数列，然后每次都增加最大子数列，（记得要更新最大子数列，每次相当于增加了一个自己）。最后只要循环增加k次即可。（最后得出的值模数必须要为正，所以先加一个mod
在取模）。
#include "bits/stdc++.h"
using namespace std;#define int long long
#define endl '\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0);
#define all(x) x.begin(),x.end()
#define pi pair<int,int>
#define vi vector<int>const int mod=1e9+7;
void solve()
{int n,k;cin>>n>>k;int sum=0;vi a(n+1);int mn=0,mx=0;for (int i=1;i<=n;i++){cin>>a[i];sum+=a[i];mn=min(mn,sum);mx=max(mx,sum-mn);}int ans=0;for (int i=1;i<=k;i++){ans=(ans*2+mx)%mod;}cout<<(ans+sum%mod+mod)%mod<<endl;}
signed main()
{IOSint t;cin>>t;while(t--){solve();}
}C - Tree Cutting
此题意思为一个n个节点的树，删去k个节点后联通块最小的最大值。所以采用二分答案，二分找到联通块的大小，然后再dfs 找如果联通块大小大于等于这个的数量大于等于k+1的话就满足条件。最后找到最大值即可。
再dfs的过程中 ：如果联通块的大小大于等于要求就间切断和父节的联系。
#include "bits/stdc++.h"
using namespace std;#define int long long
#define endl '\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0);
#define all(x) x.begin(),x.end()
#define pi pair<int,int>
#define vi vector<int>
int cnt=0;
vi v[100010];
int n,k;int dfs(int u,int fa,int ta)
{int tmp=1;for (auto x:v[u]){if(x==fa){continue;}tmp+=dfs(x,u,ta);} if(tmp>=ta){cnt++;return 0;}return tmp;}bool check(int mid)
{cnt=0;dfs(1,-1,mid);if(cnt>=k+1){return true;}else {return false;}
}void solve()
{cin>>n>>k;for (int i=1;i<=n;i++){v[i].clear();}for (int i=1;i<=n-1;i++){int a,b;cin>>a>>b;v[a].push_back(b);v[b].push_back(a);}int l=1,r=n+1;while(l<r){int mid=(l+r+1)>>1;if(check(mid)){l=mid;}else {r=mid-1;}}cout<<l<<endl;}
signed main()
{IOSint t;cin>>t;while(t--){solve();}
}这篇关于Codeforces Round 936 (Div. 2)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
