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

博客转型计划

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

阅读更多
数据结构

树链剖分 ·Decomposition

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

阅读更多
动态规划

斜率优化 DP 入门

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

阅读更多
数学

容斥原理入门

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

阅读更多
数学

莫比乌斯反演小结

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

阅读更多
简单 DP 简单 DP
总结暑假的 DP 小练习 A 有一排 n 个电线杆, 第 i 个的高度为 。要在相邻的电线杆间造电线。每一根的代价是 。为一根电线杆增加 x 高度的代价是 , 最小
2018.10.01
一套题与心路 一套题与心路
摘要 感觉是精神状态不大好的原因吧 A 给定一个 01 序列,请你找到一个最长的子序列,使得第一个 1 到开头的距离、相邻两个 1 之间的距离、最后一个 1 到结尾的距离都相同。例如00100100和0001000就是符合要求的子序列,0
2019.09.15 Sshwy
瞎扯最大子矩阵 瞎扯最大子矩阵
摘要 本文所研究的是一类序列上的“最大子矩阵”问题(其实就是瞎扯)。 序列最大子矩阵给出一个非负整数序列 ,并定义 S(l,r)=\be
2019.08.30 Sshwy
小志 小志
摘要 谨以此文,在我疲倦、颓废、迷茫的时侯,给我指引方向。 2019.8.30恩师的寄语 尧尧妈妈,第一,尧尧是我寄予大期望的孩子,必须也应该在以后考上非常好的大学,找到最好的工作,成就很大的事业。第二,关于信竞的事,首先与徐老取得联系
2019.08.16 Sshwy
菜鸡互啄 ACM 心路历程 菜鸡互啄 ACM 心路历程
摘要 极限反杀!成功追梦! 谨以此文,纪念我 OI 生涯中第一次 ACM 赛 RK1。 今天上午,打了一场 ZR 的 ACM。题是敦爷组的,现在总结一下我的心路历程。 队名:阿咆长得像地精炸弹 队长:Sshwy 队员:Sshwy Na
2019.07.27
斐波那契数列 斐波那契数列
斐波那契数列(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
Tewelvefold way Tewelvefold way
摘要 今天我们来探讨一道综合计数题。 问题描述 n个有标号/无标号的球分给m个有标号/无标号的盒子,盒子有三种限制: A. 无限制B. 每个盒子至少有一个球C. 每个盒子至多一个球 共12种问题。问方案数。(所有球都要放) 为了方便,将
2019.07.20
笛卡尔树 笛卡尔树
摘要 本文介绍一种不太常用,但是与大家熟知的平衡树与堆密切相关的数据结构——笛卡尔树。 笛卡尔树是一种二叉树,每一个结点由一个键值二元组 构成。要求 满足二叉搜索树的性质,而 满足堆的性质。一个有趣的事实是
2019.07.18
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
杜教筛 杜教筛
摘要 莫比乌斯反演推完式子后,一般考虑线性筛和数论分块。当要求在低于线性时间的求解积性函数前缀和的问题的时候就会用到杜教筛。 符号说明简单解释一下本文可能用到的记号的含义。 狄利克雷卷积符号 表示数论函数
2019.01.11
欧几里德算法专题 欧几里德算法专题
摘要 鉴于初等数论的内容太多,于是单独分出一个欧几里德算法的文章,主要讲欧几里德算法,扩欧和类欧 欧几里得算法即辗转相除法,基于 的原理,用于求解最大公约数的问题 int gcd(
2019.05.01
上下界网络流 上下界网络流
摘要 对于普通的网络流问题,我们在一个网络 上求解相关的问题。网络的边有一个容量,即流量上界 。而有时候我们要求这条边有一个流量下界 ,这样的相关问题被归为上下界网络流问题。 无源汇可行
2019.07.11
多项式与多项式乘法 多项式与多项式乘法
摘要 鸽鸽给我们讲课啦 据说讲课前通宵玩了两天。早上灵车漂移。 多项式定义给定一个环 ,( 通常是交换环,可以是有理数、实数或者复数等等)以及一个未知数 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
1 / 9