题目传送门

解题思路

最后要求输出符合条件的用户 DN 的集合, (作为一名STL战士) ,可以考虑维护以属性名和属性值为索引, 对应值为符合条件的用户的set 的一个map

属性名 -> 属性值 -> {用户1,用户2…}

unordered_map<int,unordered_map<int,set<int>>> attrName_attrVal_users;
1

操作分为原子操作和逻辑操作, 只需要判断字符串的首字符即可区分两种操作

原子操作

原子操作分为匹配和剔除, 匹配满足条件(属性名为相应属性值)的用户集合可以直接从刚才的map里找到, 作为答案, 而剔除时需要注意, 只有当用户该属性有值且不为指定值时才能作为答案, 所以为了便于判断用户指定属性是否有值(不为N/A), 可以维护一个以属性名为索引, 值为相应用户集合的map

属性名 -> {用户1,用户2…}

unordered_map<int, set<int>> attrName_users;
1

逻辑组合

逻辑操作主要是符合条件的用户集合的交和并, 以及逻辑操作的嵌套, 这里用两个set ans1和ans2 来暂存符合条件的用户

交: 将两个集合插入另一个集合即可

ans.insert(ans1.begin(), ans1.end());
ans.insert(ans2.begin(), ans2.end());
1
2

并: 枚举一个集合, 判断每个元素在不在另一个集合中即可

for(auto it : ans1) {
if(ans2.count(it)) {
ans.insert(it);
}
}
1
2
3
4
5

嵌套: 括号匹配

对于一个逻辑操作表达式的前后两个部分, 我们发现他们无论怎么嵌套, 每个部分的括号一定是匹配的, 可以维护一个括号栈, 遍历字符串直到括号栈空, 此时字符串的位置 (本文为p) 为前后两个部分的分界位置

然后递归调用即可

完整代码

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

int n;
unordered_map<int,unordered_map<int,set<int>>> attrName_attrVal_users; // 存储 属性名-属性值-用户DN 
unordered_map<int, set<int>> attrName_users; // 存储该属性不为NA的用户DN set 

int getNum(string exp) {// 字符串转整形 
int ans = 0;
for(int i = 0; i < exp.size(); i++) {
ans *= 10;
ans += (exp[i] - '0');
}
return ans;
}

set<int> AtomOP(string exp) {// 原子操作 
int p = 0;set<int> ans;
while(exp[p] != ':' && exp[p] != '~') p++;
int a = getNum(exp.substr(0,p));
int b = getNum(exp.substr(p+1, exp.size()));
if(exp[p] == ':') {
ans.insert(attrName_attrVal_users[a][b].begin(), attrName_attrVal_users[a][b].end());
}
else {
ans.insert(attrName_users[a].begin(), attrName_users[a].end());
set<int> dead;
for(auto it : attrName_attrVal_users[a][b]) {
if(ans.count(it)) {
dead.insert(it);
}
}
for(auto it : dead) ans.erase(it);
}
return ans;
}

set<int> ExprOP(string exp) { 
set<int> ans;
if(exp[0] >= '0' && exp[0] <= '9') {
ans = AtomOP(exp);
}
else if(exp[0] == '&') {
int p = 1;set<int> ans1;set<int> ans2;
stack<char> br;br.push('(');
while(!br.empty()) {
p++;
if(exp[p] == '(') {
br.push('(');
}
else if(exp[p] == ')') {
br.pop();
}
}
ans1 = ExprOP(exp.substr(2, p-2));

int q = p+2;br.push('(');
while(!br.empty()) {
q++;
if(exp[q] == '(') {
br.push('(');
}
else if(exp[q] == ')') {
br.pop();
}
}
ans2 = ExprOP(exp.substr(p+2, q-p-2));
for(auto it : ans1) {
if(ans2.count(it)) {
ans.insert(it);
}
}
}
else if(exp[0] == '|') {
int p = 1;set<int> ans1;set<int> ans2;
stack<char> br;br.push('(');
while(!br.empty()) {
p++;
if(exp[p] == '(') {
br.push('(');
}
else if(exp[p] == ')') {
br.pop();
}
}
ans1 = ExprOP(exp.substr(2, p-2));
int q = p+2;br.push('(');
while(!br.empty()) {
q++;
if(exp[q] == '(') {
br.push('(');
}
else if(exp[q] == ')') {
br.pop();
}
}
ans2 = ExprOP(exp.substr(p+2, q-p-2));

ans.insert(ans1.begin(), ans1.end());
ans.insert(ans2.begin(), ans2.end());
}
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;
int num;cin >> num;
users.insert(dn);
for(int j = 1; j <= num; j++) {
int attrName;cin >> attrName;
int attrVal; cin >> attrVal;
attrName_attrVal_users[attrName][attrVal].insert(dn);
attrName_users[attrName].insert(dn);
}
}
int m;
cin >> m;
for(int i = 1; i <= m; i++) {
string exp;cin >> exp;
set<int> ans;
ans = ExprOP(exp);
for(auto it : ans) {
cout << it << " ";
}
cout << endl;
}
return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132