从JZOI考试中提取出来的技巧/知识点

一个蒟蒻的提高组经历:

1.矩阵乘法

这个很简单,只要记住左边的矩阵从第1行开始乘右边的矩阵的列就OK了,在讲讲几个性质:

1
2
A*B<>B*A
(A*B)*C=A*(B*C)

2.Floyd式DP

我们可以根据前面的两个,或者后面的两个,或者中间断开来求出我们现在需要的值,如Floyd本身:

1
table[i,j]:=min(table[i,j],table[i,k]+table[k,j]);

3.哈夫曼树

为什么从树的节点到根的距离乘上本身的值的总和的最小值可以用合并果子做?因为他让最大的再最上面,所以只有一次,其次是第二小两次,第三小两次…这样子符合问题。(或许有一点难理解,多思考)

4.Bfs状态性质

当我们可以从一个状态转移到另一个状态求解的时候,注意可以用DP,也可以DFS或者BFS,当然平常的时候BFS回更加优越。

1
2
3
状态1 --> 状态2    (加入队列)
      --> 状态3
      --> 状态4

5.hash

当我们有一个非常大的数的时候(十进制?)我们可以使用hash。
我们可以用一个梅森素数或者一个百万级的素数来进行hash,如果觉得还不行,我们可以选择多个hash函数进行bool存储。

6.拓扑排序技巧(节选)

首先,拓扑排序只能对于有向无环图。不过,我们想判断哪些点没有在环里面的时候,我们可以用到拓扑排序。还有,如果一个点的dep没有另一个点的dep高的话,它是去不到另一个点的。

7.删边

一张强连通图有多少个多余的边?我们只需要求出最少的边数:点数,然后减去就可以了。

8.GCD技巧(节选)

当转移状态太慢的时候,我们可以考虑mod这个神奇的东西。而GCD一次操作的费用记得要求出来。

9.主席数的性质(节选)

众所周知的主席数可以实现可持久化线段树,它也可以维护可持久化数组。时间复杂度和空间复杂度知识大一个log而已。

10.差分约束系统(节选)

借用一下大佬的博客:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
I.定义:
如果一个系统由n个变量和m个约束条件组成，形成m个形如ai-aj≤k的不等式(i,j∈[1,n],k为常数),
则称其为差分约束系统。

II.关联:
if(dis[u]+w(u,v)<=dis[v])
{
    dis[v]=dis[u]+w(u,v);
}
这不正与松弛操作相似吗？但是好像不等号方向刚好相反，
但其实这并不矛盾。

上面的代码要实现的是使dis[u]+w(u,v)>dis[v],而对于不等式，
我们进行建边的操作：对于每个不等式 x[i] - x[j] <= a[k]，对结点 j 和 i 建立一条 j -> i的有向边，边权为a[k]，求x[n-1] - x[0] 
的最大值就是求 0 到n-1的最短路，两者刚好吻合。所以求解差分约束问题就转化为了最短路问题。

III.存在性
(1）、存在负环

如果路径中出现负环，就表示最短路可以无限小，即不存在最短路，那么在不等式上的表现即X[n-1] - X[0] <= T中的T无限小，
得出的结论就是 X[n-1] - X[0]的最大值不存在。在SPFA实现过程中体现为某一点的入队次数大于节点数。（貌似可以用sqrt(num_node)
来代替减少运行时间）

(2）、终点不可达

这种情况表明X[n-1]和X[0]之间没有约束关系，X[n-1] - X[0]的最大值无限大，即X[n-1]和X[0]的取值有无限多种。
在代码实现过程中体现为dis[n-1]=INF。

IV.应用
对于不同的题目，给出的条件都不一样，我们首先需要关注问题是什么，
如果需要求的是两个变量差的最大值，那么需要将所有不等式转变成"<="的形式，建图后求最短路；相反，如果需要求的是两个变量差的最小值，
那么需要将所有不等式转化成">="，建图后求最长路。

11.运算符的快速解法

n个数对m个数进行运算取出最值。有些时候是可以排序的,所以我们可以用贪心的思想来解决这些题目。同时,我们也可以建造二进制Trie(也可以叫哈夫曼编码)。如果是and那么照相同,如果是xor就找不同。

12.学会非主流线段树

线段树需要学会的很简单:

1
2
I.知道要维护什么。
II.知道怎么维护。

一般我们维护的都是很简单的东西,而我们上面提出的说起来简单,做起来就非常困难。知道要维护什么,如【NOIP2015模拟10.28B组】圣章-精灵使的魔法语 这道题,考场上又有多少人知道维护什么呢?在像这道题:1384. Alice的游戏 (Standard IO)(JZOJ)谁又知道要建造10颗线段树来维护?所以我们要练就的就是OI思想,区间问题好好思考以上两个东西。

13.学会找规律

真正一套题都是找规律,这种题目你们见过吗?规律是很重要的,它运用于各种操作,比如:数论,加速,答案,大打表之术等等。当你找不出正解又觉得这一题很水的时候,先做其它的题目,返回来再做这道题。其次,要把样例输入和样例输出仔细研究!

14.SG函数

这个就不是很懂,我只会Bash和Nimm而已,说一下大佬的定义:

1
游戏和的SG函数等于各个游戏SG函数的Nim和。这样就可以将每一个子游戏分而治之，从而简化了问题。而Bouton定理就是Sprague-Grundy定理在Nim游戏中的直接应用，因为单堆的Nim游戏 SG函数满足 SG(x) = x。对博弈不是很清楚的请参照http://www.cnblogs.com/ECJTUACM-873284962/p/6398385.html进行进一步理解。

15.二维前缀和

我们想求出(很多次,很多个)一个区间的值,一般都是运用到二维前缀和。
而二维前缀和也一般有这样一个模式:

1
2
I.代表全局的-代表某一个区域的=答案
II.代表全局的-代表某一个区域的*2+(前面减了两次,所以加上)某一个重复减去的区域

16.tarjan

在强联通分量和割点,割边,点双,边双等总多领域中,tarjan使用树中的规律来求出答案,详见博客?

17.后缀数组排序

倍增排序省去了很多时间,当然CD3也是很强的,详见博客?

18.AC自动机

把kmp思想运用到Trie中,这样AC自动机就产生了,详见博客?

以上内容大部分在我的博客中有出现(我在JZOI的十天),细节可以随时翻阅。