GoPoux4

未归档

题解(2)

/ 注册

全部文章 / 未归档（共9篇）

题解「CF1000G Two-Paths」

考试做到了类似的一道题 LOJ#6699，题解是换根DP。但是我不会换根，所以用倍增过了这道题qwq。题意给定一棵树，有点权和边权。询问从 \(u\) 到 \(v\)，每条边最多经过两次（即往返两次），经过的点权减边权（点权只算一次）的最大值。题解先考虑从点 \(u\) 开始，进...

树上问题题解动态规划

2020-08-01

0 422

题解「Luogu6189 [NOI Online #1 入门组]跑步」

整数拆分问题。首先有一个dp的方法：设 \(f_{i,j}\) 表示用小于等于 \(i\) 的正整数组合成 \(j\) 的方案数，则有转移： \[f_{i,j}=f_{i-1,j}+f_{i,j-i} \] 前一项相当于不用 \(i\) 组成 \(j\) ，后一项表示使用了 ...

根号分治动态规划题解

2020-09-01

0 484

题解「AT4995 [AGC034E] Complete Compress」

转载注明来源：https://www.cnblogs.com/syc233/p/13603919.html 注意到数据范围很小，所以我们可以枚举一个根，尽量让所有点移动到这个点上。将两颗距离至少为 \(2\) 的棋子向中间移动一步，可能会出现两种情况：它们的LCA为它们共同的祖先...

题解动态规划

2020-09-02

0 450

题解「Luogu4228 [清华集训2017] 榕树之心」

转载注明来源：https://www.cnblogs.com/syc233/p/13606704.html 题意给一棵树和一个动点，最初树只有根结点，动点在根节点。每次在已有的结点处向外扩展出一个结点，并且动点沿着新结点到动点的最短路径移动一步。必须保证在任意时刻，树的点集和边集是原树点集...

题解动态规划

2020-09-03

0 412

题解「AT1983 [AGC001E] BBQ Hard」

转载注明来源：https://www.cnblogs.com/syc233/p/13627377.html 这题的模型转化挺巧妙的，不过也都是套路。套路：从棋盘的 \((0,0)\) 走到 \((n,m)\) ，每步只能向上或向右走的方案数为 \({n+m \choose n}\) 。...

题解动态规划

2020-09-07

0 397

题解「AT1226 電圧」

转载注明来源：https://www.cnblogs.com/syc233/p/13647723.html 题意给定\(n\) 个点 \(m\) 条边的无向图，现在要对每个点黑白染色。若能够使一条边连接的两点颜色相同，其他边连接的两点颜色不同，则这条边合法。求合法的边数。 \(2...

题解树上问题动态规划

2020-09-10

0 420

总结「斯坦纳树」

转载注明来源：https://www.cnblogs.com/syc233/p/13650130.html 姑且当作状压DP的复习了。斯坦纳树问题是组合优化问题，与最小生成树相似，是最短网络的一种。最小生成树是在给定的点集和边中寻求最短网络使所有点连通。而最小斯坦纳树允许在给定点...

总结图论动态规划

2020-09-11

0 472

题解「Luogu5665 划分」

转载注明来源：https://www.cnblogs.com/syc233/p/13663639.html 丧心病狂卡时空题题意给你一个长为 \(n\) 的数列 \(\{a_n\}\) ，需要找到若干个分界点 \(1 \leq k_1 <k_2 <k_3<\cdo...

单调队列题解动态规划

2020-09-13

0 348

题解「Luogu3970 [TJOI2014]上升子序列」

转载注明来源：https://www.cnblogs.com/syc233/p/13693730.html 先不考虑序列长度至少为 \(2\) 的限制和去重，那么这道题就是一个简单的DP：令 \(f_i\) 表示以 \(a_i\) 结尾的上升子序列个数，那么很容易写出转移方程： \...

树状数组题解动态规划

2020-09-18

0 395