文章

首先，发现 $y,z$ 完全没用，题目的大意就是说每个点有一个集合，集合中的每个元素为 $(x_i,c_i)$ ，然后每一次询问一个点，再给出一个 $X$，需要你求出这个点的集合的所有元素中，$(x_i-X)^2+c_i$ 的最小值，输出这个最小值。 展开一下 $(x_i-X)^2+c_i$ ，会发 阅读更多…

感觉 $luogu$ 的题面 好 丑 啊 。 很显然的一个想法是用线段树套可持久化 $\rm{Trie}$ ，或者分块 $+$可持久化 $\rm{Trie}$ ，前者会爆空间 (当然可能可以卡过去？) ，后者好像也会爆炸。 正解是线段树分治。 按照时间构造一棵线段树，然后对于每个询问操作，将其拆入到 阅读更多…

在两年前，我学习了快速傅里叶变换。当时有许多的问题没能透彻地理解。 在半年前，我接触到了任意模数 NTT，但是当时只背了个板子，没有弄懂它的原理。 今天，隔壁机房一个高二的大佬点醒了我，我突然就明白任意模数 NTT 究竟再干啥了。 任意模数 NTT 原理 当我们处理模数为任意 $10^9$左右质数的 阅读更多…

简介 飞行一直是人类的梦想。 六百多年前，万户进行了人类历史上第一次对飞行的探索。 一百二十多年前，李林达尔进行了人类历史上第一次固定翼滑翔机的飞行。 一百多年前，莱特兄弟制造了世界上第一架完全受控的固定翼动力飞机，并且成功试飞。 八十年前，人类历史上第一架喷气式飞机诞生在德国。 一年多前，bosh 阅读更多…

单调栈 ——单调递增或单调减的栈，跟单调队列差不多，但是只用到它的一端，利用它可以用来解决一些 ACM/ICPC 和 OI 的题目，如 RQNOJ 的诺诺的队列等。 · 功能： 利用单调栈，可以找到从左/右遍历第一个比它小/大的元素的位置 · 模拟： 递增；1,5,2,7,3. 1:1 2:1,5 阅读更多…

挺傻一题，是我蠢了。 有请喜闻乐见的泰勒公式： $$ f(x)=\sum_{i=0}^{n}\frac{f^{(i)}(x_0)\cdot (x-x_0)}{i!} $$ 要求精度达到 $10^{-7}$ ，$n$ 取 $15$ 左右就够了。为了方便，令这里的 $x_0=0$ 。 每个点维护一个多项 阅读更多…

青一的电脑，为你点赞！ 卡常真恶心。 发现恐怖的奴隶主数量的上限 $k$ 和恐怖的奴隶主血量的上限 $m$ 都特别小，考虑状压当前所有恐怖的奴隶主。由于每一个恐怖的奴隶主没有不同，我们只需要记下每个不同的血量的恐怖的奴隶主的个数即可。 设 $f_{i,a,b,c}$ 表示还剩 $i$ 次攻击，当前局 阅读更多…

状压 $\rm{DP}$ 。 显然题目给出的州的不合法的条件就是这个州不存在欧拉回路，这个好办，按照欧拉回路的性质对于所有的状态相应的州预处理一下即可。 然后设 $f_S$ 表示将点集状态为 $S$ 时，这个子图的所有划分方案的满意度之和。 转移柿显然： $$ f_S=\sum_{T\subsete 阅读更多…

设 $x$ 为树的根，对于每次讯问中 $S$ 中的任意一点 $a$ ，设 $t_a$ 表示 $x$ 到 $a$ 的步数，于是我们的答案就是 $E(\max(S))$ ，好像不是很好求，考虑求 $\min(S)$ 然后进行 $\rm{Min-Max}$ 容斥。 设 $f(u)$ 表示从点 $u$ 出发 阅读更多…

对于一个询问，考虑二分其答案，对于当前的 $mid$ ，如果这个时刻存在的所有路径中所有权值 $>mid$ 的路径全部经过了当前询问的点 $x$ ，那么 $x$ 的答案只能在 $(l,mid)$ 中找，否则，如果存在权值 $>mid$ 且没有覆盖到 $x$ 的路径，那么 $x$ 的答案一定存在于 $ 阅读更多…