头像

原神高手




离线:15小时前


最近来访(36)
用户头像
安意
用户头像
和光同尘_3
用户头像
二垚
用户头像
青玄
用户头像
没有陷的包子
用户头像
Panson
用户头像
我永远喜欢七海
用户头像
白金之星.
用户头像
Z-Wiskey
用户头像
kewu
用户头像
不AK不改名123
用户头像
道理都懂就不ac
用户头像
社会废人
用户头像
万星时代

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

原神高手
16小时前

线性筛法

#include<iostream>
#include<algorithm>
using namespace std;

const int N = 1000010;

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

int get_primes(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;  //如果当i%prime[j]==0时,代表i的最小质因数是prime[j],那么i*prime[j+k]这个合数的最小质因数就不是prime[j+k]而是prime[j]了。
        }                           //所以i*prime[j+k]应该被prime[j]筛掉,而不是后续的prime[j+k]。于是在此时break。    

    }
    return cnt;
}

int main()
{
    cin >> n;

    get_primes(n);

    cout << cnt << endl;

    return 0;
}


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

原神高手
16小时前

埃氏筛法

#include<iostream>
#include<algorithm>
using namespace std;

const int N = 1000010;

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

int get_primes(int n)
{
    for(int i = 2; i <= n; i++)
    {
        if(!st[i])
        {
            prime[cnt++] = i; //存储质数
            for(int j = 2 * i; j <= n; j += i) st[j] = true; //如果是i的倍数,就筛掉(i为质数)
        }

    }
    return cnt;
}

int main()
{
    cin >> n;

    get_primes(n);

    cout << cnt << endl;

    return 0;
}


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

原神高手
16小时前

优化后时间复杂度O(√n),不优化为O(n)

#include<iostream>
#include<algorithm>
using namespace std;

int n;

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; //n将质因子除尽,保证了自己是一个质数
                s++;
            }
            printf("%d %d\n", i, s);
        }
    }
    if(n > 1) printf("%d %d\n", n, 1); //说明这就是大于sqrt(n)的唯一质因子
}

int main()
{
    cin >> n;
    while(n--)
    {
        int x;
        cin >> x;
        divide(x);
        printf("\n");
    }
}



时间复杂度O(√n),不优化为O(n)

#include<iostream>
#include<algorithm>
using namespace std;

int n;

bool is_prime(int a)
{
    if(a < 2) return false;
    for(int i = 2; i <= a / i; i++) //一个数的因数是成对出现的,只枚举较小的那个,时间复杂度为根号n
    {
        if(a % i == 0) return false;
    }
    return true;
}

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

}



匈牙利(ntr)算法,匹配男女朋友

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

const int N = 510, M = 100010;

int n1, n2, m;
int h[N], e[M], ne[M], idx;
int match[N]; //match[j]=a,表示女孩j的现有配对男友是a
bool st[N];   //st[j]=a表示一轮模拟匹配中,女孩j被男孩a预定了。

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

//这个函数的作用是用来判断,如果加入x来参与模拟配对,会不会使匹配数增多
bool find(int x)
{
    //遍历自己喜欢的女孩
    for(int i = h[x]; i != -1; i = ne[i])
    {
        int j = e[i];
        if(!st[j])  //如果这一轮匹配中女孩j未被预定
        {
            st[j] = true; //更新状态,j被预定

            if(!match[j] || find(match[j])) //如果j没有男朋友 或者 j的男朋友(match[j])能够匹配另一个喜欢的女孩(find(match[j]))
            {
                match[j] = x;  //就把j的男朋友变为x
                return true;
            }
        }
    }
    return false;
}

int main()
{
    memset(h, -1, sizeof(h));
    cin >> n1 >> n2 >> m;

    while(m--)
    {
        int a, b;
        cin >> a >> b;
        add(a, b);
    }

    int res = 0; //记录最大匹配数
    for(int i = 1; i <= n1; i++)
    {
        memset(st, false, sizeof(st));
        if(find(i)) res++; //匹配成功
    }
    cout << res;

    return 0;
}



#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

const int N = 100010, M = 200010;

int n, m;
int h[N], e[M], ne[M], idx;
int colour[N];

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

bool dfs(int u, int c)
{
    colour[u] = c;
    for(int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if(!colour[j])
        {
            if(!dfs(j, 3 - c)) return false; //如果 u 的颜色是2,则和 u 相邻的染成 1
        }
        if(colour[j] == c) return false; //如果一条边两个点颜色相同,则冲突
    }
    return true;
}

int main()
{
    memset(h, -1, sizeof(h));

    cin >> n >> m;
    while(m--)
    {
        int a, b;
        cin >> a >> b;
        add(a, b), add(b, a);
    }

    bool flag = true;
    for(int i = 1; i <= n; i++)
    {
        if(!colour[i])
        {
            if(!dfs(i, 1))    //染色该点,如果发生冲突就break
            {
                flag = false;
                break;
            }
        }
    }
    if(flag) puts("Yes");
    else puts("No");

    return 0;
}



#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

const int N = 200010;

int p[N];
int n, m;

struct Edge
{
    int a, b, w;

    bool operator< (const Edge &W) const //重载<号,为了排序时按照边权排序
    {
        return w < W.w;
    }
}edges[N];

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

int Kruskal()
{
    int res = 0, cnt = 0;
    for(int i = 0; i < m; i++)
    {
        int a = edges[i].a, b = edges[i].b, w = edges[i].w;
        if(find(a) != find(b))
        {
            p[find(a)] = find(b);
            res += w;
            cnt ++;
        }
    }
    if(cnt < n - 1) return 0x3f3f3f3f;
    else return res;
}

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

    for(int i = 0; i < n; i++) p[i] = i;

    for(int i = 0; i < m; i++)
    {
        int a, b, w;
        cin >> a >> b >> w;
        edges[i] = {a, b, w};
    }

    sort(edges, edges + m);

    int t = Kruskal();

    if(t == 0x3f3f3f3f) puts("impossible");
    else cout << t;

    return 0;
}



#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

const int N = 510, INF = 0x3f3f3f3f;
int n, m;
int g[N][N];
int dist[N];
bool st[N];

int prim()
{
    memset(dist, 0x3f, sizeof(dist));
    dist[1] = 0;

    int res = 0;
    for(int i = 0; i < n; i++)
    {
        int t = -1; 
        for(int j = 1; j <= n; j++)
        {
            if(!st[j] && (t == -1 || dist[t] > dist[j])) t = j;
        }
        if(dist[t] == INF) return INF;

        res += dist[t];
        st[t] = true;

        for(int j = 1; j <= n; j++ ) dist[j] = min(dist[j], g[t][j]);

    }
    return res;
}

int main()
{
    memset(g, 0x3f, sizeof(g));
    cin >> n >> m;
    while(m--)
    {
        int a, b, c;
        cin >> a >> b >> c;
        g[a][b] = g[b][a] = min(g[a][b], c);
    }

    int t = prim();

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

    return 0;
}


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

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

const int N = 210;

int n, m, Q;
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()
{
    memset(d, 0x3f, sizeof(d));

    cin >> n >> m >> Q;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            if(i == j) d[i][j] = 0;
        }
    }

    while(m--)
    {
        int a, b, c;
        cin >> a >> b >> c;
        d[a][b] = min(d[a][b], c);
    }

    floyd();

    while(Q--)
    {
        int a, b;
        cin >> a >> b;
        if(d[a][b] > 0x3f3f3f3f / 2) puts("impossible");
        else cout << d[a][b] << endl;
    }

}


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

#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;

const int N = 10010;

int n, m;
int e[N], ne[N], h[N], w[N], idx;
int dist[N], cnt[N]; //cnt[N] 表示1到x的最短路的边数
bool st[N];

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

int spfa()
{
    queue<int> q;
    for(int i = 1; i <= n; i++) //点1可能到不了有负环的点,因此将所有点加入队列
    {
        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(cnt[j] >= n) return true; //如果超过n,根据抽屉原理,肯定经过同一个点两次,说明有环
                if(!st[j])
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }
    return false;
}

int main()
{
    memset(h, -1, sizeof(h));
    cin >> n >> m;
    while(m--)
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
    }
    if(spfa()) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}