RenaMoe's Blog

这里放一些数学公式定理，防止健忘。

好吧现在已经是远古博客了，慎用。

题面

题面不好概括，贴个链接好了。

一条路上有 n 户人家，坐标为 \(a_i\)，需要建 k 个不同位置的信号站，每个信号站的不合理值为所有人家到信号站的距离和，求不合理值最小的 k 个信号站不合理值之和。

\(k\le n\le 10^6,0\le a_i\le 10^6\)

给出一个长为 n 的排列，每次给出询问 \([l_i,r_i]\)（可以离线），求 \(f(l_i,r_i)\)： \[ f(l,r)=\begin{cases} (r-l+1)+f(l,m_{l,r}-1)+f(m_{l,r}+1,r)\quad &(l\le r)\\ 0\quad &(l > r) \end{cases} \]

\(m_{l,r}\) 为 \([l,r]\) 的最大值的位置。

给出 n 点 m 边的有向图，设 1 点到 n 点最短路为 d，求长度小于等于 d+k 的路线方案数。

\(n\le 10^5,m\le 2\times 10^5,k\le50\)，每条边边权为非负整数。

若方案数无穷，输出 -1。

题面

给出一个 n 点 m 边的无向图，每个边有权值 \(c_i,t_i\)，求出一个生成树使最小化： \[ (\sum_{i=1}^m c_i)\times(\sum_{i=1}^m t_i) \] \(1\le n\le 200,1\le m\le 1\times 10^4\)

记录一些计算几何相关的知识。

专门用来解决石子合并问题的算法。

给出一串 01 序列和正整数 k，一次操作将长度为 k 的子区间取反，m 次询问一个区间内全部变为 0 的最小操作次数，不可能完成输出 -1。

\(1\le n\le 2\times 10^6,1\le m\le 5\times 10^5\)

大概写写中国剩余定理的公式和扩展中国剩余定理板子。