洛谷5419 [CTSC2016]单调上升路径
Luogu 分析 根据题目里提供的证明，不难得到答案的下界是 $n-1$。下面我们来考虑如何构造出这个下界。 考虑拿出 $n-1$ 组匹配，满足两两无交，这样子每组匹配中的边只会有一条被经过，组内直接赋连续权值即可。 这 $n-1$ 组匹配可以把下面这个图旋转 $n-1$ 次得到 代码 // ==================================== // author:...
分类 题解 下的文章
- 首页
- 题解
洛谷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/ // ===...
CF1172E Nauuo and ODT
Codeforces Luogu 分析 考虑计算每种颜色的贡献，即计算每种颜色包含在多少条路径中。 这个东西似乎还是不好算，可以考虑计算每种颜色不包含在多少条路径中。 我们把这种颜色染成白色，其它颜色染成黑色，那么只有黑色连通块内部的点对才满足条件。 于是我们需要支持修改颜色、求黑色连通块大小平方和，使用 QTREE6 一题的方法把颜色放到父边上，LCT 维护子树信息即可。具体细节可以看一看...
洛谷5326 [ZJOI2019]开关
Luogu LOJ 分析 设 $P=\sum_{i=1}^n p_i$。 设 $F(x)$ 为按到目标状态的指数型概率生成函数，$G(x)$ 为按回自己的指数型概率生成函数。 $F(x)$ 直接把每个开关乘在一起即可，$G(x)$ 相当于是 $s_i=0$ 时的 $F(x)$。那么有 直接计算即可。 代码 // ==================================== //...
洛谷4705 玩游戏
Luogu 分析 答案显然是 直接分治把所有 $1-a_ix$ 卷起来，然后多项式 $\ln$ + 多项式求导即可求出 $G(x)$，再推回 $A(x)$ 后卷积即可。 代码 不想写 vector，于是从鱼那里蒯了一个分治 /kel // ==================================== // author: M_sea // website: https:...
AGC038E Gachapon
AtCoder Luogu 分析 我不喜欢容斥，我不喜欢组合意义，我不喜欢生成函数，我也没有精神 首先 Min-Max 容斥一手 转移直接枚举 $d$ 即可。为了方便我们把容斥系数压到 DP 里去，转移要乘上一个 $-1$。 算答案就把上面这个东西代回去就好了。 代码 // ==================================== // author: M_sea //...
JOISC2018 部分题解
高速道路の建設 / Construction of Highway 这个操作长得很像 LCT 中的 access。 于是我们每次只要 access 一下并把所有颜色段拿出来，然后树状数组求逆序对数，再把对应的边连上并把整条重链的颜色赋值为 $c_v$。 因为 access 是均摊 $\mathcal{O}(\log n)$ 的，所以每次颜色段数也是均摊 $\mathcal{O}(\log n...
AGC035D Add and Remove
AtCoder 分析 可以发现题目中的贡献只有加，按照鸡贼的话来说这是一个很罕见的性质。 倒着看整个过程，相当于每次往里面加一个数。 我们考虑每个数对答案的贡献。假设当前有若干个数，第 $i$ 个数的贡献是 $x_i$，那么我们在 $i,i+1$ 中加一个数，新加的数的贡献显然是 $x_i+x_{i+1}$。 这个 $i,i+1$ 对应原序列中的一段区间，因此可以 DP。设 $dp_{l,r...