http://www.elijahqi.win/archives/3932
大家都知道,熊爱鱼。但是迈克是一只奇怪的熊,他讨厌鱼!更奇怪的是,他有无数的蓝色和红色的鱼。 他在平面上标出了
n
n
个不同的点。第 个是点
(xi,yi)
(
x
i
,
y
i
)
。他想在每一点都放一条鱼,使得每一条水平线或垂直线上的红鱼和蓝鱼的数量相差最多1。 他不能找到一种方式来执行,所以请你帮助他。 输入的第一行包含整数
n(1≤n≤2×105)
n
(
1
≤
n
≤
2
×
10
5
)
。 接下来的
n
n
行包含的每个点的信息,第 行包含两个整数
xi
x
i
和
yi
y
i
,(
1≤xi,yi≤2×105
1
≤
x
i
,
y
i
≤
2
×
10
5
),表示第
i
i
个点的坐标。 保证至少有一个符合题意的答案。 将答案输出为n个字符r
(红色)或b
(蓝色)的序列,其中第 个字符表示
i
i
<script type="math/tex" id="MathJax-Element-36">i</script> 点中的“鱼”的颜色。
我们考虑把每一排每一列分别看成一个点 然后我们每个点就是勾连起这样两个点的一个桥梁
要求给这些点染色 使得一行一列内不同颜色的差的绝对值小于等于1
把不同颜色看成针对这个点不同的出边或者入边
那么欧拉图的性质就是入度和出度是相等的 但是有可能出现度数是奇数的情况 不妨我们两两给他们配对起来这样跑一遍欧拉图 最后把那些多余的边删除即可 强行钦定 边的方向为什么颜色即可
这题如果不加“类似当前弧优化” 是tle的
#include<bits/stdc++.h>
using namespace std;
inline char gc(){
static char now[1<<16],*S,*T;
if (T==S) {T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;}
return *S++;
}
inline int read(){
int x=0,f=1;char ch=gc();
while(!isdigit(ch)) {if(ch=='-') f=-1;ch=gc();}
while(isdigit(ch)) x=x*10+ch-'0',ch=gc();
return x*f;
}
const int N=8e5+10;
struct node{
int y,next,x;
}data[N<<2];
int q1[N],q2[N],n1,n2,num=1,in[N],x[N],y[N],n,h[N];
bool visit[N],vis[N];int q[N<<1],top;char s[N];
inline void insert1(int x,int y){
data[++num].y=y;data[num].next=h[x];h[x]=num;data[num].x=x;
}
inline void dfs(int x){
vis[x]=1;
for (int &i=h[x];i;i=data[i].next){
int id=i;
int y=data[i].y;if (visit[i]||visit[i^1]) continue;
visit[i]=visit[i^1]=1;dfs(y);q[++top]=id;
}
}
int main(){
freopen("cf.in","r",stdin);
double t1=clock();
n=read();
for (int i=1;i<=n;++i) x[i]=read(),y[i]=read(),q1[++n1]=x[i],q2[++n2]=y[i];
sort(q1+1,q1+n1+1);sort(q2+1,q2+n2+1);
n1=unique(q1+1,q1+n1+1)-q1-1;n2=unique(q2+1,q2+n2+1)-q2-1;
for (int i=1;i<=n;++i) x[i]=lower_bound(q1+1,q1+n1+1,x[i])-q1,
y[i]=lower_bound(q2+1,q2+n2+1,y[i])-q2,y[i]+=n1;
for (int i=1;i<=n;++i) insert1(x[i],y[i]),insert1(y[i],x[i]),++in[x[i]],++in[y[i]];
int nm=num,last=-1;
//for (int i=2;i<=nm;++i) printf("%d %dn",data[i].x,data[i].y);
for (int i=1;i<=n1+n2;++i){
if (in[i]&1){
if (last==-1){
last=i;continue;
}
insert1(last,i);insert1(i,last);last=-1;
}
}
double t2=clock();if((t2-t1)/CLOCKS_PER_SEC>1) printf("%fn",(t2-t1)/CLOCKS_PER_SEC);
for (int i=1;i<=n1+n2;++i) if (!vis[i]) dfs(i);
for (int i=1;i<=top;++i){
if (q[i]>nm) continue;
int id=q[i];(id&1)?s[id>>1]='b':s[id>>1]='r';
}printf("%s",s+1);
return 0;
}
最后
以上就是优雅鸭子最近收集整理的关于codeforces 547DMike and Fish的全部内容,更多相关codeforces内容请搜索靠谱客的其他文章。
发表评论 取消回复