分类: 题解

68 篇文章

洛谷 – P3509 – [POI2010]ZAB-Frog
数轴上有 $n$ 个点,坐标分别为 $p_1, p_2, \cdots, p_n$ 在这些点上按照某些规则跳。
规则是:每次向距当前点第 $k$ 小的点跳,如果有相同距离则向下标较小的跳;
求从每个点出发跳了 $m$ 次后在哪里.
$1\leq k < n\leq 10^6, 1\leq m\leq 10^{18}, 1\leq p_i\leq 10^{18}$.
洛谷 – P5677 – [GZOI2017]配对统计
给定一个数列 $a_1, a_2, \cdots, a_n$.
定义在有序数对 $(x, y)$ 上的“好对”:对于 $a_x$,$y\in[1, x)\cup(x, n]$ 能使 $|a_x-a_y|$ 取最小值。
给定 $q\leq 3\times 10^5$ 组询问,每次询问一个区间 $[l, r]$ 中,有多少个好对。
求:每次询问的答案 $Ans_i$ 与询问编号 $i$ 的乘积的和,即:
$$ \sum_{i=1}^{m}Ans_i\times i $$
CodeForces – 1495A – Diamond Miner
给定 $2n$ 个点,其中 $n$ 个在 $x$ 轴上,另外 $n$ 个在 $y$ 轴上。现在要求每一个 $x$ 轴上的点与一个 $y$ 轴上的点连线,每个点恰好被连线一次。求所有线段的欧几里得距离之和。
洛谷 – 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$.