四糸智乃

题解

算法(12)

/ 注册

全部文章 / 题解（共2篇）

2019CEOI D1T2 Dynamic Diameter

题目大意：给一颗无根带边权树。支持两种操作： 1、修改某条边的边权。 2、查询当前直径。点分树模板题，全局开一个multiset维护直径，对于每个重心开一颗线段树和一个局部multiset，用欧拉序线段树维护每一个子树中的最值，然后将其放入局部multiset。接下来取局部mul...

线段树点分树树分治树的直径 stl

2019-07-28

0 1122

HDUBeauty Of Unimodal Sequence

同NOIP2004合唱队形，原题DP部分可以直接贴。题意：求一个最长严格先上升后下降子序列，有两问，输出字典序最小解和字典序最大解。从后往前DP，使用线段树维护，过程中使用后继数组记录转移过程。然后顺着模拟一遍取出来就行了。思路很简单。 #include<bits/stdc+...

线段树序列型DP 动态规划最长上升子序列

2019-07-24

0 781