202206-1 归一化处理
题目：202206-1
题目分析：
给出了数学上归一化的数学公式，直接按照要求完成即可。
AC代码：
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
double a[n];
double sum = 0;
for (int i = 0; i < n; i++)
{
cin >> a[i];
sum += a[i];
}
double average = sum / n;
double dtotal = 0;
for (int i = 0; i < n; i++)
{
dtotal += (a[i] - average) * (a[i] - average);
}
dtotal /= n;
for (int i = 0; i < n; i++)
{
cout << (a[i] - average) / sqrt(dtotal) << endl;
}
return 0;
}
202206-2 寻宝！大冒险！
为什么我的第一想法是这个？？？
题目：202206-2
题目分析：
【再更新】
60分代码：
【再更新】
70分代码：
【再更新】
AC代码：
【再更新】
202206-3 角色授权
题目分析：
在学习了数据库之后，对于这道题会更加熟悉。实际上本题就是模拟了数据库对于用户权限的管理。
这道大模拟题主要就是概念很复杂，不容易快速上手理解。
总结如下：
- 用户：主体
- 用户组：用户组里包括很多用户，这些用户有相同的权限
- 角色：指明了一个用户可以执行的操作
- 角色关联：一个用户和一个或多个角色之间的关系，角色关联是一个映射<角色，用户/用户组>
- 待授权行为：包括主体，操作，资源三个部分
判断一个用户能否执行某个操作的过程是：
- 检查所有的角色关联的授权对象清单，如果清单中包含该用户的名称，或者该清单中包含该用户所属的某一个用户组的名称，那么选取该角色关联所关联的角色；
- 对于所有被选取的角色，判断这些角色是否能对该资源执行该操作，如果所有角色都不能执行该操作，那么不能执行该操作；
- 允许执行该操作。
判断一个角色能否对某个资源执行某个操作的过程是：
- 检查该角色的操作清单，如果该角色的操作清单中不包含该操作，且该角色的操作清单中也不包含字符串
*，那么不能执行该操作； - 检查该角色的资源种类清单，如果该角色的资源种类清单中不包含该资源的种类，且该角色的资源种类清单中也不包含字符串
*，那么不能执行该操作； - 检查该角色的资源名称清单，如果该角色的资源名称清单中不包含该资源的名称，且该角色的资源名称清单不是空数组，那么不能执行该操作；
- 允许执行该操作。
实际上只要从头到尾执行一遍题目的过程并且不遗漏，就可以拿到大部分的分数。
【注意】一定要按照题目要求由用户->角色再判断是否满足操作、资源类型、资源名。不能直接将角色的权限分配向用户。即不要对于用户A，我知道他有角色BCD，就直接把BCD的操作、资源类型、资源名分别求并，存储在角色A下，这样看上去虽然会简单好多，似乎是优化了。但这样不等价于题目的赋值方式。
反例：
用户A被赋予角色BC
角色B：操作abc、资源类型x、资源名y
角色C：操作def、资源类型z、资源名w
现在询问用户A是否可以操作a，资源类型z，资源名y，这是不可以的。
70分代码：
这个就是从头到尾纯模拟题目的意思，包括存储的结构和执行的操作，都是完全按照题目来的。
具体来说：
前面是读入并存储题目信息。
然后对于每一个被查询的用户（外层循环），先遍历角色链接这个结构体，寻找是否有角色的u数组包含这个用户（这个是单层循环），或者g数组包含这个用户所属的用户组（角色链接一重循环，用户组数组一重循环，这里是两重循环）。现在得到所有包含这个用户的角色，把它们放在一个vector里。
最后遍历这个vector，查看这些角色的所有权限，看看有没有执行被询问的操作、资源种类、资源名的权限。
这个方法实现的瓶颈在于外层循环内的两重循环，最坏的情况下，外层循环q，内层循环m*ng，就需要q*m*ng，5000*500*400，这能达到10^9，这已经是超时了，一般10^8对应1s的数量级，这都需要10s了。因此这个方法只能拿70%数据点。
下面是代码（完全由本人完成）：
// -*- coding:utf-8 -*-
// File : 202206-3.cpp
// Time : 2024/03/26
// Author : wolf
#include <iostream>
#include <vector>
const int N = 501;
using namespace std;
// 存储角色信息
struct character
{
string name;
int nv;
vector<string> op;
int no;
vector<string> rtype;
int nn;
vector<string> rname;
};
// 存储角色与用户/用户组的链接
struct character_link
{
string cname;
struct character ch;
vector<string> u;
vector<string> g;
};
vector<character> c;
vector<character_link> c_link;
int main()
{
// 关闭同步
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
// 即使关闭同步，该算法还是会超时，这是算法本身的局限
int n, m, q;
cin >> n >> m >> q;
for (int i = 0; i < n; i++)
{
struct character ctemp;
cin >> ctemp.name;
cin >> ctemp.nv;
for (int j = 0; j < ctemp.nv; j++)
{
string temp;
cin >> temp;
ctemp.op.push_back(temp);
}
cin >> ctemp.no;
for (int j = 0; j < ctemp.no; j++)
{
string temp;
cin >> temp;
ctemp.rtype.push_back(temp);
}
cin >> ctemp.nn;
for (int j = 0; j < ctemp.nn; j++)
{
string temp;
cin >> temp;
ctemp.rname.push_back(temp);
}
c.push_back(ctemp);
}
for (int i = 0; i < m; i++)
{
struct character_link cltemp;
cin >> cltemp.cname;
for (unsigned int j = 0; j < c.size(); j++)
{
if (cltemp.cname == c[j].name)
{
cltemp.ch = c[j];
}
}
int ns;
cin >> ns;
for (int j = 0; j < ns; j++)
{
string ug, ugname;
cin >> ug >> ugname;
if (ug == "u")
{
cltemp.u.push_back(ugname);
}
else if (ug == "g")
{
cltemp.g.push_back(ugname);
}
else
{
cout << "error" << endl;
}
}
c_link.push_back(cltemp);
}
for (int i = 0; i < q; i++)
{
string query_user;
cin >> query_user;
int ng;
vector<string> query_ugroup;
cin >> ng;
for (int j = 0; j < ng; j++)
{
string uboxtemp;
cin >> uboxtemp;
query_ugroup.push_back(uboxtemp);
}
string query_op, query_rtype, query_rname;
cin >> query_op >> query_rtype >> query_rname;
// excute
int ans = 0; // default ok
vector<character> target_c;
for (unsigned int j = 0; j < c_link.size(); j++)
{
for (unsigned int k = 0; k < c_link[j].u.size(); k++)
{
if (query_user == c_link[j].u[k])
{
target_c.push_back(c_link[j].ch);
}
}
for (unsigned int k = 0; k < c_link[j].g.size(); k++)
{
for (unsigned int t = 0; t < query_ugroup.size(); t++)
{
if (query_ugroup[t] == c_link[j].g[k])
{
target_c.push_back(c_link[j].ch);
}
}
}
}
for (unsigned int j = 0; j < target_c.size(); j++)
{
character cnow = target_c[j];
// cout << cnow.name << endl;
int flag1 = false, flag2 = false, flag3 = false; // default no
for (unsigned int k = 0; k < cnow.op.size(); k++)
{
// cout << query_op << " " << cnow.op[k] << endl;
if (query_op == cnow.op[k] || cnow.op[k] == "*")
{
flag1 = true;
break;
}
}
if (flag1 == false)
continue;
for (unsigned int k = 0; k < cnow.rtype.size(); k++)
{
// cout << query_op << " " << cnow.op[k] << endl;
if (query_rtype == cnow.rtype[k] || cnow.rtype[k] == "*")
{
flag2 = true;
break;
}
}
if (flag2 == false)
continue;
if (cnow.rname.size() == 0)
flag3 = true;
else
{
for (unsigned int k = 0; k < cnow.rname.size(); k++)
{
if (query_rname == cnow.rname[k])
{
flag3 = true;
break;
}
}
}
if (flag3 == false)
continue;
// success
if (flag1 == true && flag2 == true && flag3 == true)
{
ans = 1;
break;
}
}
cout << ans << endl;
}
return 0;
}
AC代码：
基于上述的分析，我们可以发现瓶颈在于从角色链接去回溯用户对应的角色。如果我能从一开始就知道每一个用户对应哪些角色，是不是就能节省很多时间呢？c++真有这么神奇的数据结构。
使用STL库中的<map>，我们做了一些小改动：
建立<角色名称 - 角色本体>映射，在找到角色名称之后，可以使用find()直接对应到角色本体。
使用多元map保存用户，用户组和角色之间的关联关系，同样在拿到用户之后，使用find()就可以找到角色，不需要从角色的视角去遍历，使用多元map是因为对于一个用户键，可能有多个角色与之相对应，即一个用户被赋予了多个角色。
这里能显著提升效率，是因为<algorithm>中的find()，使用树结构查找，时间复杂度是O(logn)，显著大于从角色视角去for循环再验证用户/用户组在不在里面，这样是O(n)。
主要发现还是大量运用了STL库的“黑科技”。
【有参考】https://blog.csdn.net/Andy_Xie007/article/details/133800502
// -*- coding:utf-8 -*-
// File : 202206-3.cpp
// Time : 2024/03/26
// Author : wolf
#include <algorithm>
#include <iostream>
#include <map>
#include <set>
#include <unordered_set>
#include <vector>
// 有参考https://blog.csdn.net/Andy_Xie007/article/details/133800502
const int N = 501;
using namespace std;
struct character
{
string name;
set<string> op; // 操作
set<string> rtype; // 资源种类
set<string> rname; // 资源名称
// 使用unordered_set会加快速度：2.984s -> 2.39s
// unordered_set<string> op; / 操作
// unordered_set<string> rtype; // 资源种类
// unordered_set<string> rname; // 资源名称
};
map<string, character> c; // 角色名称 - 角色本体映射
// 使用find进行检索O(n)时间复杂度，比数组快
// 判断cnow角色是否有对(query_op,query_rtype,query_rname)的访问权限
// 使用&传递地址而不是参复制，节省大量时间，否则超时
int check(const character &cnow, const string &query_op, const string &query_rtype, const string &query_rname)
{
if (cnow.op.count(query_op) == 0 && cnow.op.count("*") == 0)
return 0;
if (cnow.rtype.count(query_rtype) == 0 && cnow.rtype.count("*") == 0)
return 0;
if (cnow.rname.count(query_rname) == 0 && !cnow.rname.empty())
return 0;
return 1;
}
int main()
{
// 关闭同步
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
// 加了以上三句话，由90->100
int n, m, q;
cin >> n >> m >> q;
for (int i = 0; i < n; i++)
{
struct character ctemp;
string temp;
int nv, no, nn;
cin >> ctemp.name;
cin >> nv;
for (int j = 0; j < nv; j++)
{
cin >> temp;
ctemp.op.insert(temp);
}
cin >> no;
for (int j = 0; j < no; j++)
{
cin >> temp;
ctemp.rtype.insert(temp);
}
cin >> nn;
for (int j = 0; j < nn; j++)
{
cin >> temp;
ctemp.rname.insert(temp);
}
c.insert(make_pair(ctemp.name, ctemp));
}
// 使用多元map保存用户，用户组和角色之间的关联关系，查找会很快
multimap<string, string> relative_u; // user - character
multimap<string, string> relative_g; // group - character
for (int i = 0; i < m; i++)
{
string cname;
cin >> cname;
int ns;
cin >> ns;
for (int j = 0; j < ns; j++)
{
string ug, ugname;
cin >> ug >> ugname;
if (ug == "u")
{
relative_u.insert(make_pair(ugname, cname));
}
else if (ug == "g")
{
relative_g.insert(make_pair(ugname, cname));
}
else
{
cout << "error" << endl;
}
}
}
for (int i = 0; i < q; i++)
{
string query_user;
cin >> query_user;
int ng;
cin >> ng;
vector<string> query_ugroup;
for (int j = 0; j < ng; j++)
{
string uboxtemp;
cin >> uboxtemp;
query_ugroup.push_back(uboxtemp);
}
string query_op, query_rtype, query_rname;
cin >> query_op >> query_rtype >> query_rname;
// excute
int flag = 0;
vector<character> target_c;
// u
pair<multimap<string, string>::iterator, multimap<string, string>::iterator> range_u = relative_u.equal_range(query_user);
// auto range_u = relative_u.equal_range(query_user);
for (auto it = range_u.first; it != range_u.second; it++)
{
if (check(c.find(it->second)->second, query_op, query_rtype, query_rname))
{
flag = 1;
break;
}
}
if (flag == 1)
{
cout << 1 << endl;
continue;
}
// g
for (unsigned int j = 0; j < query_ugroup.size(); j++)
{
pair<multimap<string, string>::iterator, multimap<string, string>::iterator> range_g = relative_g.equal_range(query_ugroup[j]);
// auto range_g = relative_g.equal_range(query_ugroup[j]);
for (auto it = range_g.first; it != range_g.second; it++)
{
if (check(c.find(it->second)->second, query_op, query_rtype, query_rname))
{
flag = 1;
break;
}
}
if (flag == 1)
{
break;
}
}
if (flag == 1)
{
cout << 1 << endl;
continue;
}
cout << 0 << endl;
}
return 0;
}
