Codeforces Round 936 (Div. 2)

A. Median of an Array

 分析：求使中位数增加的最少操作次数。为了使操作次数尽量少，让中位数增加1就行了。

int a[N];
void solve() {
	int n; cin >> n;
	rep(i, 1, n) cin >> a[i];
	sort(a + 1, a + 1 + n);
	int k = (n + 1) / 2;
	int ans = 0;
	rep(i, k, n) {
		if (a[i] == a[k]) ans++;
	}
	//tans;
	cout << ans << endl;
}

B. Maximum Sum

分析：为了使最后数组的和尽量大，那我们每次的插入就要尽可能大。

很显然要dp求数组的最大子数组的和，x。

第一次在最大子数组和的那个区间插入x，此时最大子数组和变成了2x

第二次同理，插入2x。

以此类推

int a[N], dp[N];
const int mod = 1e9 + 7;
void solve() {
	int n, k; cin >> n >> k;
	int cur = 0;
	int sum = 0;
	rep(i, 1, n) {
		cin >> a[i];
		sum += a[i];
		dp[i] = max(a[i], dp[i - 1] + a[i]);
		cur = max(cur, dp[i]);
	}
 
	sum = (sum % mod + mod) % mod;
	cur = cur % mod;
	int ans = (sum + qmi(2, k, mod) * cur - cur + mod) % mod;
	
 
	//tans;
	cout << ans << endl;
}

C. Tree Cutting

分析：二分+dfs。要我们求最小连通块的最大值是多少

思路：我们可以二分答案x。

因为题目要求切割k次，那么就会有k+1个连通块。所以我们二分的思路就是，尽量把树分割成尽量多个连通块（数量为cnt），且每个连通块大小>=x，若cnt>=k+1，那么x就可以。

我们用dfs来实现以上操作。我们希望从下往上遍历树的结点cur，一旦遇到 sz[cur] >= x（以cur为根结点的树的大小），就把cur与其父亲的连接切割掉。

ps：dfs中的fa，是上一个访问的结点，避免走“回头路”。

int n, k, cnt;
int a[N], sz[N];
vector<int> g[N];
void dfs(int cur, int fa, int x) {
	sz[cur] = 1;
	for (auto it : g[cur]) {
		if (it == fa) continue;
		dfs(it, cur, x);
		sz[cur] += sz[it];
	}
	if (sz[cur] >= x) cnt++, sz[cur] = 0;
}
bool check(int x) {
	cnt = 0;//连通块个数
	
	dfs(1, 0, x);

	if (cnt >= k + 1) return 1;
	return 0;
}

void solve() {
	rep(i, 0, n) g[i].clear();
	cin >> n >> k;
	rep(i, 1, n - 1) {
		int u, v; cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}

	int l = 1, r = N;
	int ans = 1;
	while (l <= r) {
		int mid = (l + r) >> 1;

		if (check(mid)) {
			l = mid + 1;
			ans = mid;
		}
		else {
			r = mid - 1;
		}
	}

	//tans;
	cout << ans << endl;
}