博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
[SRM568]DisjointSemicircles
阅读量:7235 次
发布时间:2019-06-29

本文共 2791 字,大约阅读时间需要 9 分钟。

题意:$2n$个位置排成一列,有一些位置已经填了数字($0\cdots n-1$中每个数字出现$0$次或$2$次),问是否存在一种填数方案使得用$n$个不相交的半圆可以把相同的数字连起来

首先把所有已经填了的数字的半圆画出来,如果两个半圆相交那么它们必须在异侧,在相交的半圆之间连边,如果不是二分图那么就无解

我们用$-1$代表未填数的位置,给$-1$的位置分配$1$代表这个位置向上连线,$0$代表这个位置向下连线

朴素的想法是:对于每个半圆$[l,r]$,枚举它在上方还是在下方,如果在上方,那么$[l,r]$中必须有偶数个$1$,如果在下方,那么$[l,r]$中必须有偶数个$0$(用$-1$的个数减去$0$的个数即可得到$1$的个数),并且因为对于每个不是$-1$的位置$i$,因为不能给它分配$1$,所以$[i,i]$中必须有偶数个$0$,最后,显然所有位置上必须有偶数个$1$

现在问题变为:给定一些区间$[l,r]$和对其中$1$的个数的奇偶性要求,问是否能满足,求异或前缀和后就变成对一些变量的异或值限制,直接dfs一遍看是否冲突即可

但是这样会很慢,考虑优化

如果一个半圆$[l,r]$不与其他半圆相交,当区间长度为偶数时,它放在上或下都要求区间中$1$的个数是偶数,当区间长度为奇数时,放在上或下可以使得区间中$1$的个数是奇数或是偶数,又因为它和其他半圆互不影响,所以我们这样处理:如果区间长度为奇数,不管它,如果区间长度为偶数,那么我们不用枚举它放在上还是下,直接令区间中$1$的个数是偶数即可

所以我们只用对二分图中大小$\geq2$的连通块枚举它的两半分别在上还是下,因为最多有$\frac n2$个半圆,所以最多有$\frac n4$个大小$\geq2$的连通块,所以总时间复杂度为$O(n2^{\frac n4})$

#include
#include
#include
#include
#include
using namespace std;struct seg{ int l,r; seg(int a=0,int b=0){l=a;r=b;}}e[30];bool ints(seg a,seg b){ if(a.l>b.l)swap(a,b); return b.l
a.r;}vector
vt[30][2];vector
sg;int cnt;struct graph{ int h[30],nex[610],to[610],M,n; void reset(){ M=0; memset(h,0,sizeof(h)); } void ins(int a,int b){ M++; to[M]=b; nex[M]=h[a]; h[a]=M; } void add(int a,int b){ ins(a,b); ins(b,a); } int c[30]; bool dfs(int x,int f){ if(~c[x])return c[x]==f; vt[cnt][f].push_back(x); c[x]=f; for(int i=h[x];i;i=nex[i]){ if(!dfs(to[i],f^1))return 0; } return 1; } bool gao(int n){ sg.clear(); memset(c,-1,sizeof(c)); cnt=0; for(int i=1;i<=n;i++){ if(c[i]==-1){ if(h[i]){ vt[cnt][0].clear(); vt[cnt][1].clear(); if(!dfs(i,0))return 0; cnt++; }else sg.push_back(i); } } return 1; }}g;struct graph2{ int h[60],nex[210],to[210],v[210],M; void reset(){ M=0; memset(h,0,sizeof(h)); } void ins(int a,int b,int c){ M++; to[M]=b; v[M]=c; nex[M]=h[a]; h[a]=M; } void add(int a,int b,int c){ ins(a,b,c); ins(b,a,c); } int c[60]; bool dfs(int x,int f){ if(~c[x])return c[x]==f; c[x]=f; for(int i=h[x];i;i=nex[i]){ if(!dfs(to[i],f^v[i]))return 0; } return 1; } bool gao(int n){ memset(c,-1,sizeof(c)); for(int i=0;i<=n;i++){ if(c[i]==-1&&!dfs(i,0))return 0; } return 1; }}g2;int a[60],s[60];class DisjointSemicircles{ public: string getPossibility(vector
v){ int n,i,j,M; n=v.size(); M=0; for(i=1;i<=n;i++){ a[i]=v[i-1]; s[i]=s[i-1]+(a[i]==-1); if(~a[i]){ for(j=1;j
>j&1])g2.add(e[x].l-1,e[x].r,0); for(int x:vt[j][~i>>j&1])g2.add(e[x].l-1,e[x].r,(s[e[x].r]-s[e[x].l-1])&1); } for(j=1;j<=n;j++){ if(~a[j])g2.add(j-1,j,0); } g2.add(0,n,0); if(g2.gao(n))return"POSSIBLE"; } return"IMPOSSIBLE"; }};/*int main(){ int x; DisjointSemicircles cl; vector
v; for(scanf("%d",&x);x!=-2;scanf("%d",&x))v.push_back(x); puts(cl.getPossibility(v).c_str());}*/

转载于:https://www.cnblogs.com/jefflyy/p/9758746.html

你可能感兴趣的文章
myISAM索引
查看>>
ovs 实用案例
查看>>
leetcode 104 Maximum Depth of Binary Tree二叉树求深度
查看>>
libevent2笔记(linux、windows、android的编译)
查看>>
如何减少JS的全局变量污染
查看>>
大数据计数原理1+0=1这你都不会算(二)
查看>>
Facebook的Hadoop应用与故障转移方案
查看>>
结合stack数据结构,实现不同进制转换的算法
查看>>
应用、算法、芯片,“三位一体”浅析语音识别
查看>>
14亿用户数据泄露,原因竟是垃圾邮件!
查看>>
规则引擎在数据分析中的作用
查看>>
学习ASP.NET Core, 怎能不了解请求处理管道[4]: 应用的入口——Startup
查看>>
两年之后,再思考Docker的价值
查看>>
Kubernetes性能测试和发展计划
查看>>
无服务器计算对云计算运营团队的影响
查看>>
[译] React 16 带来了什么以及对 Fiber 的解释
查看>>
重构,不要积压!
查看>>
FreeBSD恢复root密码
查看>>
大型分布式网站术语分析
查看>>
ceph在扩展mon节点时,要注意的问题
查看>>