st表（稀疏表）

发表于 2025-02-06 分类于数据结构与算法本文字数： 488 阅读时长 ≈ 2 分钟

原题与参考：
https://www.luogu.com.cn/problem/P3865
https://oi-wiki.org/ds/sparse-table/

模板题题意

给定个数，有个询问，对于每个询问，你需要回答区间中的最大值

简介

ST 表（Sparse Table，稀疏表）是用于解决可重复贡献问题的数据结构。

可重复贡献问题：对于运算opt，满足，如和。

比起线段树，只能静态查询，不能修改信息。
使用倍增思想，时间复杂度：

步骤

对数初处理

int lg[N];//对数表
for(int i=2;i<=n;i++){//初始化对数表
    lg[i]=lg[i>>1]+1;
}

转移方程

设为数序列，为区间的最大值，则

这里有张动图来着

int w=1;
for(int j=1;j<=lg[n];j++){
    for(int i=1;i<=n-w;i++){
        f[i][j]=max(f[i][j-1],f[i+w][j-1]);
    }
    w<<=1;
}

询问

询问时，把区间分成和，其中
即查询
这里有张动图来着

1
2
3

scanf("%d%d",&l,&r);
s=lg[r-l+1];
printf("%d\n",max(f[l][s],f[r-(1<<s)+1][s]));

总代码

#include<bits/stdc++.h>
const int N=(1e5)+5;
using namespace std;
int n,m;//数列的长度,询问的个数
int f[N][22];//区间[i,i+2^j-1]的最大值
int lg[N];//对数表
int main() {
    scanf("%d%d",&n,&m);
    for(int i=2;i<=n;i++){//初始化对数表
        lg[i]=lg[i>>1]+1;
    }
    for(int i=1;i<=n;i++){
        scanf("%d",&f[i][0]);
    }
    int w=1;
    for(int j=1;j<=lg[n];j++){
        for(int i=1;i<=n-w;i++){
            f[i][j]=max(f[i][j-1],f[i+w][j-1]);
        }
        w<<=1;
    }
    int l,r,s;
    while(m--){
        scanf("%d%d",&l,&r);
        s=lg[r-l+1];
        printf("%d\n",max(f[l][s],f[r-(1<<s)+1][s]));
    }
    return 0;
}

并查集

发表于 2025-02-04 分类于数据结构与算法本文字数： 843 阅读时长 ≈ 3 分钟

【模板】并查集

题目描述

如题，现在有一个并查集，你需要完成合并和查询操作。

输入格式

第一行包含两个整数 ,表示共有个元素和个操作。

接下来行，每行包含三个整数。

当时，将与所在的集合合并。

当时，输出与是否在同一集合内，是的输出
Y ；否则输出 N 。

输出格式

对于每一个的操作，都有一行输出，每行包含一个大写字母，为 Y 或者 N 。

样例 #1

样例输入 #1

样例输出 #1

N
Y
N
Y

提示

对于的数据，，。

对于的数据，，，，。

题解

#include<bits/stdc++.h>
const int N=(1e5)+5;
using namespace std;
struct dsu{
    vector<int> parent,size;
    //Single-argument constructors must be marked explicit to avoid unintentional implicit conversions
    explicit dsu(int s):parent(s+1),size(s+1,1){
        iota(parent.begin(),parent.end(),0);//1,2,...,s-1
    }
    // 查询
    int find(int x){
        return parent[x]==x?x:parent[x]=find(parent[x]);
    }
    // 启发式合并
    void unite(int x,int y){
        x=find(x),y=find(y);
        if(x==y)
            return;
        if(size[x]<size[y])
            swap(x,y);
        parent[y]=x;
        size[x]+=size[y];
    }
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    int n,m;
    cin>>n>>m;
    dsu s=dsu(n);
    int x,y,z;
    for(int i=0;i<m;i++){
        cin>>z>>x>>y;
        if(z==1){
            s.unite(x,y);
        }
        else{
            if(s.find(x)==s.find(y)){
                cout<<'Y'<<endl;
            }
            else{
                cout<<'N'<<endl;
            }
        }
    }
    return 0;
}

并查集介绍

并查集是一种数据结构，用于处理一些不交集合并及查询的问题。
并查集是森林，每个集合用一个树结构表示，树的根节点代表整个集合。

结构

struct dsu{
    vector<int> parent,size;
    // 单参数构造函数必须使用 explicit 关键字进行标记，以避免发生不必要的隐式类型转换。在<numeric>库里
    //这里节点是从1开始到s
    explicit dsu(int s):parent(s+1),size(s+1,1){
        iota(parent.begin(),parent.end(),0);//1,2,...,s-1
    }
};

合并

// 简单合并
void simple_unite(int x, int y) {
    parent[find(x)] = find(y);
}
// 启发式合并
void unite(int x,int y){
    x=find(x),y=find(y);
    if(x==y)//在同一个集合里
        return;
    if(size[x]<size[y])
        swap(x,y);
    parent[y]=x;
    size[x]+=size[y];
}

查询

找到了根节点，就顺便把父节点都更新成根节点

1
2
3

int find(int x){
    return parent[x]==x?x:parent[x]=find(parent[x]);
}

删除

void erase(int x) {
    --size[find(x)];
    parent[x] = x;
}

移动

void move(int x, int y) {
    int fx = find(x), fy = find(y);
    if (fx == fy) return;
    parent[x] = fy;
    --size[fx], ++size[fy];
}

总代码

struct dsu{
    vector<int> parent,size;
    explicit dsu(int s):parent(s+1),size(s+1,1){
        iota(parent.begin(),parent.end(),0);//1,2,...,s-1
    }
    // 查询
    int find(int x){
        return parent[x]==x?x:parent[x]=find(parent[x]);
    }
    // 合并
    void simple_unite(int x, int y) {
        parent[find(x)] = find(y);
    }
    // 启发式合并
    void unite(int x,int y){
        //找到根结点
        x=find(x),y=find(y);
        //在同一个集合里
        if(x==y)
            return;
        if(size[x]<size[y])
            swap(x,y);
        parent[y]=x;
        size[x]+=size[y];
    }
    //删除
    void erase(int x) {
        --size[find(x)];
        parent[x] = x;
    }
    //移动
    void move(int x, int y) {
        int fx = find(x), fy = find(y);
        if (fx == fy) return;
        parent[x] = fy;
        --size[fx], ++size[fy];
    }
};

2024年蓝桥杯省赛C/C++大学A组代码

发表于 2025-02-03 更新于 2025-05-10 分类于蓝桥杯本文字数： 7.3k 阅读时长 ≈ 26 分钟

[蓝桥杯 2024 省 A] 艺术与篮球

题目描述

小蓝出生在一个艺术与运动并重的家庭中。
妈妈是位书法家，她希望小蓝能通过练习书法，继承她的艺术天赋，并练就一手好字。爸爸是一名篮球教练，他希望小蓝能通过篮球锻炼身体，培养运
动的激情和团队合作的精神。
为了既满足妈妈的期望，又不辜负爸爸的心意，小蓝决定根据日期的笔画数来安排自己的练习。首先，他会将当天的日期按照 YYYYMMDD 的格式
转换成一个位数，然后将这位数对应到汉字上，计算这些汉字的总笔画数。如果总笔画数超过，他就去练习篮球；如果总笔画数不超过，他就去练习书法。
例如，在年月日这天，日期可表示为一个位数字，其转换为汉字是“二零二四零一零一”。日期的总笔画数为，因此在这天，小蓝会去练习书法。
以下是汉字的笔画数对照表：

汉字	笔画数	汉字	笔画数
零		五
一		六
二		七
三		八
四		九

现在，请你帮助小蓝统计一下，在年月日到年月日
这段时间内，小蓝有多少天是在练习篮球？

输入格式

这是一道结果填空题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

输出格式

这是一道结果填空题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

解法

模拟

#include<bits/stdc++.h>
const int N=(1e5)+5;
using namespace std;
int bh[]={13,1,2,3,5,4,4,2,2,2};
int bihua[32]={0};
int month[]={0,31,28,31,30,31,30,31,31,30,31,30,31};
int res=0;
int main() {
    int ans=0;
    for(int i=0;i<=31;i++){
        bihua[i]=bh[i/10]+bh[i%10];
    }
    int y;
    for(y=2000;y<=2023;y++){
        int year_days=bihua[y/100]+bihua[y%100];
        if(y%4==0)
            month[2]=29;
        else
            month[2]=28;
        for(int m=1;m<=12;m++){
            int mon_days=year_days+bihua[m];
            for(int d=1;d<=month[m];d++){
                if(mon_days+bihua[d]>50)
                    ans++;
            }
        }
    }
    month[2]=29;
    month[4]=13;
    int year_days=bihua[y/100]+bihua[y%100];
    for(int m=1;m<=4;m++){
        int mon_days=year_days+bihua[m];
        for(int d=1;d<=month[m];d++){
            if(mon_days+bihua[d]>50)
                ans++;
        }
    }
    cout<<ans<<endl;
    return 0;
}
//3228

[蓝桥杯 2024 省 A] 五子棋对弈

题目描述

“在五子棋的对弈中，友谊的小船说翻就翻？” 不！对小蓝和小桥来说，五子棋不仅是棋盘上的较量，更是心与心之间的沟通。这两位挚友秉承着 “友谊第一，比赛第二” 的宗旨，决定在一块的棋盘上，用黑白两色的棋子来决出胜负。但他们又都不忍心让对方失落，于是决定用一场和棋（平局） 作为彼此友谊的见证。
比赛遵循以下规则：

棋盘规模：比赛在一个的方格棋盘上进行，共有个格子供下棋使用。
棋子类型：两种棋子，黑棋与白棋，代表双方。小蓝持白棋，小桥持黑棋。
先手规则：白棋（小蓝）具有先手优势，即在棋盘空白时率先落子（下棋）。
轮流落子：玩家们交替在棋盘上放置各自的棋子，每次仅放置一枚。
胜利条件：率先在横线、竖线或斜线上形成连续的五个同色棋子的一方获胜。
平局条件：当所有个棋盘格都被下满棋子，而未决出胜负时，游戏以平局告终。

在这一设定下，小蓝和小桥想知道，有多少种不同的棋局情况（终局不同看成不同情况，终局相同而落子顺序不同看成同一种情况），既确保棋盘下满又保证比赛结果为平局。

输入格式

这是一道结果填空题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

输出格式

这是一道结果填空题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

解法

dfs，模拟

#include<bits/stdc++.h>
const int N=(1e5)+5;
using namespace std;
using ll=unsigned long long;
int arr[26];
/*
 * 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
 */
ll ans=0;
void dfs(int d,int b){
    if(b>13||d-b>13)
        return;
    if(d==26){
        bool ok=false;
        for(int i=7;i<=25;i+=6)
            if(arr[1]!=arr[i]){
                ok=true;
                break;
            }
        if(ok)
            ans++;
        return;
    }
    for(int i=0;i<=1;i++){
        arr[d]=i;
        if(d%5==0){
            bool ok=false;
            for(int j=1;j<=4;j++){//0,1,2,3,4
                if(arr[d]!=arr[d-j]){
                    ok=true;
                    break;
                }
            }
            if(!ok)
                continue;
        }
        if(d==21){
            bool ok=false;
            for(int j=9;j<=21;j+=4){//5,9,13,17,21
                if(arr[5]!=arr[j]){
                    ok=true;
                    break;
                }
            }
            if(!ok)
                continue;
        }
        if(d>=21){
            bool ok=false;
            for(int j=5;j<=20;j+=5){
                if(arr[d]!=arr[d-j]){
                    ok=true;
                    break;
                }
            }
            if(!ok)
                continue;
        }
        dfs(d+1,b+i);
    }
}
int main() {
    dfs(1,0);
    cout<<ans<<endl;
}
//3126376

[蓝桥杯 2024 省 A] 训练士兵

题目描述

在蓝桥王国中，有名士兵，这些士兵需要接受一系列特殊的训练，以提升他们的战斗技能。对于第名士兵来说，进行一次训练所需的成本为枚金币，而要想成为顶尖战士，他至少需要进行次训练。
为了确保训练的高效性，王国推出了一种组团训练的方案。该方案包含每位士兵所需的一次训练，且总共只需支付枚金币（组团训练方案可以多次购买，即士兵可以进行多次组团训练）。
作为训练指挥官，请你计算出最少需要花费多少金币，才能使得所有的士兵都成为顶尖战士？

输入格式

输入的第一行包含两个整数和，用一个空格分隔，表示士兵的数量和进行一次组团训练所需的金币数。
接下来的行，每行包含两个整数和，用一个空格分隔，表示第名士兵进行一次训练的金币成本和要成为顶尖战士所需的训练次数。

输出格式

输出一行包含一个整数，表示使所有士兵成为顶尖战士所需的最少金币数。

样例 #1

样例输入 #1

样例输出 #1

提示

花费金币最少的训练方式为：进行次组团训练，花费枚金币，此时士兵已成为顶尖战士；再花费枚金币，让士兵进行两次训练，成为顶尖战士。总花费为。

对于的评测用例， $，，$ 。

对于所有评测用例， $，，$ 。

解法

按照需要训练数，从多往少贪心

#include <bits/stdc++.h>
#define pay second
#define num first
using namespace std;
using ll = long long;
#define int long long // 十年oi一场空，不开 long long见祖宗
typedef pair<int, int> pp;

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr); // 正式比赛不要用这两行，用scanf和printf
    int n, s;
    cin >> n >> s;
    vector<pair<int, int>> arr(n);
    for (int i = 0; i < n; i++)
    {
        cin >> arr[i].pay >> arr[i].num;
    }
    sort(arr.begin(), arr.end());
    int single_paid = 0, sum = 0, i;
    for (i = n - 1; i >= 0; i--)
    {
        single_paid += arr[i].pay;
        if (single_paid >= s) // 从第i个开始往前，集体训练更便宜，使用集体训练
        {
            break;
        }
    }
    int c;
    if (i == -1) // 全都是单独训练便宜
    {
        i = 0;
        c = 0;
    }
    else
    {
        c = arr[i].num;
    }
    sum = c * s;
    for (int j = i; j < n; j++)
    {
        sum += arr[j].pay * (arr[j].num - c);
    }
    cout << sum << endl;
    return 0;
}

[蓝桥杯 2024 省 A] 团建

题目描述

小蓝正在和朋友们团建，有一个游戏项目需要两人合作，两个人分别拿到一棵大小为和的树，树上的每个结点上有一个正整数权值。
两个人需要从各自树的根结点出发走向某个叶结点，从根到这个叶结点的路径上经过的所有结点上的权值构成了一个正整数序列，两人的序列的最长公共前缀即为他们的得分。给出两棵树，请计算两个人最多的得分是多少。

输入格式

输入的第一行包含两个正整数，用一个空格分隔。
第二行包含个正整数，相邻整数之间使用一个空格分隔，其中表示第一棵树结点上的权值。
第三行包含个正整数，相邻整数之间使用一个空格分隔，其中 di 表示第二棵树结点上的权值。
接下来行，每行包含两个正整数表示第一棵树中包含一条和
之间的边。
接下来行，每行包含两个正整数表示第二棵树中包含一条
和之间的边。

输出格式

输出一行包含一个整数表示答案。

样例 #1

样例输入 #1

样例输出 #1

样例 #2

样例输入 #2

5 4
10 20 30 40 50
10 40 20 30
1 2
1 3
2 4
3 5
1 2
1 3
3 4

样例输出 #2

提示

对于的评测用例，；
对于所有评测用例， $，，，$ ，对于任意结点，其儿子结点的权重互不相同。

解法

对两个树进行dfs

#include <bits/stdc++.h>
#define N 200005
using namespace std;
using ll = long long;

int n[2], res = 0;

vector<vector<int>> node(2);
vector<vector<vector<int>>> g(2);
vector<vector<bool>> vis(2, vector<bool>(N));

void dfs(int u, int v, int d)
{
    res = max(res, d);
    map<int, int> mp; // tree2 value in tree1 value?不用map，只用双重循环过不了
    for (int i = 0, l = g[0][u].size(); i < l; i++)
    {
        int uu = g[0][u][i];
        if (vis[0][uu])
            continue;
        mp[node[0][uu]] = uu;
    }
    for (int j = 0, s = g[1][v].size(); j < s; j++)
    {
        int vv = g[1][v][j];
        if (vis[1][vv])
            continue;
        if (mp.count(node[1][vv]) > 0)
        {
            int uu = mp[node[1][vv]];
            vis[0][uu] = vis[1][vv] = true;
            dfs(uu, vv, d + 1);
        }
    }
}
signed main()
{
    for (int i = 0; i < 2; i++)
        scanf("%d", &n[i]);
    for (int i = 0; i < 2; i++)
    {
        node[i].resize(n[i] + 1);
        for (int j = 1; j <= n[i]; j++)
            scanf("%d", &node[i][j]);
    }
    int u, v;
    for (int i = 0; i < 2; i++)
    {
        g[i].resize(n[i] + 1);
        for (int j = 1; j < n[i]; j++)
        {
            scanf("%d%d", &u, &v);
            g[i][u].push_back(v);
            g[i][v].push_back(u);
        }
    }
    vis[0][1] = vis[1][1] = true;
    if (node[0][1] == node[1][1])
        dfs(1, 1, 1);
    printf("%d\n", res);
    return 0;
}

[蓝桥杯 2024 省 A] 成绩统计

题目描述

小蓝的班上有个人，一次考试之后小蓝想统计同学们的成绩，第名同学的成绩为。当小蓝统计完前名同学的成绩后，他可以从中选出任意名同学的成绩，计算出这个成绩的方差。小蓝至少要检查多少个人的成
绩，才有可能选出名同学，他们的方差小于一个给定的值？
提示：个数的方差定义为：，其中表示
的平均值，。

输入格式

输入的第一行包含三个正整数，相邻整数之间使用一个空格分隔。

第二行包含个正整数，相邻整数之间使用一个空格分隔。

输出格式

输出一行包含一个整数表示答案。如果不能满足条件，输出。

样例 #1

样例输入 #1

1 2	5 3 1 3 2 5 2 3

样例输出 #1

提示

检查完前三名同学的成绩后，只能选出，方差为；

检查完前四名同学的成绩后，可以选出，方差为，所以答案为。

对于的评测用例，保证；
对于的评测用例，保证；
对于所有评测用例，保证，，。

解法

前缀和, 二分

$\begin{aligned} \bar{v} &= \frac{\sum_{i=1}^{k}v_i}{k} \\ \sigma^2 &= \frac{\sum_{i=1}^{k}(v_i - \bar{v})^2}{k} <t\\ k\sigma^2 &= \sum_{i=1}^{k}(v_i - \bar{v})^2 \\ &=\sum_{i=1}^{k}v_i^2 - 2\bar{v}\sum_{i=1}^{k}v_i+k\bar{v}^2\\ &=\sum_{i=1}^{k}v_i^2 - 2\frac{\sum_{i=1}^{k}v_i}{k}\sum_{i=1}^{k}v_i+k(\frac{\sum_{i=1}^{k}v_i}{k})^2\\ &=\sum_{i=1}^{k}v_i^2 - \frac{2}{k}(\sum_{i=1}^{k}v_i)^2+\frac{1}{k}(\sum_{i=1}^{k}v_i)^2\\ &=\sum_{i=1}^{k}v_i^2 -\frac{1}{k}(\sum_{i=1}^{k}v_i)^2<kt \end{aligned}$

#include <bits/stdc++.h>
#define N 100005
using namespace std;
using ll = long long;
ll n, k, t, kt;
ll a[N], v[N];
ll sum[N], sum2[N];
inline ll pow2(ll x)
{
    return x * x;
}
bool check(int x)
{
    memcpy(v + 1, a + 1, x * sizeof(ll));
    sort(v + 1, v + 1 + x);
    for (int i = 1; i <= x; i++)
    {
        sum[i] = sum[i - 1] + v[i];
        sum2[i] = sum2[i - 1] + pow2(v[i]);
    }
    for (int i = k; i <= x; i++)
    {
        double ds = 1.0 * sum[i] - sum[i - k];
        if ((1.0 * sum2[i] - sum2[i - k]) - (ds / k) * ds < kt)
        {
            return true;
        }
    }
    return false;
}
signed main()
{
    scanf("%lld%lld%lld", &n, &k, &t);
    kt = k * t;
    for (int i = 1; i <= n; i++)
    {
        scanf("%lld", &a[i]);
    }
    int l = k, r = n, res = -1;
    while (l <= r)
    {
        int mid = l + ((r - l) >> 1);
        if (check(mid))
        {
            res = mid;
            r = mid - 1;
        }
        else
        {
            l = mid + 1;
        }
    }
    printf("%d\n", res);
    return 0;
}

[蓝桥杯 2024 省 A] 因数计数

题目描述

小蓝随手写出了含有个正整数的数组，他发现可以轻松地算出有多少个有序二元组满足是的一个因数。因此他定义一个整数对是一个整数对的“因数”当且仅当和分别是和的因数。他想知道有多少个有序四元组满足是的因数，其中互不相等。

输入格式

输入的第一行包含一个正整数。
第二行包含个正整数，相邻整数之间使用一个空格分隔。

输出格式

输出一行包含一个整数表示答案。

样例 #1

样例输入 #1

1 2	5 3 6 2 2 7

样例输出 #1

提示

四元组：为的因子；
四元组：为的因子；
四元组：为的因子；
四元组：为的因子。

对于的评测用例，；
对于的评测用例，；
对于所有评测用例， $，$ 。

解法

样例输入：
找到不同的两对因数

1 2	5 3 6 2 2 7

能找到(1,2), (3,2), (4,2), (3,4), (4,3)五对因数（对于(i,j), i≤j)
四元组，满足四个元素不重叠的两组因数，有{(1,2),(3,4)}, {(1,2),(4,3)},{(3,4),(1,2)},{(4,3),(1,2)}

先写了个直接按题意的代码void baoli()，造出测试例。
再尝试写了一个复杂度的代码，会有一半的测试例TLE

/*尝试的笨代码*/
#include <bits/stdc++.h>
#define N 100005
using namespace std;
using ll = long long;
ll res = 0ll;
int n;              // 数据数量
int a[N];           // 数据
ll e_sum, e_same;   // 边的总数量,端点对应数值相同的边的总数量（双向边总数量）
ll e[N];            // 连接边的数量
void baoli();       // 暴力验证
inline ll c2(int a) // 组合数,n*(n+1)/2，因为最后结果要*2就抵消了
{
    return a * (a - 1);
}
signed main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &a[i]);
    }
    // baoli();
    // return 0;
    sort(a, a + n);
    for (int i = 0; i < n; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            if (a[j] % a[i] == 0)
            {

                if (a[i] == a[j])
                {
                    e[i] += 2;
                    e[j] += 2;
                    e_sum += 2;
                    e_same += 2;
                }
                else
                {
                    e[i]++;
                    e[j]++;
                    e_sum++;
                }
            }
        }
    }
    res = c2(e_sum) + e_same;
    for (int i = 0; i < n; i++)
    {
        // cout << e[i] << ' ';
        res -= c2(e[i]);
    }
    printf("%lld\n", res);
    return 0;
}
// 以下是纯暴力验证
int baoli_ans = 0;
int t[4];
void baoli_dfs(int d)
{
    if (d == 4)
    {
        for (int i = 0; i < 4; i++)
            for (int j = i + 1; j < 4; j++)
                if (t[i] == t[j])
                    return;
        if (a[t[1]] % a[t[0]] == 0 && a[t[3]] % a[t[2]] == 0)
        {
            baoli_ans++;
        }
        return;
    }
    for (int i = 0; i < n; i++)
    {
        t[d] = i;
        baoli_dfs(d + 1);
    }
}
void baoli()
{
    baoli_dfs(0);
    cout << baoli_ans << endl;
}
/*
input:
10
1 2 2 3 3 3 4 5 6 6
//ouput: 564
*/

说明至少思路是对的，只是爆时间了👉👈。换一种方式找它们之间的因数关系。
设点

输入的数量为

，最大的因子为

，

是点

和多少个点有因数关系。把两个端点是因数关系的称作一条边。两条样的边称为一对边。
对每一个因子

，乘以倍数

，获得它的倍数

，直到

超过

为止。这样，

，点x和y之间连边，它们增加边的数量均为

。
时间复杂度：

，比

好。

一个答案：

#include <bits/stdc++.h>
#define N 100005
#define M 100000
using namespace std;
using ll = unsigned long long;

ll n, m;           // 数据数量,不重复的数据的数量
ll num[N];         // 不重复数据排列
ll cnt[N];         // 桶
ll e[N];           // 连接到的值不一样的边
ll res;            // 结果
inline ll c2(ll a) // 组合数,n*(n+1)/2，因为最后结果要*2就抵消了
{
    return a * (a - 1);
}
signed main()
{
    scanf("%d", &n);
    ll a;
    for (register ll i = 0; i < n; i++)
    {
        scanf("%d", &a);
        cnt[a]++;
    }
    for (register ll i = 1; i <= M; i++)
    {
        if (cnt[i] == 0)
            continue;
        num[m++] = i;
        res += c2(cnt[i]);
        for (register ll j = i * 2; j <= M; j += i)
        {
            e[i] += cnt[j];
            e[j] += cnt[i];
            res += cnt[i] * cnt[j];
        }
    }
    res = c2(res);
    for (register ll i = 0; i < m; i++)
    {
        res -= c2(e[num[i]] + 2 * (cnt[num[i]] - 1)) * cnt[num[i]];
        res += c2(cnt[num[i]]);
    }
    cout << res<< endl;
    return 0;
}

[蓝桥杯 2024 省 A] 零食采购

题目描述

小蓝准备去星际旅行，出发前想在本星系采购一些零食，星系内有颗星球，由条航路连接为连通图，第颗星球卖第种零食特产。小蓝想出了个采购方案，第个方案的起点为星球，终点为星球，对于每种采购方案，小蓝将从起点走最短的航路到终点，并且可以购买所有经过的星球上的零食（包括起点终点），请计算每种采购方案最多能买多少种不同的零食。

输入格式

输入的第一行包含两个正整数，，用一个空格分隔。
第二行包含个整数，相邻整数之间使用一个空格分隔。
接下来行，第行包含两个整数，用一个空格分隔，表示一条
航路将星球与相连。
接下来行，第行包含两个整数，用一个空格分隔，表示一个采购方案。

输出格式

输出行，每行包含一个整数，依次表示每个采购方案的答案。

样例 #1

样例输入 #1

样例输出 #1

1
2

3
2

提示

第一个方案路线为，可以买到第种零食；
第二个方案路线为，可以买到第种零食。

对于 20% 的评测用例，；
对于所有评测用例， $，，，$ 。

解法

使用最近公共祖先LCA板子，在其中加上状态压缩DP
我博客里的lca: https://misaka-xxw.github.io/2025/02/01/lca/

首先，注意审题，题目里说n个节点，n-1条边，连通图，所以这是一个树。任意选中一个根节点，那么点s到点e的最短路径，就是从s往上走到根节点，再往下走到点e。

#include<bits/stdc++.h>
using namespace std;
const int N=(5e5)+5;

int n,s,e;//结点数，起点，终点
vector<int> g[N];//树
int lg[N];//对数表
int c[N];//每个结点对应的食物
int depth[N],father[N][31],dp[N][31];//深度，第i结点的2^j个祖先，以及这条链路对应相应的食物购买情况
void init_lg() {
    for (int i = 2; i <= n; ++i) {
        lg[i] = lg[i>>1] + 1;
    }
}
//利用补码的性质，找二进制里最后一个1
inline int lastof1(int x){
    return x & -x;
}
//统计二进制里有多少1
inline int numof1(int x){
    int a=0;
    while(x){
        x-= lastof1(x);
        a++;
    }
    return a;
}
// 深度优先搜索，计算每个节点的父节点倍增表
void dfs(int me,int fa) {
    for (int i = 1; i <= lg[depth[me]]; ++i){
        dp[me][i]=dp[father[me][i - 1]][i - 1]|dp[me][i - 1];
        father[me][i] = father[father[me][i - 1]][i - 1];
    }
    for (int son : g[me])
        if (son!=fa){
            depth[son] = depth[me] + 1;
            father[son][0] = me;
            dp[son][0]=c[son]|c[me];
            dfs(son,me);
        }
}
// 查询x和y的最低公共祖先用lca算法，改变
int lca(int x,int y){
    int res=c[x]|c[y];
    if(depth[x]<depth[y])
        swap(x,y);
    while(depth[x]>depth[y]){
        int delta=lg[depth[x]-depth[y]];
        res|=dp[x][delta];
        x=father[x][delta];
    }
    if(x!=y){
        for(int i=lg[depth[x]];i>=0;--i){
            if(father[x][i]!=father[y][i]){
                res|=(dp[x][i]|dp[y][i]);
                x=father[x][i];
                y=father[y][i];
            }
        }
        res|=dp[x][0];
    }
    return numof1(res);
}
int main() {
    int u,v,q;
    scanf("%d%d",&n,&q);
    init_lg();
    for(int i=1;i<=n;i++){
        scanf("%d",&u);
        c[i]=(1<<u);
    }
    for(int i=1;i<n;i++){
        scanf("%d%d",&u,&v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1,1);
    while(q--){
        scanf("%d%d",&s,&e);
        printf("%d\n",lca(s,e));
    }
    return 0;
}

[蓝桥杯 2024 省 A] 封印宝石

题目描述

在一次探险中，勇者小蓝发现了颗闪烁着奇异光芒的宝石，每颗宝石都蕴含着魔法能量，分别记作。小蓝计划用个特制的魔法盒子来封
印这些宝石，防止其魔法能量被滥用。
封印宝石会消耗小蓝的体力，具体地，将第颗宝石放入第个盒子会消耗小蓝点体力（注：需满足才能将第颗宝石放入第个盒子进行有效的封印）。小蓝也可以选择将魔法盒留空，以保存体力供后续使用。
此外，为了避免魔力相冲，每个盒子最多存放一颗宝石（每个宝石也只能放进一个盒子），且任意两个相邻盒子不能存放魔力值相同的宝石，相邻的盒子允许同时为空。
小蓝初始的体力值为。在不超出体力限制的条件下，小蓝希望找出一种宝石的放置方法，使得宝石的魔力值在这个盒子中的排列顺序具有最大的字典序（注：未放置宝石的盒子在此序列中记为）。
作为勇者小蓝的追随者，请你帮他找出这一放置宝石的方法。

字典序的解释：在本题中，字典序的大小是按照宝石的魔力值进行比较的。对于两个长度同为的魔力值序列和，如果存在一个位置，使得对所有成立，但是，则序列在字典序上小于序列。
反之，如果，则序列在字典序上大于序列。如果不存在这样的，则序列和序列的字典序相等。

输入格式

输入的第一行包含两个整数和，用一个空格分隔，分别表示宝石的数量和小蓝的初始体力值。
第二行包含个整数，相邻整数之间使用一个空格分隔，分别表示每颗宝石的魔法能量值。

输出格式

输出一行包含个整数，相邻整数之间使用一个空格分隔，表示每个魔法盒中宝石的魔法能量值。如果某个魔法盒为空，则对应位置输出。

样例 #1

样例输入 #1

1
2

3 3
1 3 2

样例输出 #1

3 2 -1

提示

在开始放置宝石之前，体力为，宝石在盒子中的排列为。

将第个宝石放进第个盒子，得到，体力剩余。
将第个宝石放进第个盒子，得到，体力剩余。

最后宝石在盒子中的排列为。显然，没有比这更优的放置方法。

对于的评测用例， $，，$ 。
对于所有评测用例， $，，$ 。

解法

贪心+线段树
我博客里的线段树:https://misaka-xxw.github.io/2025/02/02/segment-tree/

解释

给定个数放到个位置上，放到位置上消耗个代价，合理放置这些数，让它们在代价范围内有最大的字典序。
要求：

数可以放在的位置区间
位置可以放置区间的数
可以有空的位置，相邻位置不能有相同的数。
字典序的解释：两个排列方法，对于最靠前的放置了不相等的数的位置，放更大的数的那个字典序更大。没有放数就是-1。如：[5,4,3,…]比[5,4,2,…]大

贪心

优先将更大的数放置到更靠前的位置
对于相等的数，选更靠前的
两个位置不能同时放一样的数

线段树

作用：区间内最大值和次大值的查询和更新
从1遍历到n，查询区间内的最大值，放在位置上。
- 如果和上一个答案相同，选次大值。
- 使用了宝石，就要更新线段树

#include<bits/stdc++.h>

using namespace std;
const int N = (1e5) + 5;

struct node {
    int num; // 数值
    int pos; // 第几个数值
    node() : num(-1), pos(0) {}

    node(int a, int b) : num(a), pos(b) {}

    bool operator>(const node &other) const {
        return num != other.num ? num > other.num : pos < other.pos;
    }
} node0;//空结点
typedef pair<node, node> maxs;//最大值和次大值,对应first和second
int n, m;//数量，代价，当前搜索
int a[N];//宝石数值
int loc[N];//判断叶子节点位置与线段树位置的对应关系
int ans[N];//答案，放置方法
maxs t[4 * N];//线段树，最大值和次大值
maxs res;//存放find_max时的最大值和次大值

// 更新某个节点的最大值和次大值，可能稍微快一点
void update_max(maxs &cur, const maxs l, const maxs r) {
    //根据l和r，更新cur的最大值和次大值
    if (l.first.num > r.first.num) {//左最大值大
        cur.first = l.first;
        if (l.second.num >= r.first.num)
            cur.second = l.second;
        else
            cur.second = r.first;
    } else if (l.first.num < r.first.num) {//右最大值大
        cur.first = r.first;
        if (l.first.num >= r.second.num)
            cur.second = l.first;
        else
            cur.second = r.second;
    } else {//左右最大值相同
        cur.first = l.first;
        if (l.second.num != cur.first.num && l.second.num >= r.second.num)
            cur.second = l.second;
        else if (r.second.num < cur.first.num)
            cur.second = r.second;
        else
            cur.second = node0;
    }
}

//效果一样的函数，似乎稍微慢一点点
void update_max2(maxs &cur, const maxs l, const maxs r) {
    //根据l和r，更新cur的最大值和次大值
    node tmp[] = {l.first, l.second, r.first, r.second};
    sort(tmp, tmp + 4, greater<>());//从大到小排
    cur.first = tmp[0];
    for (int i = 1; i < 4; i++) {
        if (cur.first.num != tmp[i].num) {
            cur.second = tmp[i];
            return;
        }
    }
    cur.second = node0;
}

//建立线段树
void build(int l, int r, int p) {
    if (l == r) {
        t[p].first = node(a[l], l);
        t[p].second = node0;
        loc[l] = p;
        return;
    }
    int mid = l + ((r - l) >> 1), lc = p << 1, rc = lc | 1;
    build(l, mid, lc);
    build(mid + 1, r, rc);
    update_max(t[p], t[lc], t[rc]);
}

//查找最大值
void find_max(int l, int r, int i, int j, int p) {
    if (l <= i && j <= r) {//找到了合适的区间
        update_max(res, res, t[p]);
        return;
    }
    int lc = p << 1, rc = lc | 1;
    int mid = i + ((j - i) >> 1);
    if (l <= mid) find_max(l, r, i, mid, lc);
    if (mid < r) find_max(l, r, mid + 1, j, rc);
}
// 自底而上，修改被影响节点的最大值和次大值
void modify(int pos) {
    int p = loc[pos];
    t[p].first = node0;
    t[p].second = node0;
    for (p >>= 1; p >= 1; p >>= 1) {
        update_max(t[p], t[p << 1], t[(p << 1) | 1]);
    }
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    memset(ans, -1, sizeof(ans));//初始化为-1，盒子为空
    build(1, n, 1);//建立线段树
    for (int i = 1; i <= n; i++) {
        res = {node0, node0};
        find_max(i, min(i + m, n), 1, n, 1);
        int pos;
        if (res.first.pos == 0)//最大值是一个空节点
            continue;
        else if (res.first.num == ans[i - 1]) {//最大值跟前一个盒子相同撞了，找次大值
            if (res.second.pos == 0)//次大值是一个空节点
                continue;
            ans[i] = res.second.num;//选次大值
            pos = res.second.pos;
        } else {
            ans[i] = res.first.num;//选最大值
            pos = res.first.pos;
        }
        m -= (pos - i);
        modify(pos);
    }
    for (int i = 1; i < n; i++) {
        printf("%d ", ans[i]);
    }
    printf("%d\n", ans[n]);
    return 0;
}

线段树

发表于 2025-02-02 更新于 2025-02-19 分类于数据结构与算法本文字数： 2.6k 阅读时长 ≈ 9 分钟

原题：https://www.luogu.com.cn/problem/P3372
教程：https://oi-wiki.org/ds/seg/

【模板】线段树 1

题目描述

如题，已知一个数列，你需要进行下面两种操作：

将某区间每一个数加上。
求出某区间每一个数的和。

输入格式

第一行包含两个整数，分别表示该数列数字的个数和操作的总个数。

第二行包含个用空格分隔的整数，其中第个数字表示数列第项的初始值。

接下来行每行包含或个整数，表示一个操作，具体如下：

1 x y k：将区间内每个数加上。
2 x y：输出区间内每个数的和。

输出格式

输出包含若干行整数，即为所有操作 2 的结果。

样例 #1

样例输入 #1

样例输出 #1

1
2
3

11
8
20

提示

对于的数据：，。
对于的数据：，。
对于的数据：。

保证任意时刻数列中所有元素的绝对值之和。

【样例解释】

线段树的结构

这个数据结构，可以高效地对区间进行更新和查询

alt text

1
2
3

int t[N];      // 线段树的值（和）
int a[N];      // 原始数组
int lazy[N];   // 懒惰标记

线段树的建立

alt text

对一整个区间和，递归，对半分成两个区间和，直到区间长度为1为止。

build(1, n, 1); //开始建树

// 构造函数：初始化原始数组，构建线段树
void build(int l, int r, int p) {
    if (l == r) {//区间长度为1
        t[p] = a[l];
        return;
    }
    int mid = l + ((r - l) >> 1);  //中分mid=(l+r)/2
    int lc = (p << 1), rc = lc | 1;//左子树lc=p*2,右子树rc=lc+1
    build(l, mid, lc);             //左递归建树
    build(mid + 1, r, rc);         //右递归建树
    t[p] = t[lc] + t[rc];          //求和
}

线段树的更新

懒惰标记

没必要每次更新，都把每个点修改。而是引入一个懒惰标记。
每当访问到一个节点时，如果它有懒惰标记，就会先更新该节点和其子节点，然后清空该节点的懒惰标记。
懒惰标记表示，此区间的子区间都还欠着多少没加。

操作前

[2,4]区间内所有数加2

[3,4]区间内所有数加1

// 区间加法操作,对区间[l,r]加上c
void add(int l, int r, int i, int j, int p, int c) {
    if (l <= i && j <= r) {     //[i,j]在更新区间[l,r]里
        t[p] += (j - i + 1) * c;//该区间[i,j]更新求和
        lazy[p] += c;           //懒惰标记，先不往子树更新，等下一次操作再说
        return;
    }
    int mid = i + ((j - i) >> 1); //中分mid=(l+r)/2
    int lc = (p << 1), rc = lc | 1;//左子树lc=p*2,右子树rc=lc+1
    if (lazy[p] && i != j) {             //已经有懒惰标记，而且长度大于1
        t[lc] += lazy[p] * (mid - i + 1);//左子树更新和
        t[rc] += lazy[p] * (j - mid);//右子树更新和
        lazy[lc] += lazy[p];//左子树更新懒惰标记
        lazy[rc] += lazy[p];//右子树更新懒惰标记
        lazy[p] = 0;//清除懒惰标记
    }
    if (l <= mid) add(l, r, i, mid, lc, c);   //左子树递归更新
    if (mid < r) add(l, r, mid + 1, j, rc, c);//右子树递归更新
    t[p] = t[lc] + t[rc];
}

线段树的求和

// 区间求和操作，求[l,r]的和
int getsum(int l, int r, int i, int j, int p) {
    if (l <= i && j <= r) return t[p];//[i,j]在[l,r]里，直接查询
    int mid = i + ((j - i) >> 1);     //中分mid=(l+r)/2
    int lc = (p << 1), rc = lc | 1;   //左子树lc=p*2,右子树rc=lc+1
    if (lazy[p]) {                       //有未更新的懒惰标记
        t[lc] += lazy[p] * (mid - i + 1);//左子树更新和
        t[rc] += lazy[p] * (j - mid);    //右子树更新和
        lazy[lc] += lazy[p];             //左子树更新懒惰标记
        lazy[rc] += lazy[p];             //右子树更新懒惰标记
    }
    lazy[p] = 0;//清除懒惰标记
    int sum = 0;
    if (l <= mid) sum = getsum(l, r, i, mid, lc);//左子树递归求和
    if (mid < r) sum += getsum(l, r, mid + 1, j, rc);//右子树递归求和
    return sum;
}

流程图

	建立	更新	查询
递归出口	if 区间长度为1	if 窗口[i,j]包含于更新区间[l,r]里
递归出口	t[p] = a[l]	更新当前区间和，加懒惰标志	返回当前区间和
设分界点	中分mid
	左子树的索引 lc
	右子树的索引 rc
分支判断	无	if 有懒惰并且长度不为1	if 只有懒惰
		左、右子树更新和、懒惰标记
		无	清除当前区间的懒惰标记
递归左右子树	无判断递归	判断区间是否越界：l <= mid < r

总代码

#include <bits/stdc++.h>
using namespace std;
#define N 400005
#define int long long

int t[N];      // 线段树的值（和）
int a[N];      // 原始数组
int lazy[N];   // 懒惰标记

// 构造函数：初始化原始数组，构建线段树
void build(int l, int r, int p) {
    if (l == r) {//区间长度为1
        t[p] = a[l];
        return;
    }
    int mid = l + ((r - l) >> 1);  //中分mid=(l+r)/2
    int lc = (p << 1), rc = lc | 1;//左子树lc=p*2,右子树rc=lc+1
    build(l, mid, lc);             //左递归建树
    build(mid + 1, r, rc);         //右递归建树
    t[p] = t[lc] + t[rc];          //求和
}

void init(int n) {
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    build(1, n, 1);  // 构建线段树
}

// 区间加法操作,对区间[l,r]加上c
void add(int l, int r, int i, int j, int p, int c) {
    if (l <= i && j <= r) {     //[i,j]在更新区间[l,r]里
        t[p] += (j - i + 1) * c;//该区间[i,j]更新求和
        lazy[p] += c;           //懒惰标记，先不往子树更新，等下一次操作再说
        return;
    }
    int mid = i + ((j - i) >> 1); //中分mid=(l+r)/2
    int lc = (p << 1), rc = lc | 1;//左子树lc=p*2,右子树rc=lc+1
    if (lazy[p] && i != j) {             //已经有懒惰标记，而且长度大于1
        t[lc] += lazy[p] * (mid - i + 1);//左子树更新和
        t[rc] += lazy[p] * (j - mid);//右子树更新和
        lazy[lc] += lazy[p];//左子树更新懒惰标记
        lazy[rc] += lazy[p];//右子树更新懒惰标记
        lazy[p] = 0;//清除懒惰标记
    }
    if (l <= mid) add(l, r, i, mid, lc, c);   //左子树递归更新
    if (mid < r) add(l, r, mid + 1, j, rc, c);//右子树递归更新
    t[p] = t[lc] + t[rc];
}

// 区间求和操作，求[l,r]的和
int getsum(int l, int r, int i, int j, int p) {
    if (l <= i && j <= r) return t[p];//[i,j]在[l,r]里，直接查询
    int mid = i + ((j - i) >> 1);     //中分mid=(l+r)/2
    int lc = (p << 1), rc = lc | 1;   //左子树lc=p*2,右子树rc=lc+1
    if (lazy[p]) {                       //有未更新的懒惰标记
        t[lc] += lazy[p] * (mid - i + 1);//左子树更新和
        t[rc] += lazy[p] * (j - mid);    //右子树更新和
        lazy[lc] += lazy[p];             //左子树更新懒惰标记
        lazy[rc] += lazy[p];             //右子树更新懒惰标记
    }
    lazy[p] = 0;//清除懒惰标记
    int sum = 0;
    if (l <= mid) sum = getsum(l, r, i, mid, lc);//左子树递归求和
    if (mid < r) sum += getsum(l, r, mid + 1, j, rc);//右子树递归求和
    return sum;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int n, m, x, y, cmd, k;
    cin >> n >> m;
    // 创建并初始化线段树
    init(n);
    // 处理操作
    while (m--) {
        cin >> cmd;
        if (cmd == 1) {
            cin >> x >> y >> k;
            add(x, y, 1, n, 1, k);  // 对区间 [x, y] 加上 k
        } else {
            cin >> x >> y;
            cout << getsum(x, y, 1, n, 1) << endl;  // 查询区间 [x, y] 的和
        }
    }
    return 0;
}

【模板】线段树 2

带乘法和加法

https://www.luogu.com.cn/problem/P3373

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5, M = 4e5 + 5;
using ll = long long;
#define int long long
int n, m, q, t[M], a[N], lazy1[M], lazy2[M];//乘法、加法懒标记
void build(int l, int r, int p)
{
    lazy1[p]=1;
    if (l == r)
    {
        t[p] = a[l] % m;
        return;
    }
    int mid = l + ((r - l) >> 1), lc = p << 1, rc = lc | 1;
    build(l, mid, lc);
    build(mid + 1, r, rc);
    t[p] = (t[lc] + t[rc]) % m;
}
inline void update(int i,int j,int p,int mid,int lc,int rc)
{
    t[lc] = (t[lc] * lazy1[p] % m + lazy2[p] * (mid - i + 1) % m) % m; // 算出来
    t[rc] = (t[rc] * lazy1[p] % m + lazy2[p] * (j - mid) % m) % m;
    lazy1[lc] = lazy1[lc] * lazy1[p] % m;
    lazy1[rc] = lazy1[rc] * lazy1[p] % m;
    lazy2[lc] = (lazy2[lc] * lazy1[p] % m + lazy2[p]) % m;
    lazy2[rc] = (lazy2[rc] * lazy1[p] % m + lazy2[p]) % m;
    lazy1[p] = 1;
    lazy2[p] = 0;
}
void add(int l, int r, int i, int j, int p, int k)
{
    if (l <= i && j <= r)
    {
        t[p] = (t[p] + (j - i + 1) * k % m) % m;
        lazy2[p] = (lazy2[p] + k) % m;
        return;
    }
    int mid = i + ((j - i) >> 1), lc = p << 1, rc = lc | 1;
    update(i,j,p,mid,lc,rc);
    if (l <= mid)
        add(l, r, i, mid, lc, k);
    if (mid < r)
        add(l, r, mid + 1, j, rc, k);
    t[p] = (t[lc] + t[rc]) % m;
}
void mul(int l, int r, int i, int j, int p, int k)
{
    if (l <= i && j <= r)
    {
        t[p] = t[p] * k % m;
        lazy1[p] = lazy1[p] * k % m;
        lazy2[p] = lazy2[p] * k % m;
        return;
    }
    int mid = i + ((j - i) >> 1), lc = p << 1, rc = lc | 1;
    update(i,j,p,mid,lc,rc);
    if (l <= mid)
        mul(l, r, i, mid, lc, k);
    if (mid < r)
        mul(l, r, mid + 1, j, rc, k);
    t[p] = (t[lc] + t[rc]) % m;
}
int getsum(int l, int r, int i, int j, int p)
{
    if (l <= i && j <= r)
    {
        return t[p];
    }
    int mid = i + ((j - i) >> 1), lc = p << 1, rc = lc | 1;
    update(i,j,p,mid,lc,rc);
    int sum = 0;
    if (l <= mid)
        sum = getsum(l, r, i, mid, lc);
    if (mid < r)
        sum += getsum(l, r, mid + 1, j, rc);
    return sum % m;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    cin >> n >> q >> m;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    build(1, n, 1);
    int cmd, l, r, k;
    while (q--)
    {
        cin >> cmd;
        switch (cmd)
        {
        case 1:
            cin >> l >> r >> k;
            mul(l, r, 1, n, 1, k % m);
            break;
        case 2:
            cin >> l >> r >> k;
            add(l, r, 1, n, 1, k % m);
            break;
        default:
            cin >> l >> r;
            cout << getsum(l, r, 1, n, 1) << endl;
            break;
        }
    }
    return 0;
}

all-contributors：在README.md文档里自动添加贡献者名单

发表于 2025-02-01 本文字数： 743 阅读时长 ≈ 3 分钟

感谢贡献者🤝

_Misaka-xxw 📝	_{Misaka-xxw-10032} 🖋	_{Misaka-xxw-20001} 💻
Add your contributions

网上的教程：https://www.jianshu.com/p/0c61cec0f5d1
官方文档：https://allcontributors.org/docs/zh-cn/overview

安装应用

安装该Github应用的网址：https://allcontributors.org/docs/zh-cn/bot/installation

all-contributors-cli和使用配置

依赖npm或者yarn

1 2	npm i -D all-contributors-cli npx all-contributors init

回答它问你的问题，会获得类似这样的一个json。失败的话可能是因为你的仓库没公开什么的

{
  "projectName": "XMU-CS-exam",
  "projectOwner": "Misaka-xxw",
  "repoType": "github",
  "repoHost": "https://github.com",
  "files": [
    "README.md"
  ],
  "imageSize": 100,
  "commit": true,
  "commitConvention": "gitmoji",
  "contributorsPerLine": 7,
  "linkToUsage": true
}

还会在README.md文档里生成一些html标签，不要删除。会在之间自动生成贡献者表格

<!-- ALL-CONTRIBUTORS-BADGE:START - Do not remove or modify this section -->
<!-- ALL-CONTRIBUTORS-BADGE:END -->
<!-- ALL-CONTRIBUTORS-LIST:START - Do not remove or modify this section -->
<!-- ALL-CONTRIBUTORS-LIST:END -->

常用指令：

1
2
3

npx all-contributors check # 检查未添加的贡献者
npx all-contributors add Misaka-xxw content # 添加贡献者Misaka-xxw，职责是内容
npx all-contributors generate # 生成表格

然后直接push即可o(￣▽￣)ブ

附录：官方文档的职责表

Emoji/Type	Represents	Comments
🔊 audio	Audio	Podcasts, background music or sound effects
♿️ a11y	Accessibility	Reporting or working on accessibility issues
🐛 bug	Bug reports	Links to issues reported by the user on this project
📝 blog	Blogposts	Links to the blogpost
💼 business	Business Development	People who execute on the business end
💻 code	Code	Links to commits by the user on this project
🖋 content	Content	e.g. website copy, blog posts are separate
🔣 data	Data	Links to contributed data for the project (both tests and datasets)
📖 doc	Documentation	Links to commits by the user on this project, Wiki, or other source of documentation
🎨 design	Design	Links to the logo/iconography/visual design/etc.
💡 example	Examples	Links to the examples
📋 eventOrganizing	Event Organizers	Links to event page
💵 financial	Financial Support	People or orgs who provide financial support, links to relevant page
🔍 fundingFinding	Funding/Grant Finders	People who help find financial support
🤔 ideas	Ideas & Planning
🚇 infra	Infrastructure	Hosting, Build-Tools, etc. Links to source file (like travis.yml) in repo, if applicable
🚧 maintenance	Maintenance	People who help in maintaining the repo, links to commits by the user on this project
🧑‍🏫 mentoring	Mentoring	People who mentor new contributors, links to the repo home
📦 platform	Packaging	Porting to support a new platform
🔌 plugin	Plugin/utility libraries	Links to the repo home
📆 projectManagement	Project Management
📣 promotion	Promotion
💬 question	Answering Questions	Answering Questions in Issues, Stack Overflow, Gitter, Slack, etc.
🔬 research	Research	Literature review.
👀 review	Reviewed Pull Requests
🛡️ security	Security	Identify and/or reduce security threats, GDPR, Privacy, etc
🔧 tool	Tools	Links to the repo home
🌍 translation	Translation	Links to the translated content
⚠️ test	Tests	Links to commits by the user on this project
✅ tutorial	Tutorials	Links to the tutorial
📢 talk	Talks	Links to the slides/recording/repo/etc
📓 userTesting	User Testing	Links to user test notes
📹 video	Videos	Links to the video

最近公共祖先（LCA）倍增法

发表于 2025-02-01 更新于 2025-02-03 分类于数据结构与算法本文字数： 1.4k 阅读时长 ≈ 5 分钟

原题：https://www.luogu.com.cn/problem/P3379

【模板】最近公共祖先（LCA）

题目描述

如题，给定一棵有根多叉树，请求出指定两个点直接最近的公共祖先。

输入格式

第一行包含三个正整数，分别表示树的结点个数、询问的个数和树根结点的序号。

接下来行每行包含两个正整数，表示结点和结点之间有一条直接连接的边（数据保证可以构成树）。

接下来行每行包含两个正整数，表示询问结点和结点的最近公共祖先。

输出格式

输出包含行，每行包含一个正整数，依次为每一个询问的结果。

样例 #1

样例输入 #1

样例输出 #1

提示

对于的数据，，。

对于的数据，，，不保证 。

样例说明：

该树结构如下：

第一次询问：的最近公共祖先，故为。

第二次询问：的最近公共祖先，故为。

第三次询问：的最近公共祖先，故为。

第四次询问：的最近公共祖先，故为。

第五次询问：的最近公共祖先，故为。

故输出依次为。

倍增法是一种用于在树中快速找到两个节点的最近公共祖先（LCA）的算法。它的核心思想是通过预处理和二进制跳跃来高效地找到公共祖先。

看了里面的题解，大概分为三步

深度优先搜索，获得每个结点的深度和祖先

dfs找深度和祖先

void dfs(int me,int fa) {
    // 填充倍增表，父节点表的大小是log2(depth)+1
    for (int i = 1; i <= lg[depth[me]]; ++i)
        father[me][i] = father[father[me][i - 1]][i - 1];
    for (int son : g[me])
        if (son!=fa)//不回环
        {
            depth[son] = depth[me] + 1;
            father[son][0] = me;
            dfs(son,me);
        }
}

father[x][i] 表示节点 x 向上跳 2^i 步后的祖先节点。
lg[depth[x]] 表示节点 x 的深度的对数值，用于确定最大跳跃步数。对数表可以提前生成好

void init_lg() {
    for (int i = 2; i < N; ++i)
        lg[i] = lg[i>>1] + 1;
}

表格如下：

x	0	1	2	3	4	5	6	7	8	9	…
lg[x]	0	0	1	1	2	2	2	2	3	3	…

寻找公共祖先，先将更深的点回溯到与另一个点深度相同的位置

快速回溯到深度相同

if (depth[x] < depth[y])
        swap(x, y);//让x比y深
while(depth[x]>depth[y])// 让x和y在同一深度
    x=father[x][lg[depth[x]-depth[y]]];
if (x == y) return x;

逐跳往上找公共祖先

for (int i = lg[depth[x]]; i >= 0; --i) // 逐步跳到二分的父节点
    if (father[x][i] != father[y][i])
        x = father[x][i],y = father[y][i];
return father[x][0];

从最大的 i 开始（即从最大的跳跃步数开始），逐步减少 i，检查节点 x 和 y 的 2^i 祖先是否相同。
如果 father[x][i] 和 father[y][i] 不相同，则将 x 和 y 更新为它们的 2^i 祖先。
目的：将 x 和 y 同时向上移动，直到它们的祖先相同。
当循环结束时，x 和 y 的最近公共祖先就是 father[x][0]，即 x 和 y 的直接父节点。

总代码

#include <bits/stdc++.h>
using namespace std;
const int N = 500005;

int n, q, root;
vector<int> g[N];

int lg[N];  // 用于存储每个节点的最大深度所需的倍增表大小
int father[N][31];  // father[i][j]:结点i的2^j祖先
int depth[N];//depth[i]:结点i的深度

// 初始化lg数组，计算log2的值
void init_lg() {
    for (int i = 2; i < N; ++i)
        lg[i] = lg[i>>1] + 1;
}

// 深度优先搜索，计算每个节点的父节点倍增表
void dfs(int me,int fa) {
    // 填充倍增表，父节点表的大小是log2(depth)+1
    for (int i = 1; i <= lg[depth[me]]; ++i)
        father[me][i] = father[father[me][i - 1]][i - 1];
    for (int son : g[me])
        if (son!=fa)//不回环
        {
            depth[son] = depth[me] + 1;
            father[son][0] = me;
            dfs(son,me);
        }
}

// 查询x和y的最低公共祖先
int lca(int x, int y) {
    if (depth[x] < depth[y])
        swap(x, y);//让x比y深
    while(depth[x]>depth[y])// 让x和y在同一深度
        x=father[x][lg[depth[x]-depth[y]]];
    if (x == y) return x;
    for (int i = lg[depth[x]]; i >= 0; --i) // 逐步跳到二分的父节点
        if (father[x][i] != father[y][i])
            x = father[x][i],y = father[y][i];
    return father[x][0];
}

int main() {
    scanf("%d%d%d", &n, &q, &root);
    init_lg();  // 初始化lg数组
    int x, y;
    for (int i = 1; i < n; i++) {
        scanf("%d%d", &x, &y);
        g[x].push_back(y);
        g[y].push_back(x);
    }
    // 初始化根节点
    dfs(root,root);  // 执行DFS，填充倍增表
    while (q--) {
        scanf("%d%d", &x, &y);
        printf("%d\n", lca(x, y));  // 查询LCA
    }
    return 0;
}

ffmpeg处理视频、音频等多媒体文件笔记

发表于 2025-01-31 更新于 2025-05-10 本文字数： 233 阅读时长 ≈ 1 分钟

一边使用，一边记录。

下载安装

windows

官网下载位置：https://www.gyan.dev/ffmpeg/builds/
按Ctrl-F，找到ffmpeg-release-essentials.zip，下载解压
设置环境变量为“【ffmpeg-release-essentials所在的路径】/bin”

linux

ubuntu

1	sudo apt install FFmpeg

其它：https://linux.cn/article-14716-1.html

使用

将某一文件夹的flac文件全部转化成wav文件

假设参数：16位PCM，采样率为44100Hz，双声道

1	for %%f in (*.flac) do (ffmpeg -i "%%f" -acodec pcm_s16le -ar 44100 -ac 2 "%%~nf.wav")

检查无误，批量删除原flac文件
如果要进行确认，就不加/q

1	del /q *.flac

提高亮度或者对比度

1 2	ffmpeg -i in.png -vf "eq=brightness=0.1" out.png ffmpeg -i in.png -vf "eq=brightness=0.1:contrast=1.1" out.png

其中亮度的基准为0，对比度的基准为1.0

将MP4视频去掉音频

1	ffmpeg -i input.mp4 -c:v copy -an output.mp4

将MP4视频每秒6帧转为800x480的bmp图片

1	ffmpeg -i input.mp4 -f image2 -vcodec bmp -s 800x480 -r 6 %d.bmp

C语言期末笔记（一）

发表于 2025-01-09 更新于 2025-01-21 分类于 C&&C++ 本文字数： 1.4k 阅读时长 ≈ 5 分钟

C语言复习过几遍，所以这里记录一些有点难记的东西。

数据类型

大小

整数类型：
short 2字节
int 4字节
long 8字节
浮点类型：
double 8字节
float 4字节
定义float类型时需写成：float num = 0.5f;（小数默认是double）
字符类型：
char 1字节
可以表示ASCLL码中所有的字符，不能表示中文等

占位（p73）

%占位：
printf格式化输出函数，%占位时有以下参数：%[占位长度][.精确位数（四舍五入）]占位格式

%d 为整数占位
%hd 为short整数占位
%ld 为long整数占位
%u 为unsigned整数占位
%lu，%hu..
对unsigned赋值负数，补码的首位依然被认为是1，但输出时这个1是会带入二进制计算的
%e 指数
例：printf("%e",123.456); 输出：1.234560e+002
例：printf("%13.2e",123.456); 输出：(四个空格）1.23e+002
%E %e的大写
%i 等同于%d
%o 八进制输出
%x 十六进制输出，小写
%X 十六进制输出，大写
%g 自动选择%f或者%e输出，小写
%G 自动选择%f或者%E输出，大写
%s 字符串

科学计数法

#include <stdio.h>
int main()
{
    printf("%lf\n", 123000000.0);      // 123000000.000000
    printf("%.2e\n", 123000000.0);     // 1.23e+008
    printf("%.2e\n", -123000000.0);    //-1.23e+008
    printf("%lf\n", 0.0000000123);     // 0.000000
    printf("%e\n", 0.0000000123);      // 1.230000e-008
    printf("%g\n", 0.0000000123);      // 1.23e-008
    printf("%.2e\n", 0.0000000123);    // 1.23e-008
    printf("%.2e\n", -0.0000000123);   //-1.23e-008
    printf("%lf, %e\n", .1e-2, .1e-2); // 0.001000, 1.000000e-003
    return 0;
}

舍入舍出

浮点型格式化输出，四舍五入：

1 2	float a; printf("%f\t%.2f\n", a, a);

浮点型强制转化，直接丢小数点后的

1	printf("%f\t%d\n", a, (int)a);

转义字符

转义字符	字符值
`\'`	‘
`\"`	“
`\?`	?
`\\`	`\`
`\a`	警告
`\b`	退格
`\f`	换页
`\n`	换行
`\r`	回车
`\t`	水平制表符
`\v`	垂直制表符
`\o、\oo、\ooo`，o代表一个八进制数字	与该八进制码对应的ASCLL字符
`\xh[h..]`，h代表一个十六进制数字	与该十六进制码对应的ASCLL字符

ASCII码

常见ASCII码：
‘ ‘: 32
‘0’: 48
‘A’: 65
‘a’: 97

运算符

优先级	运算符	运算对象个数	结合方向
1	( )		→👉
	[ ]
	->
	.
2	!	1	←👈
	~
	++
	--
	-
	(类型)
	*
	&
	sizeof
3	*	2	→👉
	/
	%
4	+	2	→👉
4	-	2	→👉
5	<<	2	→👉
5	>>	2	→👉
6	< <= > >=	2	→👉
7	==	2	→👉
7	!=	2	→👉
8	&	2	→👉
9	^	2	→👉
10	\|	2	→👉
11	&&	2	→👉
12	\|\|	2	→👉
13	? :	3	←👈
14	= += -= *= /= %= >>= <<= &= ^= \|=	2	→👉
15	,		→👉

文件操作

1. 文件类型指针

(p333)

用纸质笔记记录了。准备在C语言期末笔记（二）里面写

文件操作例子

#include <stdio.h>
int main()
{
    FILE *fp;
    int e;
    long len;
    char c;
    int status;
    fp = fopen("pi.tmp", "w");
    fputs("3.1415926", fp); // len=8,SEEK_SET=>0,SEEK_END=>9
    fclose(fp);
    fp = fopen("pi.tmp", "r");
    fscanf(fp, "%d%c", &e, &c);
    printf("e=%d,c=%c\n", e, c); // e=3,c=.

    //=============== fseek & ftell test start ===============
    len = ftell(fp);
    printf("before fseek:%ld\n", len); // 2，指向'1'之前
    status = fseek(fp, -1L, SEEK_END);
    printf("fseek -1 end:%ld (%d)\n", ftell(fp), status); // 8
    rewind(fp);                                           // void函数，没有返回值
    printf("rewind:%ld\n", ftell(fp));                    // 0
    status = fseek(fp, -1L, SEEK_SET);
    printf("fseek -1 set:%ld (%d)\n", ftell(fp), status); // 0，fseek失败
    status = fseek(fp, 111L, SEEK_SET);
    printf("fseek 111 set:%ld (%d)\n", ftell(fp), status); // 111，虽然比文件长了很多，但是fseek成功
    status = fseek(fp, -121L, SEEK_CUR);
    printf("fseek -121 cur:%ld (%d)\n", ftell(fp), status); // 111，fseek失败
    status = fseek(fp, -111L, SEEK_CUR);
    printf("fseek -111 cur:%ld (%d)\n", ftell(fp), status); // 0
}

例题

魔法阵

思路

第一排：if is middle: init 1; else: {row = a - 1;// ↓ col++;//→}		右上角：row++;//↓
row--;//↓ col++;//→	row--;//↓ col++;//→	最右列： row--;//↑ col = 0;//\|←
row--;//↓ col++;//→	row--;//↓ col++;//→	最右列： row--;//↑ col = 0;//\|←

1
2
3

if 已占数字:
    row = (row + 2) % a;//→→2，超出则|←
    col = (col + a - 1) % a;//←1，超出则→|

#include <stdio.h>
#include <string.h>
int main()
{
    int n = 3, num, row, col, a, a2;
    int arr[101][101];
    for (a = 1; a <= n; a+=2)
    {
        memset(arr, 0, sizeof arr);
        row = 0;
        col = a / 2;
        a2 = a * a;
        for (num = 1; num <= a2; num ++)
        {
            // printf("row: %d col: %d num: %d\n",row,col,num);
            arr[row][col] = num;
            if (row == 0 && col == a - 1)
            {
                row++;
            }
            else if (row == 0)
            {
                row = a - 1;
                col++;
            }
            else if (col == n - 1)
            {
                row--;
                col = 0;
            }
            else
            {
                row--;
                col++;
            }
            if (arr[row][col] != 0)
            {
                row = (row + 2) % a;
                col = (col + a - 1) % a;
            }
        }
        for (row = 0; row < a; row++)
        {
            for (col = 0; col < a; col++)
            {
                printf("%2d ", arr[row][col]);
            }
            putchar('\n');
        }
        putchar('\n');
    }
    return 0;
}

易错点

默认输出六位
1
printf("%f",f);
反常识define
1
2
#define true 0
#define false 1
switch不break就继续走
fseek(fp, 0L, 2);中，最后那个才是指示从哪儿开始的，即SEEK_END=2

计算机组成原理期末笔记（简答题）

发表于 2025-01-09 更新于 2025-05-12 分类于计算机组成原理本文字数： 2.5k 阅读时长 ≈ 9 分钟

第二章

小阶向大阶对齐的原因：
减小误差
什么叫溢出？
超出了机器的表示范围
计算机内部为什么大部分
全加器公式
全加器的时间延迟
行波进位补码加法器为什么m=0为加法，m=1为减法？
默写对2求补电路

alt text

直接补码阵列乘法器
最高位权值-1
间接补码阵列乘法器
算前求补的目的：补码变原码，扣掉符号位
算后求补的目的：原码变补码，存入计算器
原码除法：符号位单独运算
阵列除法器CAS用的是加减交替法
ALU电路的基本概念
先行进位
流水线特点：并行进行运算，速度快

[x]补+[y]补=[x+y]补的证明

补码加法的公式为：

$补补补$

</span>

证明：设x和y均为定点小数，且运算结果没有溢出。即 $︱︱ ﹤ ，︱︱ ﹤ ，︱︱ ﹤$

（1）x﹥0，y﹥0，则x+y﹥0。正数的补码和原码是一样的，可得：

[x]补+[y]补=x+y=[x+y]补 (mod 2)

（2）x﹥0，y﹤0，x+y≥0或x+y﹤0。
[x]补=x，
[y]补=2+y
[x]补+[y]补=x+2+y=2+(x+y)
- 当x+y≥0时，2 +(x+y) ≥2，对于模2来说，2被丢掉，于是
  [x]补+[y]补=x+y=[x+y]补 (mod 2)
- 当x+y﹤0时，2 +(x+y) ﹤2，于是
  [x]补+[y]补=2+(x+y)=[x+y]补
  (mod 2)
（3）x﹤0，y﹥0。
这种情况和第2种情况证明方法相同。
（4）x﹤0，y﹤0，则x+y﹤0。
[x]补=2+x，
[y]补=2+y
[x]补+[y]补=2+x+2+y=2+(2+x+y)
(2+x+y) 小于2而大于1的数，第一个2作为进位被舍弃。于是
[x]补+[y]补=2+(x+y)=[x+y]补 (mod 2)
至此我们证明了在模2意义下，两数的补码之和等于这两个数之和的补码。

第三章

高速缓冲存储器cache的目的
提升访问速度，使存取速度和CPU的运算相匹配
双译码结构优点
减少线的数目
刷新->行
地址复用技术
CDRAM DRAM里放一个SRAM
SRAM->静态存储器，比较小但快
DRAM->动态存储器
读取时高位不变，低9位连续变化
在SRAM读出期间同时对DRAM阵列进行刷新
写和读可以同时
SDRAM：同步DRAM-CPU在SDRAM执行请求CPU同时，CPU能先去做别的
DDR SDRAM：上升沿和下降沿均可读数据
SRAM和DRAM

	SRAM	DRAM
存储容量	小	大
功率	小	大
速度	快	慢
集成率	低	高
价格	贵	便宜
缓冲	高速缓冲	需要定期刷新

解决CPU和贮存之间速度差异的主要途径
- CPU内部设置更多通用寄存器
- CPU和主存之间插入高速缓冲存储器（cache）
- 采用并行操作的存储器（如双端口存储器）
- 主存储器采用更高速的技术来缩短读出时间，或加长存储器的字长
相连存储器：按内容访问所有存储器，主要用来存放cache的行地址
程序局部性：时间局部性和空间局部性
- 时间局部性：如果一个存储单元被访问，则可能该单元会很快被再次访问（因为程序存在着循环）
- 空间局部性：如果一个存储单元被访问，则该单元邻近的单元也可能很快被访问。（因为程序中大部分指令是顺序存储、顺序执行的，数据也是以向量、数组、树、表等形式簇聚地存储在一起的。）
主存与cache的地址映射(p94)
- 全相联映射方式
- 直接映射方式
- 级相连映射方式
cache的替换策略(p100)
- 最不经常使用(LFU)算法
- 近期最少使用(LRU)算法
- 随机替换

主存与cache的地址映射(p94)

	全相联映射方式	直接映射方式	组相联映射方式
主存地址长度	(s+w)位
页内地址	w位
寻址单元数	2^s+w字
块大小	2^w字
行大小	2^w字
主存的块数	2^s
标记位数	s位	(s-r)位	(s-d)位
组内块号		r位	d位
cache的行数	不由地址格式确定	m=2^r	m=uv
主存区内块号		cache行号	cache组号
每组的行数			v
cache的组数			u=2^d

PPT例题

一个四路组相联的Cache共有64行，主存有8192块，每块32个字，则主存地址中的主存字块标记(tag)为_位，组地址(组号)为_位，字块内地址为___位。
v=4
m=64=uv =>u=16
u=2^d => d=4
2^w=32 => w=5
2^s=8192=2^13 => s=13
∴ans: 9 4 5

某8位机主存1M字节，分成512块，Cache分8行，地址采用全相联映像方式，如图。

Cache容量多大？ 16KB
2^(s+w)=1M=2^20
s+w=20
2^s=512
s=9
w=20-9=11
2^w*8=2^14=16k
Cache的页内地址有多少位？ 11位
w=11
Cache的标记有多少位？ 9位
s=9

第四章

RISC和CISC的区别
CISC：复杂指令系统计算机
RISC：精简指令系统计算机
CISC比RISC指令系统庞大
为什么不同指令执行不同？
OP字段(操作码)不同。不同的op对应不同的指令
第四章拓展知识
|比较|RISC|CISC|
|-|-|-|
|名称|精简指令系统计算机|复杂指令系统计算机|
|时钟周期|通常1个|更多|
|控制|硬布线逻辑|微程序控制|
|指令种类|少|多|
|寻指方式|少|多|

两者都可以采用流水线技术，RISC更适合而已。

第五章

CPU的功能(p145)
- 指令控制
- 操作控制
- 时间控制
- 数据加工
同步/异步控制方式
- 各项操作采用/不采用统一的时钟信号控制
PC为什么加1？
为下一条指令做准备。
方框图中，为什么第一个方框能共用，后面的不行？
第一个方框是取指周期。
一个方框代表一个CPU周期
为什么取完指令后会有一个菱形框
判定测试，做的是指令译码，根据OP字段不同分析测试
微指令：在机器的一个CPU周期中，一组实现一定操作功能的微命令的组合
微程序：一条机器指令的功能是用许多条微指令组成的序列来实现的
为什么软件可以控制硬件？
指令的OP字段不一样。
为什么机器指令码的OP字段不一样？
地址转移后，强制置1的位置不一样，后面的分支和跳转不一样
机器指令和微程序的关系
- 一条机器指令对应的一个微程序，这个微程序由若干条微指令序列组成的
- 指令存放在存储器中；微指令存放在控制器中
- 一个CPU周期对应一条微指令，一个指令周期至少包含两个CPU周期（取指令，执行）
RISC的全称和特点
- 全称：精简指令系统计算机
- 一个有限的简单的指令系统
- CPU配备大量的通用寄存器
- 强调对指令流水线的优化

第五章拓展知识

同步/异步传输
- 同步传输：CPU↔内存储器、CPU↔PCI、CPU↔I/O
- 异步传输：I/O↔打印设备（基于缓存池）

第六章

总线分类(p189)
- 内部总线：CPU内部连接各寄存器及运算部件之间的总线，称为内部总线
- 系统总线：CPU同计算机系统的其他高速功能部件，如存储器、通道等互相连接的总线
- I/O总线：中、低速I/O设备之间相互连接的总线
总线带宽=总线位宽×总线工作频率
- 总线带宽：单位时间内总线上可传送的数据量
- 总线位宽：总线上能同时传送的数据位数。1/8/16/32位
- 总线工作频率：用于控制总线操作周期的时钟信号的频率
单总线结构特点：简单，易于扩充
双总线结构：ppt7
直接存储器DMA(Direct Memory Access)
如果由外围设备指定的地址对应于一个主存单元，则主存予以响应，于是在主存和外设之间将进行直接存储器传送
简单总线结构的不足之处
- CPU是总线上唯一的主控者
- 总线结构紧密与CPU相关，通用性较差
信息传送方式(p195)
- 串行传送
- 并行传送
- 分时传送
总线仲裁部件：以某种方式选择其中一个主设备作为总线的下一个主方(p198)
集中式仲裁：每个功能模块都有两条线连到总线控制器
- 总线请求信号线BR：送往仲裁器
- 总线授权信号线BG：仲裁器送出
在查询链中，离总线仲裁器最近的设备具有最高优先级
分布式仲裁：不需要集中的总线仲裁器
同步总线必须按最慢的模块来设计时钟

计算机网络期末笔记

发表于 2025-01-08 更新于 2025-10-11 分类于计算机网络本文字数： 6.4k 阅读时长 ≈ 23 分钟

Not just for exam. 后期不断补充新的知识。

第一章

OSI/RM参考模型

🚧施工中🚧

物理层：利用传输介质为数据链路层提供物理连接，负责处理数据传输并监控数据出错率，以便数据流的透明传输
数据链路层：在物理层提供的服务基础上，在通信的实体间建立数据链路连接，传输以“帧”为单位的数据包，并采用差错控制与流量控制方法，使有差错的物理线路变成无差错的数据链路
网络层：为数据在节点之间传输创建逻辑链路，通过路由选择算法为分组通过通信子网选择最适当的路径，以及实现拥塞控制、网络互联等功能
应用层：为应用软件提供了很多服务，实现具体的应用功能

网络协议

网络协议是为进行网络中的数据交换而建立的规则、标准或约定。由语法、语义和时序（或顺序或同步）三个要素组成。
语法，即数据与控制信息的结构或格式。
语义，即需要发出何种控制信息，完成何种动作以及做出何种响应。
时序，即事件实现顺序的详细说明。

各种协议

首部

首部（尾部）	长度(Byte)
以太网MAC帧首部和尾部	18
网络层IP首部	20（Max：60）
运输层UDP首部	8
运输层TCP首部	20（Max：60）

中间设备

将网络互相连接起来要使用一些中间设备

层次	中间设备
网络层以上	网关
网络层	路由器
数据链路层	网桥（桥接器）、交换机
物理层	转发器

数据传送单元

层次	单元
应用层	报文
运输层	报文段 TCP:报文段 UDP:用户数据报
网络层	包、分组 TCP/IP:IP数据报
数据链路层	帧
物理层	比特流

第二章物理层

信道的极限容量

奈奎斯特准则

在理想低通（没有噪声、带宽受限）信道中

:理想信通状态下的极限数据传输速率(bit/s或b/s或bps)
:信道的频率带宽(Hz)
:极限码原传输速率
:每个码元的离散电平数目(指有多少种不同的码元)

香农公式

$信噪比$

:信道的的极限数据传输速率(bit/s或b/s或bps)
:信道的频率带宽(Hz)
:信道内所传信号的平均功率
:信道内部的高斯信号功率

物理层4个特性

机械特性
电气特性
功能特性
过程特性

信道复用技术

(p56)

频分复用(FDM)
时分复用(TDM)
- 统计时分复用(STDM)
波分复用(WDM)
码分复用(CDM)

调制技术

调频FM
调幅AM
调相PM

第三章数据链路层

数据链路层的主要问题

封装成帧
透明传输
差错检测

网络拓补结构

局域网可按网络拓补分类(p84)

星形网（最广泛）
环形网
总线网
（网状）

数据链路层的两个子层

逻辑链路控制LLC
媒体接入控制MAC

CSMA/CD协议

载波监听多路访问/冲突检测协议(p87)
适用于总线形网络或半双工网络环境
CSMA/CD=多点载入+载波监听+碰撞检测

碰撞检测

电磁波在1km电缆的传播时延越为5μs
:单程端到端的传播时延
最迟要经过的时间才能知道自己发的数据和其他站发的是否发生碰撞
帧间最小间隔:9.6μs=96比特时间

100BASE-T以太网

在双绞线上传输(p106)

CSMA/CA协议

802.11标准定义了广泛适用于无线局域网的CSMA/CA协议，把冲突检测改为冲突避免

第四章网络层

Ip地址和Mac地址的区别

从层次的角度看，物理地址是数据链路层和物理层使用的地址。而IP地址是网络层及其以上各层使用的地址，是一种逻辑地址。

由于全世界存在各式各样的网络，使用不同的硬件地址。要使这些异构网络能够互相通信，就必须进行非常复杂的硬件地址转换工作。由用户或用户主机来完成这项工作几乎是不可能的事。但统一的IP地址把这个复杂问题解决了。连接到Internet的主机只需拥有统一的IP地址，它们之间的通信就像连接在同一个网络上那样简单方便。当需要把IP地址转换为物理地址时，使用ARP协议即可实现。

区别	IP地址	MAC地址
所在层	网络层	数据链路层
地址	逻辑地址	硬件地址
分配方式	基于网络拓补结构，通过手动或字典跟配，可以更改	基于制造商，与硬件绑定，全球唯一，一般不能更改
长度	4字节	6字节
寻址协议
地址使用	Internet协议	Erhernet协议

三种路由协议

协议	RIP	OSPF	BGP
中文	路由信息协议	开放最短路径优先协议	边界网关协议
路由算法	距离向量	链路状态	路径向量
算法基础	Bellman-Ford	Dijkstra
类型	内部网关协议IGP		外部网关协议EGP
层次	应用层	网络层	应用层
传递协议	UDP	IP	TCP
路径选择	跳数最少	代价最低	较好，非最佳
交换结点	和本结点相邻的路由器	网络中的所有路由器	和本结点相邻的路由器
交换内容	当前本路由器知道全部信息，自己的路由表	与本路由器相邻的所有路由器的链路状态	首次	整个路由表
交换内容	当前本路由器知道全部信息，自己的路由表	与本路由器相邻的所有路由器的链路状态	非首次	有变化的部分

IP的私有地址

私有地址分3类：
A类：第一段为10的都是私有地址
10.0.0.1 ~ 10.255.255.254
10.0.0.0表示整个网段，10.255.255.255是广播地址
B类：以172.16 ~ 172.31开头的都是私有地址
172.16.0.1 ~ 172.31.255.254
172.16.0.0表示整个网段，172.31.255.255是广播地址
C类：以192.168开头的都是私有地址
192.168.0.1 ~ 192.168.255.254
192.168.0.0表示整个网段，192.168.255.255是广播地址

单播和多播

在一对多通信中：
单播：点对点
多播：一点对多点
任播：终点是一组计算机，但数据报只交付其中一台，通常距离最近

常见网络命令

ping(p148)
tracert(p148)
nslookup
netstat
route
ipconfig

第五章运输层

udp和tcp

TCP/IP运输层的两个主要协议

用户数据报协议UDP
传输控制协议TCP

udp和tcp的特点

特点	UDP	TCP
主要特点	简单方便，但不可靠
连接	无连接	面向连接的运输层协议
可靠交付？	尽最大努力交付，不保证可靠交付所有维护可靠性的工作由用户在应用层完成	可靠交付无差错，不丢失，不重复，按序到达
方向	支持一对一，一对多，多对一，多对多的交互通信	每一条TCP连接只能有两个端点，每一条TCP连接只能是点对点的全双工通信
面向	报文	字节流（流入到进程或从进程流出的字节序列）
首部	开销小	开销大
拥塞控制	没有	有

虽然TCP面向字节流，但是采用的是对报文段的确认机制。

udp和tcp伪首部的作用

计算检验和。
把首部和数据部分一起检验。
udp的伪首部，协议号为17
tcp的伪首部，协议号为6

udp和tcp的首部

tcp可靠传输的工作原理

信道利用率

其中，
为信道利用率
为分组长度/数据率
为接收方发送确认分组需要的时间
为往返时间

停止等待协议

优点：简单
缺点：信道利用率太低

连续ARQ协议和滑动窗口协议

超时重传时间选择

第一次测量：

$样本$

后面：

$新的旧的新的样本$

其中，
为报文段的往返时间
为加权平均往返时间（平滑的往返时间）
为超时重传时间
是的偏差的加权平均值

tcp的流量控制

利用滑动窗口进行流量控制。
发送方的发送窗口不能超过接收方给出的接收窗口的数值。
TCP的窗口单位是字节，不是报文段。

tcp的拥塞控制

拥塞：

$对资源的需求可用资源$

拥塞控制：防止过多的数据注入到网络中，这样可以使网络中的路由器或链路不至于过载。

拥塞控制算法(p241)

MSS：最大报文段长度
cwnd：拥塞窗口
rwnd：接收方窗口（通知窗口）
ssthresh：慢开始门限
发送窗口的上限值=Min[rwnd,cwnd]

超时时，执行慢开始和拥塞避免
3-ACK时，执行快重传和快恢复

具体如下：

1.慢开始

由小到大逐渐增大注入到网络中的数据字节，由小到大逐渐增大拥塞窗口数值

tcp开始发送报文段时,先设置cwnd=1~2个MSS（目的：试探一下网络的拥塞情况），然后再逐渐增大cwnd。
发送方每收到一个对新报文的确认（不包括对重传的确认），就把发送方的拥塞窗口+1。即cwnd加倍

$初始$

$新的旧的$

当发送方判断网络拥塞（未按时收到确认）时

第一步：

$出现拥塞时的$
第二步：重新执行慢开始算法
目的：迅速减少主机发送到网络中的分组数，使得发生拥塞的路由器有足够时间把队列中积压的分组处理完。

2.拥塞避免

加法增大AI
拥塞窗口cwnd按线性规律缓慢增长，每经过一个往返时延RTT就把cwnd加1，而不是加倍。

$新的旧的$

目的：让拥塞窗口cwnd缓慢增大。

慢开始门限ssthresh的用法：

	算法
cwnd < ssthresh	慢开始
cwnd = ssthresh	拥塞避免
cwnd > ssthresh	慢开始或拥塞避免

当发送方判断网络拥塞（未按时收到确认）时

第一步：

$出现拥塞时的$
第二步：重新执行慢开始算法
目的：迅速减少主机发送到网络中的分组数，使得发生拥塞的路由器有足够时间把队列中积压的分组处理完。

慢开始和拥塞避免遇到网络拥塞，都要这么做。

3.快重传

发送方只要一连收到3个重复确认（3个冗余ACK），就可知道现在并未出现网络拥塞，而是接收方少收到一个报文段，因而立即重传相应的报文段，而不等待报文段的超时计时器再重传。
目的：让发送方尽早知道发生了个别报文段的丢失

4.快恢复

乘法减小MD
发送方连续收到3个冗余ACK时，

$新的当前$

然后执行拥塞避免算法（加法增大）

与慢开始算法不同的是，它不是将cwnd调整为1，而是减为一半。要预防网络发生拥塞，但发送方认为没有那么严重的拥塞。

tcp的有限状态机

alt text

第五章习题

课本p253

5-12

一个应用程序用 UDP, 到了IP层把数据报再划分为4个数据报片发送出去。结果前两个数据报片丢失，后两个到达目的站。过了一段时间应用程序重传UDP,而IP层仍然划分为4个数据报片来传送。结果这次前两个到达目的站而后两个丢失。试问：在目的站能否将这两次传输的4个数据报片组装为完整的数据报？假定目的站第一次收到的后两个数据报片仍然保存在目的站的缓存中。

解答：不行。重传时， IP数据报的标识字段会有另一个标识符。仅当标识符相同时IP数据报片才能组装成一个IP数据报。前两个IP数据报片的标识符与后两个IP数据报片的标识符不同，因此不能组装成一个IP数据报。

5-21

假定使用连续 ARQ 协议，发送窗口大小是3, 而序号范围是[0, 15]，而传输媒体保证在接收方能够按序收到分组。在某一时刻，在接收方，下一个期望收到的序号是5。试问：

(1) 在发送方的发送窗口中可能出现的序号组合有哪些？
(2) 接收方已经发送出的、但仍滞留在网络中（即还未到达发送方）的确认分组可能有哪些？说明这些确认分组是用来确认哪些序号的分组。

解答：

(1) 在接收方，下一个期望收到的序号是5。这表明序号到4为止的分组都已收到。若这些确认都已到达发送方，则发送窗口最靠前，其范围是[5,7]。
假定所有的确认都丢失了，发送方都没有收到这些确认。这时，发送窗口最靠后，应为[2, 4] 。因此，发送窗口可以是[2, 4], [3, 5], [4, 6], [5, 7]中的任何一个。

(2) 接收方期望收到序号5 的分组，说明序号为2,3,4的分组都已收到，并且发送了确认。
对序号为 1 的分组的确认肯定被发送方收到了，否则发送方不可能发送4号分组。可见，对序号为2,3,4的分组的确认有可能仍滞留在网络中。这些确认是用来确认序号为2,3,4的分组的。

5-68

在 TCP 的连接建立的三报文握手过程中，为什么第三个报文段不需要对方的确认？这会不会出现问题？

A在发送第三个报文段时有两种选择

仅仅是确认而不携带数据
不仅是确认，而且携带上自己的数据

当服务器端B在经过一段时间后未收到来自A的确认报文段，会终止这个半开状态，A必须重新建立TCP连接。这是第三个报文段的丢失导致TCP连接无法建立。
但假设A紧接着就发送数据，由于在数据报文段中，自己的序号不变，ACK=1，确认号是B的初始序号加1。当B收到这个报文段，就知道A收到了自己发送的SYN+ACK报文段，于是进入ESTABLISH状态。
A丢失了第三个报文段就不会造成影响。于是A发送第一种选择，只要紧接着发送数据报文段就无妨。

udp和tcp选择题

tcp首部没有目标主机ip地址
udp提供不可靠的传输服务，不需要对报文编号，所以不会有序列号字段。而tcp提供可靠的传输服务，因此需要设置序列号字段。
目的IP地址属于ip数据报中的内容。

第六章应用层

http的一次请求过程

在浏览器输入URL，并按下回车键。
浏览器向DNS服务器发出域名解析请求并获得结果。
根据目的IP地址和端口号，与服务器建立TCP连接。
浏览器向服务器发送数据请求
服务器将网页数据发送给浏览器
通信完成，断开TCP连接
浏览器解析收到的数据并显示

域名系统DNS

(p261)

电子邮件

(p296)

	SMTP	POP3	IMAP	MIME
中文	简单邮件传输协议	邮局协议	网际报文存取协议	通用互联网邮件扩充
功能	发件人的用户代理向邮件服务器发送邮件,以及发送方邮件服务器向接收方邮件服务器发送邮件	用户代理从接收方邮件服务器上读取邮件		增加邮件主体的结构

pop3和IMAP

区别		POP3	IMAP
复杂度		简单	复杂
特点		脱机协议,所有对邮件的处理者都在用户的PC机上进行	联机协议,用户可以操纵ISP的邮件服务器的邮箱
特点		从服务器读取邮件后就删除这个文件	在用户发出删除命令之前一直保存邮件
功能	收件箱	仅在客户端内	客户端与邮箱更新同步
	发件箱
	创建文件夹
	草稿
	垃圾文件夹	不支持	支持
	广告邮件	不支持	支持

MIME

SMTP的缺点

不能传送执行文件或其它的二进制对象
限于传送7为的ASCII码
拒绝超过一定长度的邮件
有的没有完全按照SMTP的互联网标准
- 回车换行
- 超过76字符的处理
- 多余空格的删除
- tab转换为若干个空格

因为SMTP存在一些缺点和不足,所以通过MIME并非改变或取代SMTP.MIME继续使用RFC822格式,但增加了邮件主体的结构,并定义了传送非ASCII码的编码规则.也就是说,MIME邮件可在已有的电子邮件和协议下传送.

包括:

5个新的邮件首部字段
邮件内容的格式
传送编码

DHCP

(p304)
动态主机配置协议
即插即用连网

端口地址

0-1023 是公认端口，通常分配给系统最关键的服务（如HTTP、FTP），普通用户程序不应使用。
1024-49151 是注册端口，可供用户进程或应用程序注册使用。
49152-65535 是动态端口，通常由客户端程序在需要时临时申请使用

端口号	传输层协议	服务/协议名称	简要说明
20	TCP	FTP-Data	文件传输协议的数据连接端口
21	TCP	FTP-Control	文件传输协议的控制连接端口，用于发送FTP命令
22	TCP	SSH	安全外壳协议，用于加密的远程登录和管理
23	TCP	Telnet	远程登录协议，因传输明文密码而不安全
25	TCP	SMTP	简单邮件传输协议，用于发送电子邮件
53	TCP 与 UDP	DNS	域名系统服务。UDP 53端口常用于查询，TCP 53端口用于区域传输等
69	UDP	TFTP	简单文件传输协议，用于小文件传输，如网络设备备份配置
80	TCP	HTTP	超文本传输协议，用于网页浏览
110	TCP	POP3	邮局协议版本3，用于从服务器接收电子邮件
143	TCP	IMAP	互联网消息访问协议，用于在服务器上管理邮件
161	UDP	SNMP	简单网络管理协议，用于网络设备的监控和管理
179	TCP	BGP	边界网关协议，用于互联网AS域间路由
389	TCP	LDAP	轻量目录访问协议，用于访问目录服务（如Microsoft Active Directory）
443	TCP	HTTPS	安全的超文本传输协议，用于加密的网页浏览

第七章网络安全

信息安全

机密性：不暴露给未授权的实体或进程
完整性：只有得到允许的人才能修改数据，能判别出数据是否已被篡改。未经授权不可改变！
可用性：得到授权的的实体在需要时可访问数据，攻击者不能占用所有的资源而阻碍授权者的工作
可控性：可以控制授权范围内的信息流向及行为方式
可审查性：对出现的信息安全问题提供调查的依据和手段

安全性威胁

(p334)

被动攻击
- 截获
- 流量分析
主动攻击
- 篡改
- 恶意程序
- 拒绝服务DOS

计算机病毒

引导区病毒：破坏引导盘、文件目录等
宏病毒：破坏OFFICE文件相关
木马病毒：控制操作
蠕虫病毒：自我复制，网络传播，消耗大量带宽，破坏文件，窃取敏感信息，并安装后门程序

安全

机密性
端点识别
信息的完整性
运行的安全性

密码体制

数据加密模型

明文
密文
密钥
加密算法
解密密钥
解密算法

两类密码体制

(p338)

对称密钥体制:加密密钥与解密密钥都是用相同密钥的密码体制

非对称密钥体制/公钥密码体制:使用不同的加密密钥与解密密钥

公钥加密,私钥解密

常见的对称加密算法：aes、des、md5等
常见的非对称加密算法有rsa、dsa、ecc等

数字证书、数字签名

用户A和B要进行安全通信，使用数字证书来对用户的身份进行认证；使用数字签名确保消息不可否认

第九章无线网络和移动网络

wifi从一代到七代，分别是802.11 b/a/g/n/ac/ax/be

DIFS, SIFS, CSMA/CA, DCF, PCF, SSID

DIFS (Distributed Inter-Frame Space)

定义：分布式帧间间隔，是IEEE 802.11无线局域网标准中定义的一种帧间间隔时间.
作用：用于在无线网络中管理信道访问，防止数据包碰撞.
特点：
- 当一个节点检测到信道空闲时，它会等待DIFS时间，然后尝试发送数据.
- 如果检测到信道忙，则等待信道空闲后再等待DIFS时间.
- DIFS是CSMA/CA协议的一部分，用于减少数据包碰撞的概率.

SIFS (Short Inter-Frame Space)

定义：短帧间间隔，是比DIFS更短的帧间间隔时间.
作用：用于高优先级的传输，如确认帧、数据帧的快速响应等.
特点：
- SIFS比DIFS短，因此具有更高的优先级.
- 在CSMA/CA协议中，SIFS用于快速响应，以减少传输延迟.

CSMA/CA (Carrier Sense Multiple Access with Collision Avoidance)

定义：带有冲突避免的载波侦听多路访问.
作用：无线局域网中的信道访问控制机制.
特点：
- 载波侦听：节点在发送数据前先侦听信道是否空闲.
- 冲突避免：通过使用DIFS和SIFS等帧间间隔来减少数据包碰撞.
- 二进制指数退避算法：如果发生碰撞，节点会等待一个随机时间后重试发送，以进一步降低碰撞概率.

DCF (Distributed Coordination Function)

定义：分布式协调功能.
作用：IEEE 802.11标准中定义的一种信道访问机制，基于CSMA/CA协议.
特点：
- 适用于无中心节点的无线网络，如对等网络.
- 使用DIFS和SIFS等帧间间隔来管理信道访问.
- 提供基本的信道访问控制，但不支持QoS（服务质量）.

PCF (Point Coordination Function)

定义：点协调功能.
作用：IEEE 802.11标准中定义的另一种信道访问机制，由中心节点（如AP）控制.
特点：
- 适用于有中心节点的无线网络，如基础设施网络.
- 中心节点负责调度和管理信道访问.
- 支持QoS，可以为不同优先级的数据提供不同的服务.

SSID (Service Set Identifier)

定义：服务集标识符.
作用：用于标识无线网络的名称.
特点：
- 用户可以通过输入正确的SSID来连接到特定的无线网络.
- SSID可以隐藏，以增加网络的安全性.
- SSID是区分不同无线网络的重要标识.