城堡

考虑将每个支撑点都先设成其下限高度，即 \(h_i\gets h_1-(i-1)\times d\)，这样就只会提高某些支撑点的高度。 显然每次提高的是一个后缀。提高某个后缀的贡献是当前高度低于原先高度的支撑点数量减去当前高度不低于原先高度的支撑点数量。选择贡献最大的后缀直到最后一个支撑点的高度等于 ......

应该是联赛前最后一次任性了，浪费的时间有点多，不过也揭露了我的基础知识和代码能力都很弱的问题，得加油啊。 先 sto dwt。 给定一棵基环树森林，起初有 \(m\) 个点已被选进 \(S\) 里，你需要再选 \(k\) 个点加入到 \(S\) 中，最小化其余点到 \(S\) 距离的最大值。 这个问 ......

分析 感觉没有蓝题难度 一道 bfs 题目，相较于大部分 bfs 题，它较为复杂，但分析一下还是很好水过的。 建立墙时，可以用三维数组，\(wall_{~i, ~j, ~pos}\) 表示 第 \(i\) 行第 \(j\) 列 \(pos\) 方向有墙。 观察发现，\(8 = 2^3，4 = 2^2 ......

找点图论练习题写，发现hdu又寄了，那就发到blog里吧。 思路：tarjan缩点判断DAG中点数是否为1。若是，则该图为强连通图。 //produced by miya555 //stupid mistakes:多测记得清空 //ideas:tarjan模板 #include<bits/stdc+ ......

1、最多可以摧毁的敌人城堡数目 题目：给你一个长度为 n ，下标从 0 开始的整数数组 forts ，表示一些城堡。forts[i] 可以是 -1 ，0 或者 1 ，其中： -1 表示第 i 个位置 没有 城堡。 0 表示第 i 个位置有一个 敌人 的城堡。 1 表示第 i 个位置有一个你控制的城堡 ......

[SCOI2008]城堡 最大值最小，显然二分答案，但考虑二分后如何 check。 $n$ 个点 $n$ 条边，显然这是一个基环树森林。对于基环树，常用的套路是拆环为链，枚举删去哪条边。但这题是基环树森林，拆环为链的复杂太高，考虑将环和树分开处理。 树上是一个很典型的 dp，和将军令一样（不了解的可 ......