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. 最短路

  1. 单源最短路 (Single-Source Shortest Paths), 对于给定带权图(有向或无向),计算从源点s 到其它所有顶点的最短路径。

    • “三角形性质”:设源点 s 到 u, v 最短路径长度分别为 dis[u], dis[v],uv 间距离为 len[u][v],则有:dis[u] + len[u][v] >= dis[v]

    • 松弛:若在处理过程中,有两点 u, v 不满足“三角形性质”,则可作改进:

      if (dis[u] + len[u][v] < dis[v])
       dis[v] = dis[u] + len[u][v];
    • Dijkstra算法:

      • 算法:将图 G 中顶点分为两个集合 A, BA 由已求出最短路的顶点组成,B由其他顶点组成,初始时 A 为空,记源点 s 到每个点最短路径为dis[v],初始时dis[s] = 0,其余点dis[v] = INF
        1. B 集合中取出一个当前距离 s 最近的点v
        2. vB中剔除、加入 A 集合,并对与 v 相邻的顶点试作松弛
        3. A = V,则算法结束​,否则转至第 1 步。
      • 伪代码:
      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)
  2. 多源最短路(Multiple-Source Shortest Paths):对于给定带权图(有向或无向),计算所有顶点间两两最短路径。

    • Floyd算法

      • 算法:有一些 dp 的思想 ->_<-,f_k[i][j]表示从 ij只经过前 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

本文链接:https://snowflake.pink/archives/7/
This blog is under a CC BY-NC-ND 4.0 Unported License