LDAP
刷新
时间限制： 10.0 秒
空间限制： 512 MiB
下载题目目录（样例文件）
题目背景
西西艾弗岛运营公司是一家负责维护和运营岛上基础设施的大型企业，拥有数千名员工。公司内有很多 IT 系统。 为了能够实现这些 IT 系统的统一认证登录，公司 IT 部门决定引入一套 LDAP 系统来管理公司内的用户信息。 轻型目录访问协议（Lightweight Directory Access Protocol，LDAP）是一种用于访问和维护目录服务的应用层协议， 基于它的数据库可以用树形结构来组织和存储数据。每一笔数据，都包含了一个唯一的标识符（DN，Distinguished Name）， 以及一系列的属性（Attribute）。
不同的 IT 系统，允许访问的用户是不相同的。每个信息系统都有一个表达式，用来描述允许访问的用户。 这个表达式可以按照某一个属性的值作为条件来匹配用户，也可以用多个条件的逻辑组合来匹配用户。 小 C 被安排来实现这样一个算法，给定一个 IT 系统的匹配表达式，找到所有与之匹配的用户的 DN。
题目描述
为了简化该问题，我们约定，每个用户的 DN 是一个正整数，且不会重复。有若干种用户的属性，用正整数编号。 每个用户可以具有这些属性中的若干个，且每个属性只能有一个值。每个属性的值也是一个正整数。例如，假定有两个用户：用户 1 和用户 2， 他们的 DN 分别是 1 和 2。一共有 3 种属性。用户 1 具有属性 1 和属性 2，且属性 1 的值为 2，属性 2 的值为 3；但不具有属性 3。 用户 2 具有属性 2 和属性 3，且属性 2 的值为 3，属性 3 的值为 1；但不具有属性 1。如下表所示：
| DN | 属性 1 | 属性 2 | 属性 3 |
|---|---|---|---|
| 1 | 2 | 3 | N/A |
| 2 | N/A | 3 | 1 |
一个匹配表达式可以是一个属性的值，也可以是多个匹配表达式的逻辑组合。只匹配一个属性的值的表达式称为原子表达式， 原子表达式的形式为 <属性编号><操作符><属性值>。其中操作符有两种：断言与反断言。断言操作符为 :，表示匹配具有该属性且值与之相等的用户； 反断言操作符为 ~，表示匹配具有该属性且值与之不等的用户。例如，表达式 1:2 可以与上述用户 1 相匹配，但不能与用户 2 相匹配；而表达式 3~1 则不能与任何一个用户相匹配。
表达式可以进行逻辑组合，其语法是：<操作符>(表达式 1)(表达式 2)。其中操作符有两种：与（&）和或（|）。如果操作符为与， 则当且仅当两个表达式都与某一用户相匹配时，该表达式与该用户相匹配；如果操作符为或，则当且仅当两个表达式中至少有一个与某一用户相匹配时， 该表达式与该用户相匹配。例如，表达式 &(1:2)(2:3) 可以与用户 1 相匹配，但不能与用户 2 相匹配；而表达式 |(1:2)(3:1) 则可以与两个用户都相匹配。
形式化地，上述语法用 BNF 范式表示如下：
NON_ZERO_DIGIT = "1" / "2" / "3" / "4" / "5" / "6" / "7" / "8" / "9"
DIGIT = "0" / NON_ZERO_DIGIT
NUMBER = NON_ZERO_DIGIT / (NON_ZERO_DIGIT DIGIT*)
ATTRIBUTE = NUMBER
VALUE = NUMBER
OPERATOR = ":" / "~"
BASE_EXPR = ATTRIBUTE OPERATOR VALUE
LOGIC = "&" / "|"
EXPR = BASE_EXPR / (LOGIC "(" EXPR ")" "(" EXPR ")")EASY_EXPR = BASE_EXPR / (LOGIC "(" BASE_EXPR ")" "(" BASE_EXPR ")")
输入格式
从标准输入读入数据。
输入的第一行包含一个正整数 nn，表示用户的数目。
接下来 nn 行，每行包含空格分隔的若干个正整数，第一个正整数表示该用户的 DN，第二个正整数表示该用户具有的属性个数，此后的每两个正整数表示该用户具有的一个属性及其值。这些属性按照属性编号从小到大的顺序给出。
接下来一行包含一个正整数 mm，表示匹配表达式的数目。
接下来 mm 行，每行包含一个匹配表达式。
输出格式
输出到标准输出。
输出 mm 行，每行包含零个或多个正整数，用空格分隔，表示与对应的匹配表达式相匹配的用户的 DN，由小到大排序。
样例1输入
2
1 2 1 2 2 3
2 2 2 3 3 1
4
1:2
3~1
&(1:2)(2:3)
|(1:2)(3:1)
样例1输出
11
1 2
样例1解释
本组输入是题目描述中的例子。
子任务
对于 20% 的输入，有 1≤n≤1001≤n≤100，1≤m≤101≤m≤10，每个用户的属性个数不超过 10，全部属性编号不超过 100，且表达式是原子表达式，即符合 BNF 语法 BASE_EXPR。
对于 40% 的输入，有 1≤m≤1001≤m≤100，每个用户的属性个数不超过 10，全部属性编号不超过 100，且表达式中至多含有两个原子表达式的逻辑组合，即符合 BNF 语法 EASY_EXPR。
对于 70% 的输入，有全部属性编号不超过 500。
对于全部输入，有 1≤n≤25001≤n≤2500，1≤m≤5001≤m≤500，每个用户的属性个数不超过 500，全部属性编号、属性值和 DN 均不超过 109109，每个表达式语句都符合题设语法，且语句字符长度不超过 2000。
数据很多的一道题
数据一多，用的数据结构就非常关键
这里我们用到一个数据结构叫做bitset<N>，N为常数
bitset 是 C++ 标准库中的一个模板类，用于高效地处理固定大小的二进制位集合（bit array） 。它非常适合用来表示状态、标志、集合等场景
简单理解 bitset 就是一个长度固定的bool数组，有很多函数可以对这些二进制位进行操作
bitset<N>dp[N*2] 意思是一个长度为N，元素数量为N*2的一个bitset数组
我们用一个bitset的每个位都表示1个用户在当前规则是否匹配，匹配为1，不匹配为0
map<int,vector<int>>mp2 保存具有该属性的用户编号
map<pii,vector<int>>mp1保存具有该属性且值也对的的用户编号
pii是一个宏定义，代表pair<int,int>单个键值对
还有就是分解长串表达式，用类似栈的思想，op[N]存放操作符，num[N]存放操作数
每两个操作数就搭配一个操作符进行匹配，得到一个基本表达式，根据得到的基本表达式对bitset进行设置，如果操作符是&或者 | 的话就取dp[d]和dp[d-1]进行 与 或者 或 的操作得到二者运算的结果
#include <bits/stdc++.h>
using namespace std;
#define N 2510 // 最大对象数量（用户/实体）上限
#define pii pair<int, int> // 表示属性编号与值的组合// dp[i]: 存储表达式解析过程中每个子表达式的匹配结果（哪些对象满足）
bitset<N> dp[N * 2];// DN[i]: 第 i 个对象的真实 ID（可能不是连续的）
int DN[N];// num[c]: 当前操作符栈中某个操作符对应的操作数个数
int op[N], num[N];// mp1[{x,y}]: 所有属性 x 的值等于 y 的对象列表
map<pii, vector<int>> mp1;// mp2[x]: 所有具有属性 x 的对象列表
map<int, vector<int>> mp2;/*** 根据一个原子逻辑表达式生成 bitset* @param l 属性编号* @param c 操作符（':' 表示等于，'~' 表示不等于）* @param r 属性值* @return 返回一个 bitset，表示哪些对象满足该条件*/
bitset<N> fun(int l, char c, int r)
{bitset<N> ans; // 初始化为空集合（所有位为0）// 找出所有属性 l 等于 r 的对象，并标记为满足条件for (auto i : mp1[pii(l, r)]){ans.set(i);}// 如果是取反操作（不等于），则对所有有属性 l 的对象进行翻转if (c == '~'){for (auto i : mp2[l]){ans.flip(i); // 翻转：原来是1变成0（不属于），原来是0变成1（属于）}}return ans;
}int main()
{int n, m;cin >> n; // 输入对象数量 nint id, k, x, y;for (int i = 1; i <= n; i++){cin >> id >> k; // 输入对象的真实ID和属性数量kDN[i] = id; // 保存第i个对象的真实IDfor (int j = 1; j <= k; j++){cin >> x >> y; // 输入属性编号x和对应的值y// 记录属性(x,y)对应的所有对象mp1[pii(x, y)].push_back(i);// 记录属性x对应的所有对象mp2[x].push_back(i);}}cin >> m; // 输入查询语句的数量mstring s;int c, d; // c:操作符栈指针，d:表达式栈指针while (m--){c = 0; // 操作符栈清空d = 0; // 表达式栈清空cin >> s; // 输入当前查询字符串int len = s.size(); // 查询字符串长度for (int i = 0; i < len;){// 遇到逻辑运算符 & 或 |if (s[i] == '&' || s[i] == '|'){op[++c] = s[i]; // 将操作符压入操作符栈i++;}else if (s[i] == '(') // 忽略左括号{i++;}else if (s[i] == ')') // 遇到右括号，处理当前操作符{num[c]++;if (num[c] == 2) // 如果当前操作符有两个操作数{d--; // 弹出两个操作数中的后一个if (op[c] == '&')dp[d] = dp[d + 1] & dp[d]; // AND 运算elsedp[d] = dp[d + 1] | dp[d]; // OR 运算num[c--] = 0; // 清空当前操作符计数并弹出}i++;}else // 处理基础表达式，如 "1:10" 或 "~3:5"{int l = 0, r = 0;// 解析属性编号 lwhile (i < len && s[i] != ':' && s[i] != '~'){l = l * 10 + s[i] - '0';i++;}char c = s[i++]; // 获取操作符 ':' 或 '~'// 解析属性值 rwhile (i < len && s[i] != ')'){r = r * 10 + s[i] - '0';i++;}// 调用函数计算该原子表达式的结果dp[++d] = fun(l, c, r);}}// 收集满足最终表达式的对象真实IDvector<int> ans;for (int i = 1; i <= n; i++){if (dp[d].test(i)) // 如果第i个对象满足最终表达式{ans.push_back(DN[i]); // 添加其真实ID}}// 输出结果if (ans.size() != 0){sort(ans.begin(), ans.end()); // 排序输出for (auto i : ans){cout << i << ' ';}}cout << endl; // 每条查询结果换行}return 0;
}满分答案
