Atcoder ABC 396

对于每一组

X_i、Y_i、Z_i

，我们建立一条以

X_i

到

Y_i

权值为

Z_i

的双向边。这样可以把条件抽象成一张图，且这张图不一定是联通的，可能会被分为若干个块。

对于每一个块，任选一个点当做起点跑一遍dfs，假设我们确定了这个起点的值，通过边(异或关系)进行传递，这个连通块所有的值都可以确定。

如果某个点被遍历过，且第二次（或更多次)到达该点的异或值，与之前保存的结果不一致，则意味着这个点不能确定，可以直接判定无解的情况。

接下来需要处理

\sum a_i

的最小值。

每个连通块都是独立的，那么只需要每个连通块的和最小。

在计算某连通块时，每次出发点的值初始值都是

0

,此时会得到同个连通块剩余点

i

的值

a[i]

,由于异或计算每一位都是独立的，则我们统计同个连通块内每个数，在二进制下同一位的

1

的个数，若

1

的数量超过一半，则这位上的

0

和

1

进行翻转。

其他连通块同样处理即可。

CPP

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e6 + 5;
int n,m,ans[N],vis[N],f,t,w;
vector<pair<int,int> > v[N];
vector<int> q;

void dfs(int x, int sum){
	if(vis[x]) {
		if(ans[x] != sum){ 
			cout << -1; 
			exit(0); 
		} 
		return; 
	}
	vis[x] = 1; ans[x] = sum; q.push_back(x);
	for(int i = 0; i < v[x].size(); i ++){
		int y = v[x][i].first;
		int w = v[x][i].second;
		dfs(y,sum ^ w);
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin >> n >> m;
	for(int i = 1;i <= m; i ++){ 
		cin >> f >> t >> w;
		v[f].push_back({t, w});
		v[t].push_back({f, w});
	}
	for(int i = 1; i <= n; i ++){
		if(vis[i]) continue;
		dfs(i, 0); // 假设起点为0  		
		for(int j = 0; j < 30; j ++){
			int cnt = 0;
			for(int i = 0; i < q.size(); i ++){
				int y = q[i];
				if(ans[y] & (1 << j)) cnt ++;
			}
			// 如果起点第j位取0时的1超过半数，翻转连通块所有j位 
			if(cnt + cnt > q.size()){
				for(int i = 0; i < q.size(); i ++){
					int y = q[i];
					ans[y] ^= (1 << j);
				}
			}
		}
		q.clear();
	}
	for(int i = 1;i <= n;i ++) cout << ans[i] << " ";
  return 0;
}

/*
5 4
4 2 6
2 3 10
4 5 0
3 1 9
*/

F - Rotated Inversions

当 $k = 0$ , 答案就是原数组的逆序对的数量
当 $k = 1$ 时,可以发现影响逆序对的只有 $a_i \% m = m−1$ 的值。因为此时 $(a_i + 1) \% = 0$ ,相当于 $a_i$ 从最大值变成了最小值，对逆序对的贡献会造成改变。
而除了 $a_i \% m = m−1$ 的位置，任意两个位置的大小关系都不会变，不会对逆序对造成影响。
假设满足 $a_i \% m = m−1$ 的位置分别是 $v = [v_1, v_2, v_3...v_k]$ ，那么对于 $v_i$ 分析，发现：
- $[1, v_i-1]$ 除了 $v$ 数组中的数，都会与 $v_i$ 形成逆序对，也就是会增加 $v_i-i$ .(减去 $i$ 个与本身相同的数)
- $[v_i+1, n]$ 除了 $v$ 数组中的数，原本的逆序对都会消失，也就是会减少， $v_i$ 后面有 $n-v_i$ 个数，减去重复的数，就是之前形成的逆序对数量，在 $[v_i+1, n]$ 中与 $a_{v_i}$ 相等的个数为： $a_{v_i}$ 总个数-前面的个数
为了方便计算，我们不枚举下标，而是枚举数值从 $i = m-1$ 开始计算，即先处理 $m-1$ ，再处理 $m-2,m-3$ ...

CPP

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int tr[N], a[N];
int n, m;
vector<int>g[N];
vector<pair<int, int> >vec;

int lowbit(int x){
	return x & -x;
}

void update(int x){
	while(x < N){
		tr[x] += 1;
		x += lowbit(x); 
	}
}

int query(int x){
	long long s = 0;
	while(x){
		s += 1ll * tr[x];
		x -= lowbit(x);
	}
	return s;
}

int main(){
	cin >> n >> m;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
		vec.push_back({a[i], i});
		g[a[i]].push_back(i);
	}
	
	sort(vec.begin(), vec.end(), greater<pair<int, int>>() );	
	long long ans = 0;
	for(auto t : vec){
		ans += query(t.second);
		update(t.second); 
	}
	cout << ans << endl; // 原逆序对数量 
	
	for(int i = m - 1; i >= 1; i--){
		for(int j = 0; j < g[i].size(); j++){
			ans += 1ll * (g[i][j] - j - 1);
			ans -= 1ll * ((n - g[i][j]) - (g[i].size() - j - 1));
		}
		cout << ans << '\n';
	}
	return 0;
}

文章操作

相关推荐

评论

Atcoder ABC 396