BZOJ5093:[Lydsy1711月赛]图的价值 – 题解

主要思路

算是个简单题吧。

首先列个暴力式子:

\[ \sum_G \sum_{i = 1}^n d_i^k \]

发现很不现实。我们考虑把点拆开来考虑,因为全集里面可以直接独立的来算。考虑某个点度数为 \(x\) 的方案数,就变成了:

\[ n \sum_{x = 0}^{n – 1} x^k f(x) \]

其中 \(f(x)\) 代表的是一个图某个点的度数为 \(x\) 的方案数。其实稍微思考下就知道,我们可以把这个点剥离出来,强制连边之后再生成一个图即可:

\[ \begin{aligned} f(x) &= {n – 1 \choose x} 2^{n – 1 \choose 2} \\ ans &= n \sum_{x = 0}^{n – 1} x^k {n – 1 \choose x} 2^{n – 1 \choose 2} \\ &= n2^{n – 1 \choose 2} \sum_{x = 0}^{n – 1} x^k {n – 1 \choose x} \end{aligned} \]

继续阅读BZOJ5093:[Lydsy1711月赛]图的价值 – 题解

「杂题集」- 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