发表于 更新于 分类于
  • 题目思路：先搞一个最小生成树，把用到的边做一个标记，然后跑一遍LCA预处理，但是要倍增维护一个最大值和一个次大值。弄完后枚举MST没用到的边，求出两个值——一个是一点到这两点LCA的边权最大值，另一个是另一个点到LCA的边权最大值。然后比较一下取min。
阅读全文 »

发表于 更新于 分类于
  • 题目思路：根据数据范围，我们可以爆搜枚举每一种情况，然后到达边界时dp一下。dp其实是一个变式01背包，以它们之累加和为容量跑一遍，更新答案。
阅读全文 »

发表于 更新于 分类于
  • 题目思路：链式前向星存图，跑一遍LCA的预处理，判断一下深度为二的有几个点，和军队的总数比较一下来判断能否控制。然后二分答案，check函数先把每个军队往上提，看能否到根节点，如果不能，则把最近能到达的点标记一下，如果能到根节点，那就记一下记录根节点最近能到的一个点并记录，然后在把能到的点按边权排个序，把不能到的点按边权排个序，判断一下最优解是否能超过不能到达的点。
阅读全文 »

发表于 更新于 分类于
  • 题目链接：SCOI2010_序列操作
  • 写在前面的话：这道题真毒！！！
  • 题目标签：线段树
  • 题目大意：给定一个序列，支持5种操作，全变0，全变1，区间取反，查询1的总数，查询连续1的总数。
阅读全文 »

发表于 更新于 分类于
  • 题目链接：中位数
  • 题目标签：线段树
  • 题意：有一个长度为N的序列，要求输出前k个的中位数（1<=k<=(N+1)/2）。
阅读全文 »