CodeForces CF875C题解

题解

非常有意思的\(2-SAT\)的题。

听学长讲完之后感觉确实容易想到\(2-SAT\)，顺理成章。

显然，对于两个串，对咱们来说有意义的显然是两个串中第一个不同的数字。那么，我们假设两个串分别是\(A,B\)，第一个不同的位置是\(pos\)，且\(A_{pos}=x,B_{pos}=y\)，如果\(x>y\)，那么显然我们需要给\(x\)加一个\('\)，且\(y\)一定不能加，要不然没有意义。所以我们把\(x+m\)向\(y\)连边，反之就反着来就好了。

然后就可以跑一遍\(2-SAT\)，就像模板一样，如果\(color_i==color_{i+m}\)，就可以直接输出\(No\)。然后就统计答案即可。

代码

#include<bits/stdc++.h>

using namespace std;

const int N=5e5+5;

int tot,head[N],ver[N<<1],nxt[N<<1],a[N],lst[N];

int n,m,lstlen;

int num,dfn[N],low[N];

int color[N],cnt,st[N],top,ans;

int read()

{

    int x=0,f=1;

    char c=getchar();

    while (c<'0'||c>'9')

    {

        if(c=='-') f=-1;

        c=getchar();

    }

    while (c>='0'&&c<='9')

    {

        x=(x<<1)+(x<<3)+(c^48);

        c=getchar();

    }

    return x*f;

}

void add(int x,int y)

{

    tot++;

    ver[tot]=y;

    nxt[tot]=head[x];

    head[x]=tot;

}

void Tarjan(int x)

{

    low[x]=dfn[x]=++num;

    st[++top]=x;

	for(int i=head[x];i;i=nxt[i])

    {

		int y=ver[i];

		if(!dfn[y]) Tarjan(y),low[x]=min(low[x],low[y]);

		else if(!color[y]) low[x]=min(low[x],dfn[y]);

	}

	if(dfn[x]==low[x])

	{

		int y=-1;

        cnt++;

		while(x!=y)

        {

			y=st[top--];

            color[y]=cnt;//cout<<y<<" "<<cnt<<endl;

		}

	}

}

int main()

{

    n=read(),m=read();

    for(int i=1;i<=n;i++)

    {

        int len=read();

        bool flag=false;

        for(int j=1;j<=len;j++) a[j]=read();

        for(int j=1;j<=min(lstlen,len);j++)

        {

            if(a[j]==lst[j]) continue;

            flag=true;

            if(a[j]>lst[j]) add(a[j]+m,lst[j]+m),add(lst[j],a[j]);

            else add(lst[j],lst[j]+m),add(a[j]+m,a[j]);

            break;

        }

        if(!flag && lstlen>len) puts("No"),exit(0);

        lstlen=len;

        for(int j=1;j<=lstlen;j++) lst[j]=a[j];

    }

    for(int i=1;i<=(m<<1);i++) if(!dfn[i]) Tarjan(i);

    for(int i=1;i<=m;i++) if(color[i]==color[i+m]) puts("No"),exit(0);

    puts("Yes");

    for(int i=1;i<=m;i++) if(color[i+m]<color[i]) ans++;

    cout<<ans<<endl;

    for(int i=1;i<=m;i++) if(color[i+m]<color[i]) cout<<i<<" ";

    return 0;

}

巴特西

CodeForces CF875C题解

题解

代码

最新文章

热门文章