P3876题解

operator_ · 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 种了！不多不少！

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

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

• l_i\le4

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

写成函数更方便。

• l_i>4

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

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

最后 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;
}