文章

在两年前，我学习了快速傅里叶变换。当时有许多的问题没能透彻地理解。 在半年前，我接触到了任意模数 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$ 的答案一定存在于 $ 阅读更多…

我第一次写游记竟然是在退役之后 qwq $day\;0$ 中午从被关了一个月的学校出来回了家，然后就跑去了机场，坐地铁到了酒店已经是十点多，然后 $uoj$群上有人说有 $cf$一场 $educational\;round$过 10 分钟就开始了，因为超级累所以带着玩的心态用小号打了打，打完 $AB 阅读更多…

这里的题目前来说都是 Atcoder 中比较简单的题。但我还是没几道是自己想出来的。 AGC018C : Coins : 贪心 $x+y+z$个人，每个人有 $a,b,c$三个参数，将这些人分为 $X,Y,Z$三类，求 $\sum_{i\in X}a_i+\sum_{i\in Y}b_i+\sum_ 阅读更多…