201612-3
试题名称: 权限查询
时间限制: 1.0s
内存限制: 256.0MB
问题描述:
问题描述
  授权 (authorization) 是各类业务系统不可缺少的组成部分,系统用户通过授权机制获得系统中各个模块的操作权限。
  本题中的授权机制是这样设计的:每位用户具有若干角色,每种角色具有若干权限。例如,用户 david 具有 manager 角色,manager 角色有 crm:2 权限,则用户 david 具有 crm:2 权限,也就是 crm 类权限的第 2 等级的权限。
  具体地,用户名和角色名称都是由小写字母组成的字符串,长度不超过 32。权限分为分等级权限和不分等级权限两大类。分等级权限由权限类名和权限等级构成,中间用冒号“:”分隔。其中权限类名也是由小写字母组成的字符串,长度不超过 32。权限等级是一位数字,从 0 到 9,数字越大表示权限等级越高。系统规定如果用户具有某类某一等级的权限,那么他也将自动具有该类更低等级的权限。例如在上面的例子中,除 crm:2 外,用户 david 也具有 crm:1 和 crm:0 权限。不分等级权限在描述权限时只有权限类名,没有权限等级(也没有用于分隔的冒号)。
  给出系统中用户、角色和权限的描述信息,你的程序需要回答多个关于用户和权限的查询。查询可分为以下几类:
  * 不分等级权限的查询:如果权限本身是不分等级的,则查询时不指定等级,返回是否具有该权限;
  * 分等级权限的带等级查询:如果权限本身分等级,查询也带等级,则返回是否具有该类的该等级权限;
  * 分等级权限的不带等级查询:如果权限本身分等级,查询不带等级,则返回具有该类权限的等级;如果不具有该类的任何等级权限,则返回“否”。
输入格式
  输入第一行是一个正整数 p,表示不同的权限类别的数量。紧接着的 p 行被称为 P 段,每行一个字符串,描述各个权限。对于分等级权限,格式为 <category>:<level>,其中 <category> 是权限类名,<level> 是该类权限的最高等级。对于不分等级权限,字符串只包含权限类名。
  接下来一行是一个正整数 r,表示不同的角色数量。紧接着的 r 行被称为 R 段,每行描述一种角色,格式为
  <role> <s> <privilege 1> <privilege 2> ... <privilege s>
  其中 <role> 是角色名称,<s> 表示该角色具有多少种权限。后面 <s> 个字符串描述该角色具有的权限,格式同 P 段。
  接下来一行是一个正整数 u,表示用户数量。紧接着的 u 行被称为 U 段,每行描述一个用户,格式为
  <user> <t> <role 1> <role 2> ... <role t>
  其中 <user> 是用户名,<t> 表示该用户具有多少种角色。后面 <t> 个字符串描述该用户具有的角色。
  接下来一行是一个正整数 q,表示权限查询的数量。紧接着的 q 行被称为 Q 段,每行描述一个授权查询,格式为 <user> <privilege>,表示查询用户 <user> 是否具有 <privilege> 权限。如果查询的权限是分等级权限,则查询中的 <privilege> 可指定等级,表示查询该用户是否具有该等级的权限;也可以不指定等级,表示查询该用户具有该权限的等级。对于不分等级权限,只能查询该用户是否具有该权限,查询中不能指定等级。
输出格式
  输出共 q 行,每行为 false、true,或者一个数字。false 表示相应的用户不具有相应的权限,true 表示相应的用户具有相应的权限。对于分等级权限的不带等级查询,如果具有权限,则结果是一个数字,表示该用户具有该权限的(最高)等级。如果用户不存在,或者查询的权限没有定义,则应该返回 false。
样例输入
3
crm:2
git:3
game
4
hr 1 crm:2
it 3 crm:1 git:1 game
dev 2 git:3 game
qa 1 git:2
3
alice 1 hr
bob 2 it qa
charlie 1 dev
9
alice game
alice crm:2
alice git:0
bob git
bob poweroff
charlie game
charlie crm
charlie git:3
malice game
样例输出
false
true
false
2
false
true
false
true
false
样例说明
  样例输入描述的场景中,各个用户实际的权限如下:
  * 用户 alice 具有 crm:2 权限
  * 用户 bob 具有 crm:1、git:2 和 game 权限
  * 用户 charlie 具有 git:3 和 game 权限
  * 用户 malice 未描述,因此不具有任何权限
评测用例规模与约定
  评测用例规模:
  * 1 ≤ p, r, u ≤ 100
  * 1 ≤ q ≤ 10 000
  * 每个用户具有的角色数不超过 10,每种角色具有的权限种类不超过 10
  约定:
  * 输入保证合法性,包括:
  1) 角色对应的权限列表(R 段)中的权限都是之前(P 段)出现过的,权限可以重复出现,如果带等级的权限重复出现,以等级最高的为准
  2) 用户对应的角色列表(U 段)中的角色都是之前(R 段)出现过的,如果多个角色都具有某一分等级权限,以等级最高的为准
  3) 查询(Q 段)中的用户名和权限类名不保证在之前(U 段和 P 段)出现过
  * 前 20% 的评测用例只有一种角色
  * 前 50% 的评测用例权限都是不分等级的,查询也都不带等级

题目链接:

  http://cspro.org/lead/leadbpm.do?__action=goto_iframe&path=CCF_KS_KSLX_LIST&djtype=TT&2

题目大意:

  一个公司有几种权限P,每种权限不分等级或者有最高等级,等级9最高0最低。

  该公司还有若干职务R,每种职务具有一个或多个不同权限的不同等级。

  该公司还有若干员工U,每个员工可能同时有一个或多个不同职务并享有其权限,拥有权限重叠时取最高权限。

  接下来有Q个询问,询问员工A是否具有权限B,分以下情况:

    如果A具有不分等级的权限B,则输出true,不具有输出false

    如果A具有分等级的权限B且B给出等级,则判断A的B权限是否达到该等级,达到true否则false

    如果A具有分等级的权限B且B未给出等级,则输出A具有B权限的最高等级。

题目思路:

  【模拟+STL】

  好大一道模拟题,耐心点写还是能1A的。

  主要就是按着题目的思路挨个找。

 /****************************************************

     Author:Coolxxx
Copyright 2017 by Coolxxx. All rights reserved.
CSDN:http://blog.csdn.net/u010568270 ****************************************************/
#include<bits/stdc++.h>
#pragma comment(linker,"/STACK:1024000000,1024000000")
#define abs(a) ((a)>0?(a):(-(a)))
#define lowbit(a) (a&(-a))
#define sqr(a) ((a)*(a))
#define mem(a,b) memset(a,b,sizeof(a))
#define eps (1e-8)
#define J 10000
#define mod 1000000007
#define MAX 0x7f7f7f7f
#define PI 3.14159265358979323
#define N 104
#define M 10004
using namespace std;
typedef long long LL;
double anss;
LL aans;
int cas,cass;
int n,m,lll,ans;
int R,U,Q;
string ch,name; struct category
{
string name;
int level;
}ca[N],p; struct role
{
int num;
string name;
category rc[N];
}ro[N];
map<string,int>r; struct user
{
int num;
string name;
map<string,int>c;
}us[N]; void change(string ch,category &aa)
{
if(ch[ch.size()-]==':')
{
aa.name=ch.substr(,ch.size()-);
aa.level=ch[ch.size()-]-'';
}
else
{
aa.name=ch;
aa.level=-;
}
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("1.txt","r",stdin);
// freopen("2.txt","w",stdout);
#endif
int i,j,k,l;
int x,y,z;
// for(scanf("%d",&cass);cass;cass--)
// for(scanf("%d",&cas),cass=1;cass<=cas;cass++)
// while(~scanf("%s",s))
while(~scanf("%d",&n))
{
for(i=;i<=n;i++)
{
cin>>ch;
change(ch,ca[i]);
}
scanf("%d",&R);
for(i=;i<=R;i++)
{
cin>>ro[i].name>>ro[i].num;
r[ro[i].name]=i;
for(j=;j<=ro[i].num;j++)
{
cin>>ch;
change(ch,ro[i].rc[j]);
}
}
scanf("%d",&U);
for(i=;i<=U;i++)
{
cin>>us[i].name>>x;
for(j=;j<=x;j++)
{
cin>>ch;
k=r[ch];
for(l=;l<=ro[k].num;l++)
{
if(us[i].c.find(ro[k].rc[l].name)==us[i].c.end())
us[i].c[ro[k].rc[l].name]=ro[k].rc[l].level;
else us[i].c[ro[k].rc[l].name]=max(us[i].c[ro[k].rc[l].name],ro[k].rc[l].level);
}
}
}
scanf("%d",&Q);
for(i=;i<=Q;i++)
{
cin>>name>>ch;
change(ch,p);
for(j=;j<=U;j++)
if(us[j].name==name)
break;
if(j>U)
{
puts("false");
continue;
}
if(us[j].c.find(p.name)!=us[j].c.end())
{
if(p.level==- && us[j].c[p.name]!=-)
cout<<us[j].c[p.name]<<endl;
else if(us[j].c[p.name]>=p.level)
puts("true");
else puts("false");
}
else puts("false");
}
}
return ;
}
/*
// //
*/

最新文章

  1. Visual Studio 2015 Pre Secondary Installer 在哪里
  2. Python之路【第十二篇】前端之js&amp;dome&amp;jQuery
  3. [Java Web整合开发王者归来&#183;刘京华] 2、 Java Web开发概述
  4. JSON.stringify语法解析(自己留存)
  5. archlinux 网络配置
  6. web.xml中 error-page的正确用法
  7. EV电池指标及特点
  8. requirejs实验001.对我来说,用AMD的方式来组织代码并不轻松.
  9. Android_常用控件及适配器
  10. WordPress 3.5.1 crypt_private()远程拒绝服务漏洞(CVE-2013-2173)
  11. access数据库 top语句失效解决方法
  12. Android 优质精准的用户行为统计和日志打捞方案
  13. shibie
  14. mySQL配置文件、备份与恢复
  15. 【noip模拟赛3】确定的位置 (map的遍历 位置原理)
  16. CAS (8) —— Mac下配置CAS到JBoss EAP 6.4(6.x)的Standalone模式(服务端)
  17. Flare-On4 解题复现
  18. MVC框架定义
  19. 【BZOJ1453】[Wc]Dface双面棋盘 线段树+并查集
  20. 在windows上搭建redis集群(redis-cluster)(转载)

热门文章

  1. python在linux下的使用
  2. &lt;Redis&gt; 入门六 主从复制方式的集群
  3. Matlab学习笔记(五)
  4. js获取指定字符前/后的字符串简单实例
  5. Leetcode 143.重排链表
  6. hihoCoder#1109 最小生成树三&#183;堆优化的Prim算法
  7. noip模拟赛 经营与开发
  8. P1072 Hankson的趣味题
  9. ajax接收json数据到js解析
  10. Android 4.4.2上与BLE 蓝牙锁设备的通讯