codeforces round 936 div2(a,b,c)

本文主要是介绍codeforces round 936 div2(a,b,c)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

快一个月没做题了…果然vp的依托，加快训练吧
比赛链接

A

题目大意

给定$n$个元素的数组$a$，每次操作可以选择一个元素并让其加$1$，问使得数组中位数（像上取整）变大的最小操作次数为多少

思路

先排序。每次操作让数字变大，中位数是否只与等于自己的有关，统计输出

ACcode

#include<bits/stdc++.h>using namespace std;#define int long longvoid solve()
{int n;cin >> n;vector<int>a(n + 3);for (int i = 1;i <= n;i++)cin >> a[i];sort(a.begin() + 1, a.begin() + 1 + n);int mid = n / 2;if (n & 1)mid++;int mm = mid;int num = 0;while (a[mid] == a[++mm] && mm <= n)num++;cout << num + 1 << '\n';
}signed main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int t;cin >> t;while (t--) {solve();}return 0;
}

B

题目大意

给定$n$个元素的数组$a$，给定$k$次操作，每次操作找到$a$的连续任意子数组（可以是$0$），并在$a$中任意位置插入连续子数组的和，找到输出$k$次操作之后的数组$a$的最大和（结果对$1e9+7$取模）

思路

求数组内连续元素的和的最大值，叠加即可

ACcode

#include<bits/stdc++.h>using namespace std;#define int long longconst int M = 1e9 + 7;void solve()
{int n, k;cin >> n >> k;vector<int>a(n + 9);int sum = 0;for (int i = 1;i <= n;i++)cin >> a[i], sum += a[i], a[i] += a[i - 1];int pl = 0;int ans = 0;//求连续最大和for (int i = 1;i <= n;i++) {ans = max(ans, a[i] - a[pl]);if (a[i] <= a[pl])pl = i;}while (k--) {sum = (sum + ans) % M;ans = (ans + ans) % M;}if (sum >= 0)cout << sum % M << '\n';else cout << sum + M << '\n';
}signed main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int t;cin >> t;while (t--) {solve();}return 0;
}

C

题目大意

给定$n$个节点的树，给定整数$k$，要求找到最大的$x$，使得删去$k$条边后每块节点数量最少为$x$

思路

找到最大值的最小，一眼二分，二分节点数量
节点最小值范围确定二分边界$[1,n/k]$，$dfs$查询判断节点数量和

ACcode

``
#include<bits/stdc++.h>

using namespace std;

#define int long long

const int M = 1e5 + 7;
vectormv[M];
int m, n, k, num;
int nex[M];

void dfs(int x, int y) {
nex[x] = 1;
for (auto p : mv[x]) {
if (p != y) {
dfs(p, x);
nex[x] += nex[p];
}
}
if (nex[x] >= m)num++, nex[x] = 0;
}

void solve()
{
cin >> n >> k;
for (int i = 0;i < M;i++)mv[i].clear();
for (int i = 2, u, v;i <= n;i++) {
cin >> u >> v;
mv[v].push_back(u);
mv[u].push_back(v);
}
int le = 1;int ri = n / k;
while (le < ri) {
m = le + ri + 1 >> 1;
num = 0;
dfs(1, 0);
if (num > k)le = m;
else ri = m - 1;
}
cout << le << ‘\n’;
}

signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t;cin >> t;
while (t–) {
solve();
}
return 0;
}

这篇关于codeforces round 936 div2(a,b,c)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---