1463

题意：树的最小点覆盖，选择最少的点覆盖所有边。 分析： 状态：f[u][0/1] 表示不选/选编号u的点的最优解 转移： 不选u，则一定选u的儿子v，即 f[u][0] +=f[v][1] 选u，则可以选，也可以不选u的儿子v，即 f[u][1] += min(f[v][0], f[v][1]); ......

# P1463 [POI2001] [HAOI2007] 反素数 题解 可以发现，最大的不超过 $n$ 的反素数就是 $1\sim n$ 中因数最多的数字。 > 证明： > > 设 $x, x\in[1, n]$ 为 $1\sim n$ 中因数最多的数字，则 $x #define x first # ......

在 $S=[1,n]\cap \mathbb Z$ 中选出一个最大子集 $T$ 使得其任意两元素差不为 $x$ 且不为 $y$，求 $|T|$。$n\le 10^9,x,y\le 22$。 通项，打表找规律套结论，或者矩乘。都是错的。考虑一个周期性。 注意到有 $n=x+y$ 的包。上结论，将对于 ......