2019暑期集训第八讲：数据结构进阶（一）
数据结构进阶(一)主讲人：孙翔
线段树为什么要线段树？题目一： 10000个正整数，编号1到10000，用A[1],A[2],A[10000]表示。 修改：无 统计：1.编号从L到R的所有数之和为多少？ 其中1<= L <= R <= 10000.
方法一：对于统计L,R ，需要求下标从L到R的所有数的和，从L到R的所有下标记做[L..R],问题就是对A[L..R]进行求和。这样求和，对于每个询问，需要将(R-L+1)个数相加。
方法二：更快的方法是求前缀和,令 S[0]=0, S[k]=A[1..k] ，那么，A[L..R]的和就等于S[R]-S[L-1]，这样，对于每个询问，就只需要做一次减法，大大提高效率。
题目二： 10000个正整数，编号从1到10000，用A[1],A[2],A[10000]表示。 修改：1.将第L个数增加C （1 <= L <= 10000） 统计：1.编号从L到R的所有数之和为多少？ 其中1<= L <= R <= 10000.
再使用方法二的话，假如A[L]+=C之后，S[L],S[L+1],,S ...
2019暑期集训第七讲：动态规划(II)
DP状压DP 首先回顾一下位运算
与 &
或 |
异或 ^
取反 ~
左移 <<
右移 >>
^ 运算的逆运算是它本身
取反是对 1 个数 $num$ 进行的计算，~ 把$num$种的0 和 1 全部取反补码——正数的补码是其（二进制) 本身，负数的补码是其（二进制）取反后加一
右移在C++中将直接舍弃右侧多余位，左侧则较为复杂，无符号数会在左侧补0，对于有符号书，则会用最高位的数补齐[注]：
1. 左移和右移是有返回值的，并非对$num$本身进行操作
2. 左移和右移优先级低于四则运算，`x<<1+1` 会被解释为`x<<(1+1)`，所以一般最好都加上括号
一些应用
num<<i 相当于$num\times 2^i$ ，而num>>i 相当于$num \div 2^i$ 。效率要比 % 和 / 操作快得多（60%？）
当$num>0$时两者并没有差别，但是当$num<0$时，普通除法时向0取整，而右移是向下取整
num * 10 = (num << 1) + (nu ...
2019暑期集训第六讲：动态规划(I)
动态规划（线性，区间，树形）对于动态规划 我们所需要确定的肯定就是以下几种元素
状态（阶段）
我们确定的状态要保证当前的状态不会对于后面的状态产生影响 这个条件也被叫做无后效性 并且这个状态能够表示出所有的状态
2.决策
我们利用什么样的决策从前面一个阶段转移到我当前的阶段过来（可能是前面的阶段去最小值，最大值之类的）
开始写代码的时候要确定状态的起始条件（也就是边界条件） 再确定状态的最总目标 （也就是我们要求的答案）
1.线性dp具有线性“阶段”划分的动态规划算法被称为线性dp
题目 1：
给定一个包含整数的二维矩阵，子矩形是位于整个阵列内的任何大小为1 * 1或更大的连续子阵列。矩形的总和是该矩形中所有元素的总和。在这个问题中，具有最大和的子矩形被称为最大子矩形。例如，下列数组：
0 -2 -7 09 2 -6 2-4 1 -4 1-1 8 0 -2其最大子矩形为：
9 2-4 1-1 8它拥有最大和15
对于这个问题 我们当然可以直接暴力枚举这个区间的起始端点和结束端点来求答案，但是这个方案的复杂度太高了，我们可以想到之前做过的最大的连续子序列和的线性dp来解 ...
2019暑期集训第五讲：基础数据结构
数据结构基础栈1.定义 栈（Stack）又称堆栈，它是一种运算受限的线性表，其限制是仅允许在表的一端进行插入和删除运算。人们把此端称为栈顶，栈顶的第一个元素被称为栈顶元素，相对地，把另一端称为栈底。向一个栈插入新元素又称为进栈或入栈，它是把该元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称为出栈或退栈，它是把栈顶元素删除掉，使其下面的相邻元素成为新的栈顶元素。
2.栗子 放盘子，装东西….
3.实现 实现一般有两种：第一种用一个数组和一个变量（栈顶指针）来实现。第二种用STL自带的stack。
常规操作：
1234567891011121314151617#include<iostream>#include<stack>using namespace std;stack<int> s;int main(){ s.push(10);//入栈 cout<<s.size()<<endl;//栈大小 int t=s.top();//栈顶元素 cout<<t ...
2019暑期集训第四讲：字符串基础
字符串基础1.字符串匹配1.暴力算法123456for (i = 0; i < n - m + 1; i++) { for (j = 0; j < m; j++) { if (a[i + j] != b[j]) break; } if (j == m) ans.push_back(i); }
2.哈希将string映射为int 每一个字符串代表一个数字 时间复杂度变为O(n+m)
转化方法可以采用
f(s) = \sum{s[i]*b^i}(modM)12345678ll hashs(char s[])//上述公式相当于把一个字符串看成一个b进制数{ int len=strlen(s); ll ans=0; for (int i=0;i<len;i++) ans=(ans*base+(ll)s[i])%mod; return ans;}
b与M应当是互质的（不然取余的时候直接约了）
在输入随机的情况下，这个求出 ...
2019暑期集训第二讲：组合数学&概率&数学期望
主讲人：韩耀东
时间：7.19
组合数学 & 概率期望DP组合数学1. 排列组合1. 加法原理 完成一列事的方法有 n 类，其中第 i 类方法包括$a_i$种不同的方法，且这些方法互不重合，则完成这件事共有 $a_1 + a_2 + \cdots + a_n$ 种不同的方法
2. 乘法原理 若完成一件事需要 n 个步骤，其中第 i 个步骤有 $a_i$ 种不同的完成方法，且这些步骤互不干扰，则完成这件事共有 $a+1 a_2 \cdots * a_n$ 种不同的方法
两原理的区别：
一个与分类有关，一个与分步有关；加法原理是“分类完成”，乘法原理是“分步完成”
3. 排列数在 $n$ 个不同元素种，任取 $与均为自然数，下同m(m\leq n,m与n均为自然数，下同)$ 个元素按照一定的顺序排成一列，叫做从$n$个不同元素中取出$m$ 个元素的一个排列；产生排列的个数叫做从 $n$ 个不同元素中取出 $m$个元素的排列数，用符号 $A_n^m$ 来表示
A_n^m = n(n-1)(n-2) \cdots (n-m+1) = ...
2019暑期集训第一讲：博弈论
主讲人：段英鹏时间：7.17
简单博弈论
本次简单博弈论讲解六个知识点：
1：bash博弈；2：nim博弈；3：威佐夫博弈；5：Fibonacci博弈；6：sg函数；
首先介绍博弈论问题有如下几个特点
1：博弈模型为两人轮流决策的博弈。并且两人都使用最优策略来取得胜利。
两个玩家，都会采取最优的决策，那么如果存在一个局面为必胜局面，某玩家位于此局面。只要自己无失误，则必胜。那么同样又一个局面为必败局面，某玩家位于此局面。只要对手无失误，则必败。
那也就是说，针对这样的游戏，我们关注点应该在局面上。
2：博弈是有限的。即无论两人如何决策，都会在有限步决出胜负。
3：博弈是公平的。即两人进行决策的规则相同。
相关概念：
先手必胜状态：先手可以从这个状态走到某一个必败状态。
先手必败状态：先手走不到任何一个必败状态。
也就是说先手必胜状态，那么先手一定能采取某些操作，让后手面对必败态。如果是先手必败态，无论先手怎么操作，都无法让后手面对必败态。
bash博弈
假设一堆石子有n个，每次最多取m个，甲乙两个玩家轮流取石子，最后把石子取完的人获胜，保证甲乙每一步的决策都是最优的， ...