建立授权对象到角色的反向索引，再取用户和当次用户组关联角色的权限并集。
OJ: shumeng
题目 ID: CSP202206C
难度:普及+/提高-
标签:哈希集合模拟
日期: 2026-07-31 16:21
形式化题目
有 * 均可匹配任意操作或任意类型。
有
思路
用户权限等于其关联的所有角色权限的并集，因此关键是把“授权对象 → 角色”的反向关系建好，避免查询时扫描全部角色关联。
建立反向索引
把每个授权对象记录为带前缀的键：用户用 u:名字，用户组用 g:名字，值是它能获得的角色编号列表。读入 map。
收集本次查询涉及的角色
每次查询读出用户和当次所属的用户组（题目强调不能记忆历史用户组，必须用本次给出的组），依次查询 u:用户 和 g:组名 对应的角色编号。不同角色、不同组可能指向同一角色，用 seen 数组按查询编号去重。
判断权限
对收集到的每个角色检查三张清单：
- 操作清单为空或包含操作，或包含
*； - 类型清单包含类型或包含
*； - 名称清单为空或包含名称。
三条件都满足即可执行；任一角色满足就输出 1。
代码
cpp
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-07-31 16:21
* update_at: 2026-08-17 22:40
*/
#include <bits/stdc++.h>
using namespace std;
// 一个角色允许的操作、资源类型和资源名称三张清单
struct Role {
string name; // 角色名称
unordered_set<string> operations; // 允许的操作清单
unordered_set<string> object_types; // 允许的资源类型清单
unordered_set<string> object_names; // 允许的资源名称清单（空表示任意名称）
};
int role_count, relation_count, query_count;
vector<Role> role;
unordered_map<string, int> role_id; // 角色名称 -> 编号
unordered_map<string, vector<int> > object_roles; // "u:用户" 或 "g:用户组" -> 可获得的角色编号列表
vector<int> seen; // 去重标记：值为最近一次查询的编号
int query_id;
// 读入一个角色并填入角色表
void read_role(int id) {
int count;
string value;
cin >> role[id].name;
role_id[role[id].name] = id;
cin >> count; // 操作清单
for (int i = 0; i < count; i++) {
cin >> value;
role[id].operations.insert(value);
}
cin >> count; // 资源类型清单
for (int i = 0; i < count; i++) {
cin >> value;
role[id].object_types.insert(value);
}
cin >> count; // 资源名称清单
for (int i = 0; i < count; i++) {
cin >> value;
role[id].object_names.insert(value);
}
}
// 读入一条角色关联：把该角色关联到若干用户或用户组
void read_relation() {
string name;
int count;
cin >> name >> count;
int id = role_id[name];
for (int i = 0; i < count; i++) {
string type, value;
cin >> type >> value; // type 为 u 或 g
object_roles[type + ":" + value].push_back(id);
}
}
// 加入一个授权对象（"u:xxx" 或 "g:xxx"）对应的角色，用 seen 去重
void collect_roles(const string &key, vector<int> &candidate) {
vector<int> &list = object_roles[key];
for (int i = 0; i < (int)list.size(); i++) {
int id = list[i];
if (seen[id] != query_id) {
seen[id] = query_id;
candidate.push_back(id);
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> role_count >> relation_count >> query_count;
role.resize(role_count);
for (int i = 0; i < role_count; i++) read_role(i);
for (int i = 0; i < relation_count; i++) read_relation();
seen.assign(role_count, 0);
query_id = 0;
while (query_count--) {
string user, operation, object_type, object_name;
int group_count;
cin >> user >> group_count;
vector<string> group(group_count);
for (int i = 0; i < group_count; i++) cin >> group[i];
cin >> operation >> object_type >> object_name;
query_id++;
vector<int> candidate; // 本次查询涉及的所有角色编号（已去重）
collect_roles("u:" + user, candidate);
for (int i = 0; i < group_count; i++) collect_roles("g:" + group[i], candidate);
// 任一角色允许该操作即输出 1
bool allowed = false;
for (int i = 0; i < (int)candidate.size() && !allowed; i++) {
Role ¤t = role[candidate[i]];
bool operation_ok = current.operations.count(operation)
|| current.operations.count("*");
bool type_ok = current.object_types.count(object_type)
|| current.object_types.count("*");
bool name_ok = current.object_names.empty()
|| current.object_names.count(object_name);
if (operation_ok && type_ok && name_ok) allowed = true;
}
cout << (allowed ? 1 : 0) << '\n';
}
return 0;
}复杂度
设一次查询涉及的不同角色数为
总结
每次查询的用户组信息独立使用，不能缓存同名用户此前的组；角色权限判断是多角色权限的并集。用带前缀的反向索引把“用户/组 → 角色”的关系组织起来，是这类授权模拟题最直接有效的做法。