AC的快乐无与伦比!
本蒟蒻刚看到这道题时,就被超长的题干和复杂的关系唬住了。
于是学习了各路大神的解法,终于AC 成功照虎画猫了!
现将在此过程中学到的种种知识总结如下,作为本小白菜(不但小白还有菜)的编程笔记。
Attention:
一、C++中的万能头文件
#include<bits/stdc++.h>
在学习许多大神的代码中,发现这个头文件被使用的频率很高。
它是C++中支持的一个几乎万能的头文件,几乎包含所有的可用到的C++库函数。以后写代码就可以直接引用这一个头文件了,不需要在写一大堆vector、string、map、stack……
最初我的vscode中写入这个头文件会提示错误,是因为本地没有该头文件的具体内容。观察发现这是一个stdc++.h,在bits的文件中,因此在头文件iostream所在的文件,创建新文件夹bits,在其中写入stdc++.h就可。
二、题目理解
因为本蒟蒻的记忆能力堪忧,只能通过非常直接的变量命名来告知自己其含义。
最初不明晰各个事物的联系,不知如何组织数据结构,后来找到一个解析是从输入进行入手进行组织分析,甚好。
因此,以下分析也从输入入手:
①输入角色数量roleNum、角色关联数量roleRelatedNum、待检查的操作数量opToCheckNum。
接下来将会根据数量分别循环依次输入对应信息。
②输入角色相关信息。
对于这个重要的中心角色,我们使用结构体来组织数据。
struct role
{
string name;
map<string, int>op, resKind, resName;
}role[501];
建立起操作名、资源种类名、资源名到01(是否存在)的映射。如果该角色存在string s的操作名,则有role[i].op[s] = 1存在。
那么为什么不将这三类的数量也存入结构体里呢?
最初我是也存的,但是发现之后也用处不大,还占地方,就直接用三个变量opNum、resKindNum、resNameNum直接即时for循环处理之后要读入的相应数据了。
这里还用到一个数据结构是
map<string, int>nameID;
即建立起角色名称到其序号ID的一个映射。
③输入角色关联相关信息。
用户和用户组没有很大区别,可不作区分,这里的重点是,对于每个新用户或用户组(g或u后的字符串),计入与其对应的角色ID(每组输入的第一个字符串)。
map<string, vector<int>>conNameID;
第一次见识了vector。
vector是向量类型,可以容纳许多类型的数据,因此也被称为容器
比如我想让新用户temp存入与其关联的角色id,就
conNameID[temp].push_back(id);
让人不禁感叹,真是简洁又漂亮。
④输入待检查的操作+检查。
使用string group[404]来存放每个操作对应的组。
对于每个要执行操作的用户,先查其在步骤③存的一些关联的角色,使用check检查是否在该角色与之关联的情况下,后续操作是否可行。
这里for循环中使用
conNameID[temp].size()
表示用户temp关联的角色数量。
如果失败,那就再看我们本次输入中给的用户组,对于某一用户组在步骤③存的一些关联角色,使用check检查是否在该角色与之关联的情况下,后续操作是否可行。
其中利用flag标识已确认操作可行,及时退出循环。
⑤check检查是否可行的函数
三层if判断,拿第一层举例:
if((role[id].op.count(o) && role[id].op[o])||( role[id].op.count("*") && role[id].op["*"]))
检查角色是否有待检查的o操作,或者有通配符*标记着任何操作都可行。
大佬的check函数写得真好真妙! 我能说count()这个函数还是第一次见吗
函数返回值是bool类型,之前我一直习惯用int类型的01表示对错。
在一次次地运行超时中,终于动脑子查为啥别人用bool!
bool型变量占用内存一个字节,int型变量占用四个字节。
由于bool型变量只分0或非0,即false(0x00)或者true(0x01)。
在需要逻辑判断时可以使用bool型,可以避免使用int导致运行超时。
AC代码如下:
#include<bits/stdc++.h>
using namespace std;
struct role
{
string name;
map<string, int>op, resKind, resName;
}role[501];
map<string, int>nameID;
map<string, vector<int>>conNameID;
int roleNum, roleRelatedNum, opToCheckNum;
int resNameNum, opNum, resKindNum, id, conObNum;
int groupNum, flag = 0;
string temp;
string group[404], opName, resKind, resName;
bool check(int id,const string &o,const string &z,const string &m)
{
if((role[id].op.count(o) && role[id].op[o])||( role[id].op.count("*") && role[id].op["*"]))
if((role[id].resKind.count(z) && role[id].resKind[z]) ||(role[id].resKind.count("*") && role[id].resKind["*"]))
if((role[id].resName.count(m) && role[id].resName[m] )|| role[id].resName.size() == 0)
return true;
return false;
}
int main()
{
cin>>roleNum>>roleRelatedNum>>opToCheckNum;
for(int i = 0; i < roleNum; ++i)
{
cin>>role[i].name>>opNum;
nameID[role[i].name] = i;
for(int j = 0; j < opNum; ++j)
{
cin>>temp;role[i].op[temp] = 1;
}
cin>>resKindNum;
for(int j = 0; j < resKindNum; ++j)
{
cin>>temp;role[i].resKind[temp] = 1;
}
cin>>resNameNum;
for(int j = 0; j < resNameNum; ++j)
{
cin>>temp;role[i].resName[temp] = 1;
}
}
for(int i = 0; i < roleRelatedNum; ++i)
{
cin>>temp;
id = nameID[temp];
cin>>conObNum;
for(int j = 0; j < conObNum; ++j)
{
cin>>temp;
cin>>temp;
conNameID[temp].push_back(id);
}
}
for(int i = 0; i < opToCheckNum; ++i)
{
flag = 0;
cin>>temp>>groupNum;
for(int j = 0; j < groupNum; ++j)
cin>>group[j];
cin>>opName>>resKind>>resName;
for(int j = 0; j < conNameID[temp].size(); ++j)
{
int id = conNameID[temp][j];
if(check(id, opName, resKind, resName))
{
flag = 1;
break;
}
}
if(!flag)
{
for(int j = 0; j < groupNum; ++j)
{
for(int k = 0; k < conNameID[group[j]].size(); ++k)
{
int id = conNameID[group[j]][k];
if(check(id, opName, resKind, resName))
{
flag = 1;
break;
}
}
if(flag)break;
}
}
cout<<flag<<endl;
}
return 0;
}
经此一役,发现map是个好东西,原来是非常常用的数据结构,它在第二题与第三题中都起了不可或缺的关键作用。
此过程中,通过拜读他人的优秀代码而从中窥得的算法分析、数据结构组织、编程习惯等,本蒟蒻也深深感受到了巨大的差距,实在道阻且长。