codeforces 429E

题意：给定n<=100000线段[l,r],然后给这些线段染色（red or blue），求最后平面上任意一个点被蓝色及红色覆盖次数只差的绝对值不大于1

思路：把每条线段拆成2个点[l<<1, r<<1|1]来表示，

那么如果把染red看成1，blue看成-1

那么对于每条线段染色为v（-1 or 1）,等价于l<<1点为v，r<<1|1为-v,

则题目等价于求一种合法的方案使得任意点的abs（前缀和S）<=1

此外，由于任一点取值为 -1 or 1，并且过程中abs(S)<=1，所以任意奇数位置（下标从0开始）的前缀和为0

所以转化为图论模型，就是经典的二分图染色模型：

对于每个线段两端连一条边；

对于排序后相邻的（i<<1, i <<1|1）连一条边，

又由于图的特殊性不会出现奇数环。。

因为对于任意的一个点，只有两条边，并且这两条边类型不同，不妨设为A和B。

那么如果出现了环，那么路径上肯定是ABAB交替出现，并且是偶数。。因为出现奇环必有路径上出现重复的AA或者BB，显然这种情况是不会出现的。。

code：

 /*

  * Author:  Yzcstc

  * Created Time:  2014/10/30 19:12:23

  * File Name: cf429.cpp

  */

 #include<cstdio>

 #include<iostream>

 #include<cstring>

 #include<cstdlib>

 #include<cmath>

 #include<algorithm>

 #include<string>

 #include<map>

 #include<set>

 #include<vector>

 #include<queue>

 #include<stack>

 #include<ctime>

 using namespace std;

 vector<int> e[];

 int col[], n;

 pair<int, int> p[];

 void dfs(int u, int color){

      if (col[u] != -) return;

      col[u] = color;

      for (int i = ; i < (int)e[u].size(); ++i)

           dfs(e[u][i], color^);

 }

 void solve(){

      for (int i = ; i <= n * ; ++i) e[i].clear();

      int l, r;

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

           scanf("%d%d", &l, &r);

           e[i<<].push_back(i<<|), e[i<<|].push_back(i<<);

           p[i<<] = make_pair(l<<,i<<), p[i<<|] = make_pair(r<<|, i<<|);

      }

      sort(p, p + *n);

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

           int x = p[i<<].second, y = p[i<<|].second;

           e[x].push_back(y), e[y].push_back(x);

      }

      memset(col, -, sizeof(col));

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

          if (col[i<<] == -) dfs(i<<, );

          printf("%d ", col[i<<]);

      }

 }

 int main(){

 //    freopen("a.in", "r", stdin);

 //    freopen("a.out", "w", stdout);

     while (scanf("%d", &n) != EOF){

         solve();

     }

     return ;

 }

巴特西

codeforces 429E

最新文章

热门文章