洛谷3779 [SDOI2017]龙与地下城
Luogu LOJ 分析 一种 FFT 做法 考虑 DP 。设 $dp_{i,j}$ 表示前 $i$ 个骰子和为 $j$ 的概率。 可以发现转移是一个多项式快速幂，于是直接 FFT 就可以了。 （大概）可以理解成概率生成函数卷积？ 然而 FFT 掉精度很严重，我只能过 $60$ 分。所以对于大数据要考虑其它做法。 一种定积分做法 首先要知道中心极限定理的一个推论： 设有 $n$ 个独立同分...
博主已经退役，评论可能会审核很久才能通过。
博主已经退役，评论可能会审核很久才能通过。
Luogu LOJ 分析 一种 FFT 做法 考虑 DP 。设 $dp_{i,j}$ 表示前 $i$ 个骰子和为 $j$ 的概率。 可以发现转移是一个多项式快速幂，于是直接 FFT 就可以了。 （大概）可以理解成概率生成函数卷积？ 然而 FFT 掉精度很严重，我只能过 $60$ 分。所以对于大数据要考虑其它做法。 一种定积分做法 首先要知道中心极限定理的一个推论： 设有 $n$ 个独立同分...
UVa Luogu 分析 状态和转移都比较奇妙的 DP 。 设 $dp_{i,j,k}$ 表示 $[i,j]$ 区间，后面还有 $k$ 个和 $j$ 颜色相同的方块的最大分数。 转移有两种： 拿掉 $j$ 和后面的 $k$ 块：$dp_{i,j-1,0}+(k+1)^2\to dp_{i,j,k}$ 。 设 $p$ 为 $[i,j)$ 中与 $j$ 颜色相同的块，那么可以拿掉 $[p+1,...
GSS1 线段树上维护以下 $4$ 个东西： 区间和 区间最大前缀和 区间最大后缀和 区间最大子段和 合并两个区间应该比较简单，这里不再赘述。 GSS2 这题就很神仙了。 把所有询问离线并按右端点排序，然后从左往右扫。 对于线段树的每个叶子节点 $[i,i]$，假设当前扫到了 $p$ ，那么该节点存的是 $\displaystyle\sum_{j=i}^pa_j$ 。 设 $pre_i...
QTREE1 把 $(fa_i,i)$ 的边权作为 $i$ 的点权，然后就是个树剖板子了... 但是注意查询时 LCA 是不能查的，需要判一下。 而且这题竟然不能交 C++ ，然后我改了半个小时才把 C++ 改成 C QAQ QTREE2 DIST 操作只需要维护树上前缀和即可求出答案。 KTH 操作大力讨论一下答案应该在 $u-lca$ 的链上还是 $v-lca$ 的链上，然后倍增上去即...
Luogu 分析 完全图的生成树个数为 $n^{n-2}$ ，每条边会出现 $2n^{n-3}$ 次。 容易得到答案为 考虑怎么计算 $\sum_{i=n+1}^{2n-1}i^k$ 。可以发现 $i^k$ 是完全积性函数，直接线性筛后求前缀和即可。 整理一下思路： 首先线性筛求出 $i^k$ ，然后求出它的前缀和。此部分时间复杂度为 $O(k)$。 然后利用算出的前缀和，递推计算出 ...
Codeforces 分析 首先询问只有一个的时候很简单，差不多就是 NOIP2018D1T3 ，直接贪心即可。 考虑根号分治： 对于链长 $\leq B$ 的询问，直接暴力求。时间复杂度 $O(nB)$ 。 对于链长 $>B$ 的询问，可以发现答案只有至多 $\frac{n}{B}$ 种，直接二分出相同的段即可。时间复杂度 $O(n\frac{n}{B}\log n)$ 。 可以...
Luogu LOJ 分析 首先你需要看懂这篇题解。 设 $f_{i,j}$ 表示长度为 $i$ 时出现 $j$ 结束的概率，$g_i$ 表示长度为 $i$ 时没有结束的概率。 设 $f_{i,j}$ 的概率生成函数为 $F_i(x)$ ，$g_i$ 的概率生成函数为 $G(x)$ 。 设 $a_{i,j,k}$ 表示 $s_{i}[1..k]$ 是否等于 $s_j[m-k+1..m]$ 。 ...
Luogu LOJ 分析 首先题目要求的其实就是方案数。 设 $cnt_i$ 表示颜色为 $i$ 的珍珠的数量，那么如果一组方案合法的话会有 显然也是一个卷积的形式。 于是只需要构造多项式求出 $f_i$ ，再构造多项式求出 $g_i$ ，再求答案即可。 另外注意特判 $2m<n-D$ 和 $2m>n$ 的情况，答案分别为 $D^n$ 和 $0$ 。 总结：这是一道好题，可是...
Luogu 分析 以下统一规定 $n$ 为字符集大小，$m$ 为名字长度。 设 $f_i$ 表示长度为 $i$ 时结束的概率，$g_i$ 表示长度为 $i$ 时没有结束的概率。 设 $f_i$ 的概率生成函数为 $F(x)$ ，$g_i$ 的概率生成函数为 $G(x)$ 。 根据 YMD 的论文可以知道我们要求的就是 $F'(1)$ 。 分析一下可以列出这样一个式子 用 KMP / has...
Codeforces 分析 首先可以发现，不到最后是不会选择猜的。 假设你问了一张牌，对手没有，那么对手就会怀疑这张牌是桌上那张。 考虑这样一种神奇的操作：询问一张自己手上有的牌。这样子对手就会怀疑这张牌是桌上的，然后如果他问了他就输了。我们把这种操作称为欺骗。 考虑 DP 。设 $f_{n,m}$ 表示先手有 $n$ 张牌、后手有 $m$ 张牌时，先手的获胜概率。 我们列一个表格，表示在先...