洛谷3704 [SDOI2017]数字表格
Luogu LOJ 分析 下面都假设 $n\leq m$。 方法一 推出来和上面是一样的。 代码 // ==================================== // author: M_sea // website: https://m-sea-blog.com/ // ==================================== #include &...
博主已经退役，评论可能会审核很久才能通过。
博主已经退役，评论可能会审核很久才能通过。
Luogu LOJ 分析 下面都假设 $n\leq m$。 方法一 推出来和上面是一样的。 代码 // ==================================== // author: M_sea // website: https://m-sea-blog.com/ // ==================================== #include &...
Luogu LOJ 分析 首先要会最小圆覆盖而且知道它是期望 $\mathcal{O}(n)$ 的。 显然可以二分答案，于是我们只要想办法判定能否分成最小圆覆盖半径都 $\leq mid$ 的 $\leq m$ 段即可。 显然最小圆覆盖半径是随着点的增多而不降的，所以每段的点越多越好。于是可以想到暴力找每段的右端点，然而可以卡成 $\mathcal{O}(n^2)$。还有一个想法是二分右端点...
Luogu LOJ 分析 显然一块画布上出现次数为 $S$ 的颜色不超过 $L=\min\left\{m,\left\lfloor\frac{n}{S}\right\rfloor\right\}$ 种。 考虑容斥。设 $f_i$ 为出现次数为 $S$ 的颜色有至少 $i$ 种的方案数，不难得到 可以发现是一个差卷积的形式，于是直接 NTT 即可。 代码 // ===============...
Luogu 分析 设 $g_n$ 为 $n$ 的答案，则 我们只需要求 $[x^n]G(x)$，即 $\frac{(1+\sqrt{2})^n-(1-\sqrt{2})^n}{2\sqrt{2}}$，而 $2$ 在模 $10^9+7$ 意义下是有二次剩余的，所以直接计算即可。 代码 // ==================================== // author: M...
Codeforces Luogu 分析 设 $s_i$ 表示 $i$ 是否在集合中，$f_i$ 表示权值和为 $i$ 的二叉树数量，那么 多项式开根+多项式求逆即可。 代码 // ==================================== // author: M_sea // website: https://m-sea-blog.com/ // =========...
Luogu 分析 设 $f_i$ 为 $i$ 个点的无向连通图个数，$g_i$ 为 $i$ 个点的无向图个数，那么显然有 多项式求逆后卷起来求出 $[x^{n-1}]F(x)$ 从而求出 $f_n$ 即可。 代码 // ==================================== // author: M_sea // website: https://m-sea-bl...
Luogu LOJ 分析 下面的 $n,m$ 和题面上是反的（因为我写完才发现这个问题所以就懒得改了）。 先复原一下样例一（$s=5,nm=60,n+m=16$）的游戏过程中双方的心理活动。 Bob：$(n,m)$ 的可能情况有 $(5,11),(6,10),(7,9),(8,8)$，所以回答不知道。 Alice：$(n,m)$ 的可能情况有 $(5,12),(6,10)$，两种情况 Bo...
Luogu LOJ 分析 考虑二分答案，则我们需要判定是否存在混合图欧拉回路。 首先混合图不连通的话一定不存在。 然后给无向边任意定向，算出每个点的度数，如果有点度数为奇数则不存在。 那么对于一条无向边，假设我们定向 $u\to v$，则我们可以改变它的方向使得 $in_u-out_u$ 增加 $2$、$in_v-out_v$ 减少 $2$。 因此可以考虑网络流。对于 $in_ out_i$...
LOJ 分析 考虑反着看整个过程，那么相当于每个点有 $y_i$ 只老鼠和 $x_i$ 个洞，所有老鼠都必须进洞。 $u,v$ 匹配的代价是 $dep_u+dep_v-2dep_{\operatorname{LCA}(u,v)}$。因此我们开两个堆维护子树中老鼠和洞的 $dep$，每次把儿子的堆合并，然后取堆顶匹配，再把反悔操作加入堆中即可。 然而这样并不能保证所有老鼠都进洞，所以我们把老鼠...
UOJ 分析 这个东西相当于洞有容量上限和额外代价，因此可以考虑模拟费用流。 我们维护两个堆，分别代表洞和老鼠，然后从左往右扫 如果当前是老鼠，取出一个代价最小的洞，代价即为 $x+cost$；后面有可能反悔，即让右边的一个洞匹配这只老鼠，所以要向老鼠堆中加入 $-(x+cost)-x$。 如果当前是洞，取出一只代价最小的老鼠，代价即为 $y+cost+w$；后面有可能反悔，即让右边的一只...