你强归你强，我永不示弱！
题目链接：Luogu 2906
了解奶牛们的人都知道，奶牛喜欢成群结队。观察约翰的 $n$ 只奶牛，你会发现她们已经结成了几个“群”。每只奶牛在吃草的时候有一个独一无二的位置坐标 $(X_i,Y_i)$。当满足下列两个条件之一，两只奶牛 $i$ 和 $j$ 是属于同一个群的：
请计算有多少个牛群，以及最大的牛群里有多少奶牛。
数据范围：$1\le n\le 10^5$，$1\le X_i,Y_i,C\le 10^9$，$X_i,Y_i,C\in \mathbb{Z}$
题目链接：UOJ 104
你正在玩一个关于长度为 $n$ 的非负整数序列 $a_i$ 的游戏。这个游戏中你需要把序列分成 $k+1$ 个非空的块。为了得到 $k+1$ 块，你需要重复下面的操作 $k$ 次：
每次操作后你将获得那两个新产生的块的元素和的乘积的分数。你想要最大化最后的总得分。
数据范围：$2\le n\le 10^5$，$1\le k\le \min(n-1,200)$，$0\le a_i\le 10^4$
题目链接：BZOJ 1086
“余”人国的国王想重新编制他的国家。他想把他的国家划分成若干个省，每个省都由他们王室联邦的一个成员来管理。他的国家有 $n$ 个城市，编号为 $1\dots n$。一些城市之间有道路相连，任意两个不同的城市之间有且仅有一条直接或间接的道路。
为了防止管理太过分散，每个省至少要有 $B$ 个城市，为了能有效的管理，每个省最多只有 $3B$ 个城市。
每个省必须有一个省会，这个省会可以位于省内，也可以在该省外。但是该省的任意一个城市到达省会所经过的道路上的城市（除了最后一个城市，即该省省会）都必须属于该省。
一个城市可以作为多个省的省会。
数据范围：$1\le n\le 3000$
题目链接：Luogu 2900
约翰准备扩大他的农场，眼前他正在考虑购买 $n$ 块长方形的土地，每块土地宽为 $w_i$、长为 $l_i$。如果约翰单买一块土地，价格就是土地的面积 $w_i\times l_i$。但他可以选择并购一组土地，并购的价格为这些土地中最大的长乘以最大的宽，即 $\max\{w_i\}\times \max\{l_i\}$。比如约翰并购一块 $3\times 5$ 和一块 $5\times 3$ 的土地，他只需要支付 $5\times 5=25$ 元， 比单买合算。约翰希望买下所有的土地。他发现，将这些土地分成不同的小组来并购可以节省经费。给定每份土地的尺寸，请你帮助他计算购买所有土地所需的最小费用。
数据范围：$1\le n\le 5\times 10^4$，$1\le w_i,l_i\le 10^6$
题目链接：BZOJ 1911
你有一支由 $n$ 名预备役士兵组成的部队，士兵从 $1$ 到 $n$ 编号，要将他们拆分 成若干特别行动队调入战场。出于默契的考虑，同一支特别行动队中队员的编号 应该连续，即为形如 $(i,i+1,\dots,i+k)$ 的序列。 编号为 $i$ 的士兵的初始战斗力为 $x_i$ ，一支特别行动队的初始战斗力 $x$ 为队内 士兵初始战斗力之和，即 $x=x_i+x_{i+1}+\cdots+x_{i+k}$。
通过长期的观察，你总结出一支特别行动队的初始战斗力 $x$ 将按如下经验公 式修正为 $x’$：$x’= ax^2+bx+c$，其中 $a,b,c$ 是已知的系数（$a<0$）。 作为部队统帅，现在你要为这支部队进行编队，使得所有特别行动队修正后战斗力之和最大。试求出这个最大和。
数据范围：$1\le n\le 10^6$，$-5\le a\le -1$，$\vert b\vert,\vert c\vert\le 10^7$，$1\le x_i\le 100$
题目链接：BZOJ 1010
P 教授要去看奥运，但是他舍不得他的玩具，于是他决定把所有的玩具运到北京。
他使用自己的压缩器进行压缩。这个压缩器可以将任意物品变成一维，再放到一种特殊的一维容器中。P 教授有编号为 $1\dots n$ 的 $n$ 件玩具，玩具经过压缩后会变成一维，第 $i$ 件件玩具压缩后长度为 $C_i$。
为了方便整理，P 教授要求：
制作容器的费用与容器的长度有关，根据教授研究，如果容器长度为 $x$，其制作费用为 $(x-L)^2$，其中 $L$ 是一个常量。
P 教授不关心容器的数目，他可以制作出任意长度的容器，甚至超过 $L$。试求最小费用。
数据范围：$1\le n\le 5\times 10^4$，$1\le L,C_i\le 10^7$
题目链接：BZOJ 1877
Elaxia 最近迷恋上了空手道，他为自己设定了一套健身计划，比如俯卧撑、仰卧起坐等 等，不过到目前为止，他坚持下来的只有晨跑。现在给出一张学校附近的地图，这张地图中包含 $n$ 个十字路口和 $m$ 条街道，Elaxia 只能从一个十字路口跑向另外一个十字路口，街道之间只在十字路口处相交。Elaxia 每天从寝室出发跑到学校，保证寝室编号为 $1$，学校编号为 $n$。Elaxia 的晨跑计划是按周期（包含若干天）进行的，由于他不喜欢走重复的路线，所以在一个周期内，每天的晨跑路线都不会相交（在十字路口处），寝室和学校不算十字路口。Elaxia 耐力不太好，他希望在一个周期内跑的路程尽量短，但是又希望训练周期包含的天数尽量长。
数据范围：$1\le n\le 200$，$1\le m\le 2\times 10^4$