Codeforces Problem 778B Bitwise Formula

题目链接：http://codeforces.com/contest/779/problem/E

题意：有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大法好

 #include <bits/stdc++.h>

 using namespace std;

 map <string, int> p;

 int n, m, c[];

 int s[][];

 struct node {

     int op;

     int v1, v2;

     string s;

 }a[];

 int main() {

     string s1, s2, s3, s4, s5, ansmin = "", ansmax = "";

     scanf("%d %d", &n, &m);

     for(int i = ;i <= n;i ++) {

         cin >> s1 >> s2 >> a[i].s, p[s1] = i;

         if(a[i].s[] == '' || a[i].s[] == '') continue;

         if(a[i].s[] == '?') a[i].v1 = n + ;

         else a[i].v1 = p[a[i].s];

         cin >> s4 >> s5;

         switch(s4[]) {

             case 'A':a[i].op = ;break;

             case 'O':a[i].op = ;break;

             case 'X':a[i].op = ;break;

         }

         if(s5[] == '?') a[i].v2 = n + ;

         else a[i].v2 = p[s5];

     }

     s[][n + ] = , s[][n + ] = ;

     for(int i = ;i < m;i ++) {

         c[] = , c[] = ;

         for(int k = ;k < ;k ++) {

             for(int j = ;j <= n;j ++) {

                 switch(a[j].op) {

                     case :s[k][j] = a[j].s[i] - '';break;

                     case :s[k][j] = s[k][a[j].v1] & s[k][a[j].v2];break;

                     case :s[k][j] = s[k][a[j].v1] | s[k][a[j].v2];break;

                     case :s[k][j] = s[k][a[j].v1] ^ s[k][a[j].v2];break;

                 }

                 if(s[k][j]) c[k] ++;

             }

         }

         ansmin += c[] <= c[] ? '' : '';

         ansmax += c[] >= c[] ? '' : '';

     }

     cout << ansmin << '\n' << ansmax;

     return ;

 }

巴特西

Codeforces Problem 778B Bitwise Formula

最新文章

热门文章