题解 | A-E

T1 放羊的贝贝

题面巨大多恶心，实际上就是给你一堆矩形，叫你再画一个平行坐标系的折线包含这些矩形，周长最小。

显然统计一个 $l,r,d,ul,\; r,\; d,\; u$，表示现在包含的外接矩形，答案显然是 $2(u-d+r-l)2(u\; -\; d\; +\; r\; -\; l)$。

T2 114514

诈骗，所有整数 $ii$ 都满足，我打表了 $1515$ 分钟才发现，以下为证明：

后面证明了下，可以证，移项过来分解个因数就行。

T3 1919810

dp，挺裸的，$f_{i,j}f\_\{i,\; j\}$ 表示当前 $19198101919810$ 序列到 $ii$ 位，第 $ii$ 位是 $jj$ 的方案数，递推统计即可。

T4 逃亡的贝贝

二分答案，设当前答案为 $midmid$，设每条边原始的边权为 $va{l}_{i}val\_i$，每条边新赋一个边权为 $v_{i}v\_i$ 表示过这条边要几个药水。

然后跑最短路，最后的 $di{s}_{n}dis\_n$ 就是最少用的药水数量，只要小于等于 $kk$ 就是一个合法的答案。

T5 炫酷反演魔术

和官方题解一样化出来这个式子：

注意到 $n\le 300000n\; \backslash le\; 300000$，所以考虑 $n\log nn\; \backslash log\; n$ 做法，

首先套板子出 $\mu \backslash mu$ 和 $\varphi \backslash phi$ 当然还有 $\text{prime}\backslash text\{prime\}$。

然后对于 ${\sum }_{d\mid n}\varphi (d)\mu (\frac{T}{d})\backslash sum\_\{d\; \backslash mid\; n\}\; \backslash phi\; (d)\backslash mu(\backslash frac\; T\; d)$ 和 ${\sum }_{i=1}^n[T\mid a_i]\backslash sum\_\{i\; =\; 1\}^n[T\; \backslash mid\; a\_i]$ 都用调和级数做，大致代码是这样的：

	for (int i = 1; i <= n; i++) {
		for (int j = 1; i * j <= n; j++) {
			G[i * j] += phi[i] * mu[j];
			F1[i] += cnt[i * j];
			
		}
		int t = i, now = 1;
		for (int j = 1; pri[j] * pri[j] <= i; j++) {
			int x = 0;
			while (t % pri[j] == 0) {
				x++; t /= pri[j];
				if (x % 3 == 1) now *= pri[j];
			}
		}
		F3[i] = F1[now * t];
	}
	for (int T = 1; T <= n; T++)
		res += G[T] * F1[T] * F3[T];