BZOJ3162:独钓寒江雪 – 题解

主要思路

刚看这题我人都是懵的…仔细看了看能大概想到,定一个根然后做 DP 得到方案,然后对于相同形态的子树进行方案分配即可。(但是不会写)

具体而言,转换成有根树的方法就是用重心来做根(如果有两个重心的话,就加一个虚根),并且每次 DFS 完之后用 Hash 值排序,然后进行分组转移。

转移的时候,可以给每一种情况进行标号,然后用前缀的组合意义来做转移即可。具体:\( dp[i] = \sum_{uniqueType \in subtree} {dp[uniqueType] + |subtree| – 1 \choose |subtree|} \)。

如果加了虚点,那就判一下就好了。

继续阅读BZOJ3162:独钓寒江雪 – 题解

雅礼集训 2018 Jan 2nd – 解题报告

A – 串

如果本身就不是回文串,那么答案就是 \(1\);如果本身是的话,考虑找一个分割点使得左右都不是,那么答案就是 \(2\);如果还是没找到,那么就是无解了,因为最后串要么就是个单纯串或者是个删完一次之后变成单纯串的东西。

继续阅读雅礼集训 2018 Jan 2nd – 解题报告

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