「杂题集」- 2019年10月1日

方程式

这个搜索好骚啊。

首先直接枚举 20 个数来搞初始根。假设我们拿到了\(s\)个根,那么我们还剩下\(n – s\)个,肯定是重根。所以我们考虑直接搜索剩下的\(n – s\)到底是哪个重根。这个复杂度就是\(\Theta(s^{n – s})\)。至于我们怎么验证解的正确性,就是这道题的精髓了:考虑把这组解写成零点式:

\[ \prod_{i = 1}^n (x – a_i) = 0 \]

我们做一个小的多项式乘法展开这个积式,然后与原式的系数进行对比即可。

继续阅读「杂题集」- 2019年10月1日

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

「2018泉州国庆集训#2」 – 解题报告

A – 奇妙的棋盘

一定要思考,不能想当然。这句话是说给我听的。

把连通块连边,每一次 BFS 扩展就算做一次点击,然后\(O(n^2)\)确定路径长度,再按奇偶性判断就行了。

继续阅读「2018泉州国庆集训#2」 – 解题报告