自动搬运

查看原文

来自洛谷，原作者为

	operator_ I I I

搬运于2025-08-24 21:53:39，当前版本为作者最后更新于2023-09-15 13:16:06，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P3876 [TJOI2010] 数字序列

题目传送门

题解

前置知识：2-sat。

如果你不会 2-sat，建议先去做P4171。

第一眼你会以为这是一道 $dp$，但只要略微想想就知道不太可能，因为第 $2$ 个条件的限制并不是区间，不太好实现。

仔细想想，其实第 $1$ 个条件已经排除了很多情况，我们把相邻 $2$ 个数的可能排列情况都列出来：$\{'01','03','12','14','21','30'\}$。

事实上，这些情况可以简写为：

• 相邻两数之和为奇数

• $2,3$ 不能相邻

换句话说，如果不考虑 $2,3$，我们完全可以分开考虑奇数位和偶数位。

显然奇数位和偶数位是对称的，不妨假定奇数位放奇数，偶数位放偶数，那么我们发现，每个位置的取值居然只有 $2$ 种了！不多不少！

于是就是一个 2-sat 板子了，考虑对于奇数位，点 $2i-1$ 代表 $1$，点 $2i$ 代表 $3$，对于偶数位，点 $2i-1$ 代表 $0$，点 $2i$ 代表 $2$。

接下来考虑 $m$ 条限制，需要简单分讨一下：

• $l_i\le4$

考虑两两枚举，记为 $a,b$，如果奇偶性不同就直接跳过不看，否则可以建出 $4$ 条边，分别是：

$(2a-1\rightarrow2b)$

$(2a\rightarrow2b-1)$

$(2b-1\rightarrow2a)$

$(2b\rightarrow2a-1)$

写成函数更方便。

• $l_i>4$

有鸽巢原理，此时一定是无解的，不过千万注意，一定要等输入完再判断！这就是血的教训。

现在我们只剩下 $2,3$ 要考虑了，我相信所有人都会：

$(2i\rightarrow2i+1)$

$(2i+2\rightarrow2i-1)$

$i\in[1,n-1)$

最后 tarjan 找强连通分量判断即可。

时间复杂度 $O(Tn)$，能过。

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read() {
	int s=0,m=0;char ch=getchar();
	while(!isdigit(ch)) {if(ch=='-')m=1;ch=getchar();}
	while( isdigit(ch)) s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
	return m?-s:s;
}
int T,n,m;
int l,p[105];
int h[200005],cnt;//奇：2i-1:1，2i:3 偶：2i-1:0，2i:2
struct QWQ{int v,nxt;} e[200005*2];
void add(int u,int v) {e[++cnt]={v,h[u]},h[u]=cnt;}
stack<int> st;
int f[200005],dfn[200005],low[200005],c,k,scc[200005],flag;
void tarjan(int u,int fa) {//板子 
	st.push(u);
	f[u]=1,dfn[u]=low[u]=++c;
	for(int i=h[u];i;i=e[i].nxt) {
		int v=e[i].v;
		if(!dfn[v])
			tarjan(v,u),low[u]=min(low[u],low[v]);
		else if(f[v])
			low[u]=min(low[u],dfn[v]);
	}
	if(dfn[u]==low[u]) {
		k++;
		while(1) {
			int top=st.top();st.pop();
			scc[top]=k,f[top]=0;
			if(top==u) break;
		}
	}
} 
void added(int x,int y) {//加边的函数 
	if(x%2==y%2) 
		add(x*2-1,y*2),add(x*2,y*2-1),add(y*2-1,x*2),add(y*2,x*2-1);
}
signed main() {
	cin>>T;
	while(T--) {
		cnt=k=c=flag=0;
		memset(h,0,sizeof(h));
		memset(f,0,sizeof(f));
		memset(dfn,0,sizeof(dfn));
		memset(low,0,sizeof(low));
		int fl=0;
		cin>>n>>m;
		for(int i=1;i<=m;i++) {
			l=read();
			for(int j=1;j<=l;j++)
				p[j]=read();
			if(l>4) {fl=1;continue;}
			for(int x=1;x<=l;x++)
				for(int y=x+1;y<=l;y++)
					added(p[x],p[y]);
		}
		if(fl) {cout<<"No\n";continue;}
		for(int i=1;i<n;i++)
			add(2*i,2*i+1),add(2*i+2,2*i-1);
		for(int i=1;i<=n*2;i++)
			if(!dfn[i])
				tarjan(i,i);
		for(int i=1;i<=2*n;i+=2)
			if(scc[i]==scc[i+1]) {
				cout<<"No\n";
				fl=1;break;
			}
		if(!fl)
			cout<<"Yes\n";
	}
	return 0;
}