• 數(shù)據(jù)結(jié)構(gòu)：結(jié)構(gòu)體數(shù)組、哈希表

• struct User
  {
  	int DN; // 存儲用戶標號 
  	unordered_map<LL, LL> attr // 哈希表存儲屬性和值;
  }user[N];
  

• 原子表達式：處理很簡單，利用string中的find()函數(shù)找到:或~的位置下標，左邊為key，右邊為value，遍歷結(jié)構(gòu)體數(shù)組尋找匹配的用戶。
• 表達式的邏輯組合:&(...)(...)括號內(nèi)也可以是邏輯組合，如&(|(1:2)(3~4))(101:202)。注意不會出現(xiàn)&(...)(...)(...)這種情況。處理思路是對于&(...)(...)提取左右括號內(nèi)的字串，并遞歸求解。
• 更多實現(xiàn)的細節(jié)請見代碼中注釋。

官網(wǎng)運行截圖如下，本來是奔著解決前40分的，沒想到拿到了100分，但由于非常暴力，運行時間10s了。
文章來源地址http://www.zghlxwxcb.cn/news/detail-459429.html

#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);
		
		// 當左右括號數(shù)量相同時，得到子表達式 
		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); // 遞歸調(diào)用 
		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)
*/

到了這里，關(guān)于CCF-CSP 29次 第三題【202303-3 LDAP】的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！