「杂题集」- 2019年9月25日

[POI2008]BLO

一眼可以了解到是一道割点题。对于不是割点的情况,那么被计算的点对一定包含此点本身,又因为有序,所以贡献就是\(2(n – 1)\)。如果是割点的话,就比较麻烦,分下面几个来算:

  • 此点延伸出去的点对。
  • 连通块之间的点对。
  • 本身就无法互通的点对。

第一个很好算,是\(2(n – 1)\)。第二个,在 Tarjan 枚举搜索子树的时候计算子树大小和全图补集的乘积(注意,这里会多计算一遍与点\(u\)的点对,所以我们第一个改成算\(n – 1\));第三个,算「当前整颗搜索树与图的补集大小」与「搜索树的大小」的乘积。

综合起来就是,对于点\(u\):

\[ ans_u = \sum_{k \in son(u)} (n – size(k)) \times size(k) + (n – 1) + (n – 1 – \sum_{k \in son(u)} size(k)) \times (1 + \sum_{k \in son(u)} size(k)) \]

继续阅读「杂题集」- 2019年9月25日

[Fortuna OJ]4606 – 序列 / HEOI 2016 Sequence

主要思路

由于本人分治很菜,所以就来刷分治题了。

先思考 50 分\(O(n^2)\)的做法。记录每一个位置的原始值、变化后的最大值、变化后的最小值,然后发现如果一个位置\(i\)对后面的位置\(j\)有贡献当且仅当:

\[a_i < minVal_j \ (1) \\ maxVal_i < a_j \ (2) \]

所以这就相当于一个二位偏序的题目,有两个限制。我们可以用整体二分,在做完左区间之后,左区间按原来的值进行排序,而右区间按最小值进行排序,即可满足第一个条件;第二个条件可以用线段树来搞,搞两个指针来比较大小,然后用线段树来统计答案即可。非常好写。

继续阅读[Fortuna OJ]4606 – 序列 / HEOI 2016 Sequence

[Fortuna OJ]Aug 18th – Group A 解题报告

A – 完全背包

这道题真的是令人窒息,也告诉了我比赛的时候上 QQ 是一个非常坏的习惯。

这道题 60 分做法非常之显然:相同体积的物品归为一种物品,且价值为同体积内最大的价值。这样就可以把物品数量压到 100 个以内。

但是这样是通过不了全部分数的,而且全部分数的容量非常之大,所以正常的 DP 优化是行不通的。做完上面的压缩之后,可以考虑做一些贪心进行优化。接下来我会详细的介绍这个贪心策略:

继续阅读[Fortuna OJ]Aug 18th – Group A 解题报告