AtCoder Grand Contest 030F:Permutation and Minimum – 题解

主要思路

主要还是需要注意设计状态。

我们称 \((-1, x)\) 为单对,称 \((-1, -1)\) 为双对。我们可以试着从大到小填数字,这样就可以避免取 \(\min\) 的问题了。考虑 \(dp[i][j][k]\) 为选到第 \(i\) 个数字,然后有 \(j\) 个待处理、\(k\) 个单对待处理。转移的话,可以试着进行讨论。如果这个数字是某个单对之一,那么一种方式是啥都不干,还有一种是尝试进行匹配,\(j -= 1\)。如果不是单对之一,那么要么匹配、要么晾着。

最后乘上一个双对个数的阶乘,使其有序。

继续阅读AtCoder Grand Contest 030F:Permutation and Minimum – 题解

「LibreOJ NOI Round #2」不等关系 – 题解

主要思路

这题好神仙啊。

首先介绍一个暴力的套路(虽然跟正解没关系,但我觉得碰上很多比赛的时候会用上):我们设置 \(f[i][j]\) 当前为前 \(i\) 个数中第 \(j\) 小的贡献,那么有

\[ f[i][j] = \begin{cases} \sum_{k = 1}^{i – 1} f[i – 1][k] (s_{i – 1} = <) \\ \sum_{k = i}^{j} f[i – 1][k] (s_{i – 1} = >) \end{cases} \]

继续阅读「LibreOJ NOI Round #2」不等关系 – 题解

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 题解