洛谷4322 [JSOI2016]最佳团体
LuoguLOJBZOJ分析分数规划问题，考虑二分答案，推一推式子可以得到将 $p_i-mid\times s_i$ 作为价值，树形背包即可。代码// =================================== // author: M_sea // website: http://m-sea-blog.com/ // ==========================...
M_sea 发布的文章
- 首页
- M_sea
洛谷4323 [JSOI2016]独特的树叶
LuoguLOJBZOJ分析先考虑一个 $\mathcal{O}(n^2)$ 的做法。先求出以每个节点为根，整棵树的哈希值。直接 DFS $n$ 次即可。然后，把 $A$ 的这 $n$ 个哈希值存到 map 中，然后枚举 $B$ 的每一个叶子节点，查一下删掉它后的哈希值是否在 map 中即可。这个算法的主要瓶颈在于求哈希值那一部分，考虑用换根 DP 优化这个过程。异或满足可减性，很容易抵消掉...
洛谷5503 [JSOI2016]灯塔
LuoguLOJBZOJ分析这题是 POI2011 的原题，原题做法戳这里。这里讲一下别的做法。首先移一下项得到显然 $\left\lceil\sqrt{|i-j|}\right\rceil$ 仅有至多 $\sqrt{n}$ 种取值，因此枚举它的取值，得到对应的 $j$ 的范围，用 ST 表查询最大值即可。时间复杂度 $\mathcal{O}(n\sqrt{n})$。代码// =======...
洛谷6084 [JSOI2015]isomorphism
LuoguBZOJ分析一道做法显然的题目，然而调了我好久 QAQ先考虑原树同构怎么做。因为是无根树，所以求出重心转为有根树，然后树哈希即可。这样子我们只需要比较重心的哈希值即可判断原树是否同构。需要注意的是无根树可能有两个重心，需要都记下来。把上面的做法扩展到简化树同构，只需要在求树的重心时把度数为 $2$ 的点不算入 $sz$ 中，然后用一些特殊的树哈希方式使得只有一个儿子时哈希值和儿子相...
洛谷6096 [JSOI2015]地铁线路
LuoguBZOJ分析首先输入的是字符串很不好，用 std::map 转成数。第一问很简单。对于每条线路新建一个点，线路上的车站向这个点连边权为 $1$ 的边，这个点向线路上的车站连边权为 $0$ 的边。求出 $s$ 到 $t$ 的最短路即为答案。第二问比较毒瘤。设 $mx_i$ 表示到达 $i$ 车站花费最少的最多乘坐时间。显然这个东西应该放在最短路图上去转移。我们把所有线路按 $dis$...
洛谷6095 [JSOI2015]串分割
LuoguBZOJ分析首先倍长字符串并跑一遍后缀排序，求出 $sa_i$ 和 $rnk_i$。先考虑一个弱化版：$k|n$ 时的情况。枚举第一个串的起始位置 $i\in[1,n/k]$，于是我们可以得到剩下所有串的起始位置 $i+n/k,i+2n/k,\cdots$。我们现在要求出该方案下最大的串，直接求出最大的 $rnk$ 即可。然后最后答案就是所有方案取个 $\min$。现在考虑一般情况...
洛谷6087 [JSOI2015]送礼物
LuoguBZOJ分析首先求一遍区间长度为 $L$ 时的最大值，枚举左端点并用 ST 表求极值即可。然后求区间长度在 $[L+1,R]$ 内时的最大值。显然最大值和最小值一定会在区间的左右端点处。注意到要最大化的式子是一个分数，根据分数规划那一套，考虑二分答案，则令 $w_i=a_i+mid\times i$，不难使用单调队列求出。代码// ========================...
洛谷6076 [JSOI2015]染色问题
LuoguBZOJ分析考虑容斥。设 $f(i,j,k)$ 为至少 $i$ 行、$j$ 列不涂色且至少有 $k$ 种颜色没有使用的方案数，根据组合意义可以得到直接 $\mathcal{O}(n^3)$ 计算即可。代码// =================================== // author: M_sea // website: http://m-sea-blog...
洛谷5502 [JSOI2015]最大公约数
LuoguBZOJ分析有一个结论：对于每个 $r$，不同的 $\gcd(a_l,a_{l+1},\cdots,a_r)$ 的数量是 $\log$ 级别的。证明：每次 $\gcd$ 发生变化时至少除以 $2$。于是我们枚举右端点，并开一个 vector 维护一下所有 $\gcd$ 发生变化的位置，更新答案就直接枚举 vector 内的每个元素即可。代码// =================...
BZOJ4484 [Jsoi2015]最小表示
BZOJ分析如果删去 $(u,v)$ 后仍存在从 $u$ 到 $v$ 的一条路径，则 $(u,v)$ 可以删去。扩展一下：如果存在一个点 $x$ 满足 $x\neq u,x\neq v$，且原图上存在从 $u$ 到 $x$ 的一条路径和从 $x$ 到 $v$ 的一条路径，则 $(u,v)$ 可以删去。于是我们对于每个点，求出它能到达的点和能到达它的点并存到 bitset 里，然后判断每条边能...