原题链接：
题解：
本来我的想法是对于每个表达式，都遍历一次用户判断是否满足该表达式，但最后超时了，只得了70分。
后来在网上看了不少博客，大多数都是采用bitset的做法，对于每个表达式中的逻辑表达式，不断递归拆分，拆分为2个基础表达式，然后分别求满足这2个基础表达式的用户，然后再回溯分别求交集或者并集即可，这样子就不需要对每个表达式都遍历一遍用户列表。
代码：
70分代码：
#pragma GCC optimize(2, 3, "Ofast", "inline")
#include<bits/stdc++.h>
using namespace std;
int n, m;
map<int, unordered_map<int, int>> v;//用户-(属性-值)
stack<int> dig;
stack<char> op;
bool judge(int a, char b, int c, int fir = 0) {
if (b == ':') return v[fir][a] == c;
else if (b == '~') return v[fir][a] != 0 && v[fir][a] != c;
else if (b == '&') return a & c;
else return a | c;
}
void eval(int dim) {//进行处理
int num2 = dig.top();dig.pop();//第2个操作数
int num1 = dig.top();dig.pop();//第1个操作数
char p = op.top();op.pop();
//计算结果
if (p == ':' || p == '~') dig.push(judge(num1, p, num2, dim));
else dig.push(judge(num1, p, num2));
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n;
for (int i = 1;i <= n;i++) {
int DN, num;cin >> DN >> num;
while (num--) {
int a, b;cin >> a >> b;
v[DN][a] = b;
}
}
cin >> m;
while (m--) {
string s;cin >> s;
for (auto k = v.begin();k != v.end();k++) {
int dim = k->first;
while (!dig.empty()) dig.pop();//清空数字栈和符号栈
while (!op.empty()) op.pop();
int len = s.size();
for (int i = 0;i < len;i++) {
if (isdigit(s[i])) {//数字入栈
int x = 0, j = i;
while (isdigit(s[j]) && j < len) {
x = x * 10 + s[j] - '0';
j++;
}
dig.push(x);
i = j - 1;
}
//else if (s[i] == '(') op.push(s[i]);//左括号入栈
else if (s[i] == ')') {//每匹配到一个右括号直接进行计算后入栈
while (op.top() != '(')
eval(dim);
op.pop();//弹出左括号
}
else op.push(s[i]);//遇见其他符号，入栈即可
}
while (op.size()) eval(dim);
if (dig.top()) cout << dim << " ";
}
cout << endl;
}
}100分代码：（转载自202303 CSP认证 | LDAP (bitset)-CSDN博客）
#include<bits/stdc++.h>
using namespace std;
using PSS = pair<string, string>;
const int N = 3010;
int n, user[N]; //存储id(dn)
unordered_map<string, unordered_set<int> > hash_k; //哪个用户具有特定的key
map<PSS, unordered_set<int>> hash_kv; //哪个用户具有某个特定的key-value对
//这里不能用unordered_map,因为cpp中没有给pair做hash的函数，所以不能用pair作为unordered_map的key。
bitset<N> handle(string expr)
{
bitset<N> ans;//最终的答案,若ans[i], 也即user[i]在返回的结果中
if (expr[0] == '&' || expr[0] == '|') {//如果为逻辑表达式
stack<char> s; s.push('(');
int i = 1;
while (!s.empty()) { //仍然用栈的方法实现括号匹配
i++;
if (expr[i] == '(') s.push('(');
else if (expr[i] == ')') s.pop();
}
//出循环时expr[i] == ),为第一个括号的最右端
string expr1 = expr.substr(2, i - 2);
string expr2 = expr.substr(i + 2, expr.size() - i - 3);
bitset<N> res1 = handle(expr1);
bitset<N> res2 = handle(expr2);
if (expr[0] == '&') ans = res1 & res2;
else ans = res1 | res2;
return ans;
}
else { //如果为基础表达式
int i = 0;
while (expr[i] != ':' && expr[i] != '~') i++;
string key = expr.substr(0, i);
string value = expr.substr(i + 1, expr.size() - i - 1);
bool flag = false; //该操作是否为反断言
if (expr[i] == '~') flag = true;
for (auto x : hash_kv[{key, value}]) {
ans[x] = 1; //x所对的位置应该是1,也即答案中存在该dn
}
if (flag) { //如果为反断言
for (auto x : hash_k[key]) {
ans.flip(x); //flip是取反操作
//对于拥有该key的，目前只有value值匹配的ans位是为一的
//现在进行取反操作,这会导致刚刚所取值1的,也就是value值匹配的,都修改为0
//而其余具有该key的(但value值不相等的), 则会置为1.此时完成了我们的要求
}
}
}
return ans;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin >> n;
for (int i = 1;i <= n;i++) {
int dn; cin >> dn;
user[i] = dn;
int k; cin >> k;
while (k--) {
string key, val; cin >> key >> val;
hash_k[key].insert(i);
hash_kv[{key, val}].insert(i);
}
}
int m; cin >> m;
string line;
while (m--) {
cin >> line;
bitset<N> v = handle(line);
vector<int> ans; //存储答案
for (int i = 1;i <= n;i++) {
if (v[i]) ans.push_back(user[i]);
}
sort(ans.begin(), ans.end()); //排序
for (auto x : ans) cout << x << ' ';
cout << endl;
}
}坑点：
可能会卡常
