按位考虑，每个变量最终的赋值要么是必为0，要么必为1，要么和所选定的数相同，记为2，要么和所选定的数相反，记为3，一共就这四种情况。
可以预处理出来一个真值表，然后从前往后推导出每个变量的赋值。
然后从高位到低位考虑，如果某一位，对于所有变量而言，2的数量大于等于3的数量，就把所选定的数的该位记为0，否则记为1，就能满足和最小。反之就能满足和最大。
#include<cstdio>
#include<string>
#include<iostream>
#include<map>
using namespace std;
map<string,int>ma;
int n,m;
string a[5010],x[5010],op[5010],y[5010];
string b[5010];
int main()
{
// freopen("e.in","r",stdin);
string t;
scanf("%d%d",&n,&m);
bool flag=0;
for(int i=1;i<=n;++i)
{
if(!flag)
cin>>a[i];
ma[a[i]]=i;
flag=0;
cin>>t;
cin>>x[i]>>op[i];
if(!(op[i]=="AND" || op[i]=="OR" || op[i]=="XOR"))
{
a[i+1]=op[i];
op[i]="";
flag=1;
}
else
cin>>y[i];
}
for(int i=1;i<=n;++i)
if(op[i]=="")
b[i]=x[i];
else if(op[i]=="AND")
{
if(x[i]=="?" && y[i]=="?")
{
for(int j=0;j<m;++j)
b[i]+="2";
}
else if(x[i]=="?")
{
string ts=b[ma[y[i]]];
for(int j=0;j<m;++j)
if(ts[j]=='0') b[i]+="0";
else if(ts[j]=='1') b[i]+="2";
else if(ts[j]=='2') b[i]+="2";
else b[i]+="0";
}
else if(y[i]=="?")
{
string ts=b[ma[x[i]]];
for(int j=0;j<m;++j)
if(ts[j]=='0') b[i]+="0";
else if(ts[j]=='1') b[i]+="2";
else if(ts[j]=='2') b[i]+="2";
else b[i]+="0";
}
else
{
string ts=b[ma[x[i]]],ts2=b[ma[y[i]]];
for(int j=0;j<m;++j)
if(ts[j]<='1' && ts2[j]<='1')
b[i]+=(((ts[j]-'0')&(ts2[j]-'0'))+'0');
else if(ts[j]=='0') b[i]+="0";
else if(ts[j]=='1')
{
if(ts2[j]=='2') b[i]+="2";
else b[i]+="3";
}
else if(ts[j]=='2')
{
if(ts2[j]=='0') b[i]+="0";
else if(ts2[j]=='1') b[i]+="2";
else if(ts2[j]=='2') b[i]+="2";
else b[i]+="0";
}
else
{
if(ts2[j]=='0') b[i]+="0";
else if(ts2[j]=='1') b[i]+="3";
else if(ts2[j]=='2') b[i]+="0";
else b[i]+="3";
}
}
}
else if(op[i]=="OR")
{
if(x[i]=="?" && y[i]=="?")
{
for(int j=0;j<m;++j)
b[i]+="2";
}
else if(x[i]=="?")
{
string ts=b[ma[y[i]]];
for(int j=0;j<m;++j)
if(ts[j]=='0') b[i]+="2";
else if(ts[j]=='1') b[i]+="1";
else if(ts[j]=='2') b[i]+="2";
else b[i]+="1";
}
else if(y[i]=="?")
{
string ts=b[ma[x[i]]];
for(int j=0;j<m;++j)
if(ts[j]=='0') b[i]+="2";
else if(ts[j]=='1') b[i]+="1";
else if(ts[j]=='2') b[i]+="2";
else b[i]+="1";
}
else
{
string ts=b[ma[x[i]]],ts2=b[ma[y[i]]];
for(int j=0;j<m;++j)
if(ts[j]<='1' && ts2[j]<='1')
b[i]+=(((ts[j]-'0')|(ts2[j]-'0'))+'0');
else if(ts[j]=='1') b[i]+="1";
else if(ts[j]=='0')
{
if(ts2[j]=='2') b[i]+="2";
else b[i]+="3";
}
else if(ts[j]=='2')
{
if(ts2[j]=='0') b[i]+="2";
else if(ts2[j]=='1') b[i]+="1";
else if(ts2[j]=='2') b[i]+="2";
else b[i]+="1";
}
else
{
if(ts2[j]=='0') b[i]+="3";
else if(ts2[j]=='1') b[i]+="1";
else if(ts2[j]=='2') b[i]+="1";
else b[i]+="3";
}
}
}
else
{
if(x[i]=="?" && y[i]=="?")
{
for(int j=0;j<m;++j)
b[i]+="0";
}
else if(x[i]=="?")
{
string ts=b[ma[y[i]]];
for(int j=0;j<m;++j)
if(ts[j]=='0') b[i]+="2";
else if(ts[j]=='1') b[i]+="3";
else if(ts[j]=='2') b[i]+="0";
else b[i]+="1";
}
else if(y[i]=="?")
{
string ts=b[ma[x[i]]];
for(int j=0;j<m;++j)
if(ts[j]=='0') b[i]+="2";
else if(ts[j]=='1') b[i]+="3";
else if(ts[j]=='2') b[i]+="0";
else b[i]+="1";
}
else
{
string ts=b[ma[x[i]]],ts2=b[ma[y[i]]];
for(int j=0;j<m;++j)
if(ts[j]<='1' && ts2[j]<='1')
b[i]+=(((ts[j]-'0')^(ts2[j]-'0'))+'0');
else if(ts[j]=='0')
{
if(ts2[j]=='2') b[i]+="2";
else b[i]+="3";
}
else if(ts[j]=='1')
{
if(ts2[j]=='2') b[i]+="3";
else b[i]+="2";
}
else if(ts[j]=='2')
{
if(ts2[j]=='0') b[i]+="2";
else if(ts2[j]=='1') b[i]+="3";
else if(ts2[j]=='2') b[i]+="0";
else b[i]+="1";
}
else
{
if(ts2[j]=='0') b[i]+="3";
else if(ts2[j]=='1') b[i]+="2";
else if(ts2[j]=='2') b[i]+="1";
else b[i]+="0";
}
}
}
for(int i=0;i<m;++i)
{
int A=0,B=0;
for(int j=1;j<=n;++j)
if(b[j][i]=='2')
++A;
else if(b[j][i]=='3')
++B;
if(A>=B)
putchar('0');
else
putchar('1');
}
puts("");
for(int i=0;i<m;++i)
{
int A=0,B=0;
for(int j=1;j<=n;++j)
if(b[j][i]=='3')
++A;
else if(b[j][i]=='2')
++B;
if(A>=B)
putchar('0');
else
putchar('1');
}
puts("");
return 0;
}