CCF-CSP 29次 第三题【202303-3 LDAP】_csp202303-3

• 数据结构：结构体数组、哈希表

• struct User
  {
  	int DN; // 存储用户标号 
  	unordered_map<LL, LL> attr // 哈希表存储属性和值;
  }user[N];
  1
  2
  3
  4
  5

• 原子表达式：处理很简单，利用string中的find()函数找到:或~的位置下标，左边为key，右边为value，遍历结构体数组寻找匹配的用户。
• 表达式的逻辑组合:&(...)(...)括号内也可以是逻辑组合，如&(|(1:2)(3~4))(101:202)。注意不会出现&(...)(...)(...)这种情况。处理思路是对于&(...)(...)提取左右括号内的字串，并递归求解。
• 更多实现的细节请见代码中注释。

官网运行截图如下，本来是奔着解决前40分的，没想到拿到了100分，但由于非常暴力，运行时间10s了。

#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)
*/
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
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175