首页 > 代码库 > BZOJ2255 : [Swerc2010]Palindromic DNA
BZOJ2255 : [Swerc2010]Palindromic DNA
考虑2-SAT建图，设$a[i][0..1]$表示$i$变不变，$b[i][0..1]$表示$i$是下降还是上升。
首先相邻的不能同时动，说明$a[i]$和$a[i+1]$里最多选一个。
对于$x$和$y$要相等，假设$s[x]\geq s[y]$。
$1.$若$s[x]-s[y]=3$，则视为$1$，并交换$x,y$。
$2.$若$s[x]=s[y]$，那么它们的任何行动都是相等的：
$a[x][0]\leftrightarrow a[y][0]$
$a[x][1]\leftrightarrow a[y][1]$
$b[x][0]\leftrightarrow b[y][0]$
$b[x][1]\leftrightarrow b[y][1]$
$3.$若$s[x]-s[y]=1$，那么它们有且仅能动一个，方向也是定的：
$a[x][0]\leftrightarrow a[y][1]$
$a[x][1]\leftrightarrow a[y][0]$
$a[x][1]$和$b[x][0]$最多只能选一个
$a[y][1]$和$b[y][1]$最多只能选一个
$4.$若$s[x]-s[y]=2$，那么它们都要动，而且方向相反：
$a[x][0]\rightarrow a[x][1]$
$a[y][0]\rightarrow a[y][1]$
$b[x][0]\leftrightarrow b[y][1]$
$b[x][1]\leftrightarrow b[x][0]$
求出SCC，若某个$a[i][0]$和$a[i][1]$在同一个SCC则无解，不需要考虑$b$，因为可以既不上升也不下降。
时间复杂度$O(n+m)$。
#include<cstdio>#include<algorithm>using namespace std;const int N=100010,M=N*4,E=2000000;int n,m,i,j,k,cnt,a[N][2],b[N][2],p[N],g[2][M],v[2][E],nxt[2][E],ed,q[M],t,f[M];bool vis[M];char s[N];inline void read(int&a){char c;while(!(((c=getchar())>=‘0‘)&&(c<=‘9‘)));a=c-‘0‘;while(((c=getchar())>=‘0‘)&&(c<=‘9‘))(a*=10)+=c-‘0‘;}inline int getid(char x){ if(x==‘A‘)return 0; if(x==‘G‘)return 1; if(x==‘T‘)return 2; return 3;}inline void add(int x,int y){ v[0][++ed]=y;nxt[0][ed]=g[0][x];g[0][x]=ed; v[1][ed]=x;nxt[1][ed]=g[1][y];g[1][y]=ed;}inline void add2(int x,int y){add(x,y),add(y,x);}inline void check(int x,int y){ if(s[x]<s[y])swap(x,y); int w=s[x]-s[y]; if(w==3)w=1,swap(x,y); if(!w){ add2(a[x][0],a[y][0]); add2(a[x][1],a[y][1]); add2(b[x][0],b[y][0]); add2(b[x][1],b[y][1]); return; } if(w==1){ add2(a[x][0],a[y][1]); add2(a[x][1],a[y][0]); add(a[x][1],b[x][0]); add(b[x][1],a[x][0]); add(a[y][1],b[y][1]); add(b[y][0],a[x][0]); return; } add(a[x][0],a[x][1]); add(a[y][0],a[y][1]); add2(b[x][0],b[y][1]); add2(b[x][1],b[y][0]);}void dfs1(int x){ vis[x]=1; for(int i=g[0][x];i;i=nxt[0][i])if(!vis[v[0][i]])dfs1(v[0][i]); q[++t]=x;}void dfs2(int x,int y){ vis[x]=0;f[x]=y; for(int i=g[1][x];i;i=nxt[1][i])if(vis[v[1][i]])dfs2(v[1][i],y);}int main(){ while(~scanf("%d%d",&n,&m)){ if(!n)return 0; scanf("%s",s); for(i=0;i<n;i++)s[i]=getid(s[i]); for(cnt=i=0;i<n;i++)for(j=0;j<2;j++)a[i][j]=++cnt,b[i][j]=++cnt; for(ed=0,i=1;i<=cnt;i++)g[0][i]=g[1][i]=0; for(i=0;i<n;i++){ if(i)add(a[i][1],a[i-1][0]); if(i+1<n)add(a[i][1],a[i+1][0]); } while(m--){ read(k); for(i=0;i<k;i++)read(p[i]); for(i=0,j=k-1;i<j;i++,j--)check(p[i],p[j]); } for(t=0,i=1;i<=cnt;i++)if(!vis[i])dfs1(i); for(i=cnt;i;i--)if(vis[q[i]])dfs2(q[i],q[i]); for(i=0;i<n;i++)if(f[a[i][0]]==f[a[i][1]])break; puts(i<n?"NO":"YES"); }}
BZOJ2255 : [Swerc2010]Palindromic DNA
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。