CSP-202206-3-角色授权
- 经过一段时间的学习,总算是没有任何参考的独立解决了一道大模拟的问题。
- 本题字数很多,重在理解题目意思,一定要仔细读懂题目,实际算法并不复杂。
- 大模拟类型的题目对于数据结构的选择非常重要,直接关系到编码的难易程度以及时间复杂度。
【70分思路】
- 数据结构的选择主要以
vector
为主进行数据结构的定义,但是忽略了本题的实质是查找,使用vector
进行查找时间复杂度是 O ( N ) O(N) 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 ) O(1) 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;
}