格言
For the shadow of lost knowledge at least protects you from many illusions
  推荐文章
Others

博客转型计划

摘要 再小的星星也有光芒 没错!你现在看到的是 Sshwy 大菜鸡的一个计划! 心的起始每个人都是有故事的,也是有追求的。在 OI 这条路上,学习知识的时侯大多数人估计

阅读更多
数据结构

树链剖分 ·Decomposition

摘要 树链剖分用于将树分割成若干条链的形式,以维护树上路径的信息。 具体来说,将整棵树剖分为若干条链,使它组合成线性结构,然后用其他的数据结

阅读更多
动态规划

斜率优化 DP 入门

前言本蒟蒻的第一道斜率优化 DP 前后卡了 3 小时…… 海星 有时候好不容易推出一个 DP 的式子,结果发现数据范围太大? 单调队列无法优

阅读更多
数学

莫比乌斯反演小结

摘要 复习莫比乌斯反演~ 前言OI 的数论涉及求和的部分,一般采用 暴力计算;但是当上界过大的时候就需要考虑数论求和法。 常用的技巧有前缀和、差分、组合计

阅读更多
数学

容斥原理入门

摘要 啃论文系列~ 考容斥原理本身的题不多,容斥原理常用于某个算法部分的求值。 2019.6.16 编入精选文章。 入门 某班有 a 歌人擅

阅读更多
小志 小志
摘要 谨以此文,在我疲倦、颓废、迷茫的时侯,给我指引方向。 文思如泉涌,思潮至时,才会想将其跃然纸上。 似乎这是第一次,可能是最后一次,父亲摆明反对的立场了。 「浙江是新高考,你去浙江学了回来怎么考」「学竞赛不搞文化课,本末倒置!」「你
2019.08.16 Sshwy
菜鸡互啄 ACM 心路历程 菜鸡互啄 ACM 心路历程
摘要 极限反杀!成功追梦! 谨以此文,纪念我 OI 生涯中第一次 ACM 赛 RK1。 今天上午,打了一场 ZR 的 ACM。题是敦爷组的,现在总结一下我的心路历程。 队名:阿咆长得像地精炸弹 队长:Sshwy 队员:Sshwy Na
2019.07.27 Sshwy
斐波那契数列 斐波那契数列
斐波那契数列(The Fibonacci sequence,OEIS A000045)的定义如下: F_0 = 0, F_1 = 1, F_n = F_{n-1} + F_{n-2}该数列的前几项如下: 0, 1, 1, 2, 3, 5
2019.07.21 Sshwy
Tewelvefold way Tewelvefold way
摘要 今天我们来探讨一道综合计数题。 问题描述 n个有标号/无标号的球分给m个有标号/无标号的盒子,盒子有三种限制: A. 无限制B. 每个盒子至少有一个球C. 每个盒子至多一个球 共12种问题。问方案数。(所有球都要放) 为了方便,将
2019.07.20 Sshwy
笛卡尔树 笛卡尔树
摘要 本文介绍一种不太常用,但是与大家熟知的平衡树与堆密切相关的数据结构——笛卡尔树。 笛卡尔树是一种二叉树,每一个结点由一个键值二元组 构成。要求 满足二叉搜索树的性质,而 满足堆的性质。一个有趣的事实是
2019.07.18 Sshwy
Stern-Brocot 树与 Farey 序列 Stern-Brocot 树与 Farey 序列
摘要 Stern-Brocot树是一种维护分数的优雅的数据结构。它分别由Moritz Stern在1858年和Achille Brocot 在1861年发现这个结构。 概述Stern-Borcot 树从两个简单的分数开始: \frac{
2019.07.17
约瑟夫问题 约瑟夫问题
摘要 约瑟夫问题由来已久,而这个问题的解法也在不断改进,只是目前仍没有一个极其高效的算法(log以内)解决这个问题。 问题描述 n个人标号 逆时针站一圈,从 号开始,每一次从当前的人逆时针数 个,然后
2019.07.16
扩展埃氏筛 扩展埃氏筛
摘要 本文介绍一种比欧拉筛更高效的筛法,扩展 Eratosthenes 筛法。 杜教筛适用范围较小,未充分利用积性。扩展埃氏筛要求对于任意质数 p, 是一个关于 p 的低阶多项式。对于任意 的指数
2019.07.13 Sshwy
杜教筛 杜教筛
摘要 莫比乌斯反演推完式子后,一般考虑线性筛和数论分块。当要求在低于线性时间的求解积性函数前缀和的问题的时候就会用到杜教筛。 符号说明简单解释一下本文可能用到的记号的含义。 狄利克雷卷积符号 表示数论函数
2019.01.11
欧几里德算法专题 欧几里德算法专题
摘要 鉴于初等数论的内容太多,于是单独分出一个欧几里德算法的文章,主要讲欧几里德算法,扩欧和类欧 欧几里得算法即辗转相除法,基于 的原理,用于求解最大公约数的问题 int gcd(
2019.05.01
上下界网络流 上下界网络流
摘要 对于普通的网络流问题,我们在一个网络 上求解相关的问题。网络的边有一个容量,即流量上界 。而有时候我们要求这条边有一个流量下界 ,这样的相关问题被归为上下界网络流问题。 无源汇可行
2019.07.11 Sshwy
多项式与多项式乘法 多项式与多项式乘法
摘要 鸽鸽给我们讲课啦 据说讲课前通宵玩了两天。早上灵车漂移。 多项式定义给定一个环 ,( 通常是交换环,可以是有理数、实数或者复数等等)以及一个未知数 x,则任何形同 \sum_{i=0}^na
2019.02.15
Prufer 序列 Prufer 序列
摘要 本文翻译自 e-maxx Prufer Code,兹瓷一下OI-WIKI的计划。另外解释一下,原文的结点是从 0 开始标号的,本文我按照大多数人的习惯改成了从 1 标号。 这篇文章介绍 Prufer 序列 (Prufer code)
2019.07.07
初等数论小结 初等数论小结
摘要 复习一下数论 符号的说明 大 符号:当且仅当存在正实数 和实数 ,使得 ,我们就可以认为,$f(x)=O(g(x
2019.01.26
析合树 析合树
摘要 作为一个没有去过 WC2019 的人去啃 WC 的课件。别问我为什么这么菜。 翻的时侯翻到一个友好的标题:《简单的连续段数据结构》。打开后,咦!析合树! 另外解释一下本文可能用到的符号: 逻辑与, 逻辑或
2019.06.27
组合数漫谈 组合数漫谈
排列与组合在考虑一类计数问题的过程中,我们常常会遇到讨论排列或者组合的问题。 排列数从 n 个不同元素中,任取 m 个元素按照一定的顺序排成一列,叫做从 n 个不同元素中取出 m 个元素的一个排列;从 n 个不同元素中取出 m 个元素的所有
2018.12.21
高斯消元 高斯消元
摘要 Gaussian Elimination,一种求解线性方程组的算法 概述高斯消元是一种求解线性方程组的方法。 线性方程组与増广矩阵我们把 \left\{\begin{matrix} a_{1,1}x_1+a_{1,2}x_2+\c
2019.04.04
概率与期望 ·expectation 概率与期望 ·expectation
概率的定义概率, 又称“或然率”、“几率”, 它是对一个随机事件的可能性的大小所作的数量方面的估计。 一个事件 A 出现的概率, 是 A 可能出现的情况与全部可能情况的比率。其计算公式为: P(A)=m(A 可能出现的情况)/n(所有可能的
2018.10.01
贪心小结 贪心小结
小 TAG观察(贪心思路) 猜测(减少决策数量) 证明(从最优解转化为贪心解,并且不改变最优性质,从而证明) 多个贪心组合 贪心与非线性算法 贪心的单调性 贪心性质 贪心算法是一种形式及其多样的算法。它的应用方式很广,简单的简单,难的难。
2018.12.19
线段树与历史区间最值问题 线段树与历史区间最值问题
摘要 读 jry《区间最值操作与历史最值问题》 前言仍然是线段树的应用问题。在前文中我们探讨了线段树的基及其应用。如果对这方面了解较少的同学请移步《线段树初步》、《线段树应用》。本文将继续讲解线段树在区间最值与历史最值问题上的应用。 区间
2019.06.19
1 / 9