长乐集训 - NOI模拟赛（二十六）
今天是几场下来第一次完整搞出一道题
虽然跑的贼慢，方法不够优，比 $\text{std}$ 慢 $200ms$。。
$\text{score：0 + 100 + 0 = 100 rk：16/32}$
Problem A：Geometric Progressions题目描述首项为 $a$ 且公比为 $b$ 的等比数列是一个形如 $a, ab, ab^2, ab^3, …$ 的数字序列
你被给定了 $n$ 个整数等比数列。你的任务是找出最小的整数 $x$，使得它是所有给定的序列的元素，或者声明这样的整数不存在
数据范围对 $100\%$ 的数据，$1 \le n \le 100, ~ 1 \le a, b \le 10^9$
题解原题 CF571E
首先将所有 $a, b$ 分解质因数，得到大小为 $m$ 质因数集 $\{p_1, p_2, …, p_m\}$
设 $c_{i, j}$ 表示 $a_i$ 分解质因数后 $p_j$ 的幂次，$d_{i, j}$ 表示 $b_i$ 分解质因数后 $p_j$ 的幂次，那么答案即可被表示为 $\prod\limits_{i = 1}^m p_i ...
长乐集训 - NOI模拟赛（二十二）
今日继续垫底系列
T1题意理解错误暴力写挂
T2怒敲 $n \le 4$ 求根公式然后发现答案还得排序。。
$\text{score：0 + 10 + 0 = 10 rk：27/27}$
Problem A：游戏题目描述ysgh是一名Herthstone大师。现在他遇到了一个很严峻的问题：
场上总共有 $n+m$ 个随从，其中ysgh控制着 $n$ 个，对手控制着 $m$ 个。每个随从有自己的血量。
如果ysgh在这一回合成功解掉了对手的所有随从，则ysgh获胜。否则下一回合对手直接骑脸，ysgh就会输掉。
ysgh现在手里仅有一场牌，属性如下：
进行 $d$ 次，每一次等概率随机一个在场上的未死亡随从（包括自己和对手的）并且对其造成一点伤害。若不存在未死亡随从，则不进行此次攻击。一个随从未死亡当且仅当其血量严格大于 $0$。每一次攻击后，所有血量小于等于 $0$ 的随从立即死亡。
ysgh想要知道，他有多大概率可以取胜，也就是多大的概率使得在使用这张牌后，对手的随从全部死亡。
特别提醒：由于描述与实际游戏规则有出入，一切以实际题面描述为准。
数据范围对于所有测试数据，满足 $1 ...
「NOI2014」购票 「树上斜率优化」
首先易得方程，且经过变换有
$$\begin{aligned} f_i &= \min\limits_{dist_i - lim_i \le dist_j} \{f_j + (dist_i - dist_j)p_i + q_i\} \\ f_j &= p_idist_j + f_i - dist_ip_i - q_i \end{aligned}$$
在一条直线上时，斜率优化可以用普通$CDQ$分治实现（会不会过于麻烦？），那么对于在树上斜率优化时，考虑点分治
这时就在点分治中运用$CDQ$分治的思想，即使用在当前重心管辖范围内的通向根节点的那一条链上的节点来更新其它节点就好了
注意在分治中的斜率优化时在凸包上加点和更新右侧节点答案要同时进行，不然当前最优解可能会在后面由于斜率被删去，导致答案错误，还有由于下面代码是由深度由小到大处理的，所以是反着维护下凸包，即上凸包
代码123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354 ...