个人空间 - AcWing

navystar

https://git.acwing.com/navy.star

关注数

粉丝数

阅读量

4.5万

+关注发消息

在线

最近来访(343)

长夜未央

yindujuxi

珂学家qwe

nothing_sybs

进餐小能手

谢广坤先生

最后五分钟

cyxbq

柏筱Bociao

小郑同学

Fkrito

incra

摆烂青年

Hasity

薯片

Warsaw

江晓_w

cannedfish

Ariesfun

一杯美式不加冰

活动打卡代码 AcWing 4286. 多少个答案是错误的

navystar
29分钟前

                //这里填你的代码^^#include <bits/stdc++.h>
using namespace std;
vector<int> p ,val;
inline void solve()
{
    int n, m, res = 0;
    cin >> n >> m;
    p.resize(n + 1 , 0), val.resize(n + 1, 0);
    for(int i = 0; i <= n;  i ++ ) p[i] = i;
    function <int (int)> find = [&](int x){
        if (p[x] == x) return p[x];
        int root = find(p[x]);
        val[x] += val[p[x]];
        p[x] = root;
        return p[x];
    };
    while (m -- )
    {
        int l, r, s;
        cin >> l >> r >> s;
        int px = find(l - 1), py = find(r);
        if (px != py)
        {
            p[px] = py;
            val[px] = s + val[r] - val[l - 1];
        }
        else
        {
            if (val[l - 1] - val[r] != s) res ++;
        }
    }
    cout << res << endl;
}
int main()
{
    cin.tie(nullptr) -> sync_with_stdio(0);
    solve();
    return 0;
}
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~

            

活动打卡代码 AcWing 4285. 多少张桌子

navystar
6小时前

                //这里填你的代码^^
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
const int N = 1e3 + 10;
int p[N];
int n, m;
inline void solve()
{
    cin >> n >> m;
    for (int i = 0; i <= n; i ++ ) p[i] = i;
    function <int (int)> find = [&](int x) {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    };
    for (int i = 0; i < m; i ++ )
    {
        int a, b;
        cin >> a >> b;
        if (find(a) != find(b)) p[find(a)] = find(b);
    }
    set<int> s;
    for (int i = 1; i <= n; i ++ )
        if (s.find(find(i)) == s.end()) s.insert(p[i]);
    cout << s.size() << endl;
}
int main()
{
    cin.tie(nullptr) -> sync_with_stdio(0);
    int t = 1;
    cin >> t;
    while (t -- ) solve();
    return 0;
}
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~

            

题解 AcWing 4285. 多少张桌子

navystar
6小时前

                并查集
C++ 代码
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
const int N = 1e3 + 10;
int p[N];
int n, m;
inline void solve()
{
    cin >> n >> m;
    for (int i = 0; i <= n; i ++ ) p[i] = i;
    function <int (int)> find = [&](int x) {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    };
    for (int i = 0; i < m; i ++ )
    {
        int a, b;
        cin >> a >> b;
        if (find(a) != find(b)) p[find(a)] = find(b);
    }
    set<int> s;
    for (int i = 1; i <= n; i ++ )
        if (s.find(find(i)) == s.end()) s.insert(p[i]);
    cout << s.size() << endl;
}
int main()
{
    cin.tie(nullptr) -> sync_with_stdio(0);
    int t = 1;
    cin >> t;
    while (t -- ) solve();
    return 0;
}



            

活动打卡代码 AcWing 4267. 可疑人员

navystar
6小时前

                //这里填你的代码^^
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
const int N = 1e6 + 10;
int p[N];
int n, m;
inline int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}
inline void solve()
{
    while(cin >> n >> m, n || m)
    {
        for (int i = 0; i < n; i ++ ) p[i] = i;
        while (m -- )
        {
            int k, x, y;
            cin >> k >> x;
            for (int i = 2; i <= k; i ++ )
            {
                cin >> y;
                p[find(x)] = find(y);
            }
        }
        int cnt = find(0), res = 0;
        for (int i = 0; i < n; i ++ ) 
            if (find(i) == cnt)
                res ++;
        cout << res << endl;
    }
}
int main()
{
    cin.tie(nullptr) -> sync_with_stdio(0);
    solve();
    return 0;
}
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~

            

题解 AcWing 4267. 可疑人员

navystar
6小时前

并查集

题目意思就是问每个集合元素与集合中第一个点合并，询问和0的祖宗节点相同的个数
暴力枚举下，看代码

C++ 代码

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
const int N = 1e6 + 10;
int p[N];
int n, m;
inline int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}
inline void solve()
{
    while(cin >> n >> m, n || m)
    {
        for (int i = 0; i < n; i ++ ) p[i] = i;
        while (m -- )
        {
            int k, x, y;
            cin >> k >> x;
            for (int i = 2; i <= k; i ++ )
            {
                cin >> y;
                p[find(x)] = find(y);
            }
        }
        int cnt = find(0), res = 0;
        for (int i = 0; i < n; i ++ ) 
            if (find(i) == cnt)
                res ++;
        cout << res << endl;
    }
}
int main()
{
    cin.tie(nullptr) -> sync_with_stdio(0);
    solve();
    return 0;
}

活动打卡代码 AcWing 220. 最大公约数

navystar
1天前

                //这里填你的代码^^
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e7 + 10;
int primes[N], cnt;
bool st[N];
int phi[N];
LL s[N];
inline void init(int x)
{
    for (int i = 2; i <= x; i ++ )
    {
        if (!st[i])
        {
            primes[cnt ++ ] = i;
            phi[i] = i - 1;
        }
        for (int j = 0; primes[j] * i <= x; j ++ )
        {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0)
            {
                phi[primes[j] * i] = phi[i] * primes[j];
                break;
            }
            phi[primes[j] * i] = phi[primes[j]] * phi[i];
        }
    }
    for (int i = 1; i <= x; i ++ ) s[i] = s[i - 1] + phi[i];
}
inline void solve()
{
    int n;
    cin >> n;
    init(n);
    LL res = 0;
    for (int i = 0; i < cnt; i ++ )
    {
        int p = primes[i];
        res += (2 * s[n / p] + 1);
    }  
    cout << res << endl;
}
int main()
{
    cin.tie(nullptr) -> sync_with_stdio(0);
    solve();
    return 0;
}
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~

            

题解 AcWing 220. 最大公约数

navystar
1天前

欧拉 + 枚举

来源： https://www.acwing.com/solution/content/25752/

C++ 代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e7 + 10;
int primes[N], cnt;
bool st[N];
int phi[N];
LL s[N];
inline void init(int x)
{
    for (int i = 2; i <= x; i ++ )
    {
        if (!st[i])
        {
            primes[cnt ++ ] = i;
            phi[i] = i - 1;
        }
        for (int j = 0; primes[j] * i <= x; j ++ )
        {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0)
            {
                phi[primes[j] * i] = phi[i] * primes[j];
                break;
            }
            phi[primes[j] * i] = phi[primes[j]] * phi[i];
        }
    }
    for (int i = 1; i <= x; i ++ ) s[i] = s[i - 1] + phi[i];
}
inline void solve()
{
    int n;
    cin >> n;
    init(n);
    LL res = 0;
    for (int i = 0; i < cnt; i ++ )
    {
        int p = primes[i];
        res += (2 * s[n / p] + 1);
    }  
    cout << res << endl;
}
int main()
{
    cin.tie(nullptr) -> sync_with_stdio(0);
    solve();
    return 0;
}

活动打卡代码 AcWing 287. 积蓄程度

navystar
1天前

                //这里填你的代码^^
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
const int N = 200010, M = N * 2, INF = 0x3f3f3f3f;
int n;
int h[N], e[M], w[M], ne[M], idx;
int d[N], f[N], deg[N];
inline void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}
inline int dfs_d(int u, int fa)
{
    if (deg[u] == 1)
    {
        d[u] = INF;
        return d[u];
    }
    d[u] = 0;
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j == fa) continue;
        d[u] += min(w[i], dfs_d(j, u));
    }
    return d[u];
}
inline void dfs_f(int u, int fa)
{
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j == fa) continue;
        if (deg[j] == 1) f[j] = w[i] < (f[u] - w[i]) ? w[i] : (f[u] - w[i]);
        else 
        {
            int cntr = w[i] < d[j] ? w[i] : d[j];
            int cntl = (f[u] - cntr) < w[i] ? (f[u] - cntr) : w[i];
            f[j] = d[j] + cntl;
            dfs_f(j, u);
        }
    }
}
inline void solve()
{
    scanf("%d", &n);
    memset(h, -1, sizeof h);
    memset(deg, 0, sizeof deg);
    idx = 0;
    for (int i = 0; i < n - 1; i ++ )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c), add(b, a, c);
        deg[a] ++, deg[b] ++;
    }
    int root = 1;
    while (root <= n && deg[root] == 1) root ++;
    if (root > n)
    {
        cout << w[0] << endl;
        return;
    }
    dfs_d(root, -1);
    f[root] = d[root];
    dfs_f(root, -1);
    int res = 0;
    for (int i = 1; i <= n; i ++ )
        if (res < f[i])
            res = f[i];
    cout << res << endl;
}
int main()
{
    int t = 1;
    scanf("%d", &t);
    while (t -- ) solve();
    return 0;
}
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~

            

新鲜事原文

navystar
1天前

240++题解
开心下😋
    

活动打卡代码 LeetCode 2712. 使所有字符相等的最小成本

navystar
2天前

                //这里填你的代码^^
class Solution {
public:
    long long minimumCost(string s) {
        long long res = 0;
        int n = s.size();
        for (int i = 0; i < n - 1; i ++ )
            if (s[i] != s[i + 1])
                res += min(i + 1, n - i - 1);    
        return res;
    }
};

//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~

            

0 评论

0 评论

并查集

C++ 代码

0 评论

0 评论

并查集

C++ 代码

0 评论

0 评论

欧拉 + 枚举

C++ 代码

0 评论

0 评论

3 评论

0 评论