算法备忘录

2019/04/09 23:45
阅读数 12

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

维护

维护说白了就是“保存信息”,是一种比较高端的说法。 信息问题一般都会用“询问-回答”的方式来出题。这类问题还可以细分为静态问题和动态问题,算法还有离线算法和在线算法之分。 对于每个询问,我们都会尝试去计算答案。有时候某些数值我们想直接调用,而不是重复计算。因此,我们会说去“维护”某个值,目的是快速得到答案。 举个例子,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$就是计算转移矩阵乘法的时间复杂度。

如果你想计算时间复杂度,可以借助下面的三个简单原理:

  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的暴力数据结构,其实质是“动态分块”。这些数据结构都可以了解学习,有时在考场有一定几率赢得暴力分甚至全分。但就事论事,这些名字确实太蠢了。

和上面一样,这些数据结构最好不要出现在任何学术性质的文章中。如果可以的话,尽可能地对数据结构的优化进行说明。毕竟信息竞赛和信息学,计算科学还是有很大的差别的。

顺带一提,最近我正好做到了一道可以用珂朵莉树解决的问题。如果想了解更多,可以移步这里

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部