202206-3 CCF 角色授权 （运用stl容器模拟 + 优化 满分题解）

问题描述

角色授权 题目链接

解题思路

这个题目和上一年的第三题十分相似，感觉是同一类型的题目，主要就是考察能否熟练的运用STL容器
首先，通读题目，理清思路，再动手写，这个很关键，还没理清楚，就开始写，逻辑上会有很多漏洞，难以调试
题目的主要意思就是
角色有名字，操作，资源等等
每一个角色有相关的拥有者或拥有组
然后给你一个人，以及需要进行的操作，问你这个人能不能执行这个操作
然后就可以根据题目细节，思考如何设计数据结构了
例如：
判断一个用户能否执行某个操作的过程，首先需要将这个人所关联的角色找出来
由于一个人可能与多个角色相关联
所以可以设计一个 unordered_map > 用来存储每个人（或组）拥有哪些角色

判断一个角色是否有xx操作，xx资源种类，xx资源
可以设计一个结构体，并且这个结构体里有三个unordered_map 这样就可以直接判断是否有xx

每一个角色都设计成结构体了，如何快速查找某个角色？
再设计一个unordered_map 用于将角色名称与结构体下标进行匹配，这样通过角色的名称就可以快速的找到对应的角色结构体

等等
将这些结构体设计出来之后
再根据题目中判断的依据，一步一步模拟就可以了（不是很难，详情见代码）

然后可能只有70+
还需要优化一下
如果最后一个查询循环里，有很多循环，尝试着进行删减或预处理，减少循环，因为可以算一下，时间复杂度可能会超
还有一个优化的点就是，这个题目的输入数据量不小，可以自己算一下，所以使用ios::sync_with_stdio(false);，时间就得到优化
得到满分啦
其实这个题目思路理清楚了，并熟练运用stl容器的话，真的不是特别难，简单的模拟就可以得70+，再小优化一下，就可以拿满分

代码实现

#include 
#include 
#include 
#include 

using namespace std;

const int N = 510;

map<string, vector <string> > rolecon; //记录该用户与哪些角色相匹配
map<string, int> rid; //记录角色所对应的结构体下标

struct role
{
    string name;
    map <string, int> opset;
    map <string, int> rskind;
    map <string, int> rsname;
}R[N];

bool check (string rolename, string opname, string rskd, string rsne)
{
    bool flag = true;
    int id = rid[rolename];

    if ((R[id].opset.count("*") == 0) && (R[id].opset.count(opname) == 0)) return false;
    if ((R[id].rskind.count("*") == 0) && (R[id].rskind.count(rskd) == 0)) return false;
    if ((R[id].rsname.size() != 0) && (R[id].rsname.count(rsne) == 0)) return false;
    return true;
}

int main()
{
    ios::sync_with_stdio(false);
    int n, m, q;
    cin >> n >> m >> q;

    //保存角色内容
    for (int i = 0; i < n; i ++)
    {
        string name;
        cin >> name;
        R[i].name = name;
        rid[name] = i;

        int opnum;
        cin >> opnum;
        for (int j = 0; j < opnum; j ++)
        {
            string t;
            cin >> t;
            R[i].opset[t] = 1;
        }

        int rk;
        cin >> rk;
        for (int j = 0; j < rk; j ++)
        {
            string t;
            cin >> t;
            R[i].rskind[t] = 1;
        }

        int rn;
        cin >> rn;
        for (int j = 0; j < rn; j ++)
        {
            string t;
            cin >> t;
            R[i].rsname[t] = 1;
        }
    }

    //存储用户或组分别拥有哪些角色
    for (int i = 0; i < m; i ++)
    {
        string rname;
        cin >> rname;

        int rcnt;
        cin >> rcnt;
        for (int j = 0; j < rcnt; j ++)
        {
            string kind, name;
            cin >> kind >> name;

            rolecon[name].push_back(rname);
        }
    }

    while (q --)
    {
        string pname;
        cin >> pname;

        int zulen;
        cin >> zulen;
        vector <string> yongzu;
        for (int i = 0; i < zulen; i ++)
        {
            string t;
            cin >> t;
            yongzu.push_back(t);
        }
        string opname, sk, sn;
        cin >> opname >> sk >> sn;

        bool flag = false;

        for (int i = 0; i < rolecon[pname].size(); i ++)
        {
            if (check(rolecon[pname][i], opname, sk, sn))
                {
                    flag = true;
                    break;
                }
        }
        if (flag)
        {
            cout << 1 << endl;
            continue;
        }

        for (int i = 0; i < yongzu.size(); i ++)
        {
            string zname = yongzu[i];
            for (int j = 0; j < rolecon[zname].size(); j ++)
            {
                if (check(rolecon[zname][j], opname, sk, sn))
                {
                    flag = true;
                    break;
                }
            }
            if (flag) break;
        }
        if (flag) cout << 1 << endl;
        else cout << 0 << endl;
    }

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142