SSF信息社团4月训练题目整理

选一些写。

Hint：可以点击右下角的目录符号快速跳转到指定位置

上接：SSF信息社团3月训练题目整理

4.6

875C

Link

2-SAT，点 \(c\) 表示这个字符不变，点 \(c+m\) 表示变为大写。考虑这样两个串：

若 \(c_4<c_5\)，则 \(c_5\) 如果变，\(c_4\) 必须变；\(c_4\) 如果不变，\(c_5\) 必须不变。连 \(c_5+m\to c_4+m,\;c_4\to c_5\)。若 \(c_4>c_5\)，则 \(c_4\) 必须变，\(c_5\) 必须不变，连 \(c_4\to c_4+m,\;c_5+m\to c_5\)。跑一遍 SCC 缩点，选 SCC 编号较小的作为方案。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
const int N=2e5+10,M=N<<1;
int head[N],ver[M],nxt[M],tot=0;
void add(int x,int y)
{
	ver[++tot]=y;
	nxt[tot]=head[x];
	head[x]=tot;
}
int low[N],dfn[N],cnt=0,num=0,col[N],st[N],top=0;
bool vis[N];
void tarjan(int x)
{
	dfn[x]=low[x]=++num;
	st[++top]=x;vis[x]=1;
	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(vis[y]) low[x]=min(low[x],dfn[y]);
	}
	if(dfn[x]==low[x])
	{
		cnt++;int y=0;
		do{
			y=st[top--];
			col[y]=cnt;
			vis[y]=0;
		}while(x!=y);
	}
}
vector<int> v[N];
bool check(vector<int> a,vector<int> b)
{
	int n=min(a.size(),b.size());
	for(int i=0;i<n;i++)if(a[i]!=b[i])return false;
	return true;
}
int main()
{
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		int k;scanf("%d",&k);
		for(int j=1;j<=k;j++)
		{
			int x;scanf("%d",&x);
			v[i].push_back(x);
		}
	}
	for(int i=1;i<n;i++)
	{
		if(check(v[i],v[i+1]))
		{
			if(v[i].size()<=v[i+1].size())continue;
			else return puts("No"),0;
		}
		int c=min(v[i].size(),v[i+1].size());
		for(int j=0;j<c;j++)
		{
			if(v[i][j]==v[i+1][j])continue;
			if(v[i][j]<v[i+1][j])
			{
				add(v[i][j],v[i+1][j]);
				add(v[i+1][j]+m,v[i][j]+m);
			}
			else
			{
				add(v[i][j],v[i][j]+m);
				add(v[i+1][j]+m,v[i+1][j]);
			}
			break;
		}
	}
	for(int i=1;i<=m*2;i++)if(!dfn[i])tarjan(i);
	for(int i=1;i<=m;i++)if(col[i]==col[i+m])return puts("No"),0;
	puts("Yes");int ans=0;
	for(int i=1;i<=m;i++)ans+=(col[i+m]<col[i]);printf("%d\n",ans);
	for(int i=1;i<=m;i++)if(col[i+m]<col[i])printf("%d ",i);
	return 0;
}

SSF信息社团4月训练题目整理

原文：https://www.cnblogs.com/juruo-zzt/p/14623989.html