CF1566 - Codeforces Global Round 16

Link: Codeforces Global Round 16

D - Seating Arrangements

题意

给出一个座位表 $n$ 行 $m$ 列，每一行从左侧向右侧入座，如果路程中已经有人入座则会产生1点不满意度，一共有 $nm$ 个人，有 $nm$ 个位置，每个位置有一个观影距离，每个人有视力值，视力值小的人的观影距离必须小于视力大的人，每个人顺次入座，要求满足上述条件，求最小的不满意度。

数据范围：$1\leqslant n,m\leqslant 300$。

思路

不难发现如果对人的视力进行排序后，相同视力值的人都会连续地坐在一起，那么考虑这连续一段的在座位表上的形态，它一定是一段后缀（可能没有），多段完整的一行（或一行中的一部分），一段前缀（可能没有）。我们贪心地将人安排进去，序号小的人应该优先安排在后缀上，然后是中间行上，最后是前缀上，都优先倒序入座。

不难证明这样贪心是最优的方案，因为如果放在后缀上一定不会对别人产生影响，中间行都是自己人也不会，最后一行的前缀是最容易影响到别人的，所以最后安排。

又由于 $m$ 的范围很小，所以可以直接暴力判断逆序对的个数，如果 $n,m$ 较大，则需要树状数组求逆序对了。

时间复杂度 $O(nm^2)$。

点击显/隐代码

#include <bits/stdc++.h>
#define db double
#define ll long long
#define int ll
#define vi vector<int>
#define vii vector<vi >
#define pii pair<int, int>
#define vp vector<pii >
#define vip vector<vp >
#define mkp make_pair
#define pb push_back
#define Case(x) cout << "Case #" << x << ": "
using namespace std;
const int INF = 0x3f3f3f3f;
const int P = 998244353;
signed main(){
#ifdef _DEBUG
//	FILE *file = freopen("out", "w", stdout);
#endif
	ios::sync_with_stdio(0);
	cin.tie(0);
	int T;
	cin >> T;
	while (T--) {
		int n, m, ans = 0;
		cin >> n >> m;
		vp a(n*m);
		for (int i = 0; i < n*m; i++) {
			cin >> a[i].first;
			a[i].second = i;
		}
		sort(a.begin(), a.end());
		for (int i = 0; i < n*m; i++) a[i].second = -a[i].second;
		for (int i = 0; i < n; i++) {
			sort(a.begin() + m*i, a.begin() + m*i+m);
			for (int j = 0; j < m; j++) {
				for (int k = 0; k < j; k++) {
					if (a[m*i + k].second > a[m*i + j].second) ans++;
				}
			}
		}
		cout << ans << '\n';
	}
	return 0;
}

E - Buds Re-hanging

题意

给出一颗含有 $n$ 个顶点的有根树，定义节点 $bud$ 满足：

• 它不是根节点

• 它至少有一个儿子节点

• 所有的儿子节点都是叶子节点

你可以操作任意多次，将 $bud$ 节点和其父节点断开，然后连接到任意一个非该子树中的节点上。

求树上最少的叶子节点数量。

数据范围：$2\leqslant n\leqslant \times 10^5$。

思路

我们发现如果一个 $bud$ 节点的父亲节点时 $root$，那么将 $bud$ 断开后连接到任意一个叶子节点上面，都会将总叶子数目 $-1$。

所以我们先考虑将所有的 $bud$ 连接到 $root$ 上面，这样所有的节点就只有三种 $root, leaf, bud$，设 $bud$ 数目是 $k$，所以答案就是：

• 如果 $root$ 有一个叶子节点：$n-2k-1$

• 否则：$n-2k$

原理就是反复使用上述方法，将 $bud$ 连接到 $leaf$ 上面就能同时保证两个节点不是叶子节点，最后由于 $root$ 和最后一个 $bud$ 不是叶子节点，最后就能推出上式。

由于一个非 $root$ 节点要么是 $bud$ 否则就是 $leaf$，所以用一次 $dfs$ 就能求出最终点的状态了。

时间复杂度 $O(n)$。

点击显/隐代码

#include <bits/stdc++.h>
#define db double
#define ll long long
#define int ll
#define vi vector<int>
#define vii vector<vi >
#define pii pair<int, int>
#define vp vector<pii >
#define vip vector<vp >
#define mkp make_pair
#define pb push_back
#define Case(x) cout << "Case #" << x << ": "
using namespace std;
const int INF = 0x3f3f3f3f;
const int P = 998244353;
vi bud;
vii edges;
void dfs(int u, int prt) {
	for (int v : edges[u]) {
		if (v == prt) continue;
		dfs(v, u);
		if (!bud[v]) bud[u] = 1;
	}
}

signed main(){
#ifdef _DEBUG
//	FILE *file = freopen("out", "w", stdout);
#endif
	ios::sync_with_stdio(0);
	cin.tie(0);
	int T;
	cin >> T;
	while (T--) {
		int n;
		cin >> n;
		bud = vi(n);
		edges = vii(n);
		for (int i = 0; i < n-1; i++) {
			int u, v;
			cin >> u >> v;
			u--, v--;
			edges[u].pb(v);
			edges[v].pb(u);
		}
		dfs(0, -1);
		int ans = n;
		for (int i = 1; i < n; i++) if (bud[i]) ans -= 2;
		if (bud[0]) ans--;
		cout << ans << '\n';
	}
	return 0;
}