题目描述

本题要求我们处理一个角色与权限的管理系统，基于角色的授权模型来验证某个用户是否能够执行某个操作。问题的关键在于如何有效地管理用户、角色以及角色与权限之间的关系，并且要高效地处理多个查询请求。

每个用户可以属于多个用户组，而每个用户组又可能与多个角色关联。因此，在查询时，我们需要根据用户直接的角色以及所属的用户组的角色，计算出用户最终可以执行哪些操作。为了实现这一点，我们需要做以下几个步骤：

角色信息的存储：每个角色有自己的操作权限清单、资源种类清单和资源名称清单。如果角色允许所有操作或资源，我们通过通配符 * 来表示这一点。我们可以使用 unordered_map<string, unordered_set<string>> role2op,role2src_kind和role2src_name来存储每个角色的权限信息。

用户与角色的关联：每个用户可能与多个角色关联，同时，用户也可能属于多个用户组，每个用户组可能与多个角色关联。我们使用 unordered_map<string, unordered_set<string>>user2role 来存储用户和角色之间的关系，group2role用户组和角色之间的关系。

查询操作：每次查询时，我们首先根据用户和所属用户组的角色集合，确定用户最终的角色集合。然后，使用这些角色集合判断该用户是否有权限执行指定操作。

注：*不要加入到role2op和role2src_kind里，而是用单独的unordered_map<string, bool> role2op_all,role2src_kind_all来加速判断。

解题代码

#include <iostream>
#include <stdio.h>
#include <bits/stdc++.h>
using namespace std;

unordered_map<string, unordered_set<string>> role2op;
unordered_map<string, unordered_set<string>> role2src_kind;
unordered_map<string, unordered_set<string>> role2src_name;

unordered_map<string, bool> role2op_all;
unordered_map<string, bool> role2src_kind_all;

bool role_check(string &role, string &operate, string &source_kind, string &source_name)
{
    if (role2op[role].count(operate) == 0 && role2op_all[role] == false)
        return false;
    if (role2src_kind[role].count(source_kind) == 0 && role2src_kind_all[role] == false)
        return false;
    if (role2src_name[role].count(source_name) == 0 && !role2src_name[role].empty())
        return false;
    return true;
}

unordered_map<string, unordered_set<string>> group2role;

unordered_map<string, unordered_set<string>> user2role;

int main()
{
    //freopen("input.txt", "r", stdin);
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int n, m, q; // 角色数量、角色关联数量和待检查的操作数量。
    cin >> n >> m >> q;
    cin.ignore();

    // 接下来的 n 行中，每行表示一个角色
    for (int i = 0; i < n; i++)
    {
        string role; // 该角色的名称
        cin >> role;
        role2op_all[role] = false;
        role2src_kind_all[role] = false;

        int nv; // 操作清单中包含的操作数量
        cin >> nv;
        for (int j = 0; j < nv; j++)
        {
            string operate;
            cin >> operate;
            if (operate == "*")
            {
                role2op_all[role] = true;
            }
            else
            {
                role2op[role].insert(operate);
            }
        }

        int no; // 资源种类清单中包含的资源种类的数量
        cin >> no;
        for (int j = 0; j < no; j++)
        {
            string source_kind;
            cin >> source_kind;
            if (source_kind == "*")
            {
                role2src_kind_all[role] = true;
            }
            else
            {
                role2src_kind[role].insert(source_kind);
            }
        }

        int nn; // 资源名称清单中包含的资源名称的数量
        cin >> nn;
        for (int j = 0; j < nn; j++)
        {
            string source_name;
            cin >> source_name;
            role2src_name[role].insert(source_name);
        }
    }

    // 接下来的 m 行中，每行表示一个角色关联
    for (int i = 0; i < m; i++)
    {
        string role; // 该角色关联的角色名称
        cin >> role;

        int ns; // 授权对象清单中包含的授权对象的数量
        cin >> ns;
        for (int j = 0; j < ns; j++)
        {
            string front, back;
            cin >> front >> back;
            if (front == "u")
            {
                user2role[back].insert(role);
            }
            else if (front == "g")
            {
                group2role[back].insert(role);
            }
        }
    }

    // 接下来的 q 行中，每行表示一个待授权的行为
    for (int i = 0; i < q; i++)
    {
        bool flag = false;

        string user; // 执行该操作的用户名称
        cin >> user;

        unordered_set<string> current_user2role = user2role[user];

        int ng; // 该用户所属的用户组的数量
        cin >> ng;

        for (int j = 0; j < ng; j++)
        {
            string group;
            cin >> group;
            for (auto p : group2role[group])
            {
                current_user2role.insert(p);
            }
        }

        string operate, source_kind, source_name;
        cin >> operate >> source_kind >> source_name;

        for (auto role : current_user2role)
        {
            if (role_check(role, operate, source_kind, source_name))
            {
                flag = true;
                break;
            }
        }

        if (flag)
            cout << 1;
        else
            cout << 0;
        cout << '\n';
    }

    return 0;
}

题主第一版代码里也是在数据较大时超时，Acwing上只能通过8/11，不断查找发现是第一版在复制user2role上选择了整体复制，即unordered_map<string, unordered_set<string>> current_user2role = user2role;这样相当于复制了很多当前无用的user信息，修改成只复制当前user的集合即可，unordered_set<string> current_user2role = user2role[user];