题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1728
最开始以为是2-sat
后来发现必须是连续一段
那这样就直接二分+染色就好了
如果两头牛同一侧的脑袋互相讨厌那就一定要翻转其中一个，所以就连一条1的边，否则连一条0的边
然后锁定左端点，二分右端点
dfs时，col[to]=col[now]^边权
当我们碰到一个访问过的但是颜色却和之前的不一样时，就代表不满足条件
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 |
#include<bits/stdc++.h> #define MAXN 25050 using namespace std; inline int rd(){ int x=0,y=1;char c=getchar(); while(!isdigit(c)){if(c=='-')y=-y;c=getchar();} while(isdigit(c))x=x*10+c-'0',c=getchar(); return x*y; } struct node{ int to; bool val; node(int a,bool b){to=a,val=b;} node(){} }; int n,m,ans; vector<node>v[MAXN]; bool col[MAXN],vis[MAXN]; inline void link(int x,int y,bool z){ v[x].push_back(node(y,z)); v[y].push_back(node(x,z)); } bool dfs(int x,int l,int r){ vis[x]=true; bool ret=true; for(int i=0; i<v[x].size(); i++){ int to=v[x][i].to; bool val=v[x][i].val; if(to<l || to>r)continue; if(vis[to]){ if((col[x]^val)!=col[to])ret=0; continue; } col[to]=col[x]^val; ret=ret&&dfs(to,l,r); } return ret; } inline bool check(int l,int r){ bool ret=true; memset(col,0,sizeof(col)); memset(vis,0,sizeof(vis)); for(int i=l; i<=r; i++)if(!vis[i])ret=ret&&dfs(i,l,r); return ret; } int main(){ n=rd(),m=rd(); while(m--){ int x,y; char op1[2],op2[2]; x=rd(); scanf("%s",op1); y=rd(); scanf("%s",op2); if(op1[0]==op2[0])link(x,y,1); else link(x,y,0); } for(int i=1; i<=n; i++){ int l=i,r=n,num=i; while(l<=r){ int mid=(l+r)/2; if(check(i,mid))l=mid+1,num=mid; else r=mid-1; } i=num; ans++; } printf("%d\n",ans); return 0; } |
