算法: dijkstra

· · 个人记录

适用范围

dijkstra 是一种求最短单元路径的算法。

使用过程中，需要保证 dijkstra 所求的图为非负权图。

实现方法

dijkstra 采用的是一种类似贪心的策略。

下面是主要步骤：

  1. 用一个 ans_i 记录 从出发点到 i 点的最小权值，一开始所有的 ans 均设为 INF 。
  2. 找出当前 ans 数组最小且没有确定的点 i ,把他标为确定点。
  3. 把从 i 出发的路径比如从 i 到 j 的都更新 ans_j ,既： ans_j=\min(ans_j,ans_i+road_{i,j})

其中 road_{i,j}表示从 i 到 j 的路径权值。

  1. 重复 2,3 操作，直到所有点都被标记为止。

  2. 输出答案。

举个例子，比如看这张无向非负权图：

从 A 出发，我们先把 A 标记为确定点，用蓝色表示。

然后变成了这样：

请原谅我不想重新画图

此时的 ans 记录 点 A , B , C , D , E 分别表示 : 0 , INF , INF , INF ,INF。

然后我们进行操作3：

然后此时 ans 记录 点 A , B , C , D , E 分别表示： 0, 3 , 4 , INF , INF 。

然后进行操作2，把 B 标成确定点，变成了这样：

越来越丑了

此时更新与 B 有直接连接且不确定的点 C , D , E 。

重点是如何更新 ans_C ,根据上面的转移方程有：

ans_C=\min(ans_C,ans_B+road_{B,C})

所以更新后的 ans_C 还是原来的 4 。

现在的此时的 ans 记录 点 A , B , C , D , E 分别表示 : 0，3 ，4 ，6 ，7 。

然后重复这样的算法，不难得到最后的ans 记录 点 A , B , C , D , E 分别表示 :0 ，3 ，4 ，9 ，10 。

请原谅我不想再画图了

输出即可。

可以发现 dijkstra 的时间复杂度竟高达:O(n^2)！朴素

但是观察步骤2，发现他可以用堆优化，没有学过堆优化（优先队列）的小伙伴戳这里。

用一个 pair 的优先队列，前数记录路程，后数记录编号，一旦这个编号的路程发生改变，就把新路程加上编号一起压进队列。

然后还有一个存边的优化,具体代码如下

void add(int from,int to,int times){
    l++;
    start[l]=from;
    end[l]=to;
    power[l]=times;
    last[l]=same[from];
    same[from]=l;
}

然后你发现你就莫名其妙的学会了 dijkstra !

然后给个参考代码吧（仅供参考，有反例找我）

#include<cstdio>
#include<iostream>
#include<cmath>
#include<queue>
using namespace std;
#define ll long long
priority_queue< pair<int,int> > q;//q前面记录长度，后面记录编号
const int MAXN=2e5+5;
const int MR=1e5+5;
int start[MAXN];//记录起点
int end[MAXN];//记录终点
ll power[MAXN];//记录权
int same[MAXN];//记录上一个与其同起点的
int last[MAXN];//记录上一个起点为i的
ll ans[MR];//记录答案
bool yes[MR];//是否白了
int l=0;
int n,m,s;
int u,v,w;
void add(int from,int to,int times){
    l++;
    start[l]=from;
    end[l]=to;
    power[l]=times;
    last[l]=same[from];
    same[from]=l;
}
int main(){
    cin>>n>>m>>s;
    for(int i=1;i<=m;i++){
        cin>>u>>v>>w;
        add(u,v,w);
    }
    q.push(make_pair(0,s));
    for(int i=1;i<=n;i++)
        ans[i]=2e9;
    ans[s]=0;
    while(!q.empty()){
        int num=q.top().second;//记录最优秀点编号
        q.pop();//删除堆顶元素
        if(yes[num]) continue;
        yes[num]=1;
        for(int i=same[num];i!=0;i=last[i]){
            if(ans[num]+power[i]<ans[end[i]]){
                ans[end[i]]=ans[num]+power[i];
                q.push(make_pair(-ans[end[i]],end[i]));
            }
        }
    }
    for(int i=1;i<=n;i++)
        cout<<ans[i]<<" ";
    return 0;
}

二进制运算问题

前言

在信息竞赛当中，二进制是一个热门考点。比如说刚考过的 \text{NOIp2021\ T2} 就是一种二进制问题。本文将主要讲二进制问题的处理方式与题型的归纳。

前铺知识：与、或、异或运算的意义。

问题类型

题型一、包含与或者或的问题

这类问题我们需要知道与和或的一些基本性质。比如一个位上是 1，无论怎么或这个位上都是 1；位运算对于每一个数位是互不影响的等。我们直接讲几道例题

例题

P2114 [NOI2014] 起床困难综合症
  • 选择一个 [0,m] 之间的整数 k。
  • 最大化 k 依次经过 n 次位运算（\text{and,or,xor} 之一）后得到的结果。
  • n\leq10^5,m\leq10^9

我们要知道“最大化”一个数，我们要让他二进制下排在前面的 1 尽可能的多。于是我么可以先用一个 u=0,v=\text{INT\_MAX} 来带入最终得到的结果。i 从 63 扫到 0，如果第 i 位上 u 是 1 就直接取，否则如果 v 是 1 并且再取总和不超过 m 就取，否则都不取即可。

展示一下代码

#include<iostream>
using namespace std;
int n,m,t;
string op;
int u=0,v=(1<<62)-1;//二进制转换 全0,全1 
int ans=0;
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>op>>t;
        if(op[0]=='A') u&=t,v&=t;
        else if(op[0]=='X') u^=t,v^=t;
        else u|=t,v|=t; //模拟 u,v 
    }
    for(int i=30;i>=0;i--){
        if((u>>i)&1)
            ans+=(1<<i);//更新答案 
        else if((v>>i)&1&&m>=(1<<i))
            ans+=(1<<i),m-=(1<<i);//m 记录剩余 
    }
    cout<<ans;
    return 0;
}
CF1557C Moamen and XOR

  • 给定 n,k 求一个长度为 n 的数列 a_i 满足：

    • a_i<2^k
    • a_1\& a_2\dots \&a_n\geq a_1⊕a_2\dots ⊕a_n

  • 本题多测，t\leq5;n,k\leq2\times 10^5

还是同上面一样的，我们希望 \&_1^na_i 大。那么他肯定要么和右边相等，要么有某一位 k，前面都相等，左边是 1，右边是 0。然而左式是 1 是很困难的，这要求所有的 a_i，第 k 位上都是 1。我们分类讨论一下

n 为偶数

此时第 k 位上右式是 0，那么剩下随便取即可。这种情况下答案是：

\sum_{i=1}^k (\text{前}k-i\text{位xor=and的方案数}\times 1\times 2^{(i-1)k}+(\text{xor=and 的方案数}) =(\sum_{i=1}^k(C_n^0+C_n^2\dots+C_n^{n-2})^{k-i}\times 2^{(i-1)k})+(C_n^0+C_n^2\dots+C_n^{n-2})^k =(\sum_{i=1}^k(2^{n-1}-1)^{k-i}\times 2^{(i-1)k})+(2^{n-1}-1)^k
n 为奇数