E. Drinking观察一下不难发现，任意一端区间$g(l,r)=\sum\limits_{i=1}^nx_{(i)}\frac{1}{2^i},x(i)$表示区间内第$i$大的值，由于误差要求$<10^{-6}$，所以估一下只要取区间最大的T=50个数
自然想到单独计算每个数对答案的贡献。设第$i$个数左边比它大的数从右到左为$l_1,l_2,\cdots,l_T$，右边比它大的数从左往右为$r_1,r_2,\cdots,r_T$，那么每个数的贡献为
val_i=w_i\sum\limits_{u=1}^T\sum\limits_{v=1}^T(l_{u-1}-l_u)(r_v-r_{v-1})\frac{1}{2^{u+v-1}}
阅读全文
MorphLing
6月 03, 2021
A签到
C简单题
D最短路、树相关 待补
F数学、思维
首先由于$n’$最终取值范围为$[1,n]$，所以枚举$n’$可以得到一个$O(n)$的做法
然后把$[1,n]$分块为$[1,\sqrt m],[\sqrt{m}+1,\min\{n,m\}]$两部分，枚举第一部分n’取值，复杂度$O(\sqrt n)$，对于第二部分，可以把式子写成$m’=n’k$，此时$k$的取值范围为$[1,\sqrt m]$，枚举k，对于每个固定的k，可以找到一个贪心方案使代价最小，所以第二部分的代价也是$O(\sqrt m)$.
阅读全文
MorphLing
4月 29, 2021
斜率优化本质上解决的是，给定一条直线的斜率和平面上的若干个点，要求选择一个点，使得该直线经过该点，且保证此时截距取到最小/最大值。
阅读全文
MorphLing
4月 01, 2021