这是我考试时写的代码，原封不动搬过来（CSP居然可以下载答卷！）
CSP：6.765s，55.78MB
search前面的部分是字符串解析，把表达式存到vector里，省得后面重复遍历字符串（PS：这题的括号不影响运算优先级）
search遍历所有用户，检查是否符合表达式条件。表达式用一个栈处理就行，最后栈顶元素就是表达式结果。
最后排个序输出即可
#include <cstdio>
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <sstream>
#include <stack>
#include <unordered_map>
#include <algorithm>
using namespace std;
const int N = 2510;
const int M = 510;
unordered_map<int, int> attr[N];
int n, m;
int selected[N];
int sel_cnt;
string expr;
typedef struct ATOM
{
int a, b;
char op;
} atom, exp;
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
int dn, n_attr, attr_n, attr_v;
scanf("%d", &dn);
attr[i][0] = dn;
scanf("%d", &n_attr);
for (int j = 1; j <= n_attr; j++)
{
scanf("%d%d", &attr_n, &attr_v);
attr[i][attr_n] = attr_v;
}
}
scanf("%d", &m);
vector<exp> v;
for (int i = 1; i <= m; i++)
{
cin >> expr;
// atom
if (expr[0] != '&' && expr[0] != '|')
{
for (int i = 0; i < expr.size(); i++)
{
if (expr[i] == ':' || expr[i] == '~')
{
string num1_s = expr.substr(0, i);
string num2_s = expr.substr(i + 1);
int num1_i, num2_i;
stringstream ss;
ss << num1_s;
ss >> num1_i;
ss.clear();
ss << num2_s;
ss >> num2_i;
atom at;
at.a = num1_i;
at.b = num2_i;
at.op = expr[i];
v.push_back(at);
break;
}
}
}
else
{
for (int i = 0; i < expr.size(); i++)
{
if (expr[i] == '&' || expr[i] == '|')
{
exp e;
e.op = expr[i];
v.push_back(e);
}
else if (expr[i] >= '0' && expr[i] <= '9')
{
// atom
int j = i + 1;
int t = i + 1;
while (expr[j] != ')')
{
if (expr[j] == ':' || expr[j] == '~')
t = j;
j++;
}
string num1_s = expr.substr(i, t - i);
string num2_s = expr.substr(t + 1, j - t - 1);
int num1_i, num2_i;
stringstream ss;
ss << num1_s;
ss >> num1_i;
ss.clear();
ss << num2_s;
ss >> num2_i;
atom at;
at.a = num1_i;
at.b = num2_i;
at.op = expr[t];
v.push_back(at);
i = j;
}
}
}
// search
for (int i = 1; i <= n; i ++)
{
bool flag = true;
stack<bool> stk;
for (int j = v.size() - 1; j >= 0; j--)
{
exp ¤t = v[j];
if (current.op == ':')
{
if (attr[i].find(current.a) == attr[i].end() || attr[i][current.a] != current.b)
stk.push(false);
else
stk.push(true);
}
if (current.op == '~')
{
if (attr[i].find(current.a) == attr[i].end() || attr[i][current.a] == current.b)
stk.push(false);
else
stk.push(true);
}
if (current.op == '&')
{
bool num1 = stk.top();
stk.pop();
bool num2 = stk.top();
stk.pop();
stk.push(num1 && num2);
}
if (current.op == '|')
{
bool num1 = stk.top();
stk.pop();
bool num2 = stk.top();
stk.pop();
stk.push(num1 || num2);
}
}
if (stk.top())
{
sel_cnt++;
selected[sel_cnt] = attr[i][0];
}
}
sort(selected + 1, selected + sel_cnt + 1);
for (int i = 1; i <= sel_cnt; i++)
printf("%d ", selected[i]);
printf("\n");
sel_cnt = 0;
vector<exp> empty_v;
v.swap(empty_v);
}
return 0;
}
