日志 - Qingyu✨的博客

Archive I

Archive II

Archive III

Archive IV

Archive V

Archive VI

Archive VII

Archive VIII

Archive IX

Archive X

Read more
[+38]

简单题。

A

先求一个最短路图然后再这个图上dfs 对于一个点的所有出点按编号从小到大dfs。这样可以保证dfs树就是题目要求的树。

然后在这棵树上跑树分治 $f{i,j,0/1/2}$ 表示前i棵子树从根出发链长为j [0：最长长度][1:这个长度条件下的方案数]

对于第 $i+1$ 棵子树单独跑一个 $f'_{i,j,0/1/2}$ 意义一样枚举这颗子树上链长和f一起更新答案然后用 $f'$ 更新 $f$

B

首先对于两个重心的情况，可以在中间加一个点，变为一个重心的情况。树形dp， $f_{i,j}$ 表示以 $i$ 为根的子树大小为 $j$ 的方案数，转移可以用背包把一个根的所有子树合并

计算 $f$ 数组复杂度 $O(n^3)$

然后对于根求 $g_{i,j,k}$ 表示前 $i$ 棵子树最大节点数 $\leq j$ 节点数和为 $k$ 的方案数，更新用背包更新，直接枚举当前子树取多少，前面的一共取多少什么，如果直接这样做，复杂度 $O(n^4)$ ，可以把根的所有子树按size从小到大排序这样就可以保证对于 $i,j$ 只要枚举 $O(\mathrm{siz}_i)$ 即共为 $\sum \mathrm{siz}_i = n$ 降了一维。

然后枚举最大的子树的大小，设为 $k$ ，只要满足总节点数 $v > 2k$ ，则这个根为唯一重心。

剩余的部分就很显然了。

C

显然答案为 $\min\left(\sum \frac{(kx_i-y_i+b)^2}{k^2 + 1}\right)$

可以三分套三分算出最优解

展开可以发现只要预处理出 $\sum x_i、\sum y_i、\sum x_i^2、\sum y_i^2、\sum x_iy_i$

就可以 $O(1)$ 计算答案

Read more
[-3]

Qingyu✨的博客

博客

上半年附加题合集

Archive I

Archive II

Archive III

Archive IV

Archive V

Archive VI

Archive VII

Archive VIII

Archive IX

Archive X

你OJ278的详细题解

下发文件密码合集

题库功能已更新

题解

提高组良心模拟题题解

A

B

C

Qingyu✨的博客

博客

上半年附加题合集

Archive I

Archive II

Archive III

Archive IV

Archive V

Archive VI

Archive VII

Archive VIII

Archive IX

Archive X

你OJ278的详细题解

下发文件密码合集

题库功能已更新

题解

提高组良心模拟题 题解

A

B

C

提高组良心模拟题题解