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\)

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\}\)

问题

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

最大化

\[\frac{\sum_{i\in S} a_i}{\sum_{i\in S} b_i}\]

保留一定精度。

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\)