RainAir
My OI Blog
RainAir

RainAir’s Blog

  SDOI 2019 Bless All!

无向图生成树计数

先记个模板,以后再写。 题目链接 [crayon-5cbd93458d00a557663076/]

   149   2019-04-02 去围观

杜教筛学习笔记

介绍 我们在 OI 题目中,不难会遇到给定一个积性函数 $f(x)$,求 $$\sum_{i=1}^N f(x)$$ 的题目。虽然对于积性函数我们已经有成熟的线性筛方法来说可以做到 $O(n)$,可是有的出题人就是毒瘤,可是有的题目的数据范围要求给出一个复杂度小于线性的做法,这时候神仙就搞…

   95   2019-03-31 去围观

「Luogu P3603」雪辉

题目链接 题目大意 给定一棵树,每个点有一个权值,每次询问给你一些链,求这些链的并上的所有点的点权中有多少种不同的点权和这些点权的 mex。 题解 首先我们考虑如何做一条链的情况。发现我们可以分块,对于每一个块都维护一下这个块中所有的权值的集合,只需要…

   88   2019-03-26 去围观

后缀数组学习笔记

定义 维基百科 - 后缀数组 让我们来看一下 wiki 上的定义: 在计算机科学里, 后缀数组(英语:suffix array)是一个通过对字符串的所有后缀经过排序后得到的数组。此数据结构被运用于全文索引、数据压缩算法、以及生物信息学。 令字符串 $ S=S[1]S[2]...S[n]$, $S[i,…

   99   2019-03-21 去围观

斐波那契数列学习笔记

定义 $$ F_n = \begin{cases} 0 & n = 0 \\ 1 & n = 1 \\ F_{n-1}+F_{n-2} & otherwise \end{cases} $$ 一些小性质 一些 simple 的运算 运算 1 $$F_n = F_{n+2} - F_{n+1}$$ 证明:拆开算就可以了 $$F_{n+2}-F_{n+1} = F_{n+1}+F_n - F_{n+1}…

   159   2019-03-14 去围观

「CF623E」 Transforming Sequence

题目链接 没想到非 Chinese Round 也会出这么毒瘤的题目...... 题目大意:对于正整数序列 $A$,定义序列 $B$: $B_1=A_1,B_i=B_{i-1}\ or\ A_i,i\in[2,n]B $ 其中 or 为位或运算。 每一个序列合法,满足对于$ \forall i\in[1,n]$,有 $A_i\in[1,2^k])$ 而且对于 $\fo…

   111   2019-03-14 去围观

线性基学习笔记

本文使用符号 $\vec{a_i}$ 来表示向量。 定义 基 是线性代数中的一个概念,它是描述,刻画线性空间的一个工具。在 OI 中经常和异或运算扯上关系。 前置芝士 向量空间 向量空间 - 维基百科 定义 $(F,V,+,\cdot)$ 为向量空间,其中 $F$ 为域,$V$ 是向量,$+$ 是向…

   108   2019-03-09 去围观

多项式初步

多项式算法学习笔记 定义 形如 $\sum a_ix^{i}$ 的式子被称为多项式。定义多项式中每个单项式叫做这个多项式的项,定义多项式的次数为项的最高次数。显然 $(n+1)$ 个点可以唯一确定一个次数为 $n$ 的多项式。 接下来我们首先来看一下多项式的基本运算怎么实现(要不…

   237   2019-02-28 去围观

密码保护:疯狂!大礼堂变教室,百名中学生初八进鲁参加竞赛培训,自主招生成新噱头

这篇文章受密码保护,输入密码才能看哦

   629   2019-02-16 去围观

二维树状数组学习笔记

我们把树状数组由一维扩展到二维。二维树状数组的定义是: $C[x][y] = \sum A[i][j]$,其中 $x - lowbit(x) + 1 \leq i \leq x$ $y - lowbit(y) + 1 \leq j \leq y$ 所以我们就可以很方便的写出来单点修改和查询 $(1,1)$ 到 $(x,y)$ 的和的代码了: [crayon-5cbd9345…

   219   2019-02-07 去围观
加载更多
文章归档