分类: 题解

28 篇文章

CodeForces – 1495A – Diamond Miner
给定 $2n$ 个点,其中 $n$ 个在 $x$ 轴上,另外 $n$ 个在 $y$ 轴上。现在要求每一个 $x$ 轴上的点与一个 $y$ 轴上的点连线,每个点恰好被连线一次。求所有线段的欧几里得距离之和。
Luogu – P3628 – [APIO2010]特别行动队
给定一个长度为 $n$ 的序列,每个元素有权值 $x_i$,现在要将序列分割为若干段,每段中元素连续。设 $s_i$ 表示前缀和,即 $s_i=\sum_{j=1}^{i}{x_j}$,那么对于每段 $[l, r]$,代价为: $$ a(s_{i}-s_{j-1})^2+b(s_i-s_{j-1})+c $$ 其中 $a, b, c$ 为题目给定的常数。整个序列的代价为每段代价之和。
求序列的代价最大值。
$1\leq n\leq 10^6, -5\leq a\leq -1, -{10}^7\leq b, c\leq 10^7, 1\leq x_i\leq 100$.
ZROI – 20普转提 – Day1 – T4 – 魔法师
有 $m$ 次询问,每次询问给定一次操作。操作分为两种:向集合 $A$ 中添加一个物品或从集合 $A$ 中删除一个物品。对于每个物品,有两个属性:
  • 物品的类别 $t_i$
  • 物品的威力 $p_i$
现在要从集合 $A$ 中选取一个子集 $B$,使得 $B$ 中物品的威力和最大,且 $B$ 满足:
  • 对于每个类别 $t_i$,最多选取 $t_i$ 本书;
  • 一共最多能够选取 $n$ 本书(题目给定 $n$)。
在每次询问之后,输出最大威力和。
Luogu – P2148 – [SDOI2009]E&D
有 $2n$ 堆石子,编号分别为 $1, 2, \cdots, 2n$。将第 $2k-1$ 和 $2k$ 堆 $(1\leq k\leq n)$,归为同一组。第 $i$ 堆石子的个数是正整数 $s_i$.
定义分割操作:
  1. 任取一堆石子,不妨为第 $i$ 堆,将其全移走;
  2. 从和第 $i$ 堆同一组的石子中,取出若干正整数个石子,放到第 $i$ 堆的位置上。操作后,两堆石子数都要大于 $0$.
给定状态,问先手是否有必胜策略。
$n\leq 2\times 10^4, 1\leq s_i\leq 2\times 10^9$.