洛谷4039 [AHOI2014/JSOI2014]拼图
Luogu 分析 看到这个 $n\times m\leq 10^5$，可以考虑根号分治。 $n\leq m$ 首先枚举上下边界 $u,d$。 那么所有拼图可以分为两类：第 $u$ 行到第 $d$ 行均为白色的、第 $u$ 行到第 $v$ 行不均为白色的。 最后的拼法会是所有第一类拼图放在中间，然后左右各接上一个第二类拼图。 于是我们算一下第一类拼图的宽度之和，以及第二类拼图左右最多多少列...
分类 题解 下的文章
- 首页
- 题解
洛谷3980 [NOI2008]志愿者招募
Luogu 分析 这是一个线性规划做法。下面举的栗子为样例。 设 $X_i$ 为第 $i$ 类志愿者的招募数，$P_i$ 为第 $i$ 天招募志愿者的数量，那么可以列出一些不等式 注意到每个变量恰出现 $2$ 次且系数一正一负。 我们可以把每个等式看做一个点，正数代表流出，负数代表流入，那么等式相当于流量平衡。 因此我们得到了这样的建图方法： 如果 $P_i-P_{i-1}>0$，...
洛谷4228 榕树之心
Luogu LOJ 分析 我们先考虑怎么算根节点的答案。 先假设它只有两棵子树 $u$ 和 $v$，榕树之心在根节点处。 如果 $u$ 长出一个节点，$v$ 长出一个节点，那么榕树之心还在根节点处，相当于这两次操作抵消掉了。 那么我们只需要判断根节点的所有子树能否相互抵消掉。 注意每棵子树是可以自行抵消一部分的，因此可以设 $f_u$ 表示 $u$ 子树内最多可以自行抵消多少对。 考虑 $f...
洛谷3687 [ZJOI2017]仙人掌
Luogu LOJ 分析 首先特判原图不是仙人掌的情况，直接输出 $0$ 即可。 显然连边不会跨过一个环，因此可以直接断掉所有环边，则原图变为一个森林，方案数即为每棵树的方案数之积。 考虑如何计算一棵树的方案数。 我们假装一个边也是一条链，那么就相当于求用若干条不相交的链覆盖树上所有边的方案数。 考虑 DP。设 $dp_u$ 为 $u$ 子树中所有边加上父边被覆盖的方案数，$g_n$ 为一个...
洛谷4609 [FJOI2016]建筑师
Luogu LOJ 分析 显然左边看到的是前缀 $\max$，右边看到的是后缀 $\max$，而最大值前后都能看到。 除去最大的，剩下的 $n-1$ 个数需要划分成 $A+B-2$ 个圆排列（圆排列的原因是因为我们需要钦定最大的放在某个端点）；然后这 $A+B-2$ 个前后缀 $\max$ 中需要选出 $A-1$ 个放在左边。 于是答案为 代码 // ===================...
LOJ6119 「2017 山东二轮集训 Day7」国王
LOJ 分析 考虑一个区间怎样才是满足条件的。 设 $A_{l,r}$ 为端点都在 $[l,r]$ 内的 exciting 的路径数，$B_{l,r}$ 为端点都不在 $[l,r]$ 内的 exciting 的路径数。则 $[l,r]$ 满足条件即 $A>B$。 现在我们要比大小，根据文化课那一套理论可以想到作差。设 $C_{l,r}$ 为一个端点在 $[l,r]$ 内、一个端点不在 ...
CF749E Inversions After Shuffle
Codeforces Luogu 分析 考虑一个点对 $(i,j)\;(i<j)$ 的贡献。 分两种情况考虑：$i,j$ 都在连续段内、$i,j$ 不都在连续段内。 先考虑第一种情况。显然连续段的左端点 $\in[1,i]$，右端点 $\in[j,n]$，于是随机出的连续段包含 $i,j$ 的概率为 那么对于每个 $i$，我们只要知道满足 $j>i,a_j<a_i$ 的...
CF903G Yet Another Maxflow Problem
Codeforces Luogu 分析 容易发现，至多只会割掉一条 A 边和一条 B 边。我们加边 $(A_0,A_1,0)$ 和 $(B_n,B_{n+1},0)$，然后求 $A_0$ 到 $B_{n+1}$ 的最大流，就可以转化成恰好割掉一条 A 边和一条 B 边的情况了。 设割掉了 $A_i\to A_{i+1}$ 和 $B_j\to B_{j+1}$，则此时的最大流为 显然对于每个...
CF901C Bipartite Segments
Codeforces Luogu 分析 「图中没有偶环」等价于「图是仙人掌」。因此本题中「一个诱导子图是二分图」等价于「一个诱导子图没有环」。 考虑求出一个 $nxt_i$ 表示以 $i$ 为左端点的最大右端点。我们找到所有的环，假设某个环上点编号的最小值为 $mn$，最大值为 $mx$，那么 $[1,mn]$ 中的所有点的 $nxt$ 都不会 $\geq mx$，即用 $mx-1$ 对 $...
AGC005F Many Easy Problems
AtCoder Luogu 分析 设要求的东西是 $f_i$，考虑怎么求这个东西。 可以想到计算每个点在多少种方案中，进而想到计算每个点不在多少种方案中。于是容易得到包含 $u$ 的方案数为 可以发现后面已经是卷积的形式了，于是直接 NTT 即可。虽然这个模数很奇怪，但是它确实是 NTT 模数。 代码 // =================================== // ...