算法备忘录

2021年09月15日 阅读数:1
这篇文章主要向大家介绍算法备忘录,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

和信息竞赛有关的备忘录。html

维护

维护说白了就是“保存信息”,是一种比较高端的说法。 信息问题通常都会用“询问-回答”的方式来出题。这类问题还能够细分为静态问题和动态问题,算法还有离线算法和在线算法之分。 对于每一个询问,咱们都会尝试去计算答案。有时候某些数值咱们想直接调用,而不是重复计算。所以,咱们会说去“维护”某个值,目的是快速获得答案。 举个例子,CQOI2018的交错序列。题目中对于一个$\mathcal{1}$字符不相邻的$\mathcal{01}$序列$\lambda$,若是有$x$个$\mathcal{0}$,$y$个$\mathcal{1}$,求: $$ \sum\limits_{|\lambda|=n}x^ay^b \pmod{m} \tag{1-1} $$ 题目再也不赘述。咱们要求的答案能够表示成: $$ \sum\limits_{k=0}^a(\dbinom{a}{k}n^a(-1)^{a-k}\sum\limits_{|\lambda|=n}y_{\lambda}^{a+b-k}) \tag{1-2} $$ 因为$\sum\limits_{|\lambda|=n}y_{\lambda}^{a+b-k}$很很差计算,咱们事先计算,对于不一样的$k$把对应的值保存起来。算法

维护的方法有不少。通常主流的方法是使用数据结构。上面这道题使用的是动态规划。固然,这里到底能不能用“维护”一词还有待考证。数组

贡献

虽然信息学的数学计算基本都是和整数打交道,但整数仍是有必定分类的。贡献一词通常是针对数值而言的。 a[i]=val; 来看这个最简单的代码块。这里的$i$是数组的下标,而$val$是数组元素对应的值。 有句俗话说得好,“不开$\mathtt{long\ long}$见祖宗”。为了防止整数“存不下”,咱们会将大部分int变量换成long long。 可是,代码中的i是数组下标,不能用long long代替。这样的整数能够叫作“标号”,反之叫作“数值”。 通常的,对于两个变量$a_1,a_2$来讲,由其中一个变量值推导出另一个变量值,而后把这个值填进去,有点相似于“数值转移”。这种数值转移的多少咱们就叫作这个变量的“贡献”。 好比说,$\mathcal{01}$序列$\lambda$,要求计算其中$\mathcal{0}$ 的个数。咱们说$\mathcal{1}$的贡献是0,由于它的存在不会使答案增长;而$\mathcal{0}$的贡献是1,由于多一个0,答案就增长1。数据结构

时间复杂度

我可能永远也学不会本身算这个东西。数据结构和算法

假设一个算法的“计算次数”是$T(n)$,$n$是数据的规模大小,若是存在两个正常数$c,n_0$使得$T(n_0) \leq cf(n_0)$,就称**$T(n)$在集合$O(f(n))$内,简记为$T(n)=O(f(n))$**。其中$c$叫作这个算法的常数。所谓的卡常是一种算法优化策略,不会改变算法的时间复杂度,但能够下降算法的常数,提升速度。函数

时间复杂度能够帮助咱们估计程序的运行时间。通常来讲,咱们会直接把$N$代入这个复杂度的表达式进行计算,并评估它的数量级。结果在$10^7$一下则说明这是一个很好的算法;结果在$10^8$以上则会愈来愈慢,每每在这种状况下,该算法只能称之为暴力算法,能获得部分分。学习

还有一些特殊的规定。咱们经常使用$\log n$代替$\log_2n$。一些带有$\log n$的时间复杂度的算法通常和“二分”“二叉树”有关。而$\log\log n$则和一些更特殊的算法有关,好比埃氏筛。优化

但在大多数状况下,时间复杂度的表示会舍弃规范而表达出更多的信息。好比$O(2^3 \log n)$这个写法是不规范的,但它比$O(\log n)$的写法更加具备实际意义。这个时间复杂度表示的是斐波那契数列的矩阵快速幂优化,而$2^3$就是计算转移矩阵乘法的时间复杂度。url

若是你想计算时间复杂度,能够借助下面的三个简单原理:spa

  1. 若是两个计算的过程有嵌套关系(好比说在每一次循环扫描的过程当中还要排一次序),总时间复杂度是二者时间复杂度的乘积;
  2. 若是有多个计算过程按照顺序前后执行,那么取过程当中“最大”的时间复杂度。(好比说先排序,再用单调队列,整个算法的时间复杂度就只能取$O(N\log N)$而不是$O(N)$)
  3. 时间复杂度的优先级:$O(\log N) < O(N) < O(N^p)(p>1) < O(a^N)(a >> 1)$

教科书和有些题解每每会给出算法的时间复杂度。记住这个模型,下次就能够本身计算它们了。

一些展开

常常写一写这些有学术味的式子是一种很好的娱乐方式。

$$ \prod_{i=1}^n{(1+a_i)}=\sum_{S \subseteq {a_i}}\prod_{k \in S}k \tag{2} $$ 其中规定$S=\varnothing$时,$\prod\limits_{k \in S}k=1$。

用这个能够结合容斥原理得出欧拉函数的表达式。

$$ (\sum_{i=1}^na_i)^2=\sum_{i=1}^na_i^2+2\sum_{1\leq i < j \leq n}a_ia_j \tag{3} $$

$$ (\sum_{i=1}^na_i)^3=\sum_{i=1}^na_i^3+\sum_{1 \leq i < j \leq n}a_i^2a_j+\sum_{1 \leq i < j \leq n}a_ia_j^2+\sum_{1\leq i <j < k \leq n}a_ia_ja_k $$ $$\vdots\tag{4}$$

事实上,这样的乘法有一个规律。若是乘积中含有$k$个项,即$k$个多项式,咱们能够**把每一个项当作一个集合。**每次从每一个集合中选取$1$个单项,获得$k$个单项,咱们就把这$k$个单项的乘积累加到答案中去。

不考虑合并同类项,咱们展开能够获得$s_1s_2\cdots s_k$个不一样的求和项。其中$s_i$是原来每一个项中单项的个数。这个定律叫作**自由组合定律,**事实上是一个遗传学定律。

首字母命名法

人名的一种简写读法。首先写出人名的拼音,而后将首字母直接拼接在一块儿。(如$zsj$就是一个首字母拼音法)首字母简写一般能够链接前缀$orz-$以表示对该人的膜拜,如$orzyyb$。

有一种特别的用法:做为模数。举个例子,若是咱们答案要求对$10000007$取模,咱们就能够令yyb=10000007;这样,在代码中咱们就能够这样写:

sum = (sum + A[i]) % yyb

这个用法和$orzyyb$等效。这样作能够表示对学长的膜拜,并让代码显得很有风趣。可是写题解或在学术场合不建议这样作,极大影响阅读体验。

一些植物衍生词

蒟蒻(jǔ ruò),就是平常说的魔芋。像魔芋豆腐,蒟蒻果冻,都是很是好吃的食物。在这里表自谦。

蒯(kuǎi),本指蒯草,多年生草本植物,叶子条形,花褐色。生长在水边或阴湿的地方。茎可用来编席,也可造纸。在这里表示“复制”的意思。多用于口语,其字较少见。

一些现代算法和数据结构。

如珂朵莉树,猫树。这些都是基于传统的数据结构和算法进行的升级。如珂朵莉树就是一种基于std::set的暴力数据结构,其实质是“动态分块”。这些数据结构均可以了解学习,有时在考场有必定概率赢得暴力分甚至全分。但就事论事,这些名字确实太蠢了。

和上面同样,这些数据结构最好不要出如今任何学术性质的文章中。若是能够的话,尽量地对数据结构的优化进行说明。毕竟信息竞赛和信息学,计算科学仍是有很大的差异的。

顺带一提,最近我正好作到了一道能够用珂朵莉树解决的问题。若是想了解更多,能够移步这里