[noi1779]D

先离散，然后将黑的看成1，白的看成-1，对整个序列差分，所有区间建为$(l,r+1)$的无向边，并标上-1和1，每一个点的前缀和即为该点的值

考虑什么情况下能够使得所有点都是0：当且仅当每一个点的度数都为偶数（证明：必要性，由于所有点奇偶性相同，因此比然要有偶数条边；必要性：每一个连通块都存在一个欧拉回路，按照欧拉回路经过方向不同标上-1和1，根据欧拉回路的性质，即所有点都为0）

原题中，允许每一个点为0或$\pm 1$，因此并不保证所有点度数都为偶数，考虑构造：将相邻两个度数为奇数的点连起来，这样构成全都是0，然后删去这些区间，由于这些区间互不相交，所以满足题中要求

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 #define N 200005

 4 struct ji{

 5     int nex,to;

 6 }edge[N<<1];

 7 pair<int,int>a[N];

 8 int E,n,x,y,head[N],vis[N],ans[N];

 9 void add(int x,int y){

10     edge[E].nex=head[x];

11     edge[E].to=y;

12     head[x]=E++;

13     if (E&1)add(y,x);

14 }

15 void dfs(int k){

16     for(int i=head[k];i!=-1;i=edge[i].nex)

17         if (ans[i/2]<0){

18             ans[i/2]=(i&1);

19             dfs(edge[i].to);

20         }

21 }

22 int main(){

23     scanf("%d",&n);

24     memset(head,-1,sizeof(head));

25     memset(ans,-1,sizeof(ans));

26     for(int i=1;i<=n;i++){

27         scanf("%d%d",&x,&y);

28         a[2*i-1]=make_pair(x*2,2*i-1);

29         a[2*i]=make_pair(y*2+1,2*i);

30         add(2*i-1,2*i);

31     }

32     sort(a+1,a+2*n+1);

33     for(int i=1;i<=n;i++)add(a[2*i-1].second,a[2*i].second);

34     for(int i=1;i<=2*n;i++)dfs(i);

35     for(int i=0;i<n;i++)printf("%d ",ans[i]);

36 }

巴特西

[noi1779]D

最新文章

热门文章