Day 1 高中部寒假集训 - 粉粉何所似？

Day1：

emming，高中部集训在春节前要上5天，春节后上2天~~（如果我没记错的话QAQ)~~。

学校的电脑系统重装了一遍，把万恶的冰点还原（^-^)和教师监控系统~~（但是我怎么接老师课件啊QAQ）~~刷掉了，嘿嘿嘿。

以上是废话。

今天课程表：

2019.1.23

上午

数学：排列组合、概率论、素数筛、快速幂、欧几里得算法、扩欧。

下午

图论：基本概念、储存方式、遍历方式、拓扑排序、最短路。

晚上

考试

笔记

1. 概率论

概率空间：
- 定义：一般我们在一个概率空间内探讨问题，概率空间即所有可能事件的集合，每一件事件有确定的概率。
- 性质： $P(AB)$ 表示 $A$ , $B$ 同时发生的概率， $P(\frac{A}{B})$ 表示在 $B$ 已经发生的情况下，A发生的概率，又叫条件概率。
期望：
- 定义：随机变量 $X$ ，概率空间中的事件为变量的取值情况， $X$ 的期望 $E(X)=∑p_i x_i$ ，即所有取值的加权平均，意义为对一个随机变量进行观测后的可能值叠加。
- 期望的线性性：
  1. $E(X+Y)=E(X)+E(Y)$
  2. 若 $X$ , $Y$ 两个变量独立，则 $E(XY)=E(X)E(Y)$

2.拓扑排序

对象：有向无环图 $（Directed　Acyclic　Graph，DAG）$ 。
作用：将一个图G中的所有顶点排序成一个序列，使得对于图中每一条边 $（u,v)$ ，满足 $u$ 在序列中排在 $v$ 的前面（便利顺序），这个序列被称为图的拓扑序列。
算法：
1. 从图中任选一个入度为 0 的顶点，加入拓扑序列末端
2. 删除这个顶点及其所有出边
3. 回到 S1 继续执行，直到图中没有顶点
结论：任意 $DAG$ 可经由拓扑排序化为合法的拓扑序列。
拓展：
1. 可以用在图中检验是否含有环，方法是拓扑排序后检查是否有未标记完的顶点。如果有，就说明有环，因为环使得不会有一个顶点入度为0。
2. 时间复杂度:
  邻接表： $O(n+m)$
  邻接矩阵： $O(n^2)$

例题： $【CodeVS】$ 2883 奇怪的梦境

分析：判断是否可以按下全部按钮就是判段有向图中是否存在环，使用拓扑排序可以判断。

Code

：

#include <iostream>
#include <cstdio>
using namespace std;
struct node{
    int v,next;//使用邻接表存边
}edge[25005];
int n,m,head[10005],cnt,deg[10005];
bool book[10005];
inline void add(int u,int v){
    cnt++;
    edge[cnt].v=v;
    edge[cnt].next=head[u];
    head[u]=cnt;
    return;
}
int main(){
    int a,b;
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++){
        scanf("%d%d",&a,&b);
        add(a,b);
        deg[b]++;
    }
    for (int i=1;i<=n;i++){
        int start=-1;
        for (int j=1;j<=n;j++)
            if (!book[j]&&deg[j]==0){
                start=j;
                book[j]=true;
                break;
            }
        if (start==-1){
            cout <<"T_T"<<endl<<n-i+1<<endl;
            return 0;
        }
        for (int j=head[start];j!=0;j=edge[j].next)
            deg[edge[j].v]--;
    }
    cout <<"o(∩_∩)o"<<endl;
    return 0;
}

3. 最短路

单源最短路 $（Single-Source　Shortest　Paths）$ ,对于给定带权图（有向或无向），计算从源点 $s$ 到其它所有顶点的最短路径。
- “三角形性质”：设源点s到u, v最短路径长度分别为 $dis[u], dis[v]，u$ 与 $v$ 间距离为 $len[u][v]$ ，则有： $dis[u] + len[u][v] >= dis[v]$ 。
- 松弛：若在处理过程中，有两点 $u, v$ 不满足“三角形性质”，则可作改进：
  CPP
  if (dis[u] + len[u][v] < dis[v]) dis[v] = dis[u] + len[u][v];
- $Dijkstra$ 算法:
  - 算法：将图 $G$ 中顶点分为两个集合 $A$ , $B$ ， $A$ 由已求出最短路的顶点组成， $B$ 由其他顶点组成，初始时 $A$ 为空，记源点 $s$ 到每个点最短路径为 $dis[v]$ ，初始时 $dis[s] = 0$ ，其余点 $dis[v] = INF$ 。
    1. 从 $B$ 集合中取出一个当前距离 $s$ 最近的点 $v$
    2. 将 $v$ 从 $B$ 中剔除、加入 $A$ 集合，并对与 $v$ 相邻的顶点试作松弛
    3. 若 $A = V$ ，则算法结束，否则转至第1步。
  - 伪代码：
  CPP
  void dijkstra(int s){ 置dis初值; 循环n次{ 找到B集合中dis最小的点v; 将v从B中剔除、加入A; 用v对其相邻点试作松弛; } }
  - 时间复杂度
    1. $O(n^2)$ ：使用循环确定松弛顶点。
    2. $O((n+m)\log m)$ ：使用优先队列。
  - 对象：
    1. 有向图、无向图（无向图看做两点两条有向边）
    2. 有环或无环
    3. 不可有负权边
- $Bellman-Ford$ 算法
  - 算法：对每条边 $(u,v)$ ，进行松弛： $dis[v]=\min⁡(dis[v],dis[u]+dis(u,v))$ ，共循环 $n-1$ 次。
  - 时间复杂度： $O(nm)$
  - 对象：相比 $Dijkstra$ 算法可出现负权值、负环。
  - 扩展：
    - 判断负权环：最后判断是否存在边 $(u,v)$ ，使得 $dis[u]+dis(u,v)<dis[v]$ 。
- $SPFA$ 算法 $(Shortest　Path　Faster　Algorithm)$ ， $Bellman-Ford$ 算法的一种队列改进:
  - 优化：
    1. 采用队列存放用来更新其它点dis值的点
    2. 当一个点的 $dis$ 值被更新时，就将它加入队列
    3. 如果队列中已有这个点，则不用加入
  - 时间复杂度：最坏 $O(nm)$ ，平均 $O(m)$
多源最短路 $（Multiple-Source　Shortest　Paths）$ ：对于给定带权图（有向或无向），计算所有顶点间两两最短路径。
- $Floyd$ 算法
  - 算法：有一些 $dp$ 的思想->_<-， $f_k[i][j]$ 表示从 $i$ 到 $j$ 只经过前 $k$ 个点的最短路径。初始状态： $f_0[i][i]=0$ , $f_0[i][j]=(u,v)\in E?dis(u,v):INF$ 。
    - 转移方程： $f_k [i][j]=min⁡(f_{k-1} [i][j],f_{k-1} [i][k]+f_{k-1} [k][j])$ ， $f_n$ 即所求。
    - $Floyd$ 算法**核心代码**：
      for (int k = 1; k <= n; k++) for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
    - 时间复杂度： $O(n^3)$

总结

今天的考试有点难，或者说码量比较大，说明我还是太菜了QAQ