Atcoder ABC 392

compaq · 2025-02-12 11:07:08 · 题解

E - Cables and Servers

假设一开始有k个联通块，因为每条边一定会让联通块的个数减1，所以最多只需要k - 1条边，就能让连通块的个数变成 1.

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+5;
int f[N];
int find(int x){
    if(f[x] == x) return x;
    return f[x] = find(f[x]);
}
array<int, 3>edg[N];

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

    for(int i = 1; i <= n; i++) f[i] = i;

    vector< array<int, 3> >vec;

    for(int i = 1; i <= m; i++){
        cin >> edg[i][0] >> edg[i][1];
        edg[i][2] = i;

        int fu = find(edg[i][0]), fv = find(edg[i][1]);
        if(fu == fv){
            vec.push_back(edg[i]);//存储多余的边
        }else{
            f[fu] = fv;
        }
    }

    set<int>st;//存储所有连通块的祖先
    for(int i = 1; i <= n; i++) st.insert(find(i));

    cout << st.size() - 1 << endl;

    int id = 0;//目前使用多余边的编号

    while(st.size() > 1){
        int u = vec[id][0], v = vec[id][1], i = vec[id][2];
        //左端点 右端点 编号
        cout << i << ' ' << v << ' ';

        int fa = find(u);// u的祖先连接到其他连通块，则u的祖先会消失 
        st.erase(fa);
        int nfa = *st.begin();// u的祖先可以连接到当前st中任意一个节点上 
        f[fa] = nfa;
        cout << nfa << endl;
        id++;
    }

    return 0;
}

F - Insert

考虑逆向插入，这样处理，插入完成的点就不会再被改动位置。

比如样例1：模拟逆向插入的过程：

• 第一步：将4插入到位置1，即a[1] = 4;
• 第二步：将3插入到位置2，本来是a[2] = 3, 但是由于第一步操作，使得3的位置后移到3的位置,即a[3] = 3
• 第三步：将2插入到1位置，此时1位置被4占用，所以，2需要挪后到2位置。
• 第四步，将1插入到1位置，但是1位置被占用，需要往后挪，但是发现位置2,3都被占用，只能往后到4位置。

综上，对i插入到位置p[i], 锁定位置的方法为：从头往后数第p[i]个空的位置。所以，需要统计空位的个数。

• 可以利用树状数组来维护空位置的数量。

• 借助树状数组的统计，二分来快速锁定位置。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
#define int long long
#define lowbit(x) x & (-x)
int n, p[N], a[N], tr[N];
//tr[i] = 0/1  第i个位置的数字有没有被删除
void update(int x, int d){
    while (x <= n){
        tr[x] += d;
        x += lowbit(x);
    }
}

int query(int x){
    int res = 0;
    while (x){
        res += tr[x];
        x -= lowbit(x);
    }
    return res;
}

signed main(){
    cin >> n;
    for (int i = 1; i <= n; i++){
        cin >> p[i];
        update(i, 1);
    }
    for (int i = n; i >= 1; i--){
        int l = 1, r = n, ans = 0;
        while (l <= r){
            int mid = (l + r) >> 1;
            if (query(mid) >= p[i])
                ans = mid, r = mid - 1;
            else
                l = mid + 1;
        }
        printf("%d %d\n", i, ans); 
        a[ans] = i;
        update(ans, -1);
    }
    for (int i = 1; i <= n; i++)
        cout << a[i] << " ";
    return 0;
}