2020春A班训练大楼

admin

20200221：第一周，预备周，
主要内容：
1、数组、字符串和多维数组
2、c++中的vector
3、多维数组和矩阵，矩阵加法，乘法，快速幂
4、KMP算法，mamcher算法，字符串哈希技术
5、ST表
6、前缀和，树状数组
7、链表、静态链表
8、块状链表

张溯源

admin 发表于 2020-3-15 18:27
20200315区间问题总结：
1、求和
2、最大最小，K大，区间K大

这个第三点是什么

admin

20200315区间问题总结：
1、求和
2、最大最小，K大，区间K大
3、

admin

20200308第三周：
复习总结区间上的统计问题专题
树
1、树模型与层级结构
2、数的表示  双亲表示法，孩子表示法，树的计数，DFS，BFS，欧拉序(!)
3、二叉树 树转成二叉树 前中后序遍历
4、常见的数  表达式树  Trie树，哈弗曼树，BST，四叉八叉树，堆，线段树
5、高级树结构

admin

20200228第二周：队列堆栈
1、C++中的vector queue stack
2、表达式中缀转后缀，后缀表达式求值，PMN的堆栈实现
3、优先队列
4、单调队列单调栈

admin

练习：
1、自己编写一个KMP 算法的程序实现查找s串在t串中出现的首位置，同时用字符哈希技术也做一下。
2、自己编写一个mamacher算法的程序求s的最长回文子串
3、三种方法的约瑟夫问题  （普通数组，链表，数组模拟的静态链表）
4、NOI2003文本编辑器   NOI2005维护数列
5、试试分块的方法做麦森数

admin

小技巧：
1、数组可以当做跳转表：我以前做过的ISBN，十进制转十六进制等，高精度计算中数组可以多装几个数位，set与布尔数组，位运算之间有联系。请体会下
2、多维数组可以转成一维数组，c++中是第一维优先。一维数组也可以拆成多维数组，这里好像隐约有升维降维的思想。练习题 ：cantor表
3、字符串常用函数size find erase和某些特殊函数 strtok strrev strups strlws
4、把二维数组和直角坐标系对应起来的话，(x,y)*(2*2矩阵)其实就是坐标旋转。这个要好好体会，怕这类题目
5、fibo中矩阵乘法的意思，floyd中矩阵的意思。交换等也可以使用矩阵（骰子问题、置换群），矩阵乘法可以做快速幂
6、KMP算法是一个递归的过程，好好在纸上画一画，练习题：环状DNA匹配，PowerString问题
7、manacher算法其实不难，前面的构造字符串很精妙，以后可以仿效。
8、字符哈希技术让kmp好像在考场上似乎没有必要，看这里
9、ST表以前讲过，但是这种思想要注意。打表大法的境界，试试这样的打表打表做做麦森数。（打2^n的表 n=10,100,1000,10000等，计算时直接调用）
A、前缀和，二维前缀和，变化的前缀和（求和），为什么还要变化成树状数组。（起点在变化！）
B、二维树状数组
C、指针链表和静态链表（很多高级数据结构，树，图等都需要这个）做约瑟夫问题的数组法，链表法，数组模拟的静态链表的三种做法
D、新内容：块状链表 结合和数组的方便查询和链表的方便插入两个优点，在处理字符串插入输出，表格内容插入删除统计等有存在的意义。