Gym 101630 题解

A

线段树套 set 维护 x 区间中的圆,由于圆互不相交,所以同一个 x 至多有 \log 个圆包含。

B

把给出的图全部放上去模拟一遍。

C

只要保证所有点能到 1 并且 1 能到所有点就行了。

D

假设 a\ge b\ge c,直接去铺一个长宽为 b, c,面积为 a 的平面即可。

E

直接贪心。

F

走一次可以让 x,y 分别减 nn-1,直接贪心。

L

考虑按长度从大往小加链,一条链被加进去的时候它覆盖的部分之前一定被若干链完全覆盖,链剖维护编号最小最大值。


G

考虑二分答案,算 \le mid 的分离的区间和交叉的区间的对数,把区间的答案按权值的不同拆成若干个前缀和,分到两个区间上。问题转化成求满足一定位置要求且和 \le mid 的位置对数,用一个双指针 + BIT 对每个区间统计合法的另一个区间个数。

H

定义 \mathrm{cov}(a,b) 表示 a,b 两组数据的协方差(covariance)。协方差用于表示两个变量间的总体误差。
\mathrm{cov}(a,b) = \frac{\sum_{}a_ib_i}{k} – \frac{\sum a_i}{k}\frac{\sum b_i}{k}

协方差为正表示两个变量变化趋势一致,为负反之,为 0 可以看作两个变量无关。

首先我们随 30000a,全部问下来,把后半段自乘的贡献去掉。

从低到高确定位,假设对于一个 a_i,当前快速幂中的 ra 分别是 r_ia_i’,剩余的贡献是 q_i

再假设 p_ir_ia_i’ 相乘造成的贡献。

假设这一位是 1,那么这个 q_i 中会包含一个 p_i 和一些之后的贡献 w_i,这些之后的贡献中不含 r_ia_i’,所以可以近似认为后面的贡献 w_iq_i 是随机的,即 \mathrm{cov}(w,q)=0。那么可以认为 q_i 是仅和 p_i 相关的,即 \mathrm{cov}(p,q)=\mathrm{cov}(p,p)

假设这一位是 0,那么这个 q_i 中包含一个 r_i 和一个随机变量(之后的某个幂)相乘的贡献 d_i,和再之后的贡献 w_i。仍然可以认为 \mathrm{cov}(w,q)=0,而且 d_ip_i 共享了一个乘数 r_i,所以可以认为 \mathrm{cov}(p,q)=\mathrm{cov}(p,d)。此处可以取生成 d_i 的随机变量是 (a_i’)^2

所以每次求出 \mathrm{cov}(p,d)\mathrm{cov}(p,p)\mathrm{cov}(p,d),若第一个接近第二个则认为这一位是 1,否则认为是 0

I

用偶数序列 a 去划分奇数序列 b,假设把 b 分成了若干段,每次可以在这些段先直接二分出 a_i 在哪两段,再暴力询问这两段把它划开。由于序列是随机的,暴力次数很少,期望下只会询问 n\log n 次。

J

枚举 k 大边的权值 m,把所有边变成 \max(w_i-m,0) 跑最短路最后加上 k\times m。这样一定可以包含正解。然后如果有权边不足 k 条,那么有一条本来 < m 的边被算成 m,不优;如果有权边多于 k 条,那么有边的权值被多算了也不优。

K

n\le 44 的时候可以 Meet in the Middle。

n> 44 的时候,考虑怎么找一些合法的 r。假设 b_0 末尾 k0,那么 a_0 末尾也会有 k0,由于本来合法的 a_0 就只有 q/2^{n-2}=2^{66-n} 个,固定了后 k 位之后就只有 2^{66-n-k} 个。但是由于 b_0 末尾 k0,所以 r 的最高 k 个位置随意取,是 2^k 的。

所以总复杂度 2^{22}

发表评论

电子邮件地址不会被公开。 必填项已用*标注