踩了很多坑，修修补补才搭起来，写一篇教程以防自己以后再遇到各种各样的问题

一.准备工作

1.魔法上网

2.github账号，(gitee理论上也可以，没试过)

3.一台可以开关机的电脑和一颗有探索精神的大脑

二.安装软件

1.安装git

​ windows：到git官网上下载，之后会有一个Git Bash的命令行工具，以后就用这个工具来使用git。

2.安装nodejs

​ windows：nodejs选择LTS版本就行了。

安装完之后试着用cmd或git bash输入指令检查一遍有没有安装成功

node -v
npm -v

3.安装hexo（博客框架）

​ 在硬盘任意地方新建一个文件夹，用来存放你的博客本地文件和后续写的文章等等，在这个文件夹下右键选择git bash打开

输入指令

npm install -g hexo-cli

接着初始化文件夹

hexo init <你的文件夹名字>
例如文件夹名为myblog:
hexo init myblog

安装npm

npm install

这时你的文件夹内会出现很多文件，这些就是hexo建站所依赖的各种包，但还没完

hexo g //生成静态文件
hexo s //启动服务

这时git base窗口会出现一串网址：http://localhost:4000 ，这时代表本地建站成功，打开浏览器输入网址可以看到网站默认主页

![image-20201220204625063](https://i-blog.csdnimg.cn/blog_migrate/e6604cfe09af32577d116c18aa7a14c1.png

到这一步已经实现一半了，但目前只能在本地访问你的博客，怎么让他在互联网上访问呢？

三.部署github

1.创建仓库

​ 打开你的github，创建一个和你用户名相同的仓库，后面加.github.io，只有这样，将来要部署到GitHub page的时候，才会被识别，也就是xxxx.github.io，其中xxx就是你注册GitHub的用户名。

2.生成所需的ssh

在git base中输入

git config --global user.name "yourname"
git config --global user.email "youremail"

按提示一路回车，之后输入

ssh-keygen -t rsa -C "youremail"

​ 复制出现的以ssh开头的字符串，接下来回到github中，点击右上角头像里的setting选项，找到SSH keys，选择New SSH key，随便起一个title，在下方key中输入你刚刚复制的密钥，回到git base，输入

ssh -T git@github.com

​ 检查是否配置成功，当出现successfully字样代表成功，但还有最后一步！

3.发布

还是git base窗口，输入

npm install hexo-deployer-git

这个插件用于把生成好的静态页面上传到 GitHub Pages 仓库，接着要告诉hexo 你的文件要发布到哪个仓库

点击根目录下的_config.yaml文件，翻到最下边，修改以下指令

deploy:
  type: git
  repo: git@github.com:xxxxxx/xxxxxx.github.io.git
  branch: main

保存，回到git base中，输入

hexo g && hexo d

等待上传文件，之后输入https://你的用户名.github.io，你会发现大功告成！

1.题意

给你一个有起点和终点的二维迷宫。你的任务是找出从起点到达终点的最快方法。最快的方法是走最少的步数，其中一步是向左、向右、向上或向下走。当然，你不能穿墙而过。

不过，也有一个问题：如果向同一方向迈出三步以上，就会失去平衡而摔倒。因此，禁止向同一方向连续走三步以上。向右走三步，然后向左走一步，再向右走三步是可以的。这与向右走五步的效果相同，但速度较慢。

2.分析

典型的dp问题，题目中提到不能连续一个方向走四步，所以转移方程需要考虑到方向和沿着当前方向已经走了几步，很容易得到dp数组的形式$$dp[N][N][4][4]$$，接着考虑转移的方式，一般求最短路的题目bfs和dfs均可，但在这道题中，由于bfs沿着步数的大小开始拓展，第一次遍历到终点既是最短路径，如果选择dfs，可能在某种状态第一次的遍历中没有得到最优答案，因此选用bfs

3.代码实现

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> PII;
const int N = 2e5 + 10;
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
void solve() {
    int n,m;
    cin>>n>>m;
    int x,y;
    int nx;
    int ny;
    vector<vector<char>>a(n+1,vector<char>(m+1));
    vector<vector<vector<vector<int>>>>dp(n+1,vector<vector<vector<int>>>(m+1,vector<vector<int>>(4,vector<int>(4))));
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
            if(a[i][j]=='S') x=i,y=j;
            if(a[i][j]=='T') nx=i,ny=j;
        }
    }
    queue<array<int,4>>q;
    q.push({x,y,0,0});
    while(!q.empty()){
        auto [x,y,dir,step]=q.front();
        q.pop();
        for(int i=0;i<4;i++){
            if(a[x+dx[i]][y+dy[i]]=='#') continue;
            if(i==dir){
                if(step==3||dp[x+dx[i]][y+dy[i]][i][step+1]) continue;
                q.push({x+dx[i],y+dy[i],dir,step+1});
                dp[x+dx[i]][y+dy[i]][i][step+1]=dp[x][y][i][step]+1;
                continue;
            }
            if(dp[x+dx[i]][y+dy[i]][i][1]) continue;
            q.push({x+dx[i],y+dy[i],i,1});
            dp[x+dx[i]][y+dy[i]][i][1]=dp[x][y][dir][step]+1;
        }
    }
    int ans=1e9;
    for(int i=0;i<4;i++){
        for(int j=0;j<4;j++){
            if(dp[nx][ny][i][j]){
                ans=min(ans,dp[nx][ny][i][j]);
            }
        }
    }
    if(ans==1e9) ans=-1;
    cout<<ans<<endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T=1;
    //cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

一.题意

题目

给你一个长度为 $n$ 的数组 $a$ 和 $q$ 查询 $l$ , $r$ .

请为每个查询找出最大可能的 $m$ ，使得所有元素 $a_l$ , $a_{l+1}$ , …, $a_r$ 都等于 $m$ 的模。换句话说， $a_l \bmod m = a_{l+1} \bmod m = \dots = a_r \bmod m$ ，其中 $a \bmod b$ - 是 $a$ 除以 $b$ 的余数。特别的，当 $m$ 可以是无限大时，请打印 $0$ 。

输入

第一行包含一个整数 $t$ （ $1 \le t \le 10^4$ ）–测试用例数。( $1 \le t \le 10^4$ ) - 测试用例的数量。

每个测试用例的第一行包含两个整数 $n$ , $q$ ( $1 \le n, q \le 2\cdot 10^5$ ) - 数组长度和查询次数。

每个测试用例的第二行包含 $n$ 个整数 $a_i$ ( $1 \le a_i \le 10^9$ ) - 数组的元素。

在每个测试用例的后续 $q$ 行中，提供了两个整数 $l$ , $r$ （ $1 \le l \le r \le n$ ）–查询范围。

保证所有测试用例中 $n$ 的总和不超过 $2\cdot 10^5$ ， $q$ 的总和不超过 $2\cdot 10^5$ 。

二.思路

若一个区间内所有数字对m同余，那这些数字在减去余数后，该区间的GCD应等于m，那么反过来若想求m的值，只需对该区间求差值，并维护差值的gcd即可，k可以使用线段树中的区间查询功能完成维护gcd，以下是完整代码

三.代码实现

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> PII;
const int N = 4e5+10;
struct tree{
    int val;
    int l,r,sum;
}tr[N*4];
int a[N],b[N];
void pushup(int p){
    tr[p].val=__gcd(tr[p*2].val,tr[p*2+1].val);
}
void build(int p,int l,int r){
    tr[p].l=l,tr[p].r=r;
    if(l==r){
        tr[p].val=a[r];
        return;
    }
    int mid=l+r>>1;
    build(p*2,l,mid);
    build(p*2+1,mid+1,r);
    pushup(p);
}
int query(int p,int l,int r,int ql,int qr){
    if(ql==l&&qr==r){
        return tr[p].val;
    }
    int mid=l+r>>1;
    if(qr<=mid) return query(p*2,l,mid,ql,qr);
    else if(ql>mid) return query(p*2+1,mid+1,r,ql,qr);
    else return __gcd(query(p*2,l,mid,ql,mid),query(p*2+1,mid+1,r,mid+1,qr));
}
void solve() {
    int n,q;
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        cin>>b[i];
        a[i]=abs(b[i]-b[i-1]);
    }
    build(1,1,n);
    while(q--){
        int l,r;
        cin>>l>>r;
        if(l==r){
            cout<<0<<' ';
            continue;
        }
        cout<<query(1,1,n,l+1,r)<<' ';
    }
    cout<<endl;
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

求因数

1.暴力枚举法

一般来说，因数分解常用方法为暴力枚举，其时间复杂度为$O(\sqrt{n}$)

vector<int> factor(int n) {
    vector<int> factors;
    for (int i = 1; i * i <= n; i++) {
       if(n%i==0){
            if(n/i!=i){
                factors.push_back(i);
                factors.push_back(n/i);
            }
            else factors.push_back(i);
       }
    }
    return factors;
}

这种方法代码简单，无需预处理，适用于少量查询，但当需要查询的数字过多，暴力法则变得不那么优秀，需引入其他更优解

2.预计算所有数的因数表

时间复杂度$O(nlog{n})$，单次查询$O(1)$

vector<int>factors[N];
void factor(){
    for(int i=1e6;i>=1;i--){
        for(int j=i;j<=1e6;j+=i){
            factors[j].push_back(i);
        }
    }
}

3.SPF 线性筛

核心思路：

1. 使用 SPF（Smallest Prime Factor）线性筛，预计算 spf[i]（最小质因子）。
2. 使用 SPF 快速分解 n 的质因子，时间复杂度 O(log n)。
3. 枚举所有可能的因数，利用回溯法生成所有因数，时间复杂度 O(d)（d 为因数个数，通常远小于 n）。

时间复杂度分析：

1. 预处理 SPF 线性筛：O(n)（一次性计算）。

2. 单次查询

   • 因数分解：O(log n)（因为 spf[n] 查询次数至多 log n）。
   • 生成所有因数：O(d)，其中 d 是因数个数，通常 $d = O(n^{1/3})$。

#include <iostream>
#include <vector>
#include <set>

using namespace std;

const int MAXN = 1000000; // 预处理范围
vector<int> spf(MAXN + 1); // 存储最小质因子

// **线性筛** 预计算 SPF
void sieve_spf(int N) {
    for (int i = 1; i <= N; i++) spf[i] = i;  // 先设为自身
    for (int i = 2; i <= N; i++) {
        if (spf[i] == i) {  // i 是质数
            for (int j = i * 2; j <= N; j += i) {
                if (spf[j] == j) spf[j] = i; // 记录最小质因子
            }
        }
    }
}

// **用 SPF 进行因数分解**
vector<pair<int, int>> factorize(int n) {
    vector<pair<int, int>> factors; // 记录 (质因子, 指数)
    while (n > 1) {
        int prime = spf[n], count = 0;
        while (n % prime == 0) {
            n /= prime;
            count++;
        }
        factors.push_back({prime, count});
    }
    return factors;
}

// **基于质因子分解，枚举所有因数**
void generate_divisors(int index, int current, vector<pair<int, int>>& factors, vector<int>& divisors) {
    if (index == factors.size()) {
        divisors.push_back(current);
        return;
    }
    int prime = factors[index].first, exponent = factors[index].second;
    for (int i = 0; i <= exponent; i++) {
        generate_divisors(index + 1, current, factors, divisors);
        current *= prime;
    }
}

// **查询 n 的所有因数**
vector<int> get_divisors(int n) {
    vector<pair<int, int>> factors = factorize(n); // O(log n) 分解
    vector<int> divisors;
    generate_divisors(0, 1, factors, divisors); // O(d) 生成因数
    sort(divisors.begin(), divisors.end()); // 让因数按顺序输出
    return divisors;
}

int main() {
    sieve_spf(MAXN); // 预计算最小质因子

    int num;
    cout << "输入要查询的数: ";
    cin >> num;

    if (num <= 0 || num > MAXN) {
        cout << "数值超出范围!\n";
        return 1;
    }

    vector<int> divisors = get_divisors(num);
    cout << "所有因数: ";
    for (int d : divisors) {
        cout << d << " ";
    }
    cout << endl;

    return 0;
}

总结

一.查询区间[l,r]第k大

离散化版本

#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 5;
struct tree{
    int ch[2];
    int s;
}tr[N<<5];
int idx=0;
int root[N];
vector<int>v;
int getid(int x){
    return lower_bound(v.begin(),v.end(),x)-v.begin()+1;
}
void build(int &x,int l,int r){
    x=++idx;
    if(l==r) return;
    int m=(l+r)>>1;
    build(tr[x].ch[0],l,m);
    build(tr[x].ch[1],m+1,r);
}
void modify(int x,int &y,int l,int r,int v){
    y=++idx;
    tr[y]=tr[x];
    tr[y].s++;
    if(l==r) return;
    int m=(l+r)>>1;
    if(v<=m) modify(tr[x].ch[0],tr[y].ch[0],l,m,v);
    else modify(tr[x].ch[1],tr[y].ch[1],m+1,r,v);
}
int query(int x,int y,int l,int r,int val){
    if(l==r) return l;
    int m=(l+r)>>1;
    int s=tr[tr[y].ch[0]].s-tr[tr[x].ch[0]].s;
    if(val<=s) return query(tr[x].ch[0],tr[y].ch[0],l,m,val);
    else return query(tr[x].ch[1],tr[y].ch[1],m+1,r,val-s); 
}
void solve(){
    int n, m;
    cin >> n >> m;
    vector<int> a(n+1);
    for (int i = 1; i <= n; i++){
        cin >> a[i];
        v.push_back(a[i]);
    }
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    int vn = v.size();
    build(root[0], 1, vn);
    for (int i = 1; i <= n; i++)
        modify(root[i-1], root[i], 1, vn, getid(a[i]));
    
    for (int i = 1; i <= m; i++){
        int l, r, k;
        cin >> l >> r >> k;
        int id = query(root[l-1], root[r], 1, vn, k) - 1;
        cout << v[id] << endl;
    }
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T=1;
    //cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

二.查询区间[l,r]中有多少个数字小于a[k]

#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 5;
struct tree{
    int ch[2];
    int s;
}tr[N>>5];
int idx=0;
int root[N];
void build(int &x,int l,int r){
    x=++idx;
    if(l==r) return;
    int m=(l+r)>>1;
    build(tr[x].ch[0],l,m);
    build(tr[x].ch[1],m+1,r);
}
void modify(int x,int &y,int l,int r,int v){
    y=++idx;
    tr[y]=tr[x];
    tr[y].s++;
    if(l==r) return;
    int m=(l+r)>>1;
    if(v<=m) modify(tr[x].ch[0],tr[y].ch[0],l,m,v);
    else modify(tr[x].ch[1],tr[y].ch[1],m+1,r,v);
}
int query(int x,int y,int l,int r,int val){
    if(r<=val) return tr[y].s-tr[x].s;
    int m=l+r>>1;
    if(val<=m){
        return query(tr[x].ch[0],tr[y].ch[0],l,m,val);
    }
    else{
        return query(tr[x].ch[0],tr[y].ch[0],l,m,val)+query(tr[x].ch[1],tr[y].ch[1],m+1,r,val);
    }
}
void solve(){
    int n,m;
    cin>>n>>m;
    build(root[0],1,n);
    vector<int>a(n+1);
    for(int i=1;i<=n;i++){
        cin>>a[i];
        modify(root[i-1],root[i],1,n,a[i]);
    }
    for(int i=1;i<=m;i++){
        int num,l,r;
        cin>>l>>r>>num;
        cout<<query(root[l-1],root[r],1,n,a[num])+l-1<<endl;
    }
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T=1;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

题意

伯纳德喜欢去看鲁道夫，但他总是迟到。问题是伯纳德需要乘坐渡船过河。鲁道夫决定帮助他的朋友解决这个问题。

河流是一个 $n$ 行 $m$ 列的网格。第 $i$ 行和第 $j$ 列的交点包含对应单元格的深度 $a_{i,j}$。所有的 第一列 和 最后一列 的单元格对应河岸，所以它们的深度为 0。

鲁道夫可以选择某一行 $(i,1), (i,2), \ldots, (i,m)$ 来建造一座桥梁。在这一行的每个单元格上，他可以安装一个桥梁支撑。安装支撑的成本为该单元格的深度加1，即 $a_{i,j}+1$。支撑必须安装满足以下条件：

1. 必须在单元格 $(i,1)$ 安装支撑；
2. 必须在单元格 $(i,m)$ 安装支撑；
3. 任意相邻支撑之间的距离必须 不超过 $d$。支撑之间的距离定义为 $|j_1 - j_2| - 1$，其中 $(i, j_1)$ 和 $(i, j_2)$ 是两个支撑。

建造一座桥梁很无聊。因此，鲁道夫决定在 连续的 k 行 上建造桥梁，即选择某些行 $i$ （$1 \leq i \leq n - k + 1$），并独立地在第 $i$ 行到第 $i + k - 1$ 行上建造桥梁。帮助鲁道夫 最小化 安装支撑的总成本。

思路

很明显的dp问题，设dp[i]为在截至到i号位置，且i号位置建造支撑的最小花费，需要从[i-d-1,i-1]的位置这个区间中挑一个最优的位置转移过来，这里直接用单调队列维护合法区间内成本最小的位置。

解出每一行的dp[m]，计算前缀和，枚举出一个最优区间即可。

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) (x).begin(), (x).end()
const int N = 2e5 + 10;
int a[110][N], b[N], ans[N];
void solve() {
    int n,m,k,d;
    cin>>n>>m>>k>>d;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
        }
    }
    vector<int>ans;
    for(int i=1;i<=n;i++){
        deque<int>dq;
        vector<int> dp(m+10);
        dp[1]=1;
        dq.push_back(1);
        for(int j=2;j<=m;j++){
            if(!dq.empty()&&j-dq.front()-1>d) dq.pop_front();
            dp[j]=dp[dq.front()]+a[i][j]+1;
            while(!dq.empty()&&dp[j]<=dp[dq.back()]) dq.pop_back();
            dq.push_back(j);
        }

        ans.push_back(dp[m]);
    }
    int res=1e9;
    for(int i=1;i<ans.size();i++) ans[i]+=ans[i-1];
    res=ans[k-1];
    for(int i=k;i<ans.size();i++) res=min(res,ans[i]-ans[i-k]);
    cout<<res<<endl;
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T=1;
    cin >> T;
    while (T--) solve();
    return 0;
}

ICPC第13届山东省赛

题面

思路

模拟一下拓扑序列的思想，把需求抽象成一种边，每一种尚未满足的需求都是一个入度，按顺序把解决的需求对应的项目入度减一，定义一个队列，把所有入度为0的项目全部加进去，当这个队列为空时，所有可解决的项目均被记录，退出循环输出答案即可

#include<bits/stdc++.h>
using namespace std;
#define int long long
constexpr int inf32 = 1e9 + 7;
constexpr int inf64 = 1e9 + 7;
const int N=2e5;
typedef pair<int,int> PII;
map<int,int>have;                                           //当前有的员工的对应数量
map<int,priority_queue<PII,vector<PII>,greater<PII>>> need; //所有需求，及对应的任务标号，用优先队列存
vector<PII>reward[N];                                       //解决某个任务之后获得的奖励人数
int din[N];
int x,n;
int ans;                    
void solve(){
    cin>>x;
    for(int i=1;i<=x;i++){
        int a,b;
        cin>>a>>b;
        have[a]+=b;
    }
    cin>>n;
    queue<int>accord;
    for(int i=1;i<=n;i++){
        int m1,m2;
        cin>>m1;                            //第i项目有m1个需求
        for(int j=1;j<=m1;j++){     
            int a,b;    
            cin>>a>>b;    
            if(have[a]<b){                  //只有当前的需求尚未被满足，才增加一个入度
                din[i]++;
                need[a].push({b,i});        //员工标号为a的增加一个数量为b的需求，该需求对因项目i
            }    
        }
        cin>>m2;                    
        for(int j=1;j<=m2;j++){
            int a,b;
            cin>>a>>b;
            reward[i].push_back({a,b});     //reward[i]表示解决项目i后获得的所有奖励
        }
        if(!din[i]) accord.push(i);         //若入度为0则已经被解决
    }
    while(!accord.empty()){                 //已经被解决的条件
        int idx=accord.front();
        accord.pop();
        ans++;
        for(auto [id,num]:reward[idx]){     //遍历得到的新员工可以解决的需求，若出现新入度为0的点，加入队列
            have[id]+=num;
            while(!need[id].empty()){
                if(need[id].top().first<=have[id]){
                    din[need[id].top().second]--;
                    if(din[need[id].top().second]==0) accord.push(need[id].top().second);
                    need[id].pop();
                }
                else break;
            }
        }
    }
    cout<<ans<<endl;
}
signed main(){
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
}

正则表达式

题目背景

小Z童鞋一日意外的看到小X写了一个正则表达式的高级程序，这个正则表达式程序仅仅由字符“0”,“1”，“.”和“*”构成，但是他能够匹配出所有在OJ上都AC的程序的核心代码！小Z大为颇感好奇，于是他决定入侵小X的电脑上去获得这个正则表达式的高级程序。

题目描述

在 Internet 网络中的每台电脑并不是直接一对一连通的，而是某些电脑之间存在单向的网络连接，也就是说存在 $A$ 到 $B$ 的连接不一定存在 $B$ 到 $A$ 的连接，并且有些连接传输速度很快，有些则很慢，所以不同连接传输所花的时间是有大有小的。另外，如果存在 $A$ 到 $B$ 的连接的同时也存在 $B$ 到 $A$ 的连接的话，那么 $A$ 和 $B$ 实际上处于同一局域网内，可以通过本地传输，这样花费的传输时间为 $0$。

现在小 Z 告诉你整个网络的构成情况，他希望知道从他的电脑（编号为 $1$），到小 X 的电脑（编号为 $n$）所需要的最短传输时间。

输入格式

第一行两个整数 $n,m$，表示有 $n$ 台电脑，$m$ 个连接关系。

接下来 $m$ 行，每行三个整数 $u,v,w$，表示从电脑 $u$ 到电脑 $v$ 传输信息的时间为 $w$。

输出格式

输出文件仅一行为最短传输时间。

样例输入

5 5
1 2 1
2 3 6
3 4 1
4 2 1
3 5 2

样例输出

3

实现

​ 简述一下题目，存在一有向有环图，在任意强连通块里面的路径权值均可看作0，求1号点到n号点最短路。

​ 在tarjan缩点得到的有向无环图上跑一遍Dijkstra即可得到答案

#include<bits/stdc++.h>
using namespace std;
#define int long long
constexpr int inf32 = 1e9 + 7;
constexpr int inf64 = 1e9 + 7;
const int N=2e5;
struct tree{
    int to;
    int w;
};
vector<tree>e[N];
vector<tree>e_dist[N];
int cnt,idx,num;
int dfn[N],instk[N],low[N];
int belong[N];
stack<int> stk;
vector<int>scc[N];
int dout[N];
typedef pair<int,int> PII;
void tarjan(int u){
    dfn[u]=low[u]=++idx;
    stk.push(u);
    instk[u]=1;
    for(auto V:e[u]){
        int v=V.to;
        if(!dfn[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(instk[v]){
            low[u]=min(low[u],dfn[v]);
        }
    }
    if(low[u]==dfn[u]){
        cnt++;
        int v;
        do{
            v=stk.top();
            stk.pop();
            instk[v]=0;
            scc[cnt].push_back(v);
            belong[v]=cnt;
        }while(v!=u);
    }
}
int dist[N];
void dijkstra(int u){
    priority_queue<PII,vector<PII>,greater<PII>> q;
    dist[u]=0;
    q.push({0,u});
    while(!q.empty()){
        auto [distance,k]=q.top();
        q.pop();
        for(auto V:e_dist[k]){
            int v=V.to;
            int w=V.w;
            if(dist[v]>distance+w){
                dist[v]=distance+w;
                q.push({dist[v],v});
            }
        }
    }
}
void solve(){
    int n,m;
    cin>>n>>m;
    memset(dist,127,sizeof(dist));
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        e[u].push_back({v,w});
    }
    for(int i=1;i<=n;i++){
        if(!dfn[i]) tarjan(i);
    }
    for(int i=1;i<=cnt;i++){
        for(auto u:scc[i]){
            for(auto v:e[u]){
                e_dist[i].push_back({belong[v.to],v.w});
            }
        }
    }
    dijkstra(belong[1]);
    cout<<dist[belong[n]]<<endl;
}
    
signed main(){
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
}

[NOIP2013 提高组] 货车运输

题目背景

NOIP2013 提高组 D1T3

题目描述

A 国有 $n$ 座城市，编号从 $1$ 到 $n$，城市之间有 $m$ 条双向道路。每一条道路对车辆都有重量限制，简称限重。

现在有 $q$ 辆货车在运输货物， 司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。

输入格式

第一行有两个用一个空格隔开的整数 $ n,m$，表示 A 国有 $ n$ 座城市和 $m$ 条道路。

接下来 $m$ 行每行三个整数 $x, y, z$，每两个整数之间用一个空格隔开，表示从 $x $ 号城市到 $ y $ 号城市有一条限重为 $z$ 的道路。
注意： $x \neq y$，两座城市之间可能有多条道路 。

接下来一行有一个整数 $q$，表示有 $q$ 辆货车需要运货。

接下来 $q$ 行，每行两个整数 $x,y$，之间用一个空格隔开，表示一辆货车需要从 $x$ 城市运输货物到 $y$ 城市，保证 $x \neq y$

输出格式

共有 $q$ 行，每行一个整数，表示对于每一辆货车，它的最大载重是多少。
如果货车不能到达目的地，输出 $-1$。

样例输入 #1

4 3
1 2 4
2 3 3
3 1 1
3
1 3
1 4
1 3

样例输出 #1

3
-1
3

实现

​ 最初的想法是tarjan缩点，去环后倍增求最小值，仔细思考后发现是完全没有道理的，无法在多条路线里面找到最优的路线，所以转变为用生成树重构图确定唯一的路线后再去倍增求最小值

#include<bits/stdc++.h>
using namespace std;
#define int long long
constexpr int inf32 = 1e9 + 7;
constexpr int inf64 = 1e9 + 7;
const int N=2e5+10;
typedef pair<int,int> PII;
int n,m;
struct tree{
    int u,v,w;
    bool operator< (const tree &t) const{
        return w>t.w;
    }
}edge[N];
vector<PII>e[N];
int p[N],ans,cnt;
int find(int x){
    if(x!=p[x]) p[x]=find(p[x]);
    return p[x];
}
int per[N][32];
int val[N][32];
int dep[N];
int st[N];
void dfs(int u,int f){
    dep[u]=dep[f]+1;
    st[u]=1;
    for(auto [v,w]:e[u]){
        if(v==f) continue;
        per[v][0]=u;
        val[v][0]=w;
        dfs(v,u);
    }
}
void kruskal(){
    sort(edge+1,edge+1+m);          //根据边权排序，由大到小枚举
    for(int i=1;i<=m;i++){
        int x=find(edge[i].u);
        int y=find(edge[i].v);
        if(x!=y){                   //若父节点与子节点在同一集合则不可连边，否则出现环
            e[edge[i].u].push_back({edge[i].v,edge[i].w});
            e[edge[i].v].push_back({edge[i].u,edge[i].w});
            p[x]=y;
            ans+=edge[i].w;
            cnt++;                  //重构后的树点的个数加一
        }
    }
}
int query(int u,int v){             //倍增lca求路径最小值
    int ans=1e9;
    if(dep[u]>dep[v]) swap(u,v);
    int d=dep[v]-dep[u];
    for(int j=20;j>=0;j--){
        if(d&(1<<j)){
            ans=min(ans,val[v][j]);
            v=per[v][j];
        }
    }
    if(u==v){
        return ans;
    }
    for(int j=20;j>=0;j--){
        if(per[u][j]!=per[v][j]){
            ans=min(ans,min(val[u][j],val[v][j]));
            u=per[u][j];
            v=per[v][j];
        }
    }
    ans=min(ans,min(val[u][0],val[v][0]));
    return ans;
}
void solve(){
    //int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        edge[i]={u,v,w};
    }
    for(int i=1;i<=n;i++){
        p[i]=i;
    }
    kruskal();
    for(int i=1;i<=n;i++){
        if(!st[i]) dfs(i,0);
    }
    //dfs(1,0);
    for(int j=1;j<32;j++){          //构建st表
        for(int i=1;i<=n;i++){
            per[i][j]=per[per[i][j-1]][j-1];
            val[i][j]=min(val[i][j-1],val[per[i][j-1]][j-1]);
        }
    }
    int q;
    cin>>q;
    for(int i=1;i<=q;i++){
        int u,v;
        cin>>u>>v;
        if(find(u)!=find(v)){
            cout<<-1<<endl;
        }
        else{
            cout<<query(u,v)<<endl;
        }
    }
}    
signed main(){
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
}

题目描述

本题和$hard$难度的区别是，询问的次数有多次！

小红拿到了一棵树，她有多次询问，每次询问输入一条简单路径$x,y$，她想知道树上所有节点到该路径的最短路之和是多少，你能帮帮她吗？

定义节点到路径的最短路为：节点到路径上所有点的最短路中，值最小的那个。特殊的，如果节点在路径上，则最短路为0。

简单路径：从树上的一个节点出发，沿着树的边走，不重复地经过树上的节点，到达另一个节点的路径。

第一行输入两个正整数$n,q$，代表节点数量和询问次数。
接下来的$n-1$行，每行输入两个正整数$u,v$，代表节点$u$和节点$v$有一条边连接。
接下来的$q$行，每行输入两个正整数$x,y$，代表一次询问。
$1\leq n,q \leq 10^5$
$1\leq u,v,x,y \leq n$

输入

4 2
1 2
1 3
1 4
2 3
2 1

输出

1
2

实现

​

​ 并没有看懂关于所有点到链的距离和即所有点到左右端点的距离和加上链长的证明，但有了这个结论就比较好写了，比较板的换根dp求距离和加上倍增lca求链长。

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e6 + 10;
const int M = 5e3 + 10;
vector<int>e[N];
int V[N],f[N],Size[N];
bool st[N];
int dep[N],fa[N],par[N][33];
void up(int u){
    Size[u]=1;
    st[u]=1;
    for(int v:e[u]){
        if(st[v]) continue;
        fa[v]=u;
        par[v][0]=u;
        up(v);
        Size[u]+=Size[v];
        f[u]+=f[v];
    }
    f[u]+=Size[u]-1;
    st[u]=0;
}
void down(int u){
    st[u]=1;
    for(int v:e[u]){
        if(st[v]) continue;
        dep[v]=dep[u]+1;
        V[v]=V[u]+f[u]-f[v]+Size[1]-Size[v]-Size[v];
        down(v);
    }
}
int lca(int u,int v){
    if(dep[u]<dep[v]) swap(u,v);
    while(dep[u]!=dep[v]){
        u=fa[u];
    }
    int d=dep[u]-dep[v];
    if(u==v) return u;
    for(int j=20;j>=0;j--){
        if(par[u][j]!=par[v][j]){
            u=par[u][j];
            v=par[v][j];
        }
    }
   return par[u][0];
}
void solve()
{   
    int n,q;
    cin>>n>>q;
    for(int i=1;i<=n-1;i++){
        int u,v;
        cin>>u>>v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dep[1]=1;
    up(1);
    down(1);
    for(int i=1;i<=21;i++){
        for(int j=1;j<=n;j++){
            if(par[j][i-1]!=0)
            par[j][i]=par[par[j][i-1]][i-1];
        }
    }
    for(int i=1;i<=q;i++){
        int u,v;
        cin>>u>>v;
        int dist1=V[u]+f[u];
        int dist2=V[v]+f[v];
        int dist3=dep[u]+dep[v]-2*dep[lca(u,v)];
        cout<<(dist1+dist2-n*dist3)/2<<endl;
    }
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    //cin >> t;
    while (t--)
    {
        solve();
    }
}