题解 CF875C 【National Property】

发表于 | 阅读次数：

2-SAT好题

题意

题目中给定n个字符串,m个字符，现在将这些字符用数字来表示。

现在可以将这些数字中的任意几个变成大写，（字符变成大写后小于任何小写的字符，但是两个大写字符按数值进行比较）

使得：

在变换后，按顺序给定的n个字符串是按字典序升序排列的。

分析

每个字符只有小写大写两种状态，可以转换成2-SAT问题。
暴力拆点，第i个点表示i取大写，i+n表示i取小写

由于是升序，所以我们只要处理前后两个字符串，对于每一位：

1.如果当前这一位大于前一个串的这位

那么前面串的这位大写，后面的大写小写都可以，如果后面的大写，前面的就必须大写

2.如果当前这一位小于前一个串的这位

那么前面串的这位必须大写，后面串必须小写

还有就是要特判全部一样但前一个串的长度大

连边就和2-SAT没什么区别了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
#include<bits/stdc++.h>
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
using namespace std;

inline void read(int &x)
{
	x=0;
	char ch=getchar();
	int pd=1;
	while(ch<'0'||ch>'9')
	{
		if(ch=='-')
		{
			pd=-pd;
		}
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		x=x*10+ch-'0';
		ch=getchar();
	}
	x*=pd;
}
inline void write(const int &x)
{
	char ggg[10001];
	int s=0;
	int tmp=x;
	if(tmp==0)
	{
		putchar('0');
		return;
	}
	if(tmp<0)
	{
		tmp=-tmp;
		putchar('-');
	}
	while(tmp>0)
	{
		ggg[s++]=tmp%10+'0';
		tmp/=10;
	}
	while(s>0)
	{
		putchar(ggg[--s]);
	}
}
const int N=3e5+7,M=3e6+7;
int t,h[N],dfn[N],low[N],id[N],num,cnt,cc,ans[N],n,m;
bool vis[N];
int a[2][1000001];
struct dd
{
	int end,nt;
}e[M];
inline void add(int begin,int end)
{
	++t;
	e[t].end=end;
	e[t].nt=h[begin];
	h[begin]=t;
}
stack<int >st;
void tarjan(int x)
{
	dfn[x]=low[x]=++num;
	st.push(x);
	for(register int i=h[x];i;i=e[i].nt)
	{
		int u=e[i].end;
		if(!dfn[u])
		{
			tarjan(u);
			low[x]=min(low[x],low[u]);
		}
		else
		{
			if(!id[u])
			{
				low[x]=min(low[x],dfn[u]);
			}
		}
	}
	if(dfn[x]==low[x])
	{
		id[x]=++cnt;
		while(st.top()!=x)
		{
			id[st.top()]=cnt;
			st.pop();
		}
		st.pop();
	}
}

void wrl(const int &x)
{
	write(x);
	puts("");
}
void wrs(const int &x)
{
	write(x);
	putchar(' ');
}
int main()
{
	read(m);
	read(n);
	int lasta;
	for(register int i=1;i<=m;++i)
	{
		int aa;
		read(aa);
		int now=(i&1);
		bool flag=false;
		for(register int j=1;j<=aa;++j)
		{
			read(a[now][j]);
			if(i>1&&!flag)
			{
				if(j>lasta)continue;
				if(a[now][j]<a[now^1][j])
				{
					add(a[now^1][j]+n,a[now^1][j]);
					add(a[now][j],a[now][j]+n);
					flag=1;
				}
				if(a[now][j]>a[now^1][j])
				{
					add(a[now^1][j]+n,a[now][j]+n);
					add(a[now][j],a[now^1][j]);
					flag=1;
				}
				if(j==aa&&lasta>aa&&!flag)
				{
					puts("No");
					return 0;
				}
			}
		}
		lasta=aa;
	}
	for(register int i=1;i<=2*n;++i)
	{
		if(!dfn[i])
		{
			tarjan(i);
		}
	}
	for(register int i=1;i<=n;++i)
	{
		if(id[i]==id[i+n])
		{
			puts("No");
			return 0;
		}

	}
	puts("Yes");
	int cc=0;
	for(register int i=1;i<=n;++i)
	{
		if(id[i]<id[i+n])
		{
			ans[++cc]=i;
		}
	}
	wrl(cc);
	for(register int i=1;i<=cc;++i)
	{
		wrs(ans[i]);
	}
}