题目链接：

 

题意：有n个变量都可以用m位二进制数表示，这n个数的value将以两种格式中的一种给出

1.变量名, 空格, ":=", 空格, 一个正好m位的二进制数

eg(m = 3):   a := 101

2.变量名, 空格, ":=", 空格, 第一个变量, 空格, 位运算符(AND，OR，XOR), 空格, 第二个变量

每一个变量都是前面被定义过的变量或者用 '?'表示

eg:  aaa := a AND  aa

       bbb := b XOR ?

你需要确定'?'这个m位的二进制数，并输出使n个数总和最小和最大时的'?'

maxn = 5000

maxm = 1000

 

解法:一个稍复杂的二进制模拟题

'?'这个二进制数的m位每一位都有2种可能

所以与'?'有关的所有变量的二进制表示中每一位最多都有2种可能

注意到第二种读入中可能某个变量的值与'?'有关，后面这个变量又会参与运算

所以我们当计算第 i 个数时，需要保证前i - 1个数都已经被计算出来

所以解题思路就是直接计算出所有变量

 

然而如果读入一个算式立即用if各种判断的话，写出来会很丑很长

我们需要考虑简化代码 (参考了rank2的代码

注意到我们如果循环读入一个变量立刻计算其value需要O(nm)的空间

转化为全部读入后再一位一位的处理只需要O(n)的空间

我们可以v1和v2表示参与运算的变量的标号('?'被表示为第n+1个变量)

并用op来记录是哪种位运算符，最后统一处理就方便了很多

(string+map大法好

 

1 #include 
      
        2  3 using namespace std; 4  5 map 
       
         p; 6  7 int n, m, c[2]; 8  9 int s[2][5010];10 11 struct node {12     int op;13     int v1, v2;14     string s;15 }a[5010];16 17 int main() {18     string s1, s2, s3, s4, s5, ansmin = "", ansmax = "";19     20     scanf("%d %d", &n, &m);21     for(int i = 1;i <= n;i ++) {22         cin >> s1 >> s2 >> a[i].s, p[s1] = i;23         if(a[i].s[0] == '0' || a[i].s[0] == '1') continue;24         if(a[i].s[0] == '?') a[i].v1 = n + 1;25         else a[i].v1 = p[a[i].s];26         27         cin >> s4 >> s5;28         switch(s4[0]) {29             case 'A':a[i].op = 1;break;30             case 'O':a[i].op = 2;break;31             case 'X':a[i].op = 3;break;32         }33         if(s5[0] == '?') a[i].v2 = n + 1;34         else a[i].v2 = p[s5];35     }36     37     s[0][n + 1] = 0, s[1][n + 1] = 1;38     for(int i = 0;i < m;i ++) {39         c[0] = 0, c[1] = 0;40         for(int k = 0;k < 2;k ++) {41             for(int j = 1;j <= n;j ++) {42                 switch(a[j].op) {43                     case 0:s[k][j] = a[j].s[i] - '0';break;44                     case 1:s[k][j] = s[k][a[j].v1] & s[k][a[j].v2];break;45                     case 2:s[k][j] = s[k][a[j].v1] | s[k][a[j].v2];break;46                     case 3:s[k][j] = s[k][a[j].v1] ^ s[k][a[j].v2];break;47                 }48                 if(s[k][j]) c[k] ++;49             }50         }51         ansmin += c[0] <= c[1] ? '0' : '1';52         ansmax += c[0] >= c[1] ? '0' : '1';53     }54     55     cout << ansmin << '\n' << ansmax; 56     return 0;57 }