题解：P16696 [CSPro 29] LDAP

AlgodQ_Q · 2026-07-24 16:00:51 · 题解

P16696题解

传送门

这道题最大的难点是读题，我说的。

题意

现有 n 个用户，每个用户都有唯一的 DN 和若干属性（属性构成为属性编号和该属性值），又给你 m 个表达式，每条表达式按如下规则来筛选用户：

• 原子表达式：有 2 种：如果是a:v，那么就要去寻找所有拥有属性编号为 a 且该属性值为 v 的用户；如果是a~v，那么就要去寻找所有属性编号为 a 但该属性值不为 v 的用户。

• 逻辑表达式：有 2 种：如果是&(表达式1):(表达式2)，那么就要去找所有表达式1和表达式2都满足的用户；如果是|表达式1):(表达式2)，那么就要去找所有满足表达式1或表达式2的用户。

  思路

  如果你读懂了题，那么这道题你就完成了一半。

注意到 n\le 2500，所以我们可以通过 bitset 去表示一个用户集合，如果第 i 位为 1 就相当于 i 属于该集合（1\le i\le n），这样我们就完成了该题的 4 个操作。

为了避免过多次处理a:v和a~v操作导致 TLE，我们需要预处理。首先我们要扫描所有的表达式，提取其中所有出现的属性编号和该属性的值。接着我们可以通过定义两个 bitset 来预处理：

• have[a]：表示拥有 a 属性的所有用户。

• eq[a][v]：表示属性编号为 a 且该属性值恰好为 v 的所有用户。

然后遍历所有用户，根据他们的属性去填充这些 bitset。

注意到题目中的所有表达式都符合巴科斯范式，我们可以通过递归去解析这些表达式。

首先我们要维护一个位置指针 pos 表示当前要读取的字符的位置。如果 pos 所指向的字符为&或|，就是逻辑表达式：首先读取这个操作符，跳过(去解析左子表达式，再跳过)和(去解析右子表达式，再跳过)，最后根据操作符来返回结果；否则就是原子表达式：如果操作符是:，直接返回eq[a][v]即可；不然就是~，返回have[a]&~eq[a][v]即可。

最后附上代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,a[2505],b[2505],c[2505][505],d[2505][505],q;
string s[505];
map<int,bitset<2505> >mp;                           //对应have[a] 
map<int,map<int,bitset<2505> > >mp2;                //对应eq[a][v] 
bitset<2505>run(int &x,string s){
    if(s[x]=='&'||s[x]=='|'){
        char op=s[x];
        x+=2;
        bitset<2505>l=run(x,s);
        x+=2;
        bitset<2505>r=run(x,s);
        x++;
        if(op=='&'){
            return l&r;
        }else{
            return l|r;
        }
    }else{
        int num=0,nnum=0;
        while(x<s.size()&&s[x]>='0'&&s[x]<='9'){
            num=num*10+s[x]-'0';
            x++;
        }char op=s[x];
        x++;
        while(x<s.size()&&s[x]>='0'&&s[x]<='9'){
            nnum=nnum*10+s[x]-'0';
            x++;
        }bitset<2505>ans;
        if(op==':'){
            map<int,map<int,bitset<2505> > >::iterator i1=mp2.find(num);
            if(i1!=mp2.end()){
                map<int,bitset<2505> >::iterator i2=i1->second.find(nnum);
                if(i2!=i1->second.end()){
                    ans=i2->second;
                }
            }
        }else{
            map<int,bitset<2505> >::iterator i1=mp.find(num);
            if(i1!=mp.end()){
                ans=i1->second;
                map<int,map<int,bitset<2505> > >::iterator i2=mp2.find(num);
                if(i2!=mp2.end()){
                    map<int,bitset<2505> >::iterator i3=i2->second.find(nnum);
                    if(i3!=i2->second.end()){
                        ans&=~(i3->second);
                    }
                }
            }
        }return ans;
    }
}void print(bitset<2505>&ans){
    vector<int>vec;
    for(int i=1;i<=n;i++){
        if(ans.test(i-1)){
            vec.push_back(a[i]);
        }
    }sort(vec.begin(),vec.end());
    for(int i=0;i<vec.size();i++){
        cout<<vec[i]<<" ";
    }cout<<endl;
}signed main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i]>>b[i];
        for(int j=1;j<=b[i];j++){
            cin>>c[i][j]>>d[i][j];
        }
    }cin>>q;
    for(int i=1;i<=q;i++){
        cin>>s[i];
    }
    //提取所有出现的属性编号和该属性的值 
    set<int>sx;
    set<pair<int,int> >v;
    for(int i=1;i<=q;i++){
        int p=0;
        while(p<s[i].size()){
            if(s[i][p]>='0'&&s[i][p]<='9'){
                int x=0,xx=0;
                while(p<s[i].size()&&s[i][p]>='0'&&s[i][p]<='9'){
                    x=x*10+s[i][p]-'0';
                    p++;
                }char op=s[i][p];
                p++;
                while(p<s[i].size()&&s[i][p]>='0'&&s[i][p]<='9'){
                    xx=xx*10+s[i][p]-'0';
                    p++;
                }sx.insert(x);
                v.insert(make_pair(x,xx));
            }else{
                p++;
            }
        }
    }for(set<int>::iterator i=sx.begin();i!=sx.end();i++){
        mp[*i]=bitset<2505>();
    }for(set<pair<int,int> >::iterator i=v.begin();i!=v.end();i++){
        mp2[i->first][i->second]=bitset<2505>();
    }
    //预处理 
    for(int i=1;i<=n;i++){
        for(int j=1;j<=b[i];j++){
            map<int,bitset<2505> >::iterator i1=mp.find(c[i][j]);
            if(i1!=mp.end()){
                i1->second.set(i-1);
            }map<int,map<int,bitset<2505> > >::iterator i2=mp2.find(c[i][j]);
            if(i2!=mp2.end()){
                map<int,bitset<2505> >::iterator i3=i2->second.find(d[i][j]);
                if(i3!=i2->second.end()){
                    i3->second.set(i-1);
                }
            }
        }
    }for(int i=1;i<=q;i++){
        int pos=0;
        bitset<2505>bs=run(pos,s[i]);
        print(bs);
    }
}