计算机软件能力认证考试系统
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <unordered_map>
#include <string>using namespace std;typedef long long LL;const int N = 2510, M = 510;int n, m;struct User
{int DN;unordered_map<LL, LL> attr;
}user[N];// 原子操作
vector<int> match(string str)
{vector<int> res;if (str.find(":") != -1){int loc = str.find(":");auto key = str.substr(0, loc);auto value = str.substr(loc + 1, str.size() - loc - 1);// str to int int k = stoi(key);int v = stoi(value);for (int i = 0; i < n; i ++ ){if (user[i].attr.count(k))if (user[i].attr[k] == v)res.push_back(user[i].DN);}sort(res.begin(), res.end());}else if (str.find('~') != -1){int loc = str.find('~');auto key = str.substr(0, loc);auto value = str.substr(loc + 1, str.size() - loc - 1);// str to int int k = stoi(key);int v = stoi(value);for (int i = 0; i < n; i ++ ){if (user[i].attr.count(k))if (user[i].attr[k] != v)res.push_back(user[i].DN);}sort(res.begin(), res.end());}return res;
}vector<int> match2(string str) // &(|(1:2)(3~4))(101:202)
{vector<int> res;// 匹配 1:2 if (str[0] > '0' && str[0] <= '9') return match(str); // 匹配 &(...)(...) else{char c = str[0];str.erase(0, 1);// 当左右括号数量相同时，得到子表达式 int len = str.size();string s;int loc;for (int i = 1; i <= len; i ++ ){s = str.substr(0, i);if (count(s.begin(), s.end(), '(') == count(s.begin(), s.end(), ')')){loc = i;break;}}string sub_l = str.substr(1, loc - 2); // 左边括号中字串 string sub_r = str.substr(loc + 1, str.size() - loc - 2); // 右边括号中字串 vector<int> res_l = match2(sub_l); // 递归调用 vector<int> res_r = match2(sub_r);if (c == '&'){ vector <int> v_intersection;// 取交集 set_intersection(res_l.begin(), res_l.end(),res_r.begin(), res_r.end(),back_inserter(v_intersection)); return v_intersection;}else if (c == '|'){vector <int> v_union;// 取并集 set_union(res_l.begin(), res_l.end(),res_r.begin(), res_r.end(),back_inserter(v_union)); return v_union;}}
}int main()
{scanf("%d", &n);for (int i = 0; i < n; i ++ ){int DN, cnt;scanf("%d%d", &DN, &cnt);user[i].DN = DN;while (cnt -- ){LL a, v;scanf("%lld%lld", &a, &v);user[i].attr[a] = v;}}scanf("%d", &m);while (m -- ){string str;cin >> str;vector<int> res;res = match2(str);sort(res.begin(), res.end());if (res.size() == 0) cout << endl;else{for (auto i: res) cout << i << " "; cout << endl;}}return 0;
}/*
2
1 2 1 2 2 3
2 2 2 3 3 1
5
1:2
3~1
&(1:2)(2:3)
|(1:2)(3:1)
&(|(1:2)(3~4))(101:202)
*/
