「Summary」2022-08-09 做题记录

😭😭😭😭😭

2022-08-09

$\mathbb{HDU \ 5294}$

《奇门遁甲》

看到题面，感觉很乐。
先把最短路上可能存在的边拿出来，问题一是最小割，问题二是最小边数。

$\mathbb{HDU \ 6598}$

题面告诉我们一个团队里既要有强硬的上单又要有能输出的中单。

连边和《文理分科》比较相似。
对于一组 $u, v, a, b, c$ 连边为 $(st, u / v) = b + a, (u / v, ed) = b + c, (u, v) = 2 \times b - a - c$ 。
贡献是负的。

$\mathbb{CF\ 1146G}$

串联分压

懒，直接给代码。

read(n, h, m), st = n * (h + 2) + 1, ed = st + 1;
for (int i = 1; i <= n; i++) {
	res += h * h;
	AddEdge(st, ind(i, 1), INF);
	for (int j = 1; j <= h + 1; j++) AddEdge(ind(i, j), ind(i, j + 1), h * h - (j - 1) * (j - 1));
	AddEdge(ind(i, h + 2), ed, INF);
}
for (int i = 1, l, r, x, c; i <= m; i++) {
	read(l, r, x, c);
	for (int pos = l; pos <= r; pos++) AddEdge(ind(pos, x + 2), ed + i, INF);
	AddEdge(ed + i, ed, c);
}

$\mathbb{CF\ 903G}$

看了一个小时才看懂题解

设左边取的是 $u$, 右边是 $v$ ，则答案为 $A_u + B_v + \sum_{x > u, y < v} w_{u, v}$ 。修改只会影响 $A_u$ 则线段树可以直接维护右边的一坨。