洛谷4173 残缺的字符串
Luogu 分析 令 * 为 $0$ ，a 为 $1$ ，以此类推；定义 $dis(A,B)=\sum\limits_{i=0}^{n-1}(A_i-B_i)^2A_iB_i$ 。 显然，当且仅当 $dis(A,B)=0$ 时，$A=B$ 。 将 $dis(A, B)$ 展开得到 将 $A$ 翻转后 FFT 即可。 代码 //It is made by M_sea #include <...
分类 题解 下的文章
- 首页
- 题解
洛谷3288 [SCOI2014]方伯伯运椰子
Luogu 分析 显然调整后总交通量不变是最佳的，因为不能减少，并且增加的话费用一定会变大。 发现压缩操作很像网络流中的退流，扩充操作很像网络流中的增广。 所以对于原图中的每条边 $(u,v,a,b,c,d)$ ，新建两条边： $v\to u$ ，边权为 $a-d$ （如果 $c=0$ ，不要建这条边）。对应压缩。 $u\to v$ ，边权为 $b+d$ 。对应扩充。 发现在这张图跑，经...
洛谷4449 于神之怒加强版
Luogu 分析 设 $\mathbf{f}(i)=i^k$，$\mathbf{g}(i)=\mathbf{f}*\mu$ 。 线性筛 $\mathbf{g}$ 的前缀和，然后数论分块计算即可。 代码 //It is made by M_sea #include <algorithm> #include <iostream> #include <cstdlib...
洛谷4546 [THUWC2017]在美妙的数学王国中畅游
Luogu LOJ 分析 LCT + 泰勒展开。 取 $x_0=0.5$ ，然后泰勒展开，发现后面的项的贡献很小，可以只保留 $13$ 项。 $\mathrm{LCT}$ 的每个节点维护该点函数的 $n$ 阶导数与子树的 $n$ 阶导数和，这样子查询就可以直接拿出来算。 至于 $n$ 阶导数怎么算... $sin'(x)=cos(x),\ cos'(x)=-sin(x)$ $(e^x)'=...
洛谷5268 [SNOI2017]一个简单的询问
Luogu LOJ 分析 这样子就可以把每个询问拆成四个，然后莫队即可。 代码 //It is made by M_sea #include <algorithm> #include <iostream> #include <cstdlib> #include <cstring> #include <cstdio> #includ...
洛谷4065 [JXOI2017]颜色
Luogu 分析 首先发现，两个不同的连续区间对应两个不同的删除方案。 那么就可以统计合法区间的数量。 枚举右端点 $r$ ，考虑左端点 $l$ 怎么样才合法。 设颜色 $k$ 最右边的出现位置为 $max[k]$ ，最左边的出现位置为 $min[k]$ 。 显然所有 $max[k]$大于 $r$ 的颜色都会被删去，所以有在 $(l,r)$ 中不存在一定会被删去的颜色。 也就是要找到一个 $...
CF961G Partitions
CodeForces 分析 可以发现每种权值的贡献是一样的，我们只要求出这个系数就好了。 注意到贡献的式子里有一个 $|S|$ 。我们可以认为集合中的每个元素对答案都有一次贡献。 于是枚举每一对数的贡献即可。 $i$ 对自身的贡献显然为 $S_n^k$ 。 当 $j\neq i$ 时，贡献为 $S_{n-1}^k$ 。 于是总的系数就是 $S_n^k+(n-1)\times S_{n-1}^...
CF802C Heidi and Library (hard)
CodeForces 分析 首先将每天拆成两个点，入点 $s_i$ 和出点 $t_i$ 。 考虑怎么建图： 从源点向 $s_i$ 连容量为 $1$ 、费用为 $c_{a_i}$ 的边，表示每本书。 从 $s_i$ 向 $s_{i+1}$ 连容量为 $k-1$ 、费用为 $0$ 的边，表示第 $i$ 天最多留 $k-1$ 本书。 从 $s_i$ 向 $t_i$ 连容量为 $1$ 、费用为 $...
AGC004F Namori
AtCoder 分析 分三种情况讨论。 树 给奇数层的点染成白色，偶数层的点染成黑色。 现在问题变成，每次可以交换两个相邻的不同色的点，要让所有黑点变白、白点变黑。 显然，如果黑点数和白点数不同，则无解；否则设白点的权值为 $1$，黑点的权值为 $-1$，$sum_i$ 表示子树中的权值和，那么答案为 $\sum_{i=1}^n |sum_i|$。 奇环 可以看做树多了一条边。继续沿用上面的...
CF891C Envy
CodeForces 分析 考虑一个性质：对于一个图的所有 MST，每种边权的边的数量都相等。 因此我们把每种边权的边拿出来单独考虑。我们把并查集恢复到加该种边以前的状态，然后判断这些边加进去会不会成环即可。 现在的问题在于怎么把并查集恢复回去。显然可以可持久化并查集，但是有更优美的做法：预处理出每条边在加该种边权的边时两端点所在的连通块即可。 代码 //It is made by M_se...