洛谷2519 [HAOI2011]Problem A
Luogu分析每个人的话相当于 $[a_i+1,n-b_i]$ 中的人排名相同。那么如果两个人的话不同且对应的区间无交，他们就可能都说了真话。把相同的区间缩在一起，问题变成每个区间有一个权值，选出若干个无交的区间使得权值和最大。这个可以直接 DP，把所有区间按右端点排序后，二分找到最后的左端点小于当前右端点的位置，然后转移即可。注意把 $a_i+1>n-b_i$ 的人掉，这些人一定说了...
M_sea 发布的文章
- 首页
- M_sea
洛谷4351 [CERC2015]Frightful Formula
LuoguGym分析先考虑 $c=0$ 的情况。我们计算每个 $l_i$ 和 $t_i$ 对 $(n,n)$ 的贡献。只考虑 $l_i$，那么相当于从 $(i,1)$ 走到 $(n,n)$，第一步必须往右，往右走一步乘 $a$，往下走一步乘 $b$，求所有路径的权值和。这个东西显然等于可以发现，当 $i+j\leq n-2$ 时，贡献就是 $c(a+b)^{i+j}$；当 $i+j>n...
洛谷6920 [ICPC2016 WF]Clock Breaking
LuoguGym分析竟然一遍 A 了，写篇题解纪念一下。如果一个灯管一直都是 X 或者一直都是 .，那它就有可能恒亮或恒灭。枚举起始时间，那么如果一个不可能恒亮或恒灭的灯管没有正常发光，那么这个起始时间就不合法。如果对于某个起始时间，某个灯管都正常发光，那它就有可能是正常工作的。如果一个灯管的可能性超过 $2$ 种，那么就输出 ?，否则输出对应的东西即可。难点主要在于码，但是想清楚了也不是很...
洛谷4747 [CERC2017]Intrinsic Interval
LuoguGym分析析合树模板题。如果两个点在析合树上的 LCA 是析点，那么答案就是这个析点对应的段；否则还要找到两个点所在的两棵子树，LCA 的儿子序列中这两个子树间的子序列才是答案。代码// ==================================== // author: M_sea // website: https://m-sea-blog.com/ // =...
洛谷5419 [CTSC2016]单调上升路径
Luogu分析根据题目里提供的证明，不难得到答案的下界是 $n-1$。下面我们来考虑如何构造出这个下界。考虑拿出 $n-1$ 组匹配，满足两两无交，这样子每组匹配中的边只会有一条被经过，组内直接赋连续权值即可。这 $n-1$ 组匹配可以把下面这个图旋转 $n-1$ 次得到代码// ==================================== // author: M_sea ...
洛谷5607 [Ynoi2013]无力回天NOI2017
Luogu分析没想到差分 /ll根据要求的东西，不难想到线性基。现在既然有一个区间询问，而且线性基还很好合并，那么可以想到在外面套一层线段树。问题是区间修改时一个线性基如何整体异或一个值。考虑差分，变成单点修改，直接把叶节点线性基清空然后 pushup 上去即可。可以证明 $a_{l..r}$ 的线性基和 $a_l\cup(a_i-a_{i-1})_{l+1..r}$ 的线性基是相同的，所以...
洛谷5296 [北京省选集训2019]生成树计数
Luogu分析根据二项式定理有所以我们只要把边权设成 $e^{a_ix}$，然后直接矩阵树定理即可。因为数据范围很小，所以多项式乘法和求逆可以直接暴力，NTT 甚至会慢。代码// ==================================== // author: M_sea // website: https://m-sea-blog.com/ // ==========...