CSP-202206-3-角色授权

CSP-202206-3-角色授权

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

【70分思路】

  • 数据结构的选择主要以vector为主进行数据结构的定义,但是忽略了本题的实质是查找,使用vector进行查找时间复杂度是 O ( N ) O(N) O(N) 级别,我想这也是时间超限的原因。
  • 按照题目描述,定义储存角色和角色关联的结构体MyRoleRoleRelevancy,感觉本题解决的有些像数据库中的问题,如果用数据库的视角去理解角色角色关联,可能会更容易理清两者之间的关系。
  • 需要注意的一个关键点是:本题虽然声明了用户名和用户组名的关系,但是在实际解题的过程中两者的作用是等价的,可以划归为一类变量去处理,不在需要单独判断,即只要满足输入用户名(组)所有对应的角色名称即可进行多具体操作是否符合要求的判断
  • 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_mapunordered_set代替vector,这改变了数据的存取方式。unordered_mapunordered_set基于哈希表实现,它们的平均时间复杂度为 O ( 1 ) O(1) O(1) 对于插入、删除和查找操作。

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

  • 因此,代码2的时间复杂度对于每个查询主要是O(u + r),其中u是用户或用户组数量,r是用户或用户组相关的角色数量。由于哈希表的使用,这大大减少了所需的时间,尤其是在处理大量数据时。总的来说,代码2时间复杂度低的原因在于使用了哈希表(unordered_mapunordered_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;
}

请添加图片描述

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://xiahunao.cn/news/2812769.html

如若内容造成侵权/违法违规/事实不符,请联系瞎胡闹网进行投诉反馈,一经查实,立即删除!

相关文章

【Flink精讲】Flink反压调优

Flink 网络流控及反压的介绍&#xff1a; Apache Flink学习网 反压的理解 简单来说&#xff0c; Flink 拓扑中每个节点&#xff08;Task&#xff09;间的数据都以阻塞队列的方式传输&#xff0c;下游来不及消费导致队列被占满后&#xff0c;上游的生产也会被阻塞&#xff0c;…

DataSpell 2023:专注于数据,加速您的数据科学之旅 mac/win版

JetBrains DataSpell 2023是一款专为数据科学家和数据分析师设计的集成开发环境&#xff08;IDE&#xff09;。这款IDE提供了强大的数据分析和可视化工具&#xff0c;旨在帮助用户更快速、更高效地进行数据科学工作。 DataSpell 2023软件获取 DataSpell 2023在保持其一贯的数…

用39块钱的全志V851se视觉开发板做了个小相机,还可以物品识别、自动追焦!

用39块钱的V851se视觉开发板做了个小相机。 可以进行物品识别、自动追焦&#xff01; 这个超低成本的小相机是在V851se上移植使用全志在线开源版本的Tina Linux与OpenCV框架开启摄像头拍照捕获视频&#xff0c;并结合NPU实现Mobilenet v2目标分类识别以及运动追踪等功能…并最终…

springboot+vue项目基础开发(19)vue使用axios拦截器

添加拦截器,将token存在拦截器 在request.js添加拦截器 import {useTokenStore} from @/stores/token.js //添加请求拦截器 instance.interceptors.request.use((config)=>{

备战蓝桥杯---树形DP基础1

我们先来看几个比较简单的例子来引入&#xff1a; 我们令f[i]表示以i为根节点的子树大小&#xff0c;易得状态转移方程为&#xff1a; f[i]1f[son1]....f[soni]; 我们用DFS即可&#xff0c;下面是大致的模板&#xff1a; 让我们来看看几道题吧&#xff1a; 1.贪心树形DPDFS&…

终于,我们拿下了硅谷的那个 Linear

就像设计领域的 Figma&#xff0c;文档领域的 Notion&#xff0c;Linear 同样在软件开发管理领域推出了革命性的工具。而且以其名字 Linear Style 命名的设计风格&#xff0c;也成为了一股软件设计潮流。 Linear 于 2019 年在美国 &#x1f1fa;&#x1f1f8; 旧金山创立。目前…

echarts在线样式

makeapie echarts社区图表可视化案例makeapie echarts图表可视化案例, 分享你的可视化作品https://www.makeapie.cn/echarts

数据库orclec;nvl和nvl2的区别

Oracle中nvl()与nvl2()函数详解-CSDN博客 select nvl(null,2) as vb from dual select nvl2(666,2,3) as vb from dual

AI与大数据:智慧城市安全的护航者与变革引擎

一、引言 在数字化浪潮的席卷下&#xff0c;智慧城市正成为现代城市发展的新方向。作为城市的神经系统&#xff0c;AI与大数据的融合与应用为城市的安全与应急响应带来了革命性的变革。它们如同城市的“智慧之眼”和“聪明之脑”&#xff0c;不仅为城市管理者提供了强大的决策…

LeetCode 刷题 [C++] 第73题.矩阵置零

题目描述 给定一个 m x n 的矩阵&#xff0c;如果一个元素为 0 &#xff0c;则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。 题目分析 题目中要求使用原地算法&#xff1a;即直接在输入矩阵上进行修改。因此如果在输入矩阵上把行/列的值修改成0后&#xff0c;在…

《数据治理简易速速上手小册》第4章 数据安全与合规性(2024 最新版)

文章目录 4.1 数据安全的基本原则4.1.1 基础知识4.1.2 重点案例&#xff1a;在线零售商的数据加密4.1.3 拓展案例 1&#xff1a;医疗机构的访问控制4.1.4 拓展案例 2&#xff1a;金融服务提供商的数据备份和恢复 4.2 遵循数据合规性的策略4.2.1 基础知识4.2.2 重点案例&#xf…

SwiftUI- DatePicker的集成

在SwiftUI中&#xff0c;DatePicker是用于显示和选择日期的视图&#xff0c;可以通过以下步骤集成DatePicker&#xff1a; 1.创建一个日期变量来存储选定的日期&#xff1a; State private var selectedDate Date()2.在视图中使用DatePicker&#xff0c;并将其绑定到先前创建…

机器学习-02-机器学习算法分类以及在各行各业的应用

总结 本系列是机器学习课程的第02篇&#xff0c;主要介绍机器学习算法分类以及在各行各业的应用 本门课程的目标 完成一个特定行业的算法应用全过程&#xff1a; 定义问题&#xff08;Problem Definition&#xff09; -> 数据收集(Data Collection) -> 数据分割(Data…

docker容器配置mysql5.7主从复制

介绍 本文将通过docker创建3个mysql数据库容器&#xff0c;实现数据库主从复制功能&#xff0c;三个数据库容器分别为主库mysql-master:3307&#xff0c;从库mysql-slave-01:3308&#xff0c;mysql-slave-02:3309。使用的是mysql5.7版本 1. 拉取mongo镜像 docker pull mysql…

React Hooks概述及常用的React Hooks介绍

Hook可以让你在不编写class的情况下使用state以及其他React特性 useState ● useState就是一个Hook ● 通过在函数组件里调用它来给组件添加一些内部state,React会在重复渲染时保留这个state 纯函数组件没有状态&#xff0c;useState()用于设置和使用组件的状态属性。语法如下…

【QT+QGIS跨平台编译】之五十二:【QGIS_CORE跨平台编译】—【qgsexpressionlexer.cpp生成】

文章目录 一、Flex二、生成来源三、构建过程一、Flex Flex (fast lexical analyser generator) 是 Lex 的另一个替代品。它经常和自由软件 Bison 语法分析器生成器 一起使用。Flex 最初由 Vern Paxson 于 1987 年用 C 语言写成。 “flex 是一个生成扫描器的工具,能够识别文本中…

微信公众号关键词自动回复

今天主要给大家讲一下如何实现微信公众号关键词的自动回复功能&#xff0c;就如网站的文章而言&#xff0c;进行人机识别&#xff0c;需要关注公众号回复验证码获取到验证码从而展示文章内容&#xff0c;&#xff0c;具体效果如下图。 springboot 2.3.2RELEASE 1、微信公众平台…

跨境电商必读:如何选择适合跨境ERP系统?

在当今全球化的商业环境下&#xff0c;跨境电商已经成为许多企业拓展业务的重要途径。而选择适合的ERP系统&#xff0c;对于实现跨境电商的高效运营和持续发展至关重要。本文将为您详细介绍如何选择适合跨境电商的ERP系统&#xff0c;助您在激烈的市场竞争中脱颖而出。 为什么…

2024.2.25 模拟实现 RabbitMQ —— 网络通信设计(服务器)

目录 引言 约定应用层的通信协议 自定义应用层协议 Type Length PayLod 实现 Broker Server 类 属性 与 构造 启动 Broker Server 停止 Broker Server 处理客户端连接 读取请求 与 写回响应 根据请求计算响应 清除 channel 引言 生产者 和 消费者 都是客户端&…

决策支持系统(DSS):一文读懂,同时分清和BI的区别

大家好&#xff0c;我是贝格前端工场&#xff0c;本期继续分享决策支持系统的设计&#xff0c;欢迎大家关注&#xff0c;如有B端系统界面的设计和前端需求&#xff0c;可以联络我们。 一、什么是DSS DSS系统是指决策支持系统&#xff08;Decision Support System&#xff09;…