文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

CCF-CSP真题《202303-3 LDAP》思路+python,c++满分题解

2023-09-01 11:44

关注

想查看其他题的真题及题解的同学可以前往查看:CCF-CSP真题附题解大全


试题编号:202303-3
试题名称:LDAP
时间限制:12.0s
内存限制:1.0GB
问题描述:

题目背景

西西艾弗岛运营公司是一家负责维护和运营岛上基础设施的大型企业,拥有数千名员工。公司内有很多 IT 系统。为了能够实现这些 IT 系统的统一认证登录,公司 IT 部门决定引入一套 LDAP 系统来管理公司内的用户信息。轻型目录访问协议(Lightweight Directory Access Protocol,LDAP)是一种用于访问和维护目录服务的应用层协议,基于它的数据库可以用树形结构来组织和存储数据。每一笔数据,都包含了一个唯一的标识符(DN,Distinguished Name),以及一系列的属性(Attribute)。

不同的 IT 系统,允许访问的用户是不相同的。每个信息系统都有一个表达式,用来描述允许访问的用户。
这个表达式可以按照某一个属性的值作为条件来匹配用户,也可以用多个条件的逻辑组合来匹配用户。
小 C 被安排来实现这样一个算法,给定一个 IT 系统的匹配表达式,找到所有与之匹配的用户的 DN。

问题描述

为了简化该问题,我们约定,每个用户的 DN 是一个正整数,且不会重复。有若干种用户的属性,用正整数编号。每个用户可以具有这些属性中的若干个,且每个属性只能有一个值。每个属性的值也是一个正整数。例如,假定有两个用户:用户 1 和用户 2,他们的 DN 分别是 1 和 2。一共有 3 种属性。用户 1 具有属性 1 和属性 2,且属性 1 的值为 2,属性 2 的值为 3;但不具有属性 3。用户 2 具有属性 2 和属性 3,且属性 2 的值为 3,属性 3 的值为 1;但不具有属性 1。如下表所示:

DN属性 1属性 2属性 3
123N/A
2N/A31

一个匹配表达式可以是一个属性的值,也可以是多个匹配表达式的逻辑组合。只匹配一个属性的值的表达式称为原子表达式,原子表达式的形式为 <属性编号><操作符><属性值>。其中操作符有两种:断言与反断言。断言操作符为 :,表示匹配具有该属性且值与之相等的用户;反断言操作符为 ~,表示匹配具有该属性且值与之不等的用户。例如,表达式 1:2 可以与上述用户 1 相匹配,但不能与用户 2 相匹配;而表达式 3~1则不能与任何一个用户相匹配。

表达式可以进行逻辑组合,其语法是:<操作符>(表达式 1)(表达式 2)。其中操作符有两种:与(&)和或(|)。如果操作符为与,则当且仅当两个表达式都与某一用户相匹配时,该表达式与该用户相匹配;如果操作符为或,则当且仅当两个表达式中至少有一个与某一用户相匹配时,该表达式与该用户相匹配。例如,表达式 &(1:2)(2:3) 可以与用户 1 相匹配,但不能与用户 2 相匹配;而表达式 |(1:2)(3:1) 则可以与两个用户都相匹配。

形式化地,上述语法用 BNF 范式表示如下:

NON_ZERO_DIGIT =  "1" / "2" / "3" / "4" / 
                  "5" / "6" / "7" / "8" / "9"
DIGIT          =  "0" / NON_ZERO_DIGIT
NUMBER         =  NON_ZERO_DIGIT / (NON_ZERO_DIGIT DIGIT*)
ATTRIBUTE      =  NUMBER
VALUE          =  NUMBER
OPERATOR       =  ":" / "~"
BASE_EXPR      =  ATTRIBUTE OPERATOR VALUE
LOGIC          =  "&" / "|"
EXPR           =  BASE_EXPR / (LOGIC "(" EXPR ")" "(" EXPR ")")

EASY_EXPR      =  BASE_EXPR / 
                  (LOGIC "(" BASE_EXPR ")" "(" BASE_EXPR ")")

输入格式

从标准输入读入数据。

输入的第一行包含一个正整数 n,表示用户的数目。

接下来 n 行,每行包含空格分隔的若干个正整数,第一个正整数表示该用户的 DN,第二个正整数表示该用户具有的属性个数,此后的每两个正整数表示该用户具有的一个属性及其值。这些属性按照属性编号从小到大的顺序给出。

接下来一行包含一个正整数 m,表示匹配表达式的数目。

接下来 m 行,每行包含一个匹配表达式。

输出格式

输出到标准输出。

输出 m 行,每行包含零个或多个正整数,用空格分隔,表示与对应的匹配表达式相匹配的用户的 DN,由小到大排序。

样例输入1

2
1 2 1 2 2 3
2 2 2 3 3 1
4
1:2
3~1
&(1:2)(2:3)
|(1:2)(3:1)

样例输出1

1

1
1 2

样例解释

本组输入是题目描述中的例子。

子任务

对于 20% 的输入,有 1≤n≤100,1≤m≤10,每个用户的属性个数不超过 10,全部属性编号不超过 100,且表达式是原子表达式,即符合 BNF 语法 BASE_EXPR

对于 40% 的输入,有 1≤m≤100,每个用户的属性个数不超过 10,全部属性编号不超过 100,且表达式中至多含有两个原子表达式的逻辑组合,即符合 BNF 语法 EASY_EXPR

对于 70% 的输入,有全部属性编号不超过 500。

对于全部输入,有 1≤n≤2500,1≤m≤500,每个用户的属性个数不超过 500,全部属性编号、属性值和 DN 均不超过 109,每个表达式语句都符合题设语法,且语句字符长度不超过 2000。

真题来源:LDAP

感兴趣的同学可以如此编码进去进行练习提交

思路分析:

        主要是要解决表达式嵌套的问题,与栈实现计算器时维护一个符号栈、一个数值栈类似。这里维护了两个栈,一个符号栈op,一个bitset集合栈stk,集合求交、或,由bitset完成。当遇到&或|时,将符号压栈;当遇到)时,将bitset压栈;()内正常读取,求bitset即可。当同一个符号对应两个bitset在栈内(num[c]=2)时,将两个bitset运算为一个bitset。其余部分map乱搞,q[i][j]表示DN=i用户的j属性值,p(i,j)表示i属性值为j的有哪些用户,has[i]表示i属性有哪些用户,i:j操作时,p[i][j]即为所求;i~j操作时,has[i]内去掉p[i][j]即为所求。to[i]记录了第i个用户对应的DN值,输出时按DN从小到大排序即可。

 c++满分题解:

#includeusing namespace std;typedef long long ll;typedef pair P;const int N=2502;int n,m,sz,id,k,c,d,x,y,num[N],to[N],f[N];mapq[N];map>p;map>has;char s[N],op[N];bitsetstk[N*2],res;bitsetcal(int l,char x,int r){bitsetans;for(auto &v:p[P(l,r)]){ans.set(v);}if(x=='~'){for(auto &v:has[l]){ans.flip(v);}}return ans;}int main(){scanf("%d",&n);for(int i=1;i<=n;++i){scanf("%d%d",&id,&k);to[i]=id;for(int j=1;j<=k;++j){scanf("%d%d",&x,&y);q[i][x]=y;has[x].push_back(i);p[P(x,y)].push_back(i);}}scanf("%d",&m);for(int i=1;i<=m;++i){scanf("%s",s);sz=strlen(s);c=d=0;for(int j=0;j

运行结果:

来源地址:https://blog.csdn.net/weixin_53919192/article/details/131565996

阅读原文内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯