Codeforces779E-E. Bitwise Formula 【模拟】

对于 “？”的每一位，可以单独拆开来看。
所以对于”？”每一位枚举0,还是1，统计由？导出的其余变量，当前取0多还是取1多。取1个数多，最大。取0个数多，最小。
分析样例1
a := 101
b := 011
c := ? XOR b
预处理一下那些量跟？有关
  1 #include <iostream>
  2 #include <cstring>
  3 #include <string>
  4 #include <vector>
  5 #include <cstdio>
  6 #include <map>
  7 #include <cmath>
  8 #include <algorithm>
  9 using namespace std;
 10 map<string,int> id;
 11 map<string,int> opp;
 12 struct node
 13 {
 14     int id1,id2;
 15     int op;
 16     int in;
 17     int tt;
 18     string v;
 19 }k[6000];
 20 vector<int>to[6000];
 21 vector<int>ids;
 22 int ans1[2000];
 23 int ans2[2000];
 24 void topp(int i)
 25 {
 26         if (i!=0) ids.push_back(i);
 27         for (int j = 0;j<to[i].size();j++)
 28         {
 29             k[to[i][j]].in--;
 30             if (k[to[i][j]].in==0) topp(to[i][j]);
 31         }
 32 }
 33 int main()
 34 {
 35     int n,m;
 36     ios::sync_with_stdio(false);
 37     cin >> n >> m;
 38     string s1,ss,s2,so,s3;
 39     id["?"] = 0;
 40     k[0].in = 1;
 41 
 42     opp["AND"] = 1;
 43     opp["OR"] = 2;
 44     opp["XOP"] = 3;
 45     string sp;
 46     for (int i = 1; i<=m;i++)
 47     {
 48         sp+=" ";
 49     }
 50     k[0].v=sp;
 51     for (int i = 1; i<=n; i++)
 52     {
 53         cin >> s1 >> ss >> s2;
 54         id[s1] = i;
 55         k[i].in = 0;
 56         if (s2[0]!='0'&&s2[0]!='1')
 57         {
 58            cin >> so >> s3;
 59            k[i].tt = 0;
 60            k[i].v = sp;
 61            k[i].op = opp[so];
 62            k[i].id1 = id[s2];
 63            k[i].id2 = id[s3];
 64            if (k[id[s2]].in != 0)
 65            {
 66                k[i].in++;
 67                to[id[s2]].push_back(i);
 68            }
 69            if (k[id[s3]].in != 0)
 70            {
 71                k[i].in++;
 72                to[id[s3]].push_back(i);
 73            }
 74         }
 75         else
 76         {
 77             k[i].v = s2;
 78             k[i].tt = 1;
 79         }
 80     }
 81     for (int i = 1 ; i <= n ; i++ )
 82     {
 83         if (k[i].in==0)
 84             ids.push_back(i);
 85     }
 86     topp(0);
 87     int ans[2];
 88     int tans;
 89     for (int i = 0; i<m; i++)
 90     {
 91         for (int kk = 0; kk<=1; kk++)
 92         {
 93             k[0].v[i] = '0'+kk;
 94             ans[kk] = 0;
 95             for (int j = 0; j<ids.size(); j++)
 96             {
 97                if (k[ids[j]].tt==1)
 98                {
 99                    ans[kk]+=(k[ids[j]].v[i]-'0');
100                    continue;
101                }
102                int v1 = k[k[ids[j]].id1].v[i]-'0';
103                int v2 = k[k[ids[j]].id2].v[i]-'0';
104                if (k[ids[j]].op==1)
105                {
106                     tans = v1 & v2;
107                }
108                else if (k[ids[j]].op==2)
109                {
110                    tans = v1|v2;
111                }
112                else
113                {
114                    tans = v1^v2;
115                }
116                ans[kk]+=tans;
117                k[ids[j]].v[i] = tans+'0';
118             }
119         }
120         if (ans[0]>ans[1])
121         {
122             ans1[i] = 1;ans2[i] = 0;
123         }
124         else if (ans[1]>ans[0])
125         {
126             ans1[i] = 0; ans2[i] = 1;
127         }
128         else ans1[i] = ans2[i] = 0;
129     }
130     for (int i = 0 ;i <m; i++)
131         cout <<ans1[i];
132     cout <<endl;
133     for (int i = 0 ;i <m; i++)
134         cout <<ans2[i];
135     cout <<endl;
136 }
View Code