首页 > 其他 > 详细

题解 [ABC155F] Perils in Parallel

时间:2020-03-25 20:50:21      阅读:67      评论:0      收藏:0      [点我收藏+]

题目描述

平面上有 \(n\) 个点,每个点有一个位置是 \(p_i\) 和一个状态 0 / 1。

\(m\) 个操作,每个操作将 \(l_i \to r_i\) 的点全部翻转。

问可不可以将所有点都翻成 0,如果可行输出方案。

正解

一次操作将 \(l \to r\) 全部翻转,翻转的点太多了,可不可以让翻转的点少一些?

考虑”做差“,令排序后第 \(i\) 个点的状态为 \(s_i \operatorname{xor} s_{i - 1}\),这样每次翻转只会变动两个位置 \(l_i\)\(r_{i + 1}\)

将所有操作的 \(l_i\)\(r_i\) 连边,发现一个联通块里面每次可以选两个状态为 1 的点进行一次消除。

那么每个联通块只要判断一下 1 的奇偶性就可以确定是否有答案了。

考虑怎么构造一组解,状态为 1 的点可以通过一条边的操作到达另一短,那么我就让一个联通块内的点都到 \(dfs\) 树的根节点就好了。

从当前节点到根节点路径的边全部 + 1 操作,树差分可以解决,最后输出操作数为奇数的边即可。

\(\color{DeepSkyBlue} {Code}\)

#include <bits/stdc++.h>
#define N 200005

using namespace std;

int n, m;
int head[N], nex[N << 1], to[N << 1], eid[N << 1], ecnt;
int p[N], s[N];

struct light {
	int pos, state;
}lig[N];

bool cmpLight(const light &lhs, const light &rhs) { return lhs.pos < rhs.pos; }

inline int read() {
	int x = 0; char ch = getchar();
	while(!isdigit(ch)) ch = getchar();
	while(isdigit(ch)) x = x * 10 + ch - ‘0‘, ch = getchar();
	return x;
}
inline void addE(int u, int v, int id) {
	to[++ecnt] = v, eid[ecnt] = id;
	nex[ecnt] = head[u], head[u] = ecnt;
}

int cntOne;
int dif[N], fa[N], fe[N];
bool vis[N];

void dfs(int u) {
	if(s[u]) ++dif[u], ++cntOne;
	for(int i = head[u], v; i; i = nex[i]) {
		v = to[i];
		if(fa[v]) continue;
		fa[v] = u, fe[v] = eid[i], dfs(v);
		dif[u] += dif[v];
	}
}

int main() {
	n = read(), m = read();
	for(int i = 1; i <= n; ++i)
		lig[i].pos = read(), lig[i].state = read();
	
	sort(lig + 1, lig + n + 1, cmpLight);
	for(int i = 1; i <= n; ++i)
		p[i] = lig[i].pos, s[i] = lig[i].state;
	for(int i = n + 1; i >= 1; --i)
		s[i] = s[i] ^ s[i - 1];
		
	for(int i = 1, l, r; i <= m; ++i) {
		l = read(), r = read();
		l = lower_bound(p + 1, p + n + 1, l) - p;
		r = upper_bound(p + 1, p + n + 1, r) - p - 1;
		if(l <= r) {
			addE(l, r + 1, i), addE(r + 1, l, i);
		}
	}
	
	for(int i = 1; i <= n + 1; ++i)
		if(!fa[i]) {
			fa[i] = i;
			dfs(i);
			if(cntOne & 1) {
				puts("-1");
				return 0;
			}
		}
	
	int cnt = 0;
	for(int i = 1; i <= n + 1; ++i)
		if(dif[i] & 1)
			vis[fe[i]] = true, ++cnt;
	
	printf("%d\n", cnt);
	for(int i = 1; i <= m; ++i)
		if(vis[i])
			printf("%d ", i);
	putchar(‘\n‘);
	return 0;
}

题解 [ABC155F] Perils in Parallel

原文:https://www.cnblogs.com/Lskkkno1/p/12568984.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!