洛谷

P3406 海底高铁

tag：差分

构造差分数组的方法比较巧

这也是在学了差分之后遇到的第一道应用相关知识的题目，不用差分会超时

  • 思路：

    这道题里面如果我们从城市 1 到城市 3 则需要走 1-2，2-3 这两条路，即走一次1号路，走一次2号路。

    构造差分数组d[N]：我们标记 d[1] 为 1，标记 d[3] 为 -1，之后计算前缀和，得到的即为每段路走的次数。

    对每一段出差都这么处理，可以大大简化计算的过程。最后我们判断每一段路走过的次数及买卡和买票的花费，选择花费小的即可。

  • 像这类结果可能很大的题目一定要注意数据范围，本题中总花费就可能很大，需要用long long

    int的取值范围为: -2^31——2^31-1,即-2147483648——2147483647

  • 差分数组的构造

AcWing

1583. PAT 计数

tag：前缀和

也是算法笔记上一道题

  • 我的代码：

    据说形式很像dp

    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
    #include <iostream>
    using namespace std;
    const int N = 1e5+10,M=1000000007;
    string s;
    int p[N],pa[N],pat[N];

    int main()
    {
        cin>>s;
        if(s[0]=='P')
            p[0]=1;
        for (int i = 1; i < s.size(); i ++ )
        {
            p[i]=p[i-1]%M;
            pa[i]=pa[i-1]%M;
            pat[i]=pat[i-1]%M;
            if(s[i]=='P')
                p[i]=p[i-1]+1;
            else if(s[i]=='A')
                pa[i]=pa[i-1]%M+p[i]%M;
            else if(s[i]=='T')
                pat[i]=pat[i-1]%M+pa[i]%M;
        }
        cout<<pat[s.size()-1]%M;
    }

  • 大佬的代码：

    //因为中间结果不用保存，求的是最终结果，所以其实没必要像求前缀和那样开个数组保存中间结果

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    #include <iostream>
    using namespace std;
    const int mod = 1e9 + 7;
    long long p, a, b, res;
    int main()
    {
        string str;
        cin >> str;
        for (auto c : str)
            if (c == 'P') p ++;
            else if (c == 'A') b += p;
            else res = (res + b) % mod;
        cout << res;
    }

  • 算法笔记上的答案：

    这个思路在判断>3个字符的串时不好用，就不复现了

    正着循环一遍统计字符P的前缀和，倒着循环一遍统计字符T的前缀和，再对每个A统计其参与构成的PAT个数，最后求和

257.关押罪犯

tag：拓展域并查集

贪心+排序+拓展域并查集

拓展域并查集：例题有本题和食物链，本题是食物链的简化版本

原本的并查集仅仅是普通的集合，拓展域并查集的集合之间有相互对立的性质，如本题中的罪犯相互对立，食物链中不同种类的动物相互对立

要表示这种相互对立的性质，可以使用拓展域，开的结点数是原来的2倍3倍，具体根据有几种对立的“阵营”

  • 本题：先贪心排序，之后按怨气值从大到小将每一对罪犯加入到互斥的两个域中。加入前要判断这对罪犯在不在一个并查集里，若不在，那么将两名罪犯加入到补集之中。若在一个并查集里，那么我们可以直接输出，因为我们使用贪心的思想，是从怨气值大的罪犯开始分隔的

  • 代码：

    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<bits/stdc++.h>
    using namespace std;
    const int N = 1e5+10;
    int n,m,p[N];

    struct node
    {
        int a,b,c;
    }e[N];
    int find(int x) //寻找根结点的find函数的写法
    {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }
    bool cmp(node a,node b)
    {
        return a.c>b.c;
    }
    int main()
    {
        cin>>n>>m;
        for (int i = 1; i <= m; i ++ )
            cin>>e[i].a>>e[i].b>>e[i].c;
        for (int i = 1; i <= (n<<1); i ++ )
            p[i]=i;
        sort(e+1,e+m+1,cmp);//自定义sort比较函数的写法
        for (int i = 1; i <= m; i ++ )
        {
            int x=find(e[i].a);
            int y=find(e[i].b);
            if(x==y)//在同一个集合 直接输出
            {
                cout<<e[i].c;
                return 0;
            }
            p[x]=find(e[i].b+n);//加入到其对立的拓展域
            p[y]=find(e[i].a+n);//加入到其对立的拓展域
        }
        cout<<0;
        return 0;
    }

力扣

2021.11.8

发现力扣自带的的笔记功能不错，支持一部分markdown，就打算只在这里记录自己A不掉的题目

2021.11.23

没更新本文的日子里都有在好好刷题，只是博主懒得写题解🙄

200.岛屿数量

date：2021.11.7

tag：BFS

BFS/DFS/并查集

在力扣上刷的第一道题，BFS暴搜即可解决

但刷的题还是太少，导致没办法第一时间联想：连通块的数量->BFS；连通块的大小：DFS

  • 熟悉力扣模式：

    • 不需要考虑头文件
    • 只写函数，不用写输入输出

  • 注意不要把BFS（队列）和DFS（栈-递归）搞混

    听的算法课还是不能仅仅停留在输入，一定要输出，多练

  • ==争取多点亮力扣小绿点！==