拉格朗日插值学习笔记
已知 $n$ 次多项式 $P(x)$ 在 $n+1$ 个点的值 $P(x_0),P(x_1),\cdots,P(x_n)$，则
博主已经退役，评论可能会审核很久才能通过。
博主已经退役，评论可能会审核很久才能通过。
已知 $n$ 次多项式 $P(x)$ 在 $n+1$ 个点的值 $P(x_0),P(x_1),\cdots,P(x_n)$，则
AtCoder Luogu 分析 可以发现 $(2i)\oplus (2i+1)=1$，因此可以想到大致的构造方法：连 $(1,2i)$、$(1,2i+1)$、$(2i+1+n,2i)$、$(2i+n,2i+1)$。这样子就满足了 $2i$ 和 $2i+1$。 然而有一些问题。一个问题是 $1$ 如何处理。可以仿照样例，使 $2$ 和 $3$ 不按上面的方式连边，而是连 $(1,2)$、$(...
AtCoder Luogu 分析 首先，如果存在 $i,j$ 满足 $|x_i+y_i|$ 与 $|x_j+y_j|$ 的奇偶性不同，则无解。因为走到 $(x,y)$ 的步数一定与 $|x_i+y_i|$ 的奇偶性相同。 先考虑 $|x_i+y_i|$ 全部为奇数的情况。 先考虑步长的问题。可以利用二进制进行构造，即令步长为 $2^0,2^1,\cdots$。容易发现最大只需要到 $2^{3...
51nod 分析 首先考虑一个暴力做法。 假设我们现在正在计算张三的期望收益。则根据期望的线性性，我们只需要求出张三抽到某一张卡时位于某一个排名的概率。 枚举张三抽到的卡（为了方便称这张卡为 A），然后考虑 DP。设 $dp_{i,j}$ 表示前 $i$ 个不是张三的人中有 $j$ 个抽到的卡比张三大的概率。设 $p$ 为第 $x$ 个不是张三的人抽到的卡比 A 大的概率，容易得到转移 这...
BZOJ 分析 容易看出最小割。考虑连边： 对于每个方格，从 $s$ 向它连容量为 $b_i$ 的边，从它向 $t$ 连容量为 $w_i$ 的边。 对于每个方格，新建一个节点 $i'$，从 $i$ 向 $i'$ 连容量为 $p_i$ 的边，从 $i'$ 向 $a_j\in [l_i,r_i]$ 且 $j<i$ 的方格 $j$ 连容量为 $+\infty$ 的边。 考虑正确性...
Codeforces Luogu 分析 二分答案，则我们需要判定是否能够让所有竹子的高度 $\leq mid$。 由于竹子的高度不能小于 $0$，所以正着做不太好做；考虑反过来做，即每根竹子初始高度为 $mid$，每天会变矮 $a_i$，你每天可以选 $k$ 根竹子让他们变长 $p$，判断最后所有竹子的高度是否能 $\geq h_i$，且操作过程中竹子的高度不能 $<0$。 考虑贪心，...
51nod 分析 甲胜和乙胜类似，三者概率之和为 $1$，因此只考虑计算甲胜的概率，即甲胜的方案数除以总方案数。 设甲的第 $i$ 个数为 $X_i$，乙的第 $i$ 个数为 $Y_i$，则甲胜当且仅当 则我们相当于要求这个 $k_1+k_2+1$ 元不定方程的非负解数，其中一些变量有上界。 考虑容斥掉上界的限制，即钦定一些变量超过了上界，则我们只需要计算不定方程 $\sum_{i=1}^...
Codeforces Luogu 分析 考虑 DP。设 $dp_i$ 表示前 $i$ 条道路的最大收益，不难得到转移 这里的 $c(i,j)$ 表示修建 $i$ 到 $j$ 的道路的花费，$w(i,j)$ 表示修建 $i$ 到 $j$ 的道路获得的收益。 考虑用线段树优化，即要求扫到 $i$ 时每个叶结点的值 $j$ 为 $dp_j-c(j+1,i)+w(j+1,i)$。对于一个新的 $i...