【LGR-068】洛谷 2 月月赛 I & 加油武汉！ 题解

【LGR-068】洛谷 2 月月赛 I & 加油武汉！

居家隔离

先将 $a_i$ 排序，然后枚举 $k,y$ 即可，时间复杂度 $\mathcal O(n^2)$。

const int N = 1e3 + 7;
int n, a[N];
modint s[N], v[N], p[N], vp[N], ans[N];

int main() {
	rd(n), p[0] = v[0] = 1;
	for (int i = 1; i <= n; i++) rd(a[i]), p[i] = p[i-1] * i;
	sort(a + 1, a + n + 1);
	vp[n] = 1 / p[n];
	for (int i = n; i; i--)
		s[i] = s[i+1] + a[i], v[i] = vp[i] * p[i-1], vp[i-1] = vp[i] * i;
	sort(a + 1, a + n + 1);
	for (int k = 1; k < n; k++) {
		for (int i = k; i < n; i++)
			ans[k] += s[i+1] * v[n-i] * k * p[i-1] * vp[i-k] * p[n-k] * vp[n];
		ans[k] += (s[1] - a[n]) * v[n-1] * k * p[n-1] * vp[n-k] * p[n-k] * vp[n];
		print(ans[k], ' ');
	}
	return 0;
}

七步洗手法

对于每个不合法的三角形，都有两个内角满足两边颜色不一样，因此

$$ans = \binom{n}{3} - \frac{\sum_{i=1}^n d_i \times (n - 1 - d_i)}{2}$$

const int N = 1e5 + 7;
int n, m, d[N];

int main() {
	rd(n), rd(m);
	for (int i = 1, x, y; i <= m; i++) rd(x), rd(y), ++d[x], ++d[y];
	ll ans = 1ll * n * (n - 1) * (n - 2) / 6, now = 0;
	for (int i = 1; i <= n; i++) now += d[i] * (n - 1 - d[i]);
	print(ans - now / 2);
	return 0;
}

疫情调查

首先 Floyd 出任意两点间的最短距离。

建一个二分图，左右部各有 $n$ 个点。

对于左部点 $u$ 和右部点 $v$ 之间的边，若 $u\ne v$，边权为 $\operatorname{dist}(u, v)$，否则为 $a_u$。

可以发现这个二分图的最大匹配一定是个完美匹配，而权值最小的完美匹配就是答案。

那么用最小费用最大流求二分图最小权最大匹配即可。

普通的 EK-SPFA 费用流跑不过去，时间复杂度大概是 $\mathcal O(n^5)$，要进行一些优化。

传染病研究

题目太神仙了，先咕咕咕着。

$\textstyle$