题目详情题解（0）讨论（0）提交记录（0）

AT_past202306_g.N-SAT

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

判断是否存在一种方法，为每个 NN 个变量 x1,x2,…,xNx_1,x_2,\ldots,x_N 分别赋值 00 或 11，使得：

  • 对所有 i=1,2,…,Mi=1,2,\ldots,M，都满足：
    • 对于每一个 ii，存在一个整数 jj，1≤j≤ki1 \leq j \leq k_i，使得 xai,j=bi,jx_{a_{i,j}}=b_{i,j}。

输入格式

输入按如下格式从标准输入给出：

N MN \ M
k1k_1
a1,1 b1,1a_{1,1}\ b_{1,1}
⋮\vdots
a1,k1 b1,k1a_{1,k_1}\ b_{1,k_1}
⋮\vdots
kMk_M
aM,1 bM,1a_{M,1}\ b_{M,1}
⋮\vdots
aM,kM bM,kMa_{M,k_M}\ b_{M,k_M}

输出格式

如果存在一种赋值方案，输出 Yes，否则输出 No。

输入输出样例

  • 输入#1

    5 3
1
4 0
1
5 0
2
2 0
3 1

    输出#1

    Yes

  • 输入#2

    1 2
1
1 0
1
1 1

    输出#2

    No

说明/提示

样例解释 1

例如，将 x1=1,x2=0,x3=0,x4=0,x5=0x_1=1, x_2=0, x_3=0, x_4=0, x_5=0 时，可以满足题目要求。

数据范围

  • 1≤N≤151 \leq N \leq 15
  • 1≤M≤1001 \leq M \leq 100
  • 1≤ki≤N1 \leq k_i \leq N
  • 1≤ai,1<ai,2<…<ai,ki≤N1 \leq a_{i,1} < a_{i,2} < \ldots < a_{i,k_i} \leq N
  • bi,j∈{0,1}b_{i,j} \in \{0,1\}
  • 输入中的所有数均为整数。

由 ChatGPT 5 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页