蓝书（算法竞赛进阶指南）刷题记录——POJ1733 Parity game（带权并查集）

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了蓝书（算法竞赛进阶指南）刷题记录——POJ1733 Parity game（带权并查集），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1808字，纯文字阅读大概需要3分钟。

内容图文

题目：POJ1733.
题目大意：给定$n$n个区间$[l_i,r_i]$[li?,ri?]和$a_i$ai?，表示$[l_i,r_i]$[li?,ri?]的权值和为奇数或偶数，问到哪一个区间不矛盾，但它的下一个区间矛盾.
$1\leq n\leq 5*10^3$1≤n≤5?103.

容易想到前缀和，那么区间就变成了两个点$l_i-1$li??1和$r_i$ri?上的信息.

考虑用带权并查集维护每个点的前缀和$d[i]$d[i]，一个点$i$i的点权表示$i$i的前缀和异或$i$i的父亲的点权，即区间$[fa[i]+1,i]$[fa[i]+1,i]的奇偶性.

加入一个区间$[l_i,r_i]$[li?,ri?]时若$l_i-1,r_i$li??1,ri?在同一个区间就大力判断它们点权异或是否等于$a[i]$a[i].然后加入这个区间就相当于把$r_i$ri?的祖先设为$l_i-1$li??1，并同时更新点权.

注意这个时候路径压缩时也要更新点权.

时间复杂度$O(n\log n)$O(nlogn).

代码如下：

#include<iostream>
#include<cstdio>
#include<algorithm>
  using namespace std;

#define Abigail inline void
typedef long long LL;

const int N=5000;

int ri(){
  char c=getchar();
  int x=0,y=1;
  for (;c<'0'||c>'9';c=getchar()) if (c=='-') y=-1;
  for (;c<='9'&&c>='0';c=getchar()) x=x*10+c-'0';
  return x*y;
}

int rc(){
  char c=getchar();
  while (c<'a'||c>'z') c=getchar();
  return c=='o'?1:0;
}

int n,ord[N*2+9],x[N+9],y[N+9],a[N+9];
int fa[N*2+9],d[N*2+9],ans;

int lower(int k){
  int l=1,r=n<<1,mid=l+r>>1;
  for (;l<r;mid=l+r>>1)
    k<=ord[mid]?r=mid:l=mid+1;
  return l;
}

int get(int u){
  if (u==fa[u]) return u;
  int rot=get(fa[u]);d[u]^=d[fa[u]];
  return fa[u]=rot;
}

Abigail into(){
  ri();n=ri();
  for (int i=1;i<=n;++i){
  	x[i]=ri()-1;y[i]=ri();a[i]=rc();
  	ord[i*2-1]=x[i];ord[i*2]=y[i];
  }
}

Abigail work(){
  sort(ord+1,ord+1+2*n);
  for (int i=0;i<=n;++i)
    x[i]=lower(x[i]),y[i]=lower(y[i]);
  for (int i=1;i<=n<<1;++i) fa[i]=i;
  int u,v;
  ans=n;
  for (int i=1;i<=n;++i){
  	u=get(x[i]);v=get(y[i]);
  	if (u==v&&d[x[i]]^d[y[i]]^a[i]){ans=i-1;return;}
  	fa[v]=u,d[v]=d[x[i]]^d[y[i]]^a[i];
  }
}

Abigail outo(){
  printf("%d\n",ans);
}

int main(){
  into();
  work();
  outo();
  return 0;
}

内容总结

以上是互联网集市为您收集整理的蓝书（算法竞赛进阶指南）刷题记录——POJ1733 Parity game（带权并查集）全部内容，希望文章能够帮你解决蓝书（算法竞赛进阶指南）刷题记录——POJ1733 Parity game（带权并查集）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---