Codeforces 1239A:Ivan the Fool and the Probability Theory 题解

主要思路

首先需要知道一个性质:如果第一行和第一列确定,那么这个方案就已经完全确定了。这个可以用归纳法证明:

证明  如果格子\((i – 1, j)\)、\((i, j – 1)\)和\((i – 1, j – 1)\)的颜色确定,那么显然\((i, j)\)的颜色就能被唯一确定。如果第一行和第一列可以被确定,那么根据上述描述,便可生成一个唯一的方案。

所以欲记录方案的个数,那么就要记录合法的第一行和第一列的方案数。这样我们把问题转换到了长条上。

设置\(dp[i][0/1][0/1]\)为到第\(i\)位是否连续、最后一位填的数字。那么转移非常自然,可以自行推导(确实啊)。

最后答案就是把所有情况加起来,再减去非法的两种情况(也就是左上角的三格同色的情况)。

继续阅读Codeforces 1239A:Ivan the Fool and the Probability Theory 题解

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