Codeforces Round 936 (Div. 2)

Codeforces Round 936 (Div. 2) (A~C)

目录：A B 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 操作后数组的最大和。输出答案的模数 10^9^ + 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\ |\__/
         `-'| :="~` _ `~"=: |
            \`     (_)     `/
     .-"-.   \      |      /   .-"-.
.---{     }--|  /,.-'-.,\  |--{     }---.
 )  (_)_)_)  \_/`~-===-~`\_/  (_(_(_)  (
(                         				)
 )                                     (
'---------------------------------------'
*/