CSP-202206-3-角色授权

• 经过一段时间的学习，总算是没有任何参考的独立解决了一道大模拟的问题。
• 本题字数很多，重在理解题目意思，一定要仔细读懂题目，实际算法并不复杂。
• 大模拟类型的题目对于数据结构的选择非常重要，直接关系到编码的难易程度以及时间复杂度。

【70分思路】

• 数据结构的选择主要以vector为主进行数据结构的定义，但是忽略了本题的实质是查找，使用vector进行查找时间复杂度是 $O(N)$ 级别，我想这也是时间超限的原因。
• 按照题目描述，定义储存角色和角色关联的结构体MyRole和RoleRelevancy，感觉本题解决的有些像数据库中的问题，如果用数据库的视角去理解角色和角色关联，可能会更容易理清两者之间的关系。
• 需要注意的一个关键点是：本题虽然声明了用户名和用户组名的关系，但是在实际解题的过程中两者的作用是等价的，可以划归为一类变量去处理，不在需要单独判断，即只要满足输入用户名（组）所有对应的角色名称即可进行多具体操作是否符合要求的判断。
• 70分思路的问题在于所有查找都采用了暴力枚举的方式，使得时间复杂度较高，本质上是数据结构（vector）没有选择好。

完整代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int nv, no, nn, ns, ng;// 角色
struct MyRole
{string name;vector<string> operateList; // 操作清单bool operateListHaveStar = 0; // 操作清单有*   vector<string> resourceType; // 资源种类bool resourceTypeHaveStar = 0; // 资源种类有*vector<string> resourceName; // 资源名称bool resourceNameHaveStar = 0; // 资源名称有*bool resourceNameIsEmpty = 0; // 资源名称清单空数组
};// 角色关联
struct RoleRelevancy
{string roleName; // 角色名称vector<string> authorizationList; // 授权对象清单:一个或多个用户名称或者用户组名称
};int main() {int n, m, q;cin >> n >> m >> q;// 输入角色vector<MyRole> RoleList;for (int i = 0; i < n; i++){MyRole t;cin >> t.name;// 输入操作清单cin >> nv;for (int j = 0; j < nv; j++){string optName;cin >> optName;if (optName == "*"){t.operateListHaveStar = 1;}else{t.operateList.push_back(optName);}          }// 输入资源种类cin >> no;for (int j = 0; j < no; j++){string resType;cin >> resType;if (resType=="*"){t.resourceTypeHaveStar = 1;}else{t.resourceType.push_back(resType);}}// 输入资源名称cin >> nn;if (nn == 0){t.resourceNameIsEmpty = 1;}else{for (int j = 0; j < nn; j++){string resName;cin >> resName;if (resName == "*"){t.resourceNameHaveStar = 1;}else{t.resourceName.push_back(resName);}}}RoleList.push_back(t);}// 输入角色关联vector<RoleRelevancy> roleRelevancyList;for (int i = 0; i < m; i++){RoleRelevancy t;cin >> t.roleName;// 授权对象cin >> ns;for (int j = 0; j < ns; j++){char isU;cin >> isU;string autName;cin >> autName;t.authorizationList.push_back(autName);}roleRelevancyList.push_back(t);}// 输入待授权的行为for (int i = 0; i < q; i++){string currentUserOrGroup;cin >> currentUserOrGroup;cin >> ng;// 所属用户组名称vector<string> UserOrGroup;UserOrGroup.push_back(currentUserOrGroup);for (int j = 0; j < ng; j++){cin >> currentUserOrGroup;UserOrGroup.push_back(currentUserOrGroup);}string q_opt, q_res_kind, q_res_name;cin >> q_opt >> q_res_kind >> q_res_name;// 查询// 1.检查所输入的用户名或所属的用户组所对应的所有角色名称vector<string> currentRoleNameList;for (const auto& ii : UserOrGroup){for (const auto& jj : roleRelevancyList){for (const auto& kk : jj.authorizationList){if (ii == kk){currentRoleNameList.push_back(jj.roleName);break;}}}}// 2.检查角色列表中，找到该角色的名字，检查q_opt, q_res_kind, q_res_name是否在操作清单/*，资源种类清单/*，资源名称清单/*bool isExecutable = 0;for (const auto& ii : currentRoleNameList){for (const auto& jj : RoleList){if (ii == jj.name){int flag = 0;// 1.通配符/操作清单中包含该操作if (jj.operateListHaveStar){flag++;}else{for (const auto& kk : jj.operateList){if (q_opt == kk){flag++;}}}// 2.通配符/资源种类清单中包含该种类if (jj.resourceTypeHaveStar){flag++;}else{for (const auto& kk : jj.resourceType){if (q_res_kind == kk){flag++;}}}// 3.通配符/资源名称清单中包含该名称/数组为空if (jj.resourceNameHaveStar || jj.resourceNameIsEmpty){flag++;}else{for (const auto& kk : jj.resourceName){if (q_res_name == kk){flag++;}}}if (flag == 3){isExecutable = 1;break;} }}if (isExecutable == 1){break;}}if (isExecutable){cout << "1\n";}else{cout << "0\n";}}return 0;
}

【100分思路】

• 角色信息的存储：使用unordered_map和unordered_set代替vector，这改变了数据的存取方式。unordered_map和unordered_set基于哈希表实现，它们的平均时间复杂度为 $O(1)$ 对于插入、删除和查找操作。

• 查询处理：当处理查询时，代码2利用unordered_map来直接访问与当前用户或用户组相关联的角色，消除了遍历角色关联列表的需要。然后，对于每个角色，它使用unordered_set来检查操作、资源类型和资源名称的存在性，这些操作的时间复杂度也是O(1)。

• 因此，代码2的时间复杂度对于每个查询主要是O(u + r)，其中u是用户或用户组数量，r是用户或用户组相关的角色数量。由于哈希表的使用，这大大减少了所需的时间，尤其是在处理大量数据时。总的来说，代码2时间复杂度低的原因在于使用了哈希表（unordered_map和unordered_set），这使得数据的查找、插入和删除操作平均时间复杂度降至O(1)。与代码1相比，代码2减少了对列表的遍历，从而避免了O(n)或O(m)的时间复杂度，特别是在处理大量查询时，这种差别会非常显著。

完整代码

#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <string>
using namespace std;struct MyRole {unordered_set<string> operateList;bool operateListHaveStar = false;unordered_set<string> resourceType;bool resourceTypeHaveStar = false;unordered_set<string> resourceName;bool resourceNameHaveStar = false;bool resourceNameIsEmpty = false;
};unordered_map<string, MyRole> roles;
unordered_map<string, unordered_set<string>> userToRoles;
int nv, no, nn, ns, ng;int main() {int n, m, q;cin >> n >> m >> q;// 输入角色for (int i = 0; i < n; i++) {string name;cin >> name;MyRole& role = roles[name];cin >> nv;for (int j = 0; j < nv; j++) {string opt;cin >> opt;if (opt == "*") role.operateListHaveStar = true;else role.operateList.insert(opt);}cin >> no;for (int j = 0; j < no; j++) {string type;cin >> type;if (type == "*") role.resourceTypeHaveStar = true;else role.resourceType.insert(type);}cin >> nn;if (nn == 0) {role.resourceNameIsEmpty = true;}else {for (int j = 0; j < nn; j++) {string name;cin >> name;if (name == "*") role.resourceNameHaveStar = true;else role.resourceName.insert(name);}}}// 输入角色关联for (int i = 0; i < m; i++) {string roleName, userName;cin >> roleName >> ns;for (int j = 0; j < ns; j++) {char isU;cin >> isU;cin >> userName;userToRoles[userName].insert(roleName);}}// 输入待授权的行为for (int i = 0; i < q; i++) {string currentUserOrGroup;cin >> currentUserOrGroup;cin >> ng;// 所属用户组名称vector<string> UserOrGroup;UserOrGroup.push_back(currentUserOrGroup);for (int j = 0; j < ng; j++){cin >> currentUserOrGroup;UserOrGroup.push_back(currentUserOrGroup);}string opt, resType, resName;cin >> opt >> resType >> resName;bool authorized = false;for (const auto& userOrGroup : UserOrGroup) {// 检查当前用户或用户组是否有对应的角色if (userToRoles.count(userOrGroup)) {// 获取当前用户或用户组的所有角色for (const auto& roleName : userToRoles[userOrGroup]) {// 获取角色详细信息const MyRole& role = roles[roleName];// 检查权限if ((role.operateListHaveStar || role.operateList.count(opt)) &&(role.resourceTypeHaveStar || role.resourceType.count(resType)) &&(role.resourceNameHaveStar || role.resourceNameIsEmpty || role.resourceName.count(resName))) {authorized = true;break; // 找到授权，跳出角色遍历}}}if (authorized) break; // 找到授权，跳出用户或用户组遍历}if (authorized) {cout << "1\n";}else {cout << "0\n";}}return 0;
}