高中部寒假集训Day1

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$:

      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
      33
      34
      35
      36
      37
      38
      39
      40
      41
      #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],u$与$v$间距离为 $len[u][v]$,则有:$dis[u] + len[u][v] >= dis[v]$。

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

      1
      2
      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步。
      • 伪代码:
      1
      2
      3
      4
      5
      6
      7
      8
      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]$表示从$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$算法核心代码

          1
          2
          3
          4
          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

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×