深圳市罗湖建设局网站,自己用dw做网站能加声音吗,包头微网站开发,营销型网站建设制作多少钱CF429E Points and Segments
给定n 条线段[li,ri][l_i,r_i][li,ri] ,然后给这些线段红蓝染色#xff0c;求最后直线上上任意一个点被蓝色及红色线段覆盖次数之差的绝对值不大于1
首先见到绝对值不大于1我们就容易想到欧拉回路#xff0c;因为欧拉回路可以用来构造恰好相…CF429E Points and Segments
给定n 条线段[li,ri][l_i,r_i][li,ri] ,然后给这些线段红蓝染色求最后直线上上任意一个点被蓝色及红色线段覆盖次数之差的绝对值不大于1
首先见到绝对值不大于1我们就容易想到欧拉回路因为欧拉回路可以用来构造恰好相等然后通过一些另加的边或者已经有的其他限制就可以构造出绝对值小于等于1然后考虑先将n条线段离散化将其转化为左闭右开的形式然后排序去重这样每个节点就对应了一种线段覆盖状态总的点数是O(n)O(n)O(n)级别的然后将对应左右端点连边如果能够欧拉回路那么就相当于是构造图的一个环划分那么将向右视作红色向左视作蓝色那么所有点红蓝被覆盖次数的差应该是0。
但是需要考虑图上有奇度数点的情况可以发现这样的点的个数一定是偶数所以我们从左到右x1−x2,x3−x4...x_1-x_2,x_3-x_4...x1−x2,x3−x4...这样连边可以让所有点的度数变为偶数这样求解欧拉回路之后去掉这些边每个个点最多被删去一种颜色一次所以绝对值一定小于等于1.
#includebits/stdc.h
#define LL long long
#define V inline void
#define I inline int
#define FOR(i,a,b) for(register int ia,end##ib;iend##i;i)
#define REP(i,a,b) for(register int ia,end##ib;iend##i;--i)
#define go(i,x) for(int ihed[x];i;ie[i].pre)
using namespace std;
inline int read()
{char x\0;int fh1,sum0;for(xgetchar();x0||x9;xgetchar())if(x-)fh-1;for(;x0x9;xgetchar())sumsum*10x-0;return fh*sum;
}
const int N2e59;
const int M5e59;
int n,l[N],r[N],b[N],bcnt;
int nd[N],ncnt;
struct lian{int to,pre,id;bool flag;
}e[M1];
int hed[N],lcnt1;
V jlian(int x,int y,int id)
{e[lcnt]{y,hed[x],id};hed[x]lcnt;
}
int du[N],es[N],et[N];
bool vis[N];
V dfs(int x)
{vis[x]true;for(int ihed[x];i;ie[i].pre){int toe[i].to;if(e[i].flag)continue;e[i].flage[i^1].flagtrue;es[e[i].id]x,et[e[i].id]to;dfs(to);}
}
int main()
{nread();FOR(i,1,n){l[i]read(),r[i]read()1;b[bcnt]l[i],b[bcnt]r[i];}sort(b1,bbcnt1);bcntunique(b1,bbcnt1)-b-1;FOR(i,1,n){l[i]lower_bound(b1,bbcnt1,l[i])-b;r[i]lower_bound(b1,bbcnt1,r[i])-b;jlian(l[i],r[i],i),jlian(r[i],l[i],i);du[l[i]],du[r[i]];}FOR(i,1,bcnt)if(du[i]1)nd[ncnt]i;for(int i1;incnt;i2){jlian(nd[i],nd[i1],n1);jlian(nd[i1],nd[i],n1);}FOR(i,1,bcnt)if(!vis[i])dfs(i);FOR(i,1,n){if(es[i]et[i])printf(1%c,(in)?\n: );else printf(0%c,(in)?\n: );}return 0;
}
