题目链接

http://codeforces.com/contest/779/problem/E

解题思路

感觉思路比较简单，但是模拟的过程是真的难啊
大致思路：
输入统计，为数，或者为计算式，若为计算式还需要记录左右操作数为问号还是变量。
我们优先遍历每一个二进制位，再看每个变量本位为1的个数，统计问号在本位为0时所有变量中本位为1的个数，统计问号为1时所有变量中本位为1的个数，根据最小值或最大值进行字符串拼接。
我觉得还是得看代码

AC代码

#include<bits/stdc++.h>
using namespace std;

const int N=5e3+10;

struct node
{
    int op,l,r;//当第i个变量为表达式时，l表示左操作数变量对应的编号，r表示右操作数变量对应的编号，op表示操作数之间的运算符，op=0表示，此变量为数而非表达式，op=1表示&，op=2表示|，op=3表示^
    string s;//当第i个变量为数，而非表达式的时候，s表示二进制串（以字符串形式存储）
}a[N];

map<string,int> idx;//idx[str]=i表示变量str的编号为i

string var,tmp,op,s,mn="",mx="";

int t[2][N],cnt[2],n,m;//后面讲解

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>var>>tmp>>a[i].s;
        idx[var]=i;
        if(isdigit(a[i].s[0])) continue;//若为数值，直接continue
        cin>>op>>s;

        if(op[0]=='A') a[i].op=1;
        else if(op[0]=='O') a[i].op=2;
        else if(op[0]=='X') a[i].op=3;

        a[i].l=(a[i].s=="?"?n+1:idx[a[i].s]);//如果操作数为问号，操作数为对应的编号为n+1，否则通过idx找到其对应编号
        a[i].r=(s=="?"?n+1:idx[s]);//同上

//        cout<<var<<' '<<tmp<<' '<<sl<<' '<<op<<' '<<sr<<endl;
    }
    //下面比较难理解了
    t[0][n+1]=0,t[1][n+1]=1;//t[0][n+1]表示第n+1个变量，即问号，为0；t[1][n+1]表示第n+1个变量，即问号，为1//临时
    for(int i=0;i<m;i++)//先遍历每一个二进制位
    {
        cnt[0]=0,cnt[1]=0;//统计问号的第i个二进制位为0/1时，所有变量的第i个二进制位为1的个数
        for(int k=0;k<=1;k++)//问号的第i个二进制位为0或1
        {
            for(int j=1;j<=n;j++)//遍历每一个变量
            {
                if(a[j].op==0) t[k][j]=a[j].s[i]-'0';//若为数值，找到数值对应的第i个二进制位。
                else if(a[j].op==1) t[k][j]=t[k][a[j].l] & t[k][a[j].r];
                else if(a[j].op==2) t[k][j]=t[k][a[j].l] | t[k][a[j].r];
                else if(a[j].op==3) t[k][j]=t[k][a[j].l] ^ t[k][a[j].r];

                if(t[k][j]) cnt[k]++;//当前二进制位为1，才进行统计
            }
        }
        mn+=cnt[1]>=cnt[0]?'0':'1';//稍微注意等于的情况，自己写一下就行
        mx+=cnt[1]> cnt[0]?'1':'0';//同上
    }
    cout<<mn<<endl<<mx<<endl;
}