头像

小-胡-胡

东北大学




离线:5天前


最近来访(24)
用户头像
imnoob
用户头像
DPH
用户头像
string-s
用户头像
Albert_Seven
用户头像
不念过去_努力向前
用户头像
封禁用户
用户头像
南馆潇湘
用户头像
czk
用户头像
asc
用户头像
好好学算法
用户头像
huiyu
用户头像
tky
用户头像
和彦在等空银子
用户头像
Rice_Porridge
用户头像
-See_the_twinkle_star-
用户头像
yuwer
用户头像
yxc
用户头像
花白
用户头像
RyanMoriarty
用户头像
村东头那小伙儿_4

活动打卡代码 AcWing 868. 筛质数

利用埃氏筛法筛选质数

首先整理一般思路 o(nlogn):
将2-n数字排成一排,依次遍历每个数字,则当前遍历到的数字的倍数一定全部为合数,我们对每个数字的倍数全部都作一个标记,则每当我们遍历到一个数字时,如果它没有被标记则它一定为质数(它前面所有的数字都被遍历过了而它还没有被标记,则它一定不是某个数的倍数)

改进思路 o(nloglogn) 近似为 o(n):
我们不用将每个数字的倍数进行标记,只用标记质数的倍数即可,因为合数一个是某个数i的倍数,而该合数的倍数也一定是i的倍数,所以在我们遍历到i的时候已经将其标记过了

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1000010;

bool st[N];
int cnt;

void get_prime(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i]) 
        {
            cnt ++ ;

        }
        for (int j = i + i; j <= n; j += i) st[j] = true;
    }
    cout << cnt << endl;
}

int main()
{
    int n;
    cin >> n;
    get_prime(n);

    return 0;
}

利用线性筛法筛选质数 o(n)

核心思路:利用每个数的最小质因子筛除该数
核心代码:

for (int j = 0; prime[j] <= n / i; j ++ )
    {
        st[prime[j] * i] = true;
        if (i % prime[j] == 0) break;
    }

首先是关于循环的结束条件:由于我们规定了只用一个数的最小质因子将该数筛除,所以结束条件有两个:一是i遍历到了该数的最小质因子,另一个是i与质因子相乘已经大于n了所以结束循环
下面是有关筛除部分的两行代码的证明:
1.如果pj比i的最小质因子还要小,那么pj一定是pj * i的最小质因子。利用反证法进行证明,假设pj不是pj * i的最小质因子,那么设定n为其最小质因子(n比pj小),首先pj是质数一定不能被n整除,那么n一定就是i的最小质因子,那么可以推断出n比pj大,与前面的条件相矛盾了,所以pj一定是pj * i的最小质因子
2.如果pj是i的质因子,那么pj一定是pj * i的最小质因子。首先我们的质因子在存储时是按照从小到大的顺序进行存储的,所以先遍历到的质因子一定是i的最小质因子,当i乘以一个质数后它的最小质因子是不会发生改变的,所以结论一定是成立的

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1000010;

bool st[N];
int prime[N], cnt;

void get_prime(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i]) prime[cnt ++ ] = i;
        for (int j = 0; prime[j] <= n / i; j ++ )
        {
            st[prime[j] * i] = true;
            if (i % prime[j] == 0) break;
        }
    }

    cout << cnt << endl;
}

int main()
{
    int n;
    cin >> n;

    get_prime(n);

    return 0;
}


活动打卡代码 AcWing 867. 分解质因数

试除法分解质因数 o(logn) ~ o(sqrt(n))

质因数定义:
如果i是n的一个因子且i本身为质数,则i称为n的质因数

时间复杂度分析:
如果n是一个数的logn次方则为前者,如果n有一个大于sqrt(n)的质因数则为后者

思路分析:
i从2开始至n/i依次进行遍历,如果i能够被n整除,我们就一直用n除i直到无法被整除为止,这样能够保证每个被整除的i都是n的质因数(下图给出证明),最后如果剩下的n是大于1的话,那么n就是最后一个质因数(因为一个n最多只能有一个大于sqrt(n)的质因数,利用反证法即可证明)
QQ图片20220119142921.png

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

void divide(int n)
{
    for (int i = 2; i <= n / i; i ++ )
    {
        if (n % i == 0)
        {
            int s = 0;
            while (n % i == 0)
            {
                n /= i;
                s ++ ;
            }
            cout << i << ' ' << s << endl;
        }
    }
    if (n > 1) cout << n << ' ' << 1 << endl;
    puts("");
}

int main()
{
    int n;
    cin >> n;
    while (n -- )
    {
        int a;
        cin >> a;
        divide(a);
    }

    return 0;
}



试除法判断质数 o(sqrt(n))

质数定义:大于1的整数并且只能被1和它自己整除,又称素数

试除法思路:
1.先判断该数n是否大于1
2.i从2遍历到n/i判断n是否能被i整除,不写i * i <= n是防止整数溢出,不写i <= sqrt(n)是因为开根函数较慢

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

int n;

bool is_prime(int x)
{
    if (x <= 1) return false;
    for (int i = 2; i <= x / i; i ++ )
        if (x % i == 0) 
            return false;
    return true;
}

int main()
{
    cin >> n;
    while (n -- )
    {
        int a;
        cin >> a;
        if (is_prime(a)) puts("Yes");
        else puts("No");
    }

    return 0;
}



利用匈牙利算法进行二分图最大匹配

二分图匹配就是指在没有两条边公用一个点的情况下所能匹配的点的数量,而最大匹配就是指最大数量。故该算法又称为恋爱算法(bushi)

算法思路:
1.首先利用邻接表存边,虽然是无向图,但是我们其实只会用到一个方向,所以只存一次就可以
2.对于每个男生,我们都进行一次匹配,匹配成功就使答案加1
3.在匹配过程中,对于每个男生我们遍历一遍所有与他有关系的女生,如果该女生还未匹配,则直接进行匹配,如果该女生已经匹配,我们则尝试让与她匹配的男生换另外一个女生进行匹配
4.注意对于每个男生,遍历到的女生都要进行标记,在结束完一个男生的匹配之后要清空所有标记

思考过后的几个问题

1.标记非常重要,体现在:
(1)如果是在find(match[j])的过程中,说明其他的男生无论如何也不能遍历该女生,假设遍历了并且成功匹配,那么尝试的男生仍然不能匹配
(2)如果是在男生遍历完该女生且仍未匹配之后,那么标记就表示与该女生匹配的对象不可能更改对象,所以不能有任何男生尝试与该女生进行匹配,否则就会浪费时间

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 510, M = 100010;

int h[N], e[M], ne[M], idx;
int n1, n2, m;
int match[N];
bool st[N];
int u, v;
int res;

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

bool find(int x)
{
    for (int i = h[x]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!st[j])
        {
            st[j] = true;
            if (match[j] == 0 || find(match[j]))
            {
                match[j] = x;
                return true;
            }
        }
    }

    return false;
}

int main()
{
    cin >> n1 >> n2 >> m;
    memset(h, -1, sizeof h);
    while (m -- )
    {
        cin >> u >> v;
        add(u, v);
    }

    for (int i = 1; i <= n1; i ++ )
    {
        memset(st, 0, sizeof st);
        if (find(i)) res ++ ;
    }

    cout << res << endl;

    return 0;
}



利用深搜判断二分图思路

当一个图中不存在奇数环时,该图就为二分图。形象地表示就是用两个集合装入所有点,如果在一个集合中不存在两个点相连的情况那么该图就为二分图

思路:
1.用邻接表存储所有边的信息
2.遍历所有点,当该点未被上色时利用深搜将该点以及所有相邻的点进行上色,并同时判断是否有两个相邻的点被上了相同颜色
3.对结果做出判断

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010, M = 200010;

int h[N], e[M], ne[M], idx;
int n, m;
int u, v;
int color[N];

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

bool dfs(int u, int c)
{
    color[u] = c;
    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!color[j])
        {
            if (!dfs(j, 3 - c))
                return false;
        }

        else if (color[j] == c) return false;
    }

    return true;
}

int main()
{
    cin >> n >> m;
    memset(h, -1, sizeof h);
    while (m -- )
    {
        cin >> u >> v;
        add(u, v), add(v, u);
    }

    for (int i = 1; i <= n; i ++ )
        if (!color[i])
            if (!dfs(i, 1))
            {
                puts("No");
                return 0;
            }
    puts("Yes");

    return 0;
}



if 与 else if连用时else if会无视缩进对应到上一个没被括号包含的if或else if,也就是说如果在外层if中写了嵌套if,且外层if未加大括号的情况,那么本应对应外层if的else if会对应到内层的嵌套if上




kruskal算法求稀疏图的最小生成树思路 o(mlogm)

1.用结构体记录下每条边的信息
2.创建并查集
3.将所有边按照权重值进行排序
4.依次遍历所有边,如果边上的两个点未相连(不在一个并查集中),则将它们加入到一个并查集中,并更新答案
5.最后根据所连边数判断是否存在生成树

几个思考过后的问题

1.如果存在重边或者自环是否会影响最后的判断?
不会,自环是自己连接自己,自己肯定是在一个并查集中的,所以答案不会被更新。由于我们将边按照权重进行了排序,所以我们会先遍历到重边当中最短的一条,这时两个点已经在一个并查集中了,后面的重边不会再被遍历到了

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010, M = 200010;

struct Edge
{
    int u, v, w;

    bool operator< (const Edge &E) const
    {
        return w < E.w;
    }
}edge[M];

int n, m;
int p[N];
int cnt, res;

int find(int u)
{
    if (p[u] != u) p[u] = find(p[u]);
    return p[u];
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) p[i] = i;
    for (int i = 0; i < m; i ++ ) cin >> edge[i].u >> edge[i].v >> edge[i].w;

    sort(edge, edge + m);

    for (int i = 0; i < m; i ++ )
    {
        int a = find(edge[i].u), b = find(edge[i].v), c = edge[i].w;
        if (a != b)
        {
            p[a] = b;
            res += c;
            cnt ++ ;
        }
    }
    if (cnt < n - 1) puts("impossible");
    else cout << res << endl;

    return 0;
}



朴素prim算法求稠密图的最小生成树思路 o(n^2)

prim算法与Dijkstra算法非常相似,唯一区别在dist数组记录的是点到集合的距离而不是源点的距离

算法思路:
1.首先初始化邻接矩阵,需要注意处理重边
2.初始化所有点的dist为正无穷
3.遍历一遍所有点,找出距集合最近的点,并确定其距集合的距离就是最短距离,更新答案
4.利用确定的点更新所有点距集合的距离,并将已确定的点加入集合中
5.循环次数为n次,每次将一个点加入集合中

几个思考过后的问题

1.由于本题存在负权边同时本题不是到源点的距离,所以自环很可能会影响最终结果,故我们确定一个点后必须先更新答案再去更新其他点,避免自环影响
2.为什么本题要循环n次,而朴素版的Dijkstra只用循环n - 1次。因为后者是到源点的距离,只要前n - 1个点的所有距离都确定了,又有第n个点到所有点的距离都是确定的,所以第n个点就确定了。而本题是到集合的距离,与前面点的距离无关,所以必须要遍历n次

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 510, INF = 0x3f3f3f3f;

int n, m;
int g[N][N];    // 邻接矩阵,用于存储每条边的信息
int dist[N];    // 存储每个点到集合的距离
int u, v, w;
bool st[N];     // 记录每个点是否被加入了集合中

int prim()
{
    int res = 0;
    memset(dist, 0x3f, sizeof dist);

    for (int i = 0; i < n; i ++ )       // 遍历n次,每次往集合中加入一个点
    {
        int t = -1;
        for (int j = 1; j <= n; j ++ )  // 找出不存在集合中离集合最近的点
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;

        if (t != 1 && dist[t] == INF) return INF;       // 除了点1之外有距离为INF的点则表明不存在生成树
        if (t != 1) res += dist[t];

        for (int j = 1; j <= n; j ++ ) dist[j] = min(dist[j], g[t][j]);     // 更新所有点到集合的距离

        st[t] = true;                   // 对加入集合的点进行标记
    }

    return res;
}

int main()
{
    memset(g, 0x3f, sizeof g);  
    cin >> n >> m;
    while (m -- )       // 记录题目所给的每条边的信息
    {
        cin >> u >> v >> w;
        g[u][v] = g[v][u] = min(g[u][v], w);
    }

    int t = prim();

    if (t == INF) puts("impossible");
    else cout << t << endl;

    return 0;
}


活动打卡代码 AcWing 854. Floyd求最短路

floyd求多源汇最短路思路 o(n^3)

floyd用到了动态规划,d[k][a][b] 表示只经过1-k号点从点a到b的最短距离,完整的状态转移方程为d[k][i][j] = min(d[k - 1][i][j], d[k - 1][i][k] + d[k - 1][k][j]);,与背包问题类似,我们可以直接将第一维给优化掉

算法思路:
1.对邻接矩阵进行初始化
2.利用邻接矩阵储存每条边的信息
3.套用floyd算法模板直接将图中任意点到任意点的最短路径全部更新出来

思考过的几个问题

1.朴素版的Dijkstra算法也是用邻接矩阵存储,但是矩阵初始化时并没有筛选掉自环,因为根据算法原理自环会被自动滤去,而本题必须要在初始化时就滤去自环是因为本题的询问有可能是两个相同的点
2.根据算法原理,我们每次都要遍历所有的点来更新d数组,所以即使两个点ab不是互相连通的,由于负权边的存在d[a][b]可能会变小,最后判断路径不存在时要注意

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 210, M = 20010, INF = 1e9;

int n, m, k;
int x, y, z;
int d[N][N];

void floyd()
{
    for (int k = 1; k <= n; k ++ )
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= n; j ++ )
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}

int main()
{
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ )
            if (i != j) d[i][j] = INF;

    while (m -- )
    {
        cin >> x >> y >> z;
        d[x][y] = min(d[x][y], z);
    }

    floyd();

    while (k -- )
    {
        cin >> x >> y;
        if (d[x][y] > INF / 2) puts("impossible");
        else cout << d[x][y] << endl;
    }

    return 0;
}


活动打卡代码 AcWing 852. spfa判断负环

用spfa判断负环思路

想清楚一个问题就好:为什么能够判断负环?
因为一共只存在n个点,也就是说从一个点到另一个点最多只会经过n - 1条边,如果经过了n条边,那么说明路径中一定存在两个相同的点,又因为我们是求最短路径,根据我们的更新方式只有最短距离被更新过的点才会被遍历到,所以这个环一定是负环

几个思考过后的问题

1.cnt数组存储的不一定是第一个点到该点经过的边数
2.为什么可以不初始化dist数组?直接来看那就是初始所有点最短距离一样,只有负权边连接的点的最短距离才会被更新。
我们也可以自己画一个图模拟一下,根据本算法我们是一定可以找出负环的

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 2010, M = 10010;

int n, m;
int dist[N], cnt[N];
int h[N], e[M], ne[M], w[M], idx;
int x, y, z;
bool st[N];

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

bool spfa()
{
    queue<int> q;
    for (int i = 1; i <= n; i ++ ) 
    {
        st[i] = true;
        q.push(i);
    }

    while (q.size())
    {
        int t = q.front();
        q.pop();
        st[t] = false;

        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                cnt[j] = cnt[t] + 1;
                if (!st[j])
                {
                    q.push(j);
                    st[j] = true;
                }
                if (cnt[j] >= n) return true;
            }
        }
    }

    return false;
}

int main()
{
    memset(h, -1, sizeof h);
    cin >> n >> m;
    while (m -- )
    {
        cin >> x >> y >> z;
        add(x, y, z);
    }

    if (spfa()) puts("Yes");
    else puts("No");

    return 0;
}