Codeforces Round 936 (Div. 2) (A~C)
A题:Median of an Array
标签: 实现问题,编程技巧,模拟(implementation)
题目大意
- 一个由 n 个整数组成的数组 a。在一次操作中将 ai 增加 1
- 找出增加数组中位数所需的最少操作次数。
- 这里中位数为 ak,k = n / 2 上取整
思路
- 从小到大排序,找到中位数前面有几个于其相等的值+1即可
AC代码
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 200010;
int f[N];
void solve()
{
int n;
cin >> n;
for(int i = 1; i <= n; i++)
cin >> f[i];
sort(f + 1, f + 1 + n);
int i = (n + 1) / 2, cnt = 0, tt = f[i];
while(i <= n && tt == f[i]) i++, cnt ++;
cout << cnt << endl;
}
int main()
{
int T; cin >> T;
while(T--)
solve();
return 0;
}
B题:Maximum Sum
标签: 贪心策略(greedy)数学(math)
题目大意
- 选择数组 a 的任意连续子数组(可能为空),并在数组的任意位置插入该子数组的和。
- 找出经过 k 操作后数组的最大和。输出答案的模数 109 + 7
思路
- 贪心:找到 连续子序列最大和,如果大于0将其和添加到这个连续子序列旁边。所以,每次插入后连续子序列最大和翻倍
- 注意:连续子序列最大和中也可能包含负数,例如:10 -9 10 -3 2,连续子序列最大和为10 - 9 +10 = 11
AC代码
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int mod = 1e9 + 7;
void solve()
{
int n, k;
cin >> n >> k;
LL sum = 0, res = 0, t = 0;
for(int i = 0; i < n; i++)
{
int a; cin >> a;
sum += a;
t += a;
if(t < 0) t = 0;
res = max(t, res);
}
// 所有数的和 - 连续子序列最大和 = 剩下数的和
sum = sum - res;
// 反复插入连续子序列最大和,每次插如后翻倍
for(int i = 0; i < k; i++)
res = res * 2 % mod;
// 加上最大数的和,防止为负数
res = ((res + sum) % mod + mod) % mod;
cout << res << endl;
}
int main()
{
int T; cin >> T;
while(T--)
solve();
return 0;
}
C题:Tree Cutting
标签: 二分搜索(binary search)动态规划(dp)贪心策略(greedy)实现问题,编程技巧,模拟(implementation)树形结构(trees)
题目大意
- 一棵有 n个顶点的树
- 找出最大的 x ,从而可以从这棵树上删除 k 条边,使得每个剩余的连接部分点的个数至少为 x
思路
- 贪心:找出可以将树切割成至少有 x 个顶点的最大连通组件数。从顶点 1 开始切分,假设当前位于顶点 v,且其子树中的顶点数大于或等于 x ,那么删除顶点 v 到其父树的边。如果经过上述处理后,至少有 k 个相连的成分,那么这个 x 的条件就满足了
- 如果我们可以得到某个答案 x ,那么我们也可以得到答案 x−1 (与 x 的方法完全相同),因此我们可以对 x 进行二分查找。
AC代码
#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int t, n, k, sz[N], cnt;
vector<int> v[N];
void dfs(int u, int fa, int x)
{
for(auto j : v[u])
{
if(j == fa) continue;
dfs(j, u, x);
sz[u] += sz[j];
}
if(sz[u] >= x && cnt)
sz[u] = 0, cnt--;
}
bool check(int mid)
{
cnt = k;
for(int i = 1;i <= n; i++) sz[i]=1;
dfs(1, -1, mid);
if(cnt == 0 && sz[1] >= mid) return true;
return false;
}
void solve()
{
cin >> n >> k;
for(int i = 1;i <= n; i++) v[i].clear();
for(int i = 1;i < n; i++)
{
int x, y;
cin >> x >> y;
v[x].push_back(y);
v[y].push_back(x);
}
int l = 1, r = n;
while(l <= r)
{
int mid = (l+r)/2;
if(check(mid)) l = mid+1;
else r = mid-1;
}
cout << r << endl;
}
int main()
{
cin >> T;
while(T--)
solve();
return 0;
}
logo
//へ /|
// /\7 ∠_/
// / │ / /
// │ Z _,< / /`ヽ
// │ ヽ / 〉
// Y ` / /
// イ● 、 ● ⊂⊃〈 /
// () へ | \〈
// >ー 、_ ィ │ //
// / へ / ノ<| \\
// ヽ_ノ (_/ │//
// 7 |/
//
/*
__ _,--="=--,_ __
/ \." .-. "./ \
/ ,/ _ : : _ \/` \
\ `| /o\ :_: /o\ |\__/
`-'| :="~` _ `~"=: |
\` (_) `/
.-"-. \ | / .-"-.
.---{ }--| /,.-'-.,\ |--{ }---.
) (_)_)_) \_/`~-===-~`\_/ (_(_(_) (
( )
) (
'---------------------------------------'
*/