CCF刷题计划——LDAP（交集、并集 how to go）

LDAP

计算机软件能力认证考试系统

不知道为什么，直接给我报一个运行错误，得了0分。但是我在Dev里，VS里面都跑的好好的，奇奇怪怪。如果有大佬路过，请帮小弟看看QWQ。本题学到的：交集set_intersection、并集set_union的使用

这道题按照常规思路来说的话并不复杂，其实就是一个集合的差集、并集、交集的问题。我的思路里，因为最后想要得到关于DN的集合，所以我以属性编号和属性值作为索引（也就是map中的键值），用set存在了DN。map<int, map<int, set<int>>>mp; //属性序号，属性值，id集合，这样的好处是，如果想得到某一属性下值为val的DN的集合，可以直接来：set<int>target = mp[attr][val];，然后再对这个集合进行后续的处理会方便很多。通过手写差集、交集、并集，最后也是成功做出来了，在其他编译环境下测试样例也是过的好好的，但是提交的时候运行错误我是真的会谢……

运行错误，but样例过了：

#include <iostream>
#include <string>
#include <set>
#include <algorithm>
#include <map>
using namespace std;
const int M = 502;
const int N = 2502;int n, m;
map<int, map<int, set<int>>>mp;	//属性序号，属性值，id集合
set<int>totalId;
bool book[N][M] = { false };	//book[id][attr] id的 attr属性 是否存在//毕竟不是求真的差集，魔改一下也是可以的
set<int>different(set<int>s1, set<int>s2,int attr)	//默认s1-s2（s1要大）
{set<int>temp;for (auto it1 = s1.begin(), it2 = s2.begin(); it2 != s2.end();){if ((*it1) < (*it2)){if(book[(*it1)][attr])	//如果这个属性存在temp.insert((*it1));	//不相同，将值插入新的setit1++;	//因为是求差集，所以只会出现it1比it2慢的情况，这时让it1加把劲}else	{it1++; it2++;	//否则两个都并进}}return temp;
}set<int>Same(set<int>s1, set<int>s2)
{set<int>temp;//让s1大if (s1.size() < s2.size()){temp = s1;s1 = s2;s2 = temp;}//遍历s2，看s1有没有temp.clear();for (auto it : s2){if (s1.find(it) != s1.end())	//如果存在temp.insert(it);	//s1存在，说明交集上了}return temp;
}set<int>Union(set<int>s1, set<int>s2)	//并集
{set<int>temp;//让s1大if (s1.size() < s2.size()){temp = s1;s1 = s2;s2 = s1;}temp = s1;//将s2的元素都添加到s1中for (auto it : s2)temp.insert(it);	//s1存在，说明交集上了return temp;
}set<int> baseDeal(string s)
{int attr, val;int pos = 1;while (s[pos] >= '0' && s[pos] <= '9')	pos++;attr = stoi(s.substr(0, pos));val = stoi(s.substr(pos + 1));set<int>target = mp[attr][val];if (s[pos] == ':')	//断言，找同属性同值的id集合 return target;	//就是我们之前存的那些 else //非断言，其实就是求id总集和mp集合中的差集{//set_difference(totalId.begin(), totalId.end(), target.begin(), target.end(), temp.begin());return different(totalId, target,attr);}}set<int> easyDeal(string s)
{//将两个base分离string b1, b2;int pos=2;while (s[pos]!=')')	pos++;	//找到括号b1 = s.substr(2, pos - 2);	//第一个num:numint tpos = pos + 2;	//定位到第一个数字，记录下来pos++;while (s[pos] != ')')	pos++;b2 = s.substr(tpos, pos - tpos);set<int>temp1 = baseDeal(b1);set<int>temp2 = baseDeal(b2);if (s[0] == '&')	return Same(temp1, temp2);else				return Union(temp1, temp2);
}int main()
{cin >> n;int id, cnt, attr, val;	//DN，属性个数，属性序号，属性值 for (int i = 0; i < n; i++){cin >> id >> cnt;totalId.insert(id);while (cnt--){cin >> attr >> val;mp[attr][val].insert(id);		//id号attr属性的值是val book[id][attr] = true;}}cin >> m;string str;set<int> ans;while (m--){cin >> str;if (str[0] >= '0' && str[0] <= '9')	//BASE_EXPRans = baseDeal(str);else	ans = easyDeal(str);for (auto it : ans)	cout << it << " ";cout << endl;}return 0;
}

看了题解，发现和我的思路差不多，但是相对而言使用了 set_intersection、set_union 这两个已经写好的函数。所以根本不需要自己写首先并集、交集。

注意，使用set只能过70%，使用unordered_map和vector可以更快，不会超时。

AC：

#include <Iostream>
#include <unordered_map>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;unordered_map<int,unordered_map<int,set<int>>>mp;	// <属性序号，<属性值，DN集合>> 
unordered_map<int,set<int>>book;int n,m; vector<int> baseDeal(string s)
{int attr=0, val=0;int i,j;for(i=0;isdigit(s[i]);i++) attr=attr*10+s[i]-'0';//属性编号for(j=i+1;j<s.size();j++) val=val*10+s[j]-'0';//属性vector<int> temp;if (s[i] == ':')	//断言，找同属性同值的id集合{for(auto it:mp[attr][val])	//就是我们之前存的那些temp.push_back(it); }else //非断言，其实就是求id总集和mp集合中的差集{for(auto it:book[attr])	//遍历存在这个属性的所有DNif(!mp[attr][val].count(it))	//如果不存在，那就加进去temp.push_back(it);return temp;}
}vector<int> solve(string str)
{if(str[0]!='&'&&str[0]!='|') 	return baseDeal(str);//基本表达式//走到这里的都是复合表达式vector<int> ans,ans1,ans2;int p=2;for(int num=1;num;p++){//根据括号数量获得两个表达式if(str[p]==')') num--;if(str[p]=='(') num++;}ans1=solve(str.substr(2,p-3));ans2=solve(str.substr(p+1,str.size()-p-2));if(str[0]=='&')	//交集set_intersection(ans1.begin(),ans1.end(),ans2.begin(),ans2.end(),inserter(ans,ans.begin()));else	//并集set_union(ans1.begin(),ans1.end(),ans2.begin(),ans2.end(),inserter(ans,ans.begin()));return ans;
}int main()
{cin>>n;int id, cnt, attr, val;	//DN，属性个数，属性序号，属性值 for (int i = 0; i < n; i++){cin >> id >> cnt;while (cnt--){cin >> attr >> val;mp[attr][val].insert(id);		//attr 属性 值为val 的有 这些id book[attr].insert(id);			//标记这些属性在这些id中存在 }}cin>>m;while(m--) {string s; cin>>s;vector<int> ans=solve(s);for(auto it:ans) cout<<it<<" ";cout<<endl;}return 0;} 

参考代码：【CCF-CSP】 202303-3 LDAP_csp ldap-CSDN博客