P4694 PA 2013 Raper

发表于2077-03-02|更新于2025-03-06

|浏览量:

考虑将每次的决策分为两部分：从左往右的以及从右往左的

额外记录一个 $f_i,g_i$ 表示 $a_i,b_i$ 是否被选择

对于从左往右的，直接线段树上分治即可

对于从右往左的，我们考虑记录一个 $h_i$ 表示 $i+1$ 到 $i$ 的反向边的流量

考虑记录区间前缀的最大联通 $b_i$ ，区间后缀的最大联通 $a_i$ ，区间内最大的从右到左段的大小，区间从右往左方案中的最大值

因为区间内 $h_i$ 非负，所以只需要记录区间内 $Min$ 为 $0$ 以及 $Min$ 非 $0$ 的情况即可

文章作者: my9r

文章链接: http://example.com/2077/03/02/%E9%A2%98%E8%A7%A3/P4694%20PA%202013%20Raper/

版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 mygr main()！

相关推荐

AT_awtf2024_d Almost Bubble Sort 题解

考虑这么证明：将所有点绘制到一个坐标系上，若一个点被选择了，则我们称其为 $1$ 结论：当我们有 $i < j,p_{i} > p_{j}$ 且 $i$ 被选择，则 $j$ 一定被选择我们考虑这么证明：若 $j$ 被选择，则一定能够构造出一种新的方案使得其比当前方案更优使用反证法，不妨设当前是最优答案且答案中存在两位置 $i,j$ 使得 $i<j,p_i>p_j$ 且 $i$ 选 $j$ 不选不妨找到其中使得 $p_j-p_i$ 最小的 $i,j$ ，那么他就会满足 $p_i,p_j$ 中间没有比 $p_i$ 小且被选择的点 $p_i,p_j$ 中间没有比 $p_j$ 大且未被选择的点没有值在 $i，j$ 中间的元素发现这样就将整个平面分割为了九个部分，我们分别将其称为 $$\begin{array}{a|a|a|a}\hline 1 & 2 & 3 \ \hline 4 & 5 & 6 \ \hline 7 & 8 & 9 \ \hline\end{array}$$ 考虑让 $i,j$...

AT_cf17_final_j Tree MST 题解

考虑使用 b 算法解决问题就变成了：对于一个集合 $S$ ，我如何去寻找一个点 $p$ 使得 $$\min_{s \in S}w_{p}+w_{s}+dis_{p,s} \le \min_{s\in S,j\not \in S \wedge j \not = p}w_{s}+w_{j}+dis_{s,j}$$ 我们称每个节点所属的集合为他的颜色考虑启发式合并，对树上每一个点 $u$ 用一个 $set$ 维护子树内每种颜色的点的 $dis_{u,p}+w_{p}$ 的最小值，额外维护所有颜色中的最小值和次小值，启发式合并的同时统计每种颜色的答案即可发现其实不用启发式合并，用类似树形dp的方式上下 dfs 即可

P7486 「Stoi2031」彩虹题解

没啥好说的，暴解 $$\begin{eqnarray} && \prod_{i=l}^{r}\prod_{j=l}^{r} \frac{ij}{gcd(i,j)}^{\frac{ij}{gcd(i,j)}} \ \end{eqnarray}$$ 设 $f(x,y)=\prod_{i=1}^{x}\prod_{j=1}^{y} \frac{ij}{gcd(i,j)}^{\frac{ij}{gcd(i,j)}}$ 那么答案则为 $$\frac{f(r,r)f(l-1,l-1)}{f(l-1,r)f(r,l-1)}$$ $$\begin{eqnarray} f(x,y)&=&\prod_{i=1}^{x}\prod_{j=1}^{y} \frac{ij}{gcd(i,j)}^{\frac{ij}{gcd(i,j)}}\ &=&\prod_{d=1}^{y}\prod_{i=1}^{x}\prod_{j=1}^{y}...

P7907 Ynoi2005 rmscne 题解

很妙的思路转换显然扫描线，一个很自然的想法是用数据结构维护 $f_i$ 表示左端点为 $i$ 时…的答案，然后单点查询，但是我们发现当 $l$ 不同时，其对应的答案其实也是不好维护的考虑这么转换，假设查询区间为 $[l,r]$ ，其内部有一个子区间 $[l’,r’]$ ，那么合法的 $l’$ 一定是 $[l,r]$ 的一段前缀，发现通过这么转化可以成功的将单点查询转化为区间查询这样有什么好处呢？首先我们可以二分得到这个前缀的具体区间，接下来对于这个前缀内的每个 $l’$ 一定能够找到一个对应的 $r’$ 使得其合法，所以说即使对于不同的 $l$ ，只要其被包含在前缀区间内，那么他的答案都是相同的，记其为 $f_i$ ，那么我们最后要求的其实就是 $$\min_{p \in [l_e,r_e]}f_{p}-p+1$$ 然后我们发现当我们对应的 $r \leftarrow r+1$ 时，我们只需要更新 $i \in [las_{a_r},r]$ 的 $f_{i}\leftarrow r$ 即可然后就做完了

数据加载中