头像

AcWing_czy

HL




在线 


最近来访(373)
用户头像
hanyucan
用户头像
种花家的兔兔
用户头像
立志干翻丨IUV丶
用户头像
AcWing2AK
用户头像
wolf
用户头像
incra
用户头像
JcWing
用户头像
人间过客_追梦人
用户头像
磨糖fly
用户头像
太雪菜
用户头像
liumusi2022
用户头像
xtxxueyan
用户头像
种花家的市长
用户头像
lcjsjez
用户头像
wisdom2010
用户头像
窗外的麻雀
用户头像
忘打周赛
用户头像
HanlinXu
用户头像
那必须得是我了
用户头像
陌上花开Charlie


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

using namespace std;

const int N = 2e5 + 10;

int n, m;
int p[N];

struct Info
{
    int a, b, w;
}edges[N];

bool cmp(Info x, Info y)
{
    return x.w < y.w;
}

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

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

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

    int t = Kruscal();

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



#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int h[N], e[N], ne[N], idx;
int dd[N];
int n1, n2, m;
bool st[N];
int 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 (dd[j] == 0 || find(dd[j]))
            {
                dd[j] = x;
                return true;
            }
        }
    }
    return false;
}
int main()
{
    cin >> n1 >> n2 >> m;
    memset(h, -1, sizeof h);
    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 << endl;
}


活动打卡代码 AcWing 4508. 移动的点

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;

int main()
{
    int n, a, b;
    cin >> n >> a >> b;

    LL res = 0;
    map<LL, int> cnt;
    map<PII, int> s;
    while (n -- )
    {
        int x, vx, vy;
        cin >> x >> vx >> vy;

        LL y = vy - (LL)a * vx;
        res += (cnt[y] - s[{vx, vy}]) * 2;
        cnt[y] ++ ;
        s[{vx, vy}] ++ ;
    }

    cout << res << endl;

    return 0;   
}


活动打卡代码 AcWing 4505. 最大子集

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

using namespace std;

const int N = 1999997, null = 0x3f3f3f3f;

int h[N], a[N];
int ans[3], cur[3];
int n, mi = 0x3f3f3f3f;

int find(int x)
{
    int t = (x % N + N) % N;
    while (h[t] != null && h[t] != x)
    {
        t ++ ;
        if (t == N) t = 0;
    }
    return t;
}

int main()
{
    memset(h, 0x3f, sizeof h);
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ ) 
    {
        scanf("%d", &a[i]);
        mi = min(mi, a[i]);
    }
    sort(a + 1, a + n + 1);
    int idx = 0;
    for (int i = 1; i <= n; i ++ )
    {
        cur[0] = a[i];
        for (int j = 0; j <= 30; j ++ )
        {
            int idx1 = 1, k = 1;
            while (true)
            {
                int x = a[i] - (1 << j) * k;
                if (h[find(x)] == null || x < mi) break;
                cur[idx1 ++ ] = x;
                k ++ ;
            }
            if (idx < idx1)
            {
                idx = idx1;
                memcpy(ans, cur, sizeof cur);
            }
            if (idx == 3) break;
        }
        if (idx == 3) break;
        h[find(a[i])] = a[i];
    }

    printf("%d\n", idx);
    for (int i = 0; i < idx; i ++ ) printf("%d ", ans[i]);

    return 0;
}


活动打卡代码 AcWing 4503. 数对数量

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

using namespace std;

int a, b, n;
int ans;

int main()
{
    cin >> a >> b >> n;
    for (int i = 0; i <= a; i ++ )
        for (int j = 0; j <= b; j ++ )
            if (i + j == n) ans ++ ;
    cout << ans << endl;
    return 0;
}


活动打卡代码 AcWing 4504. 字符串消除

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

using namespace std;

string str, st;

int main()
{
    cin >> str;

    int res = 0;
    for (int i = 0; i < str.size(); i ++ )
    {
        if (st[st.size() - 1] != str[i]) st += str[i];
        else 
        {
            st.erase(st.size() - 1, 1);
            res ++ ;
        }
    }

    if (res % 2 == 1) puts("Yes");
    else puts("No");

    return 0;
}


活动打卡代码 AcWing 839. 模拟堆

#include <iostream>
#include <algorithm>
#include <string.h>

using namespace std;

const int N = 100010;

int h[N], ph[N], hp[N], cnt;

void heap_swap(int a, int b)
{
    swap(ph[hp[a]],ph[hp[b]]);
    swap(hp[a], hp[b]);
    swap(h[a], h[b]);
}

void down(int u)
{
    int t = u;
    if (u * 2 <= cnt && h[u * 2] < h[t]) t = u * 2;
    if (u * 2 + 1 <= cnt && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
    if (u != t)
    {
        heap_swap(u, t);
        down(t);
    }
}

void up(int u)
{
    while (u / 2 && h[u] < h[u / 2])
    {
        heap_swap(u, u / 2);
        u >>= 1;
    }
}

int main()
{
    int n, m = 0;
    scanf("%d", &n);
    while (n -- )
    {
        char op[5];
        int k, x;
        scanf("%s", op);
        if (!strcmp(op, "I"))
        {
            scanf("%d", &x);
            cnt ++ ;
            m ++ ;
            ph[m] = cnt, hp[cnt] = m;
            h[cnt] = x;
            up(cnt);
        }
        else if (!strcmp(op, "PM")) printf("%d\n", h[1]);
        else if (!strcmp(op, "DM"))
        {
            heap_swap(1, cnt);
            cnt -- ;
            down(1);
        }
        else if (!strcmp(op, "D"))
        {
            scanf("%d", &k);
            k = ph[k];
            heap_swap(k, cnt);
            cnt -- ;
            up(k);
            down(k);
        }
        else
        {
            scanf("%d%d", &k, &x);
            k = ph[k];
            h[k] = x;
            up(k);
            down(k);
        }
    }

    return 0;
}


活动打卡代码 AcWing 4500. 三个元素

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

using namespace std;

int n;
set<int> a;
int b[3005];

int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i ++ )
    {
        cin >> b[i];
        a.insert(b[i]);
    }
    if (a.size() < 3)
    {
        puts("-1 -1 -1");
        return 0;
    }
    int k = 0;
    for (auto x = a.begin(); x != a.end(); x ++ )
    {
        for (int i = 1; i <= n; i ++ )  
            if (*x == b[i])
            {
                cout << i << " ";
                break;
            }
        if (k == 2) break;
        k ++ ;
    }
}


活动打卡代码 AcWing 4501. 收集卡牌

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

using namespace std;

const int N = 1e5 + 10;

int n, m;
int a[N];
int cur;

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

    while (m -- )
    {
        int x;
        cin >> x;

        if (a[x] == 0) cur ++ ;
        a[x] ++ ;
        if (cur == n)
        {
            cout << 1;
            for (int i = 1; i <= n; i ++ )
            {
                a[i] -- ;
                if (a[i] == 0) cur -- ;
            }
        }
        else cout << 0;
    }

    return 0;
}


活动打卡代码 AcWing 4502. 集合操作

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

using namespace std;

const int N = 5e5 + 10;

int n, idx;
int opt, x;
int a[N];
int k;
double now, sum;

int main()
{
    cin >> n;
    while (n -- )
    {
        cin >> opt;

        if (opt == 1) 
        {
            cin >> x;

            a[ ++ idx] = x;
            while (k < idx && a[k + 1] <= (sum + a[idx]) / (k + 1))
            {
                k ++ ;
                sum += a[k];
            }
            now = max(now, a[idx] - (sum + a[idx]) / (k + 1));
        }
        else printf("%.6lf\n", now);
    }

    return 0;
}