算法1
使用结构体直接使用unordered_map查找比后面使用循环快不少
当然正如很多代码,我这份代码也是在acwing上过不去,但是ccf官网上面可以过
C++ 代码
#include <bits/stdc++.h>
//#define int long long
#define eb emplace_back
#define pii pair<int,int>
using namespace std;
const int N=1e3+10;
using ll=long long;
int n,m,q;
struct node
{
string ndsname;
unordered_map<string,bool>ops;//记录当前用户可以执行的操作
unordered_map<string,bool>categories;//记录操作的种类
unordered_map<string,bool>names;//记录操作的名称
};
unordered_map<string,node>nds;
unordered_map<string,vector<string>>groups;//每个组中下的用户名字
unordered_map<string,vector<string>>usrs;//每个用户和其他的用户的关联情况
void solve()
{
cin>>n>>m>>q;
for(int i=0;i<n;++i)
{
string name;
cin>>name;
int nv,no,nn;
cin>>nv;
for(int i=0;i<nv;++i)
{
string tmp;
cin>>tmp;
nds[name].ops[tmp]=1;
}
cin>>no;
for(int i=0;i<no;++i)
{
string tmp;
cin>>tmp;
nds[name].categories[tmp]=1;
}
cin>>nn;
for(int i=0;i<nn;++i)
{
string tmp;
cin>>tmp;
nds[name].names[tmp]=1;
}
if(nn==0)nds[name].names["*"]=1;
}
for(int i=0;i<m;++i)
{
string namestr;
cin>>namestr;
int ns;cin>>ns;
for(int i=0;i<ns;++i)
{
char ch; string link;
cin>>ch>>link;
if(ch=='g')
{
groups[link].eb(namestr);
}
else if(ch=='u')
{
usrs[link].eb(namestr);
}
}
}
while(q--)
{
vector<string>links;//关联的用户名称
string chaname;
cin>>chaname;
// cout<<"chaname "<<chaname<<"\n";
int ng;
cin>>ng;
for(auto &it:usrs[chaname])links.eb(it);//注意一个字符串ng只是代表一个组的名字,不是代表和当前 查询直接关联的名字
for(int i=0;i<ng;++i)
{
string curname;
cin>>curname;
if(groups.count(curname)!=0)//组全部相关
{
vector<string>vec=groups[curname];
for(auto &it:vec)links.eb(it);
}
}
string curop,curcate,curname;
cin>>curop>>curcate>>curname;
bool flag=0;
for(auto &name:links)
{
if(nds[name].names.count("*")==0 and nds[name].names.count(curname)==0)continue;
else if(nds[name].categories.count("*")==0 and nds[name].categories.count(curcate)==0)continue;
else if(nds[name].ops.count("*")==0 and nds[name].ops.count(curop)==0)continue;
else
{
flag=1;
break;
}
}
if(flag)cout<<1<<"\n";
else cout<<0<<"\n";
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int T=1;
while(T--)solve();
return 0;
}
/*
*/
算法2 70分超时
一开始直接全部都放入了unordered_map,导致最后便利的时候超时了
C++ 代码
#include <bits/stdc++.h>
//#define int long long
#define eb emplace_back
#define pii pair<int,int>
using namespace std;
const int N=1e3+10;
using ll=long long;
int n,m,q;
unordered_map<string,vector<string>>ops;//记录当前用户可以执行的操作
unordered_map<string,vector<string>>categories;//记录操作的种类
unordered_map<string,vector<string>>names;//记录操作的名称
unordered_map<string,vector<string>>groups;//每个组中下的用户名字
unordered_map<string,vector<string>>usrs;//每个用户和其他的用户的关联情况
void solve()
{
cin>>n>>m>>q;
for(int i=0;i<n;++i)
{
string name;
cin>>name;
int nv,no,nn;
vector<string>caozuo;
vector<string>zhonglei;
vector<string>mingzi;
cin>>nv;
for(int i=0;i<nv;++i)
{
string tmp;
cin>>tmp;
caozuo.eb(tmp);
}
cin>>no;
for(int i=0;i<no;++i)
{
string tmp;
cin>>tmp;
zhonglei.eb(tmp);
}
cin>>nn;
for(int i=0;i<nn;++i)
{
string tmp;
cin>>tmp;
mingzi.eb(tmp);
}
if(nn==0) mingzi.eb("*");
ops[name]=caozuo;
categories[name]=zhonglei;
names[name]=mingzi;
// for(auto it:ops[name])cout<<it<<"==\n";
// for(auto it:categories[name])cout<<it<<"==\n";
// for(auto it:names[name])cout<<it<<"==\n";
}
for(int i=0;i<m;++i)
{
string namestr;
cin>>namestr;
int ns;cin>>ns;
for(int i=0;i<ns;++i)
{
char ch; string link;
cin>>ch>>link;
if(ch=='g')
{
groups[link].eb(namestr);
}
else if(ch=='u')
{
usrs[link].eb(namestr);
}
}
}
while(q--)
{
vector<string>links;//关联的用户名称
string chaname;
cin>>chaname;
// cout<<"chaname "<<chaname<<"\n";
int ng;
cin>>ng;
for(auto &it:usrs[chaname])links.eb(it);//注意一个字符串ng只是代表一个组的名字,不是代表和当前 查询直接关联的名字
for(int i=0;i<ng;++i)
{
string curname;
cin>>curname;
if(groups.count(curname)!=0)//组全部相关
{
vector<string>vec=groups[curname];
for(auto &it:vec)links.eb(it);
}
}
string curop,curcate,curname;
cin>>curop>>curcate>>curname;
bool flag=0;
for(auto &it:links)
{
// cout<<"it "<<it<<"\n";
// cout<<"\n";
bool flag1=0,flag2=0,flag3=0;
for(auto& nxt:names[it])
{
// cout<<nxt<<"**\n";
if(nxt==curname or nxt=="*")
{
flag3=1;
break;
}
}
for(auto& nxt:categories[it])
{
if(nxt==curcate or nxt=="*")
{
flag2=1;
break;
}
}
for(auto &nxt:ops[it])
{
if(nxt==curop or nxt=="*")
{
flag1=1;
break;
}
}
if(flag1 and flag2 and flag3)
{
flag=1;
break;
}
}
if(flag)cout<<1<<"\n";
else cout<<0<<"\n";
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int T=1;
while(T--)solve();
return 0;
}
/*
*/