Atcoder ABC 392

假设一开始有

k

个联通块，因为每条边一定会让联通块的个数减1，所以最多只需要

k - 1

条边，就能让连通块的个数变成 1.

CPP

#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]个空的位置。所以，需要统计空位的个数。

可以利用树状数组来维护空位置的数量。
借助树状数组的统计，二分来快速锁定位置。

CPP

#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;
}

文章操作

相关推荐

评论

Atcoder ABC 392