博客

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

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

• 原子表达式：处理很简单，利用
  
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)
*/