问题2765--J

2765: J

时间限制: 1 Sec  内存限制: 128 MB
提交: 61  解决: 5
[状态] [讨论版] [提交] [命题人:]
题目描述

运算包含很多种,在计算机中除了算术运算以外,还涉及到了其它运算,比如逻辑运算。逻辑运算包括与(AND)、或(OR)、异或(XOR)等。其运算规则如下:

1 AND 1 = 1   1 OR 1 = 1    1 XOR 1 = 0

1 AND 0 = 0   1 OR 0 = 1    1 XOR 0 = 1

0 AND 1 = 0   0 OR 1 = 1    0 XOR 1 = 1

0 AND 0 = 0   0 OR 0 = 0    0 XOR 0 = 0

现有n个变量d[1]d[n],每个变量的值非01。有m个算式,每个式子形如a b c op,其中ab是两个下标,分别代表d[a]d[b]两个变量的值;c是一个数字,非01op代表一种操作,是ANDORXOR其中的一个,算式的含义为:d[a] op d[b] = c。请判断,是否存在一组d[1]d[n]的赋值,使得m个算式都成立。

输入

第一行两个整数nm1n≤1000, 0≤m≤1000000

接下来m行,每行三个整字abc和一个操作op,如题目描述所示。
        0≤a, b<n

输出
如果存在一组赋值使得m个算式都成立,则输出YES否则输出NO
样例输入 Copy
3 3
0 1 0 AND 
1 2 1 OR
0 2 0 XOR
样例输出 Copy
YES
提示

这个序列包含三个整数,当d[0] = 1, d[1] = 0, d[2] = 1时,三个式子d[0] AND d[1] = 0, d[1] OR d[2] = 1, d[0] XOR d[2] = 0都成立,因此输出YES

来源/分类