AtCoder Grand Contest 002E – Leftmost Ball 题解

主要思路

我们发现只需要保证在任何时候\(0\)的个数都大于等于颜色的数量。直接考虑一个一个塞球,不仅要考虑同质问题,还要考虑具体的颜色排列非常麻烦,不如我们一次性把所有的球都在序列上放好:设置\(dp[i][j]\)为\(i\)个\(0\)、\(j\)种颜色的局面,我们可以这样转移:

\[ dp[i][j] = dp[i – 1][j] + {n – i + (n – j + 1) \times (k – 2) – 1 \choose k – 2 } dp[i][j – 1] (n – j + 1) \]

解释一下:我们固定住该颜色的球的位置为最左能放置的点,然后乘上\(n – j + 1\)进行染色,并给剩余的\(k-2\)个球选位置。

继续阅读AtCoder Grand Contest 002E – Leftmost Ball 题解

AtCoder Grand Contest 001E – BBQ Hard 题解

主要思路

也是比较巧妙的一个转换思想。

我们考虑列式:

\[ \sum_{i = 1}^n \sum_{j = i + 1}^n {a_i + b_i + a_j + b_j \choose a_i + b_i} \]

直接去算或者是按贡献计算都不行,我们考虑转换成这样:

\[ \frac{ \sum_{i = 1}^n \sum_{j = 1}^n {a_i + b_i + a_j + b_j \choose a_i + b_i} – \sum_{i = 1}^n {2(a_i + b_i) \choose a_i + b_i} }{2} \]

前面那个部分我们可以把点\((-a_i, -b_i)\)放在平面上,然后算一个路径计数的 DP 即可(因为平面大小比较小)。前半部分就是所有第三象限的点走到\((x_i, y_i)\)的路径总数,后半部分直接暴力算即可。

继续阅读AtCoder Grand Contest 001E – BBQ Hard 题解

Codeforces 981H: K Paths 题解

主要思路

首先仔细剖析出题目意思:我们要规定一个路径,要被经过\(k\),然后再到路径的两头延伸出不大于 \(k\) 的分支,且每个分支独占一颗子树,求方案数。

那么我们可以先把 \(1\) 定为根,然后算出以点 \(u\) 为端点、分支在子树内的方案数 \(f_u\),然后再算向父亲侧的方案数 \(g_u\),再枚举 \((u, v)\):

继续阅读Codeforces 981H: K Paths 题解

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日