在二维平面上给若干个点,将这些点划分为若干个区域,定义两个区域的距离为这两个区域之间最近点对的距离。求将这些点划分为 个区域,使得最近的两个区域的距离最大值。
「SCOI2016」背单词 - Trie + 贪心
总共有 n 个单词,对于一个序号为 x 的单词(序号 1…x−1 都已经被填入):
- 如果存在一个单词是它的后缀,并且当前没有被填入表内,代价为 n×n 颗泡椒才能学会;
- 当它的所有后缀都被填入表内的情况下,如果在 1…x−1 的位置上的单词都不是它的后缀,那么代价为 x;
- 当它的所有后缀都被填入表内的情况下,如果 1…x−1 的位置上存在是它后缀的单词,所有是它后缀的单词中,序号最大为 y,那么代价为 x−y。
「SDOI2014」LIS - 最小割 + 网络流退流
给定序列 A,序列中的每一项 Ai 有删除代价 Bi 和附加属性 Ci。请删除若干项,使得 A 的最长上升子序列长度减少至少 1,且付出的代价之和最小,并输出方案。
如果有多种方案,请输出将删去项的附加属性排序 Ci 之后,字典序最小的一种。
「BZOJ 4499」线性函数 - 线段树
小 C 最近在学习线性函数,线性函数可以表示为 f(x)=kx+b。现在小 C 面前有 n 个线性函数 fi(x)=kix+bi,他对这 n 个线性函数执行 m 次操作,每次可以:
M i K B
代表把第 i 个线性函数改为 fi(x)=kx+b;Q l r x
返回 。
「HNOI2005」狡猾的商人 - 差分约束
刁姹接到一个任务,为税务部门调查一位商人的账本,看看账本是不是伪造的。账本上记录了 n 个月以来的收入情况,其中第 i 个月的收入额为 Ai。当 Ai 大于 0 时表示这个月盈利 Ai 元,当 Ai 小于 0 时表示这个月亏损 Ai 元。所谓一段时间内的总收入,就是这段时间内每个月的收入额的总和。刁姹的任务是秘密进行的,为了调查商人的账本,她只好跑到商人那里打工。她趁商人不在时去偷看账本,可是她无法将账本偷出来,每次偷看账本时她都只能看某段时间内账本上记录的收入情况,并且她只能记住这段时间内的总收入。现在,刁姹总共偷看了 m 次账本,当然也就记住了 m 段时间内的总收入,你的任务是根据记住的这些信息来判断账本是不是假的。
「BZOJ 2588」Count on a tree - 主席树
给定一棵 N 个节点的树,每个点有一个权值,对于 M 个询问 (u,v,k),你需要回答 u 和 v 这两个节点间第 k 小的点权。
「SCOI2016」幸运数字 - 线性基 + 树链剖分 / 倍增
A 国共有 n 座城市,这些城市由 n−1 条道路相连,使得任意两座城市可以互达,且路径唯一。每座城市都有一个幸运数字,以纪念碑的形式矗立在这座城市的正中心,作为城市的象征。一些旅行者希望游览 A 国。旅行者计划乘飞机降落在 x 号城市,沿着 x 号城市到 y 号城市之间那条唯一的路径游览,最终从 y 城市起飞离开 A 国。
在经过每一座城市时,游览者就会有机会与这座城市的幸运数字拍照,从而将这份幸运保存到自己身上。然而,幸运是不能简单叠加的,这一点游览者也十分清楚。他们迷信着幸运数字是以异或的方式保留在自己身上的。例如,游览者拍了 3 张照片,幸运值分别是 5、7、11,那么最终保留在自己身上的幸运值就是 9()。
有些聪明的游览者发现,只要选择性地进行拍照,便能获得更大的幸运值。例如在上述三个幸运值中,只选择 5 和 11,可以保留的幸运值为 14。现在,一些游览者找到了聪明的你,希望你帮他们计算出在他们的行程安排中可以保留的最大幸运值是多少。