2-SAT 习题
1. Codeforces - 468B Two Sets
1.1 题意
给定
n
(
1
≤
n
≤
1
0
5
)
n(1 \le n \le 10^5)
n(1≤n≤105) 个互不相同的数
p
i
(
1
≤
p
i
≤
1
0
9
)
p_i(1 \le p_i \le 10^9)
pi(1≤pi≤109)，现在要将它们分成两个集合
A
A
A 和
B
B
B，并满足以下两个条件：
如果
x
∈
A
x \in A
x∈A，则
a
−
x
∈
A
a-x \in A
a−x∈A；
如果
x
∈
B
x \in B
x∈B，则
b
−
x
∈
B
b-x \in B
b−x∈B。
给定
a
,
b
(
1
≤
a
,
b
≤
1
0
9
)
a,b(1 \le a,b \le 10^9)
a,b(1≤a,b≤109)，将序列
p
p
p 进行划分，或者输出无解。
1.2 解题过程
设
x
0
x_0
x0 表示
x
∈
A
x \in A
x∈A，
x
1
x_1
x1 表示
x
∈
B
x \in B
x∈B。
则根据题意，我们进行如下建边：
<
x
0
,
(
a
−
x
)
0
>
<x_0, (a-x)_0>
<x0,(a−x)0> （条件 1）
<
(
a
−
x
)
1
,
x
1
>
<(a-x)_1, x_1>
<(a−x)1,x1>（条件 1 的逆否命题）这条很不显然，但可以这么想：如果
a
−
x
∈
B
a-x \in B
a−x∈B，那么
x
x
x 必然不可能属于
A
A
A，否则就与题意矛盾了。
<
x
1
,
(
b
−
x
)
1
>
<x_1,(b-x)_1>
<x1,(b−x)1> （条件 2）
<
(
b
−
x
)
0
,
x
0
>
<(b-x)_0,x_0>
<(b−x)0,x0> （条件 2 的逆否命题）
需要注意的是，进行上述建边的条件是
x
x
x 和
a
−
x
a-x
a−x 或者
x
x
x 和
b
−
x
b-x
b−x 同时在集合
p
p
p 中。
特别地，若对于
x
∈
p
x \in p
x∈p，在
p
p
p 中不存在
a
−
x
a-x
a−x，则建边
<
x
0
,
x
1
>
<x_0,x_1>
<x0,x1>，表示
x
x
x 必然不可能属于
A
A
A，根据必须分割的原则，
x
x
x 必须属于
B
B
B。
x
x
x 和
b
−
x
b-x
b−x 同理。
之后跑一遍 2-SAT 即可。
时间复杂度：
O
(
2
n
)
O(2n)
O(2n)。
1.3 错误点
逆否命题在大部分情况下都需要考虑，不要根据自己不深刻的理解断言不需要/不可以建立逆否命题。
1.4 代码
int head
[maxn
], n
, m
, cnt
, tot
, top
, num
;
int dfn
[maxn
], low
[maxn
], st
[maxn
], col
[maxn
];
bool instack
[maxn
];
struct edge
{
int v
, nxt
;
} Edge
[8 * maxn
];
void init()
{
for(int i
= 0; i
<= 2 * n
; i
++) head
[i
] = -1;
cnt
= tot
= top
= num
= 0;
}
void addedge(int u
, int v
)
{
Edge
[cnt
].v
= v
;
Edge
[cnt
].nxt
= head
[u
];
head
[u
] = cnt
++;
}
void tarjan(int id
)
{
dfn
[id
] = low
[id
] = ++tot
;
st
[++top
] = id
;
instack
[id
] = true;
for(int i
= head
[id
]; i
!= -1; i
= Edge
[i
].nxt
)
{
int v
= Edge
[i
].v
;
if(!dfn
[v
])
{
tarjan(v
);
low
[id
] = min(low
[id
], low
[v
]);
}
else if(instack
[v
])
low
[id
] = min(low
[id
], dfn
[v
]);
}
if(dfn
[id
] == low
[id
])
{
int v
;
num
++;
do
{
v
= st
[top
--];
instack
[v
] = false;
col
[v
] = num
;
} while(v
!= id
);
}
}
int p
[maxn
], ans
[maxn
], opp
[maxn
];
unordered_map
<int, int> mp
;
int main()
{
int a
, b
;
scanf("%d%d%d", &n
, &a
, &b
);
init();
for (int i
= 1; i
<= n
; i
++) {
scanf("%d", &p
[i
]);
mp
[p
[i
]] = i
;
}
for (int u
= 1; u
<= n
; u
++) {
int x
= p
[u
];
int y
= a
- x
;
int mark
= 0;
if (mp
.count(y
)) {
int v
= mp
[y
];
addedge(u
, v
);
addedge(v
+ n
, u
+ n
);
} else {
addedge(u
, u
+ n
);
}
y
= b
- x
;
if (mp
.count(y
)) {
int v
= mp
[y
];
addedge(u
+ n
, v
+ n
);
addedge(v
, u
);
} else {
addedge(u
+ n
, u
);
}
}
for (int i
= 1; i
<= 2 * n
; i
++) {
if (!dfn
[i
]) tarjan(i
);
}
for (int i
= 1; i
<= n
; i
++) {
if (col
[i
] == col
[i
+ n
]) return 0 * puts("NO");
opp
[i
] = i
+ n
;
opp
[i
+ n
] = i
;
}
puts("YES");
for (int i
= 1; i
<= 2 * n
; i
++) {
ans
[i
] = (col
[i
] > col
[opp
[i
]]);
}
for (int i
= 1; i
<= n
; i
++) {
if (ans
[i
] == 1 || ans
[opp
[i
]] == 0) printf("1 ");
else printf("0 ");
}
return 0;
}
2. Codeforces - 776D - The Door Problem
2.1 题意
给你
n
(
2
≤
n
≤
1
0
5
)
n(2 \le n \le 10^5)
n(2≤n≤105) 扇门和
m
(
2
≤
m
≤
1
0
5
)
m(2 \le m \le 10^5)
m(2≤m≤105) 个开关，每扇门恰好由两个开关控制，每个开关控制着若干个门。
对于门
i
i
i，若
r
i
=
0
r_i=0
ri=0 表明初始状态下门是锁着的，若
r
i
=
1
r_i=1
ri=1 表明初始状态下门是打开的。
触动开关会使其控制的每一扇门的状态取反。
问是否可以通过某种策略（即选择某些开关将其打开），使得所有的门都是打开的。
2.2 解题过程
本题为
2-SAT
\text{2-SAT}
2-SAT 问题。
设点
j
(
1
≤
j
≤
m
)
j(1 \le j \le m)
j(1≤j≤m) 表示开关
j
j
j 处于关闭（初始）状态，设点
j
+
m
j+m
j+m 表示开关
j
j
j 处于开启状态。
考虑每扇门
i
i
i，有以下两种情况：
(
1
)
(1)
(1) 若
r
i
=
0
r_i=0
ri=0，则控制这扇门的两个开关必须且只能开启其中一个。
因此建立有向边
<
i
+
m
,
j
>
<i+m, j>
<i+m,j> 和
<
j
,
i
+
m
>
<j, i+m>
<j,i+m> 以及它们的逆否命题
<
j
+
m
,
i
>
<j+m, i>
<j+m,i> 和
<
i
,
j
+
m
>
<i, j + m>
<i,j+m>。
(
2
)
(2)
(2) 若
r
i
=
1
r_i=1
ri=1，则控制这扇门的两个开关要么全部打开，要么全部关闭。
因此建立有向边
<
i
+
m
,
j
+
m
>
<i+m, j+m>
<i+m,j+m> 和
<
i
,
j
>
<i, j>
<i,j> 以及它们的逆否命题
<
j
,
i
>
<j, i>
<j,i> 和
<
j
+
m
,
i
+
m
>
<j+m, i+m>
<j+m,i+m>。
图建完之后，跑一遍
2-SAT
\text{2-SAT}
2-SAT 即可。
时间复杂度：
O
(
2
m
)
O(2m)
O(2m)。
2.3 代码
int head
[maxn
], n
, m
, cnt
, tot
, top
, num
;
int dfn
[maxn
], low
[maxn
], st
[maxn
], col
[maxn
];
bool instack
[maxn
];
int r
[maxn
];
struct edge
{
int v
, nxt
;
} Edge
[8 * maxn
];
void init()
{
for(int i
= 0; i
<= 2 * m
; i
++) head
[i
] = -1;
cnt
= tot
= top
= num
= 0;
}
void addedge(int u
, int v
)
{
Edge
[cnt
].v
= v
;
Edge
[cnt
].nxt
= head
[u
];
head
[u
] = cnt
++;
}
void tarjan(int id
)
{
dfn
[id
] = low
[id
] = ++tot
;
st
[++top
] = id
;
instack
[id
] = true;
for(int i
= head
[id
]; i
!= -1; i
= Edge
[i
].nxt
)
{
int v
= Edge
[i
].v
;
if(!dfn
[v
])
{
tarjan(v
);
low
[id
] = min(low
[id
], low
[v
]);
}
else if(instack
[v
])
low
[id
] = min(low
[id
], dfn
[v
]);
}
if(dfn
[id
] == low
[id
])
{
int v
;
num
++;
do
{
v
= st
[top
--];
instack
[v
] = false;
col
[v
] = num
;
} while(v
!= id
);
}
}
vector
<int> ve
[maxn
];
int main()
{
int num
, v
;
scanf("%d%d", &n
, &m
);
init();
for(int i
= 1; i
<= n
; i
++) scanf("%d", &r
[i
]);
for(int i
= 1; i
<= m
; i
++)
{
scanf("%d", &num
);
for(int j
= 1; j
<= num
; j
++)
{
scanf("%d", &v
);
ve
[v
].pb(i
);
}
}
for(int i
= 1; i
<= n
; i
++)
{
int a
= ve
[i
][0], b
= ve
[i
][1];
if(r
[i
])
{
addedge(a
+ m
, b
+ m
);
addedge(a
, b
);
addedge(b
+ m
, a
+ m
);
addedge(b
, a
);
}
else
{
addedge(a
+ m
, b
);
addedge(a
, b
+ m
);
addedge(b
, a
+ m
);
addedge(b
+ m
, a
);
}
}
for(int i
= 1; i
<= 2 * m
; i
++)
{
if(!dfn
[i
]) tarjan(i
);
}
bool isok
= true;
for(int i
= 1; i
<= m
; i
++)
{
if(col
[i
] == col
[i
+ m
])
{
isok
= false;
break;
}
}
if(isok
) printf("YES\n");
else printf("NO\n");
return 0;
}
3. Codeforces - 228E - The Road to Berland is Paved With Good Intentions
3.1 题意
现在有一个有
n
(
1
≤
n
≤
100
)
n(1 \le n \le 100)
n(1≤n≤100) 个节点，
m
(
1
≤
m
≤
n
(
n
−
1
)
2
)
m(1 \le m \le \frac{n(n-1)}{2})
m(1≤m≤2n(n−1)) 条边的无向图。
每条边都有边权
c
i
(
c
i
∈
{
0
,
1
}
)
c_i(c_i \in \left\{0,1 \right\})
ci(ci∈{0,1})。
现在可以进行若干次（可以为零）如下操作：选择一个点，将其所有出边的权值全部取反。
问是否可以通过若干次操作，使得所有边的权值为
1
1
1。
若可以，输出所要操作的节点编号。
题目保证两点之间最多有一条路径。
3.2 解题思路
本题为
2-SAT
\text{2-SAT}
2-SAT 问题。
对于每一条边
e
d
g
e
i
edge_i
edgei，若其权值为
1
1
1，则连接它的两点要么全部操作，要么全部不操作；
若其权值为
0
0
0，则连接它的两点需要且只能操作其中一个。
求解思路与
776D
\text{776D}
776D 相同，这里不再赘述。
3.3 代码
int head
[maxn
], n
, m
, cnt
, tot
, top
, num
;
int dfn
[maxn
], low
[maxn
], st
[maxn
], col
[maxn
], var
[maxn
];
bool instack
[maxn
];
struct edge
{
int v
, nxt
;
} Edge
[8 * maxn
* maxn
];
void init()
{
for(int i
= 0; i
<= 2 * n
; i
++) head
[i
] = -1;
cnt
= tot
= top
= num
= 0;
}
void addedge(int u
, int v
)
{
Edge
[cnt
].v
= v
;
Edge
[cnt
].nxt
= head
[u
];
head
[u
] = cnt
++;
}
void tarjan(int id
)
{
dfn
[id
] = low
[id
] = ++tot
;
st
[++top
] = id
;
instack
[id
] = true;
for(int i
= head
[id
]; i
!= -1; i
= Edge
[i
].nxt
)
{
int v
= Edge
[i
].v
;
if(!dfn
[v
])
{
tarjan(v
);
low
[id
] = min(low
[id
], low
[v
]);
}
else if(instack
[v
])
low
[id
] = min(low
[id
], dfn
[v
]);
}
if(dfn
[id
] == low
[id
])
{
int v
;
num
++;
do
{
v
= st
[top
--];
instack
[v
] = false;
col
[v
] = num
;
} while(v
!= id
);
}
}
vector
<int> ans
;
int main()
{
int u
, v
, w
;
scanf("%d%d", &n
, &m
);
init();
for(int i
= 1; i
<= m
; i
++)
{
scanf("%d%d%d", &u
, &v
, &w
);
if(w
)
{
addedge(u
+ n
, v
+ n
);
addedge(v
, u
);
addedge(v
+ n
, u
+ n
);
addedge(u
, v
);
}
else
{
addedge(u
+ n
, v
);
addedge(v
+ n
, u
);
addedge(u
, v
+ n
);
addedge(v
, u
+ n
);
}
}
for(int i
= 1; i
<= 2 * n
; i
++)
{
if(!dfn
[i
]) tarjan(i
);
}
bool isok
= true;
for(int i
= 1; i
<= n
; i
++)
{
if(col
[i
] == col
[i
+ n
])
{
isok
= false;
break;
}
}
if(!isok
)
{
printf("Impossible\n");
return 0;
}
for(int i
= 1; i
<= n
; i
++)
{
var
[i
] = col
[i
] > col
[i
+ n
];
if(var
[i
]) ans
.pb(i
);
}
printf("%d\n", (int)ans
.size());
for(int i
= 0; i
< ans
.size(); i
++)
{
if(i
> 0) printf(" ");
printf("%d", ans
[i
]);
}
return 0;
}
4. Codeforces - 780D - Innokenty and a Football League
4.1 题意
现在有
n
(
1
≤
n
≤
1
0
3
)
n(1 \le n \le 10^3)
n(1≤n≤103) 支球队，每支球队
i
i
i 有两个名字
n
a
m
e
i
,
0
name_{i,0}
namei,0 和
n
a
m
e
i
,
1
name_{i,1}
namei,1。每个球队必须在两个名字中选择其中一个，并且满足如下条件：
(
1
)
(1)
(1) 不能有任意两支球队的名字相同。
(
2
)
(2)
(2) 对于球队
i
i
i，若其选择了
n
a
m
e
i
,
1
name_{i, 1}
namei,1，则对于任意的
j
(
1
≤
j
≤
n
,
i
≠
j
)
j(1 \le j \le n,i \ne j)
j(1≤j≤n,i=j)，若满足
n
a
m
e
i
,
0
≠
n
a
m
e
j
,
0
name_{i,0} \ne name_{j,0}
namei,0=namej,0，则不可选择
n
a
m
e
j
,
0
name_{j,0}
namej,0。
问每支球队的取名方案。
4.2 解题思路
本题为
2-SAT
\text{2-SAT}
2-SAT 问题，需要建立一个
2
n
2n
2n 个点的有向图。
设
i
,
j
∈
[
1
,
n
]
,
i
≠
j
i,j \in [1,n], i \ne j
i,j∈[1,n],i=j，
则设点
i
,
j
i,j
i,j 分别表示
i
i
i 选择了
n
a
m
e
i
,
0
name_{i,0}
namei,0 和
j
j
j 选择了
n
a
m
e
j
,
0
name_{j,0}
namej,0；
设点
i
+
n
,
j
+
n
i + n,j + n
i+n,j+n 分别表示
i
i
i 选择了
n
a
m
e
i
,
1
name_{i,1}
namei,1 和
j
j
j 选择了
n
a
m
e
j
,
1
name_{j,1}
namej,1。
设有向边
<
i
,
j
>
<i,j>
<i,j> 表示若
i
i
i 选择了
n
a
m
e
i
,
0
name_{i,0}
namei,0，则
j
j
j 必须选择
n
a
m
e
j
,
0
name_{j,0}
namej,0。
其他情况同理。
我们可以在
[
1
,
n
]
[1,n]
[1,n] 范围内遍历
i
i
i 和
j
(
i
≠
j
)
j(i \ne j)
j(i=j)，根据题中条件有以下三种情况：
(
1
)
(1)
(1) 若
n
a
m
e
i
,
0
=
n
a
m
e
j
,
0
name_{i,0}=name_{j,0}
namei,0=namej,0，则添加如下边：
<
i
,
j
+
n
>
<i,j+n>
<i,j+n> 及其逆否命题
<
j
,
i
+
n
>
<j, i+n>
<j,i+n>（条件
(
1
)
(1)
(1)）
<
i
+
n
,
j
+
n
>
<i+n, j+n>
<i+n,j+n> 及其逆否命题
<
j
,
i
>
<j, i>
<j,i>（条件
(
2
)
(2)
(2)）
（考虑条件 2 的逆否命题：若
j
j
j 选择了
n
a
m
e
j
,
0
name_{j,0}
namej,0 且
n
a
m
e
i
,
0
=
n
a
m
e
j
,
0
name_{i,0}=name_{j,0}
namei,0=namej,0，则
i
i
i 选择了
n
a
m
e
i
,
0
name_{i,0}
namei,0）
(
2
)
(2)
(2) 若
n
a
m
e
i
,
1
=
n
a
m
e
j
,
1
name_{i,1}=name_{j,1}
namei,1=namej,1，则添加如下边：
<
i
+
n
,
j
>
<i+n, j>
<i+n,j> 及其逆否命题
<
j
+
n
,
i
>
<j+n, i>
<j+n,i>（条件
(
1
)
(1)
(1)）
(
3
)
(3)
(3) 若
n
a
m
e
i
,
0
=
n
a
m
e
j
,
1
name_{i,0}=name_{j,1}
namei,0=namej,1，则添加如下边：
<
i
,
j
>
<i, j>
<i,j> 及其逆否命题
<
j
+
n
,
i
+
n
>
<j+n, i+n>
<j+n,i+n>（条件
(
1
)
(1)
(1)）
(
4
)
(4)
(4)若 $name_{i,0} \ne name_{j,0} $，则添加如下边：
<
i
+
n
,
j
+
n
>
<i+n, j+n>
<i+n,j+n> 及其逆否命题
<
j
,
i
>
<j, i>
<j,i>（条件
(
2
)
(2)
(2)）
建边之后，在整张图上面跑 Tarjan，求出所有的强连通分量。
之后，判断每个
i
(
1
≤
i
≤
n
)
i(1 \le i \le n)
i(1≤i≤n) 是否满足
i
i
i 和
i
+
n
i + n
i+n 在同一个强连通分量中，若满足，则表明若选择
n
a
m
e
i
,
0
name_{i,0}
namei,0，则必须选择
n
a
m
e
i
,
1
name_{i,1}
namei,1，这与题意矛盾，因此答案不存在。
否则，输出一种合法的答案。
时间复杂度：
O
(
2
n
)
O(2n)
O(2n)。
4.3 代码
int head
[maxn
], n
, m
, cnt
, tot
, top
, num
;
int dfn
[maxn
], low
[maxn
], st
[maxn
], col
[maxn
], rev
[maxn
], var
[maxn
];
bool instack
[maxn
];
struct edge
{
int v
, nxt
;
} Edge
[8 * maxn
* maxn
];
void init()
{
for(int i
= 0; i
<= 2 * n
; i
++) head
[i
] = -1;
cnt
= tot
= top
= num
= 0;
}
void addedge(int u
, int v
)
{
Edge
[cnt
].v
= v
;
Edge
[cnt
].nxt
= head
[u
];
head
[u
] = cnt
++;
}
void tarjan(int id
)
{
dfn
[id
] = low
[id
] = ++tot
;
st
[++top
] = id
;
instack
[id
] = true;
for(int i
= head
[id
]; i
!= -1; i
= Edge
[i
].nxt
)
{
int v
= Edge
[i
].v
;
if(!dfn
[v
])
{
tarjan(v
);
low
[id
] = min(low
[id
], low
[v
]);
}
else if(instack
[v
])
low
[id
] = min(low
[id
], dfn
[v
]);
}
if(dfn
[id
] == low
[id
])
{
int v
;
num
++;
do
{
v
= st
[top
--];
instack
[v
] = false;
col
[v
] = num
;
} while(v
!= id
);
}
}
string name
[maxn
][2];
int main()
{
string stra
, strb
;
scanf("%d", &n
);
init();
for(int i
= 1; i
<= n
; i
++)
{
cin
>> stra
>> strb
;
name
[i
][0] += stra
[0];
name
[i
][0] += stra
[1];
name
[i
][0] += stra
[2];
name
[i
][1] += stra
[0];
name
[i
][1] += stra
[1];
name
[i
][1] += strb
[0];
}
for(int i
= 1; i
<= n
; i
++)
{
for(int j
= 1; j
<= n
; j
++)
{
if(i
== j
) continue;
if(name
[i
][0] == name
[j
][0])
{
addedge(i
, j
+ n
);
addedge(j
, i
+ n
);
addedge(i
+ n
, j
+ n
);
addedge(j
, i
);
}
if(name
[i
][1] == name
[j
][1])
{
addedge(i
+ n
, j
);
addedge(j
+ n
, i
);
}
if(name
[i
][0] == name
[j
][1])
{
addedge(i
, j
);
addedge(j
+ n
, i
+ n
);
}
}
}
for(int i
= 1; i
<= 2 * n
; i
++)
{
if(!dfn
[i
]) tarjan(i
);
}
bool isok
= true;
for(int i
= 1; i
<= n
; i
++)
{
if(col
[i
] == col
[i
+ n
])
{
isok
= false;
break;
}
rev
[i
] = i
+ n
;
rev
[i
+ n
] = i
;
}
if(!isok
)
{
printf("NO\n");
return 0;
}
for(int i
= 1; i
<= 2 * n
; i
++)
{
var
[i
] = col
[i
] > col
[rev
[i
]];
}
printf("YES\n");
for(int i
= 1; i
<= n
; i
++)
{
cout
<< name
[i
][var
[i
]] << endl
;
}
return 0;
}
5. Codeforces - 875C - National Property
题目链接：https://codeforces.com/problemset/problem/875/C
5.1 题意
给你
n
(
2
≤
n
≤
1
0
5
)
n(2 \le n \le 10^5)
n(2≤n≤105) 个字符串（由
[
1
,
m
]
(
1
≤
m
≤
1
0
5
)
[1,m](1 \le m \le 10^5)
[1,m](1≤m≤105) 之间的小写字母组成）。
现在可以把某些字母变成大写，例如
2
2
2 变成
2
′
2'
2′。
规定大写字母的字典序小于小写字母，如果同是大写字母或同是小写字母，则值小的字典序小。
问是否存在一种小写转大写的方案，使得字符串按照字典序不减的顺序排列。
题目保证字符串的总长不超过
1
0
5
10^5
105。
5.2 解题过程
比较显然的 2-SAT 问题。
设
x
0
x_0
x0 表示
x
x
x 字母保持小写状态，
x
1
x_1
x1 表示
x
x
x 字母转化为大写。
则我们可以遍历所有相邻的字符串，之后内层循环枚举字符串中相同位置的字母，分别设为
u
u
u 和
v
v
v。
则存在以下三种情况：
u
=
v
u=v
u=v，此时无需进行任何操作；
u
>
v
u > v
u>v，此时只有一种方案，那就是
u
u
u 强制转化为大写，
v
v
v 强制保持为小写。因此建有向边
<
u
0
,
u
1
>
<u_0,u_1>
<u0,u1> 以及
<
v
1
,
v
0
>
<v_1,v_0>
<v1,v0>；
u
<
v
u < v
u<v，此时若
u
u
u 保持小写，则
v
v
v 也必须保持小写，因此建立有向边
<
u
0
,
v
0
>
<u_0,v_0>
<u0,v0> 以及其逆否命题
<
v
1
,
u
1
>
<v_1,u_1>
<v1,u1>；若
u
u
u 转化为大写，则
v
v
v 的状态随意，即没有任何限制，无需建边。
之后一遍 2-SAT 即可解决问题。
注意要特判前面字符串是后面字符串前缀，且前面字符串的长度更小的情况，此时无解。
时间复杂度：
O
(
n
m
+
2
m
)
O(nm+2m)
O(nm+2m)。
5.3 错误点
没有特判前面字符串是后面字符串前缀，且前面字符串的长度更小的情况。
5.4 代码
int head
[maxn
], n
, m
, cnt
, tot
, top
, num
;
int dfn
[maxn
], low
[maxn
], st
[maxn
], col
[maxn
];
bool instack
[maxn
];
struct edge
{
int v
, nxt
;
} Edge
[8 * maxn
];
void init()
{
for(int i
= 0; i
<= 2 * m
; i
++) head
[i
] = -1;
cnt
= tot
= top
= num
= 0;
}
void addedge(int u
, int v
)
{
Edge
[cnt
].v
= v
;
Edge
[cnt
].nxt
= head
[u
];
head
[u
] = cnt
++;
}
void tarjan(int id
)
{
dfn
[id
] = low
[id
] = ++tot
;
st
[++top
] = id
;
instack
[id
] = true;
for(int i
= head
[id
]; i
!= -1; i
= Edge
[i
].nxt
)
{
int v
= Edge
[i
].v
;
if(!dfn
[v
])
{
tarjan(v
);
low
[id
] = min(low
[id
], low
[v
]);
}
else if(instack
[v
])
low
[id
] = min(low
[id
], dfn
[v
]);
}
if(dfn
[id
] == low
[id
])
{
int v
;
num
++;
do
{
v
= st
[top
--];
instack
[v
] = false;
col
[v
] = num
;
} while(v
!= id
);
}
}
vector
<int> words
[maxn
];
int ans
[maxn
];
vector
<int> ve
;
int main()
{
scanf("%d%d", &n
, &m
);
init();
for (int i
= 1; i
<= n
; i
++) {
int k
;
scanf("%d", &k
);
for (int j
= 1; j
<= k
; j
++) {
int num
;
scanf("%d", &num
);
words
[i
].emplace_back(num
);
}
}
for (int i
= 1; i
< n
; i
++) {
int len
= min(words
[i
].size(), words
[i
+ 1].size());
for (int j
= 0; j
< len
; j
++) {
int u
= words
[i
][j
];
int v
= words
[i
+ 1][j
];
if (u
> v
) {
addedge(u
, u
+ m
);
addedge(v
+ m
, v
);
break;
} else if (u
< v
) {
addedge(u
, v
);
addedge(v
+ m
, u
+ m
);
break;
}
if (j
== len
- 1 && j
< (int)words
[i
].size() - 1) {
return 0 * puts("No");
}
}
}
for (int i
= 1; i
<= 2 * m
; i
++) {
if (!dfn
[i
]) tarjan(i
);
}
for (int i
= 1; i
<= m
; i
++) {
if (col
[i
] == col
[i
+ m
]) return 0 * puts("No");
}
for (int i
= 1; i
<= m
; i
++) {
ans
[i
] = col
[i
] > col
[i
+ m
];
if (ans
[i
]) ve
.emplace_back(i
);
}
puts("Yes");
printf("%d\n", (int)ve
.size());
for (auto x
: ve
) {
printf("%d ", x
);
}
return 0;
}
6. Codeforces - 1218I - The Light Square
题目链接：https://codeforces.com/problemset/problem/1218/I
6.1 题意
给你一个
n
×
n
(
1
≤
n
≤
2000
)
n \times n(1 \le n \le 2000)
n×n(1≤n≤2000) 的
0
−
1
0-1
0−1 矩阵
A
A
A，然后给你一个长度为
n
n
n 的串
s
s
s。
每次你可将某行（从左往右看）或某列（从上往下看）异或上
s
s
s。
问是否存在一种方案，可以使
A
A
A 转化为
B
B
B，或者说明方案不存在。
6.2 解题过程
首先，我们需要清楚，
0
0
0 异或上一个数会使这个数保持原样，
1
1
1 异或上一个数会使这个数字取反。
之后，设
l
i
n
e
[
i
]
[
0
]
line[i][0]
line[i][0] 表示第
i
i
i 行不进行任何操作，
l
i
n
e
[
i
]
[
1
]
line[i][1]
line[i][1] 表示将第
i
i
i 行异或上
s
s
s；
c
o
l
[
j
]
[
0
]
col[j][0]
col[j][0] 表示第
j
j
j 列不进行任何操作，
c
o
l
[
j
]
[
1
]
col[j][1]
col[j][1] 表示将第
j
j
j 列异或上
s
s
s。
遍历矩阵
A
A
A，设当前遍历到的元素为
A
[
i
]
[
j
]
A[i][j]
A[i][j]，则分两种情况讨论：
（一）若
A
[
i
]
[
j
]
≠
B
[
i
]
[
j
]
A[i][j] \ne B[i][j]
A[i][j]=B[i][j]，
如果
s
[
i
]
=
0
s[i]=0
s[i]=0 且
s
[
j
]
=
0
s[j]=0
s[j]=0，表明
A
[
i
]
[
j
]
A[i][j]
A[i][j] 的值已经无法改变，此时无解。如果
s
[
i
]
=
1
s[i]=1
s[i]=1 且
s
[
j
]
=
1
s[j]=1
s[j]=1，表明我们必须对第
i
i
i 行和第
j
j
j 列中的恰好一个进行操作，因此建边
<
l
i
n
e
[
i
]
[
0
]
,
c
o
l
[
j
]
[
1
]
>
<line[i][0], col[j][1]>
<line[i][0],col[j][1]> 及其逆否命题
<
c
o
l
[
j
]
[
0
]
,
l
i
n
e
[
i
]
[
1
]
>
<col[j][0], line[i][1]>
<col[j][0],line[i][1]>，以及
<
l
i
n
e
[
i
]
[
1
]
,
c
o
l
[
j
]
[
0
]
>
<line[i][1], col[j][0]>
<line[i][1],col[j][0]> 及其逆否命题
<
c
o
l
[
j
]
[
1
]
,
l
i
n
e
[
i
]
[
0
]
>
<col[j][1], line[i][0]>
<col[j][1],line[i][0]>。如果
s
[
i
]
=
1
s[i]=1
s[i]=1 且
s
[
j
]
=
0
s[j]=0
s[j]=0，表明第
i
i
i 行必须操作，因此建边
<
l
i
n
e
[
i
]
[
0
]
,
l
i
n
e
[
i
]
[
1
]
>
<line[i][0], line[i][1]>
<line[i][0],line[i][1]>。如果
s
[
i
]
=
0
s[i]=0
s[i]=0 且
s
[
j
]
=
1
s[j]=1
s[j]=1，表明第
j
j
j 列必须操作，因此建边
<
c
o
l
[
j
]
[
0
]
,
c
o
l
[
j
]
[
1
]
>
<col[j][0], col[j][1]>
<col[j][0],col[j][1]>。
（二）若
A
[
i
]
[
j
]
=
B
[
i
]
[
j
]
A[i][j] = B[i][j]
A[i][j]=B[i][j]，
如果
s
[
i
]
=
0
s[i]=0
s[i]=0 且
s
[
j
]
=
0
s[j]=0
s[j]=0，表明第
i
i
i 行或第
j
j
j 列的异或与否，没有任何影响，因此无需进行任何操作。如果
s
[
i
]
=
1
s[i]=1
s[i]=1 且
s
[
j
]
=
1
s[j]=1
s[j]=1，表明我们对第
i
i
i 行和第
j
j
j 列要么同时进行操作，要么都不进行操作，因此建边
<
l
i
n
e
[
i
]
[
0
]
,
c
o
l
[
j
]
[
0
]
>
<line[i][0], col[j][0]>
<line[i][0],col[j][0]> 及其逆否命题
<
c
o
l
[
j
]
[
1
]
,
l
i
n
e
[
i
]
[
1
]
>
<col[j][1], line[i][1]>
<col[j][1],line[i][1]>，以及
<
l
i
n
e
[
i
]
[
1
]
,
c
o
l
[
j
]
[
1
]
>
<line[i][1], col[j][1]>
<line[i][1],col[j][1]> 及其逆否命题
<
c
o
l
[
j
]
[
0
]
,
l
i
n
e
[
i
]
[
0
]
>
<col[j][0], line[i][0]>
<col[j][0],line[i][0]>。如果
s
[
i
]
=
1
s[i]=1
s[i]=1 且
s
[
j
]
=
0
s[j]=0
s[j]=0，表明第
i
i
i 行不可以操作，因此建边
<
l
i
n
e
[
i
]
[
1
]
,
l
i
n
e
[
i
]
[
0
]
>
<line[i][1], line[i][0]>
<line[i][1],line[i][0]>。如果
s
[
i
]
=
0
s[i]=0
s[i]=0 且
s
[
j
]
=
1
s[j]=1
s[j]=1，表明第
j
j
j 列不可以操作，因此建边
<
c
o
l
[
j
]
[
1
]
,
c
o
l
[
j
]
[
0
]
>
<col[j][1], col[j][0]>
<col[j][1],col[j][0]>。
建边之后，跑一遍 2-SAT，之后输出方案即可。
时间复杂度：
O
(
n
2
+
4
n
)
O(n^2 + 4n)
O(n2+4n)。
6.3 代码
int head
[maxn
], n
, m
, cnt
, tot
, top
, num
;
int dfn
[maxn
], low
[maxn
], st
[maxn
], col
[maxn
];
bool instack
[maxn
];
struct edge
{
int v
, nxt
;
} Edge
[2 * maxn
];
void init() {
for (int i
= 0; i
<= 4 * n
; i
++) {
head
[i
] = -1;
}
cnt
= tot
= top
= num
= 0;
}
void addedge(int u
, int v
) {
Edge
[cnt
].v
= v
;
Edge
[cnt
].nxt
= head
[u
];
head
[u
] = cnt
++;
}
void tarjan(int id
)
{
dfn
[id
] = low
[id
] = ++tot
;
st
[++top
] = id
;
instack
[id
] = true;
for(int i
= head
[id
]; i
!= -1; i
= Edge
[i
].nxt
)
{
int v
= Edge
[i
].v
;
if(!dfn
[v
])
{
tarjan(v
);
low
[id
] = min(low
[id
], low
[v
]);
}
else if(instack
[v
])
low
[id
] = min(low
[id
], dfn
[v
]);
}
if(dfn
[id
] == low
[id
])
{
int v
;
num
++;
do
{
v
= st
[top
--];
instack
[v
] = false;
col
[v
] = num
;
} while(v
!= id
);
}
}
char S
[2005][2005], T
[2005][2005];
char bar
[2005];
int ans
[4005];
vector
<pii
> ve
;
int main()
{
scanf("%d", &n
);
init();
for (int i
= 1; i
<= n
; i
++) {
scanf("%s", S
[i
] + 1);
for (int j
= 1; j
<= n
; j
++) {
S
[i
][j
] = (S
[i
][j
] == '1');
}
}
for (int i
= 1; i
<= n
; i
++) {
scanf("%s", T
[i
] + 1);
for (int j
= 1; j
<= n
; j
++) {
T
[i
][j
] = (T
[i
][j
] == '1');
}
}
scanf("%s", bar
+ 1);
for (int i
= 1; i
<= n
; i
++) {
bar
[i
] = (bar
[i
] == '1');
}
for (int i
= 1; i
<= n
; i
++) {
for (int j
= 1; j
<= n
; j
++) {
if (S
[i
][j
] != T
[i
][j
]) {
if (bar
[i
] == 0 && bar
[j
] == 0) {
return 0 * puts("-1");
}
if (bar
[i
] && bar
[j
]) {
addedge(i
, j
+ 2 * n
+ n
);
addedge(j
+ 2 * n
, i
+ n
);
addedge(i
+ n
, j
+ 2 * n
);
addedge(j
+ 2 * n
+ n
, i
);
} else if (bar
[j
]) {
addedge(i
, i
+ n
);
} else if (bar
[i
]) {
addedge(j
+ 2 * n
, j
+ 2 * n
+ n
);
}
} else {
if (bar
[i
] && bar
[j
]) {
addedge(i
, j
+ 2 * n
);
addedge(j
+ 2 * n
+ n
, i
+ n
);
addedge(i
+ n
, j
+ 2 * n
+ n
);
addedge(j
+ 2 * n
, i
);
} else if (bar
[j
]) {
addedge(i
+ n
, i
);
} else if (bar
[i
]) {
addedge(j
+ 2 * n
+ n
, j
+ 2 * n
);
}
}
}
}
for (int i
= 1; i
<= 4 * n
; i
++) {
if (!dfn
[i
]) {
tarjan(i
);
}
}
for (int i
= 1; i
<= n
; i
++) {
if (col
[i
] == col
[i
+ n
]) return 0 * puts("-1");
ans
[i
] = (col
[i
] > col
[i
+ n
]);
}
for (int i
= 1 + 2 * n
; i
<= 4 * n
; i
++) {
if (col
[i
] == col
[i
+ n
]) return 0 * puts("-1");
ans
[i
] = (col
[i
] > col
[i
+ n
]);
}
for (int i
= 1; i
<= n
; i
++) {
if (ans
[i
]) ve
.pb({0, i
- 1});
}
for (int i
= 1 + 2 * n
; i
<= 3 * n
; i
++) {
if (ans
[i
]) ve
.pb({1, i
- 2 * n
- 1});
}
printf("%d\n", (int)ve
.size());
for (auto element
: ve
) {
if (!element
.first
) printf("row %d\n", element
.second
);
else printf("col %d\n", element
.second
);
}
return 0;
}
7. Codeforces - 27D - Ring Road 2
题目链接：https://codeforces.com/problemset/problem/27/D
7.1 题意
现在有一个
n
(
4
≤
n
≤
100
)
n(4 \le n \le 100)
n(4≤n≤100) 元环和
m
(
1
≤
m
≤
100
)
m(1 \le m \le 100)
m(1≤m≤100) 条边，第
i
i
i 条边连接
a
i
a_i
ai 和
b
i
b_i
bi 两个点。
每条边可以被安排到在环内或者环外。
现在需要你输出一种安排边的方案，使得所有的边不存在在非端点处相交的情况，或者说明答案不存在。
7.2 解题过程
如果把每条边都看作一段线段的话，会发现边在非端点处相交等价于线段在非端点处相交。
设
x
0
x_0
x0 表示
x
x
x 在环内，
x
1
x_1
x1 表示
x
x
x 在环外。
对于两条边
i
i
i 和
j
j
j：
若
i
i
i 和
j
j
j 不在非端点处相交，则可以任意安排，无任何限制。若
i
i
i 和
j
j
j 在非端点处相交，表明
i
i
i 和
j
j
j 不可以同时在环内或者环外，因此建边
<
i
0
,
j
1
>
<i_0, j_1>
<i0,j1> 及其逆否命题
<
j
0
,
i
1
>
<j_0, i_1>
<j0,i1>，以及
<
i
1
,
j
0
>
<i_1, j_0>
<i1,j0> 及其逆否命题
<
j
1
,
i
0
>
<j_1, i_0>
<j1,i0>。
之后一遍 2-SAT 之后输出方案即可。
时间复杂度：
O
(
m
2
+
2
⋅
m
)
O(m^2 + 2 \cdot m)
O(m2+2⋅m)。
7.3 代码
int head
[maxn
], n
, m
, cnt
, tot
, top
, num
;
int dfn
[maxn
], low
[maxn
], st
[maxn
], col
[maxn
];
bool instack
[maxn
];
struct edge
{
int v
, nxt
;
} Edge
[2 * maxn
];
void init() {
for (int i
= 0; i
<= 2 * m
; i
++) {
head
[i
] = -1;
}
cnt
= tot
= top
= num
= 0;
}
void addedge(int u
, int v
) {
Edge
[cnt
].v
= v
;
Edge
[cnt
].nxt
= head
[u
];
head
[u
] = cnt
++;
}
void tarjan(int id
)
{
dfn
[id
] = low
[id
] = ++tot
;
st
[++top
] = id
;
instack
[id
] = true;
for(int i
= head
[id
]; i
!= -1; i
= Edge
[i
].nxt
)
{
int v
= Edge
[i
].v
;
if(!dfn
[v
])
{
tarjan(v
);
low
[id
] = min(low
[id
], low
[v
]);
}
else if(instack
[v
])
low
[id
] = min(low
[id
], dfn
[v
]);
}
if(dfn
[id
] == low
[id
])
{
int v
;
num
++;
do
{
v
= st
[top
--];
instack
[v
] = false;
col
[v
] = num
;
} while(v
!= id
);
}
}
bool check(pii a
, pii b
) {
if (a
> b
) swap(a
, b
);
if (b
.first
> a
.first
&& b
.first
< a
.second
&& b
.second
> a
.second
) return false;
return true;
}
pii point
[maxn
];
int ans
[maxn
];
int main()
{
int u
, v
;
scanf("%d%d", &n
, &m
);
init();
for (int i
= 1; i
<= m
; i
++) {
scanf("%d%d", &u
, &v
);
point
[i
] = {min(u
, v
), max(u
, v
)};
}
for (int i
= 1; i
<= m
; i
++) {
for (int j
= i
+ 1; j
<= m
; j
++) {
if (!check(point
[i
], point
[j
])) {
addedge(i
, j
+ m
);
addedge(j
, i
+ m
);
addedge(i
+ m
, j
);
addedge(j
+ m
, i
);
}
}
}
for (int i
= 1; i
<= 2 * m
; i
++) {
if (!dfn
[i
]) {
tarjan(i
);
}
}
for (int i
= 1; i
<= m
; i
++) {
if (col
[i
] == col
[i
+ m
]) return 0 * puts("Impossible");
ans
[i
] = (col
[i
] > col
[i
+ m
]);
}
for (int i
= 1; i
<= m
; i
++) {
if (ans
[i
]) printf("o");
else printf("i");
}
return 0;
}
8. Gym - 100112K - Kindergarten
题目链接：https://codeforces.com/gym/100112
题目来源：2012 Nordic Collegiate Programming Contest (NCPC)
8.1 题意
有三个班级（编号为
{
0
,
1
,
2
}
\left\{ 0,1,2\right\}
{0,1,2}）和
n
(
n
≤
200
)
n(n \le 200)
n(n≤200) 名学生，每个学生最初都有一个班级。
现在每个学生都要转入一个新的班级，且每个学生都有一个对其他
n
−
1
n-1
n−1 个学生的排序表。
现在要找到最小的
T
T
T，使得满足每个学生新班级中的学生都来自其排序表中的前
T
T
T 项。
8.2 解题过程
首先，我们可以发现，若一个
T
0
T_0
T0 可行，则所有的
T
>
T
0
T > T_0
T>T0 均可行，因为条件被放宽了。
因此我们可以二分这个
T
T
T，之后只需进行可行性判断。
每个学生新班级中的学生都来自其排序表中的前
T
T
T 项，等价于排序表中的后面项都不可以出现在学生的新班级中。
考虑 2-SAT，设
x
0
x_0
x0 表示学生
x
x
x 转入了第一个可以转入的班级，
x
1
x_1
x1 表示学生
x
x
x 转入了第二个可以转入的班级。（
0
0
0 班可转入
{
1
,
2
}
\left\{ 1,2\right\}
{1,2} 班，
1
1
1 班可转入
{
0
,
2
}
\left\{ 0,2\right\}
{0,2} 班，
2
2
2 班可转入
{
0
,
1
}
\left\{ 0,1\right\}
{0,1} 班）。
设
c
l
a
s
s
[
x
]
class[x]
class[x] 表示学生
x
x
x 所属班级，
s
t
a
t
e
[
y
]
[
0
]
state[y][0]
state[y][0] 表示原班级为
x
x
x 的学生可转入的第一个班级，
s
t
a
t
e
[
y
]
[
1
]
state[y][1]
state[y][1] 表示原班级为
x
x
x 的学生可转入的第二个班级。
之后对于每个学生
x
x
x，枚举其在前
T
T
T 个意向学生之外的学生
y
y
y，以及
x
x
x 转入的班级顺序号
k
(
k
∈
[
0
,
1
]
)
k(k \in [0,1])
k(k∈[0,1])，然后进行分类讨论：
若
s
t
a
t
e
[
c
l
a
s
s
[
x
]
]
[
k
]
≠
s
t
a
t
e
[
c
l
a
s
s
[
y
]
]
[
0
]
state[class[x]][k] \ne state[class[y]][0]
state[class[x]][k]=state[class[y]][0] 并且
s
t
a
t
e
[
c
l
a
s
s
[
x
]
]
[
k
]
≠
s
t
a
t
e
[
c
l
a
s
s
[
y
]
]
[
1
]
state[class[x]][k] \ne state[class[y]][1]
state[class[x]][k]=state[class[y]][1]，表明若
x
x
x 转入第
k
k
k 个可以转入的班级，
y
y
y 一定和
x
x
x 不同班，因此无需进行任何操作；
若
s
t
a
t
e
[
c
l
a
s
s
[
x
]
]
[
k
]
≠
s
t
a
t
e
[
c
l
a
s
s
[
y
]
]
[
0
]
state[class[x]][k] \ne state[class[y]][0]
state[class[x]][k]=state[class[y]][0] 并且
s
t
a
t
e
[
c
l
a
s
s
[
x
]
]
[
k
]
=
s
t
a
t
e
[
c
l
a
s
s
[
y
]
]
[
1
]
state[class[x]][k] = state[class[y]][1]
state[class[x]][k]=state[class[y]][1]，表明若
x
x
x 转入第
k
k
k 个可以转入的班级，
y
y
y 若想和
x
x
x 不同班，就必须转入他的第一个可转入的班级。因此建边
<
x
k
,
y
0
>
<x_k, y_0>
<xk,y0> 及其逆否命题
<
y
1
,
x
1
−
k
>
<y_1, x_{1-k}>
<y1,x1−k>。
若
s
t
a
t
e
[
c
l
a
s
s
[
x
]
]
[
k
]
=
s
t
a
t
e
[
c
l
a
s
s
[
y
]
]
[
0
]
state[class[x]][k] = state[class[y]][0]
state[class[x]][k]=state[class[y]][0] 并且
s
t
a
t
e
[
c
l
a
s
s
[
x
]
]
[
k
]
≠
s
t
a
t
e
[
c
l
a
s
s
[
y
]
]
[
1
]
state[class[x]][k] \ne state[class[y]][1]
state[class[x]][k]=state[class[y]][1]，表明若
x
x
x 转入第
k
k
k 个可以转入的班级，
y
y
y 若想和
x
x
x 不同班，就必须转入他的第二个可转入的班级。因此建边
<
x
k
,
y
1
>
<x_k, y_1>
<xk,y1> 及其逆否命题
<
y
0
,
x
1
−
k
>
<y_0, x_{1-k}>
<y0,x1−k>。
之后通过 2-SAT 判断合法性即可。
时间复杂度：
O
(
n
2
log
n
)
O(n^2 \log n)
O(n2logn)。
8.3 代码
int head
[maxn
], n
, m
, cnt
, tot
, top
, num
;
int dfn
[maxn
], low
[maxn
], st
[maxn
], col
[maxn
];
bool instack
[maxn
];
struct edge
{
int v
, nxt
;
} Edge
[8 * maxn
];
void init()
{
for(int i
= 0; i
<= 2 * n
; i
++) {
head
[i
] = -1;
dfn
[i
] = 0;
low
[i
] = 0;
st
[i
] = 0;
col
[i
] = 0;
instack
[i
] = false;
}
cnt
= tot
= top
= num
= 0;
}
void addedge(int u
, int v
)
{
Edge
[cnt
].v
= v
;
Edge
[cnt
].nxt
= head
[u
];
head
[u
] = cnt
++;
}
void tarjan(int id
)
{
dfn
[id
] = low
[id
] = ++tot
;
st
[++top
] = id
;
instack
[id
] = true;
for(int i
= head
[id
]; i
!= -1; i
= Edge
[i
].nxt
)
{
int v
= Edge
[i
].v
;
if(!dfn
[v
])
{
tarjan(v
);
low
[id
] = min(low
[id
], low
[v
]);
}
else if(instack
[v
])
low
[id
] = min(low
[id
], dfn
[v
]);
}
if(dfn
[id
] == low
[id
])
{
int v
;
num
++;
do
{
v
= st
[top
--];
instack
[v
] = false;
col
[v
] = num
;
} while(v
!= id
);
}
}
int teacher
[maxn
], matrix
[205][205];
int state
[3][2] = {1, 2, 0, 2, 0, 1};
int id(int x
, int type
) {
if (type
== 1) return x
+ n
;
return x
;
}
bool check(int x
) {
init();
for (int i
= 1; i
<= n
; i
++) {
for (int j
= n
- 1; j
> x
; j
--) {
for (int k
= 0; k
< 2; k
++) {
int v
= matrix
[i
][j
];
if (state
[teacher
[i
]][k
] != state
[teacher
[v
]][0] && state
[teacher
[i
]][k
] != state
[teacher
[v
]][1]) {
continue;
} else if (state
[teacher
[i
]][k
] != state
[teacher
[v
]][0]) {
addedge(id(i
, k
), v
);
addedge(v
+ n
, id(i
, 1 - k
));
} else if (state
[teacher
[i
]][k
] != state
[teacher
[v
]][1]) {
addedge(id(i
, k
), v
+ n
);
addedge(v
, id(i
, 1 - k
));
}
}
}
}
for (int i
= 1; i
<= 2 * n
; i
++) {
if (!dfn
[i
]) tarjan(i
);
}
for (int i
= 1; i
<= n
; i
++) {
if (col
[i
] == col
[i
+ n
]) return false;
}
return true;
}
int main()
{
scanf("%d", &n
);
for (int i
= 1; i
<= n
; i
++) {
scanf("%d", &teacher
[i
]);
for (int j
= 1; j
< n
; j
++) {
scanf("%d", &matrix
[i
][j
]);
}
}
int ans
= 0x3f3f3f3f;
int left
= 0, right
= n
- 1;
while (left
<= right
) {
int mid
= (left
+ right
) / 2;
if (check(mid
)) {
ans
= min(ans
, mid
);
right
= mid
- 1;
} else {
left
= mid
+ 1;
}
}
printf("%d\n", ans
);
return 0;
}
9. Gym - 101987K - TV Show Game
题目链接：https://codeforces.com/gym/101987
题目来源：2018-2019 ACM-ICPC, Asia Seoul Regional Contest
9.1 题意
有
k
(
3
<
k
≤
5000
)
k(3 < k \le 5000)
k(3<k≤5000) 盏灯，每个灯可以亮红色和蓝色其中之一的颜色，最初不知道每个灯的颜色。
现在有
n
(
1
≤
n
≤
10000
)
n(1 \le n \le 10000)
n(1≤n≤10000) 名竞猜者，每个人可以随意挑选三盏灯并猜测它们的颜色。
猜中至少两个灯的竞猜者获胜。
现在需要设计一种灯泡颜色的方案，使得每个人都可以获胜，或者说明无解。
9.2 解题过程
考虑反面情况，如果一个选手猜测的一个灯猜错了，则他猜测的其他两盏灯必须是正确的。
基于此，可以通过 2-SAT 来进行求解。
时间复杂度：
O
(
n
+
k
)
O(n + k)
O(n+k)。
9.3 代码
int head
[maxn
], n
, m
, cnt
, tot
, top
, num
;
int dfn
[maxn
], low
[maxn
], st
[maxn
], col
[maxn
];
bool instack
[maxn
];
struct edge
{
int v
, nxt
;
} Edge
[8 * maxn
];
void init()
{
for(int i
= 0; i
<= 2 * n
; i
++) head
[i
] = -1;
cnt
= tot
= top
= num
= 0;
}
void addedge(int u
, int v
)
{
Edge
[cnt
].v
= v
;
Edge
[cnt
].nxt
= head
[u
];
head
[u
] = cnt
++;
}
void tarjan(int id
)
{
dfn
[id
] = low
[id
] = ++tot
;
st
[++top
] = id
;
instack
[id
] = true;
for(int i
= head
[id
]; i
!= -1; i
= Edge
[i
].nxt
)
{
int v
= Edge
[i
].v
;
if(!dfn
[v
])
{
tarjan(v
);
low
[id
] = min(low
[id
], low
[v
]);
}
else if(instack
[v
])
low
[id
] = min(low
[id
], dfn
[v
]);
}
if(dfn
[id
] == low
[id
])
{
int v
;
num
++;
do
{
v
= st
[top
--];
instack
[v
] = false;
col
[v
] = num
;
} while(v
!= id
);
}
}
struct node
{
int a
, b
;
} data
[5];
int state
[3][2] = {2, 3, 1, 3, 1, 2};
int id(int x
, int y
) {
if (y
) return x
+ n
;
else return x
;
}
int ans
[maxn
];
int main()
{
scanf("%d%d", &n
, &m
);
init();
for (int i
= 1; i
<= m
; i
++) {
for (int j
= 1; j
<= 3; j
++) {
char str
[2];
scanf("%d", &data
[j
].a
);
scanf("%s", str
);
data
[j
].b
= (str
[0] == 'B');
}
for (int j
= 1; j
<= 3; j
++) {
int x
= state
[j
- 1][0];
int y
= state
[j
- 1][1];
addedge(id(data
[j
].a
, 1 - data
[j
].b
), id(data
[x
].a
, data
[x
].b
));
addedge(id(data
[j
].a
, 1 - data
[j
].b
), id(data
[y
].a
, data
[y
].b
));
}
}
for (int i
= 1; i
<= 2 * n
; i
++) {
if (!dfn
[i
]) tarjan(i
);
}
for (int i
= 1; i
<= n
; i
++) {
if (col
[i
] == col
[i
+ n
]) return 0 * puts("-1");
ans
[i
] = col
[i
] > col
[i
+ n
];
}
for (int i
= 1; i
<= n
; i
++) {
if (ans
[i
]) printf("B");
else printf("R");
}
return 0;
}
