Day 1 高中部寒假集训
浏览 1237 | 评论 1 | 字数 4283
Snowflake_Pink
2019年01月23日
  • 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],u$与$v$间距离为 $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$, $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步。
        • 伪代码:
        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)$
    1. 多源最短路$(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

    本文作者:Snowflake_Pink
    本文链接:https://snowflake.pink/archives/7/
    最后修改时间:2020-04-13 11:18:33
    本站未注明转载的文章均为原创,并采用 CC BY-NC-SA 4.0 授权协议,转载请注明来源,谢谢!
    评论
    评论会由可爱的 AI 来审核鸭~
    textsms
    支持 Markdown 语法
    email
    link
    评论列表
    已有 1 条评论
    学校卖鸡鸡
    2020-07-11 13:32
    老哥冒昧问一下你上几年级 ୧(๑•̀⌄•́๑)૭