2020-2021:teams:manespace:codeforces_round_661_div3
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:manespace:codeforces_round_661_div3 [2020/08/07 10:57] iuiou 创建 |
2020-2021:teams:manespace:codeforces_round_661_div3 [2020/08/09 09:42] (当前版本) iuiou |
||
|---|---|---|---|
| 行 24: | 行 24: | ||
| 题解：首先它是边权，可以将边权转化为点权，首先dfs算出目前的值，然后发现没对一个点进行操作后，对整体答案做出的贡献是可以量化的，具体表现为，节点i的子节点中有$sz_i$个叶节点，目前权值为$d_i$，则一次操作队整体的贡献为$sz_i*(d_i-\lfloor\frac{d_i}{2}\rfloor)$,这样先预处理出每个点的贡献权值，之后用一个优先队列维护即可。 | 题解：首先它是边权，可以将边权转化为点权，首先dfs算出目前的值，然后发现没对一个点进行操作后，对整体答案做出的贡献是可以量化的，具体表现为，节点i的子节点中有$sz_i$个叶节点，目前权值为$d_i$，则一次操作队整体的贡献为$sz_i*(d_i-\lfloor\frac{d_i}{2}\rfloor)$,这样先预处理出每个点的贡献权值，之后用一个优先队列维护即可。 | ||
| + | |||
| + | =====F Weights Division (hard version)===== | ||
| + | 题意：上一题的条件下，增加一个对每个节点经行操作的代价，规定代价只能为$1$或者$0$，问达到上述目的的最小代价。 | ||
| + | |||
| + | 题解：按照上一题得方法，将耗费为$1$和耗费为$2$时操作$i$次的最优情况分别全部计算出来，然后枚举二分计算答案即可。 | ||
| + | |||
| + | =====G Yet Another Segments Subset====== | ||
| + | 题意：给出一些区间，问总最多能有多少个区间满足互不相交或者相互嵌套？ | ||
| + | |||
| + | 题意：首先离散化，按照区间大小从小到大排序，从小的开始到大的开始线性$dp$，开一个数组记录每个区间最多能够嵌套多少个小区间。预先设定一个包含了所有范围的大区间，然后大区间的答案即为最终答案。 | ||
2020-2021/teams/manespace/codeforces_round_661_div3.1596769074.txt.gz · 最后更改: 2020/08/07 10:57 由 iuiou
