#601. 信号传输

信号传输

附加文件

【题目描述】

有一个信号发射装置,该装置上有 L+1L+1 个按钮,编号为 00 ~ LL。当你按下编号为 jj 的按钮时,该发射装置便会发出一个强度为 jj 的信号,该信号要依次经过 nn 个节点进行传输,最后到达信号接收装置。

每经过一个节点,信号强度可能会发生变化。具体地,对于第 ii 个节点,如果到达该节点前的信号强度为 xx,则经过该节点后,信号强度将变为 xx OiO_i KiK_i,其中 OiO_i 为运算符,包含一个字符,其可能是 &、 |、 ^ 中的一种,分别表示 按位与、按位或、按位异或 运算,KiK_i 为一个整数。

那么,按下发射装置上的哪一个按钮,可以使得接收装置接收到的信号强度最大?你只需要输出最终接收到的信号强度的最大值。

假设信号强度只在经过节点时发生运算产生变化,其他传输过程中无损失。

【输入格式】

第一行:两个整数 n,Ln, L

接下来 nn 行,每行包括一个字符 OiO_i 和一个整数 KiK_i。

【输出格式】

一个整数,表示可以得到的最大的信号强度。

【输入样例】

3 2
& 5
| 6
^ 7

【输出样例】

1

【样例解释】

样例中,信号发射装置共有 3 个按钮,编号为 0 ~ 2。

若按 0 号按钮,即信号初始强度为 00,其强度变化为:

  • 00 & 55 = 00;
  • 00 | 66 = 66;
  • 66 ^ 77 = 11。

若按 1 号按钮,即信号初始强度为 11,其强度变化为:

  • 11 & 55 = 55;
  • 55 | 66 = 77;
  • 77 ^ 77 = 00。

若按 2 号按钮,即信号初始强度为 22,其强度变化为:

  • 22 & 55 = 00;
  • 00 | 66 = 66;
  • 66 ^ 77 = 11。

综上,按 00 或 22 号按钮时,最终得到的信号强度最大,值为 11。

【数据范围】

测试点编号 n≤n≤ L≤L≤ 性质
11 100100 00 无
22 10001000
33
44 10510^5 10510^5 AA
55 BB
66 无
77 10910^9 BB
88 无
99
1010
  • 性质 AA:至少存在一个节点 p 满足 OpO_p 为 & , Kp=0K_p = 0;
  • 性质 BB:所有节点的运算符均相同。

100% 的数据:2≤n≤1052 ≤ n ≤ 10^5,0≤L≤1090 ≤ L ≤ 10^9,0≤Ki≤1090 ≤ K_i ≤ 10^9。数据保证 OiO_i 为 &、 |、 ^ 中的一种。