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

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

方格取数

看一眼复杂度,\(O(nm)\)级别的,考虑两个循环的 DP。分析整个题面之后发现,我们穿过边界时,当且仅当另一个连通块的权值比当前的大,否则便不会为了穿过边界而损失当前金块。所以,我们做一个 DP 一样的东西:因为发现每个格子只能走一遍,那么在每一列你只能选择一直向上走和一直向下走,所以这个 DP 便没了后效性,然后再处理连通块之间的连接判断就做完了。

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

[Fortuna OJ]6352 – 给(ca)题解

主要思路

首先,叶子结点为\(k\)时,整个完整的二叉树存在\(2k – 1\)个节点。我们设置一个 DP 来进行计数。

考虑设置状态\(dp[i][j]\)为当前树已有\(i\)个节点,且有当前加入的节点到根的路径有\(j\)单位长度。考虑以下转移:

\[ dp[i + 1][j + 1] += dp[i][j] \\ dp[i + 1][j – 1] += dp[i][j] \]

向新的节点加入统计数据:多了一个叶子结点,要么向左走,加深当前的路径;要么补上最后一个向左走的右节点。

然后就可以写代码了。

继续阅读[Fortuna OJ]6352 – 给(ca)题解

CF1204E:Natasha, Sasha and the Prefix Sums 题解

主要思路与推导

这道题是一道好题。

我们可以直接暴力 DP,考虑状态\(dp[i][j]\)为\(i\)个\(1\)与\(j\)个\(-1\)的答案。那么,我们可以从少一个\(1\)的情况和少一个\(-1\)的情况进行转移:

  • 对于少一个\(1\)的情况,也就是\(dp[i – 1][j]\),我们把\(1\)放在这样序列的前面,这样可以让所有序列的最大前缀和都加一,所以贡献就是\(dp[i – 1][j] + {i + j – 1 \choose j}\)。
  • 对于少一个\(-1\)的情况,也就是\(dp[i][j – 1]\),我们把\(-1\)放在这样的区间前面,会产生两种情况:对于贡献大于\(0\)的序列,\(-1\)的贡献就是这样的序列的个数;如果贡献本来就小于等于\(0\),那么就无贡献。所以我们还需要额外计算一个无贡献的序列的个数并加回来。

继续阅读CF1204E:Natasha, Sasha and the Prefix Sums 题解

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

A – Count

真难。

简单来讲,题目要求满足\(\{x_i \mod m \in [1, m – 1]\}\)的\(k\)元组个数。我们可以先把\(x_i\)全部模上一个\(m\),然后令\(A = \sum_{i = 1}^k (x_i \mod m)\)(注意,\(A\)并没有被整体取模,只是各项余数之和),可知\(A \mod m = n \mod m\),且\(A\)的上限就是\(A = k(m – 1)\)(各项上限)。

我们做了这样一个设置之后,问题就可以转换为:对于每一个不同的\(A\),满足\(A \mod m = n \mod m\)且\(A = \sum_{i = 1}^k (x_i \mod m), \forall i, x_i \in [1, m – 1]\)的\(k\)元组方案数。首先,我们可以先枚举每一个\(A\)来缩小问题的范围,根据\(A\)所满足的条件,可以这样遍历\(i\)来获得每一个\(A\):

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

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

A – 小L的数列

这道题的式子跟 Codeforces 一道 F 题是一样的,让我误以为是 BSGS 之类的玩意,最后发现其实算是矩阵乘法的题。

考虑任意一个答案都是由\(\{f_n\}\)的幂的积组成的,由于\(k\)很小,所以我们可以考虑计算每一个\(f\)的指数,然后就可以用快速幂来计算这些东西。

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