「LOJ 3059」「HNOI 2019」序列

LOJ #3059. 「HNOI 2019」序列

题意

给定一个长为 $n$ 的序列 $A_1,\dotsc,A_n$,求一个长为 $n$ 的不下降序列 $B_1,\dotsc,B_n$,使得 $\sum_{i=1}^n (A_i-B_i)^2$ 最小,只需要输出最小值

以及 $m$ 次互相独立的修改,每次会更改一个位置的值,要求输出修改后的答案

模 $998244353$

$n,m\le 10^5$

Read more

「Codeforces 1034D」Intervals of Intervals

zx2003说多 log 过不去,不然就去写了

Codeforces 1034D

题意

你有 $n$ 个区间 $[a_i, b_i]$,定义区间的区间 $[l,r]$ 的价值是第 $l$ 个区间到第 $r$ 个区间的并的总长度

你需要找出 $k$ 个不同的区间的区间,使得它们的总价值最大

输出总价值

$1\le n \le 3 * 10^5,1 \le k \le \min{\frac{n(n+1)}{2},10^9}$

Read more

01分数规划

问题

有 $n$ 个物品,每个物品有两个属性 $a_i$ 和 $b_i$,需要选出 $k$ 个,设选出的编号集合是 $S$。

最大化

$$\frac{\sum_{i\in S} a_i}{\sum_{i\in S} b_i}$$

保留一定精度。

Read more

「LOJ 2585」「APIO2018」新家

LOJ #2585

题意

在数轴上有$n$家商店,第$i$个商店有坐标$x_i$,种类$t_i\in[1..k]$,出现时间$[a_i,b_i]$

有$q$组询问$l_i,y_i$,表示询问在时间$y_i$,离坐标$l_i$最远的商店类型到$l_i$的距离

类型$t$的商店到一个点的距离定义为所有存在的$t$类商店到这个点的距离的最大值

$1\le n,q\le 3*10^5,1\le k\le n$

$1\le x_i,a_i,b_i\le 10^9$

$1\le l_i,y_i\le 10^8$

Read more