【题解】细胞

【题目描述】小 X 在上完生物课后对细胞的分裂产生了浓厚的兴趣。于是他决定做实验并观察细 胞分裂的规律。 他选取了一种特别的细胞,每天每个该细胞可以分裂出 $x-1$ 个新的细胞。 小 X 决定第 i 天向培养皿中加入 $i$ 个细胞(在实验开始前培养皿中无细胞)。 现在他想知道第 n 天培养皿中 阅读更多…

【题解】烹调计划

一共有 n 件食材,每件食材有三个属性,$a[i],b[i] 和 c[i]$,如果在 t 时刻完成第 $i$样食材则得到 $ai-t*bi$的美味指数,用第 $i$件食材做饭要花去 $c[i]$的时间。 众所周知,gw 的厨艺不怎么样,所以他需要你设计烹调方案使得美味指数最大。 一开始,我抱着试试看 阅读更多…

【题解】[SDOI2010] 所驼门王的宝藏 tarjan+DP luoguP2403

作为一个好(e)的(xin)的小紫题,很值得去做(虽然题目废话多,而且做法恶心)题目描述 在宽广的非洲荒漠中,生活着一群勤劳勇敢的羊驼家族。被族人恭称为 “先知” 的 Alpaca L. Sotomon 是这个家族的领袖,外人也称其为 “所驼门王”。所驼门王毕生致力于维护家族的安定与和谐,他曾亲自 阅读更多…

【题解】洛谷 5435[模板] 快速 GCD

对于 $gcd$的询问,设值域为 $V$,询问次数为 $Q$, 有一种奇奇怪怪的时空复杂度都是 $O(V+Q)$,即 $O(V)——O(1)$的做法。 题面 解题思路: 把值域内的数 $x$都分解成 $3$个都不大于 $\sqrt x$的数相乘 (允许出现大于 $\sqrt x$的质数),步骤如下: 阅读更多…

【题解】严格次小生成树

题目大意: 给定一个无向图,求出该图的次小生成树,点数 $n≤100 000$ 边数 $m≤300 000$。 首先,思考暴力做法,求出最小生成树,从图中向树中加入一条边,显然, 图中就会出现一个环,而我们只需去掉环上次大的那条边(因为,最大的那条边肯定是刚加进去的,否则就不满足最小生成树的定义)。 阅读更多…

【算法】任意模数 NTT 原理 -boshi

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