2 条题解

  • 1
    @ 2022-03-30 20:21:38

    本来是想用暴力开掉,然后有5个点爆了……
    这道题还是典型并查集,附上并查集核心代码

    int find(int x)                     //查找结点 x的爸比
    {
        if(pre[x] == x) return x;       //递归出口:x的爸比为 x本身,即 x为孤儿        
        return pre[x] = find(pre[x]);   //此代码相当于先找到爸比 rootx,然后pre[x]=爸比 
    }
    
    
    

    这个是爆掉的能过15个点的暴力开,不过没试过卡常能多对几个点……
    哈哈就这样吧

    #include "bits/stdc++.h"
    using namespace std;
    #define N 100010
    
    struct Arr{
        bool vis;
        Arr() : vis(true) { }
        void Tip() { this->vis = true; }
        void Del() { this->vis = false; }
    };
    
    int n, m;
    Arr ans[N];
    
    int main()
    {
        int a = 0, b = 0;
        cin >> n >> m;
        while (m--)
        {
            char op;
            cin >> op;
            switch (op)
            {
            case 'D':
                cin >> a >> b;
                for (int i = a; i <= b; i++)
                {
                    ans[i].Del();
                }
                break;
            case 'Q':
                cin >> a;
                for (int i = a; i <= n; i++)
                {
                    if (ans[i].vis == true)
                    {
                        cout << i << endl;
                        break;
                    }
                }
                break;
            default:
                break;
            }
        }
        return 0;
    }
    
    
    
  • 0
    @ 2022-04-04 10:54:08
    #include<iostream>
    using namespace std;
    const int Max = 100010;
    int n,m;
    int cnt=0;
    int a[Max];
    int b[Max]; //路径压缩
    int P[Max];
    int f(int p){
        if(b[p]==p)return p;
        return f(b[p]);
    }
    int main() {
        cin >> n>>m;
        for(int i=1;i<=n;i++){
            a[i]=i;
            b[i]=i;
        }
        for(int i=1;i<=m;i++){
            char s;cin>>s;
            if(s=='D'){
                int c,d;cin>>c>>d;
                for(int j=c;j<=d;j++)b[j]=d+1;
            }
            if(s=='Q'){
                int c;cin>>c;
                P[cnt++]=f(b[c]);
            }
        }
        for(int i=0;i<cnt;i++)cout<<P[i]<<endl;
        return 0;
    }
    
    
    
  • 1

信息

ID
3066
难度
6
分类
并查集 点击显示
标签
(无)
递交数
45
已通过
4
通过率
9%
上传者