T1 放羊的贝贝
题面巨大多恶心,实际上就是给你一堆矩形,叫你再画一个平行坐标系的折线包含这些矩形,周长最小。
显然统计一个 l,r,d,u,表示现在包含的外接矩形,答案显然是 2(u−d+r−l)。
T2 114514
诈骗,所有整数 i 都满足,我打表了 15 分钟才发现,以下为证明:
后面证明了下,可以证,移项过来分解个因数就行。
T3 1919810
dp,挺裸的,fi,j 表示当前 1919810 序列到 i 位,第 i 位是 j 的方案数,递推统计即可。
T4 逃亡的贝贝
二分答案,设当前答案为 mid,设每条边原始的边权为 vali,每条边新赋一个边权为 vi 表示过这条边要几个药水。
vi=⎩⎪⎨⎪⎧0,vali≤mid1,⌈514114vali⌉≤mid<vali+∞,mid<⌈514114vali⌉
然后跑最短路,最后的 disn 就是最少用的药水数量,只要小于等于 k 就是一个合法的答案。
T5 炫酷反演魔术
和官方题解一样化出来这个式子:
T=1∑nd∣n∑ϕ(d)μ(dT)i=1∑n[T∣ai]j=1∑n[T∣aj3]
注意到 n≤300000,所以考虑 nlogn 做法,
首先套板子出 μ 和 ϕ 当然还有 prime。
然后对于 ∑d∣nϕ(d)μ(dT) 和 ∑i=1n[T∣ai] 都用调和级数做,大致代码是这样的:
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];