LOJ6503 「雅礼集训 2018 Day4」Magic
LOJ 分析 容易想到容斥，计算至少包含 $i$ 个魔术对的序列数 $g_i$。根据二项式反演不难得到 分治求出所有 $f_i$ 的卷积即可得到 $dp_m$。 然而 $dp_{m,i}$ 并不等于 $g_i$，因为我们还可以任意排列不构成魔术对的 $n-i$ 张牌，所以还需要乘上一个 $(n-i)!$。 最后二项式反演一下即可得到答案。记得把答案除掉 $\prod a_i!$。 代码 /...
分类 题解 下的文章
- 首页
- 题解
洛谷3703 [SDOI2017]树点涂色
Luogu LOJ 分析 可以发现每种颜色一定是一条链，则整棵树相当于被剖分成了若干条链。 考虑 LCT 维护，则 1 操作相当于 access(x)，2 操作相当于询问一条路径上的链数，3 操作相当于求子树中到根路径上链数最大的点。 考虑将 2 操作差分，则只需要用一个数据结构维护每个点到根路径的链数，要求支持区间求最大值。 考虑 access(x) 时对每个点到根路径上的链数的影响。对于...
洛谷4768 [NOI2018]归程
Luogu 分析 考虑把边按海拔从大到小排序并建 Kruskal 重构树。 每个询问从 $v$ 往上倍增找到最浅的 $a>p$ 的点 $u$，则子树 $u$ 中的点是可以开车到达的，找一个到 $1$ 的距离最小的点即可。 一遍 Dijkstra（关于 SPFA：它死了）预处理出每个点到 $1$ 的最短路，在重构树上维护子树最值即可。 代码 // ====================...
洛谷5304 [GXOI/GZOI2019]旅行者
Luogu LOJ 做法一 将所有关键点随机分到两组中，然后新建两个点 $s,t$，从 $s$ 向第一组中所有点连 $0$ 边，从第二组中所有点向 $t$ 连 $0$ 边，求 $s$ 到 $t$ 的最短路即可。这样子的正确率大概是 $\frac{1}{4}$，所以我们只要多做几次就可以过了。 代码没有。 做法二 分析 事实上没有必要随机。我们枚举二进制位 $i$，将所有不含这个二进制位的关键...
洛谷2619 [国家集训队]Tree I
Luogu 分析 设 $f(x)$ 为恰好选 $x$ 条白边的答案。容易发现 $f(x)$ 是凹的。 考虑 WQS 二分。二分斜率 $m$，则我们需要最小化截距 $b=f(x)-mx$。 把每条白边的权值减去 $m$ 即可求出 $b$ 的最小值，再根据此时最多选出的白边数调整二分上下界即可。 代码 // ==================================== // au...
洛谷4287 [SHOI2011]双倍回文
Luogu 分析 考虑建 PAM，对每个节点额外求出一个 $trans_u$ 表示长度 $\leq$ 当前节点长度一半的最长回文后缀。 这个直接从 $trans_{fa}$ 往上跳 $fail$ 直到跳到一个能扩展新加的字符且扩展后长度小于新节点一半的节点即可。 那么我们只需要判断 $len_{trans_u}$ 是否为偶数且 $len_u$ 是否等于 $len_{trans_u}$ 即可判...
CF1063F String Journey
Codeforces Luogu 分析 为了方便，把串翻转，条件改为「使 $t_{i-1}$ 是 $t_i$ 的真子串」。 可以发现一个性质，即在一定存在一组最优解使得 $|t_i|=i$，因为某个不满足的串删去多的部分一定不会差。 于是可以考虑一个 DP。设 $dp_i$ 表示最后一个串以 $i$ 结尾时最多能选出多少个串。 然而这个似乎没法转移。冷静分析一下可以发现一定有 $dp_{i-...
CF639E Bear and Paradox
Codeforces Luogu 分析 首先考虑怎么放最优。考虑邻项交换法 于是按照 $\frac{a_i}{t_i}$ 从大到小排序即可。 一个想法是二分答案，check 时按 $a_i$ 排序然后看 $a_i\left(1-\frac{cx}{T}\right)$ 是否满足条件。但很容易发现这个是假的，因为 $\frac{a_i}{t_i}$ 相同的题目无法确定顺序，从而无法确定完成时...
洛谷5470 [NOI2019]序列
Luogu LOJ 分析 至少有 $L$ 个下标相同 $\Longleftrightarrow$ 至多有 $K-L$ 个下标不同。 考虑一个费用流模型，即从源点向 $a$ 中所有点连容量为 $1$、费用为 $a_i$ 的边，从 $b$ 中所有点向汇点连容量为 $1$、费用为 $b_i$ 的边，从 $a_i$ 向 $b_i$ 连容量为 $1$、费用为 $0$ 的边，再新建两个点 $C,D$，从...
CF603E Pastoral Oddities
Codeforces Luogu 分析 首先有一个结论：一个大小为偶数的连通块一定存在一个合法的边集，一个大小为奇数的连通块一定不存在一个合法的边集。 证明： 如果连通块大小为奇数，又因为每个点度数都为奇数，所以总度数为奇数，这是不可能的。 如果连通块大小为偶数，此时我们可以先找到一棵生成树，从下往上构造即可。可以发现一定能构造出解。 于是我们只需要保证图中没有大小为奇数的连通块即可。 ...