P2831 [NOIP 2016 提高组] 愤怒的小鸟

P2831 [NOIP 2016 提高组] 愤怒的小鸟 算法 搜索 思路 由于 n \le 18，可以考虑搜索。 定义 dfs(cur, a, b) 表示搜索到了第 cur 头猪，使用了 a 条抛物线，前面还有 b 头猪为被击中。 对于一条抛物线 y=ax^{2}+bx+c，需要三个点确定其解析式。

SP1716 GSS3 - Can you answer these queries III

SP1716 GSS3 - Can you answer these queries III 算法 线段树 思路 题目要求维护支持单点修改和查询区间最大子段和的数据结构。 考虑使用线段树维护。对于区间 [l_1,r_1], [l_2,r_2] ，合并后的最大子段和有一下三种情况： 区间 [l_1,r

CF727F Polycarp's problems

CF727F Polycarp's problems 算法 贪心 思路 考虑特殊情况。当 m=1 时，问题转化为：给定 a_0, 求删除最少元素使得对于任意的 i，满足 \Sigma_{j=0}^{i} a_{j} \ge 0。 将特殊情况扩展到 m \le 10^6，即对于每一个给定的 a_0，求

CF1192B Dynamic Diameter

CF1192B Dynamic Diameter 算法 欧拉序 线段树 思路 对于这道题考虑使用欧拉序的性质： 对于树上的每一个子树，在欧拉序上都有一个区间与之对应。 对于 (u, v) 的最近公共祖先，在欧拉序上表现为区间 [pos_u, pos_v] 内深度最浅的节点。 所以可以将原树转化为欧拉

Luogu P3129 [USACO15DEC] High Card Low Card P

Luogu P3129 [USACO15DEC] High Card Low Card P P3129 [USACO15DEC] High Card Low Card P 算法 贪心 思路 由于 Bessie 预先知道了 Elsie 的出牌策略, 所以可以贪心, 考虑每次都出比 Elsie 大一点点

P1445 [Violet] 樱花

P1445 [Violet] 樱花 算法 数学（素数筛，因子个数） 思路 对于原式做如下推导： \large \begin{aligned} \frac{1}{x} + \frac{1}{y} &= \frac{1}{n!} \\ \frac{x + y}{xy} &= \frac{1}{n!} \

P1471 方差

P1471 方差 算法 线段树 数学推导（平均数，方差） 思路 区间操作，很容易想到线段树。 但是方差不好合并，考虑拆解： \begin{aligned} s^2 &= \frac{1}{n} \sum_{i = 1}^{n} (A_i - \overline A)^2 \\ &= \frac{1}