CCF CSP 202303-3 LDAP题解_csp202303-3

一道很简单的题，主要是看到BNF文法我就想写Parser，看见逻辑运算符就想写短路运算。然后浪费了很多时间。使用了类似解释器的结构，好像比一般用集合运算写快，但是时间限制是14s，所有没有任何作用。

`

//
// Created by 11067 on 2023/5/11.
//
#include <cstdio>
#include <unordered_map>
#include <set>
using namespace std;
 
 
enum class InstrType {
    JS,
    JNS,
    SEQ,
    SNE
};
struct Instr {
    InstrType type;
    int opr;
    int value;
};
Instr instrs[1000];
int pc;
int prog_length;
struct Record {
    unordered_map<int, int> attributes;
    int dn;
} records[2500];
 
 
//parse query
char buffer[2005];
int current;
 
int number() {
    int n = 0;
    while (buffer[current] >= '0' && buffer[current] <= '9') {
        n *= 10;
        n += buffer[current] - '0';
        current++;
    }
    return n;
}
 
void expr();
 
void base_expr() {
    int attribute = number();
    char op = buffer[current++];
    int value = number();
    instrs[pc++] = Instr{op == ':' ? InstrType::SEQ : InstrType::SNE, attribute, value};
}
 
void logic_or() {
    current += 2;
    expr();
    int back_patch = pc;
    instrs[pc++] = Instr{InstrType::JS, 0, 0};
    current += 2;
    expr();
    instrs[back_patch].value = pc;
    current += 1;
}
 
void logic_and() {
    current += 2;
    expr();
    int back_patch = pc;
    instrs[pc++] = Instr{InstrType::JNS, 0, 0};
    current += 2;
    expr();
    instrs[back_patch].value = pc;
    current += 1;
}
 
void expr() {
    char peek = buffer[current];
    if (peek == '&') {
        logic_and();
    } else if (peek == '|') {
        logic_or();
    } else {
        base_expr();
    }
}
 
// runner
 
 
int run(Record &record) {
    int flag = 0;
    pc = 0;
    while (pc < prog_length) {
        switch (instrs[pc].type) {
            case InstrType::JS:
                if (flag) {
                    pc = instrs[pc].value - 1;
                }
                break;
            case InstrType::JNS:
                if (!flag) {
                    pc = instrs[pc].value - 1;
                }
                break;
            case InstrType::SEQ:
                if (record.attributes.count(instrs[pc].opr) > 0 &&
                    record.attributes[instrs[pc].opr] == instrs[pc].value) {
                    flag = 1;
                } else {
                    flag = 0;
                }
                break;
            case InstrType::SNE:
                if (record.attributes.count(instrs[pc].opr) > 0 &&
                    record.attributes[instrs[pc].opr] != instrs[pc].value) {
                    flag = 1;
                } else {
                    flag = 0;
                }
                break;
        }
        pc++;
    }
    return flag;
}
 
 
int main() {
    int n, m;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        auto &record = records[i];
        scanf("%d", &record.dn);
        int t;
        scanf("%d", &t);
        for (int j = 0; j < t; ++j) {
            int k, v;
            scanf("%d %d", &k, &v);
            record.attributes.insert({k, v});
        }
    }
    scanf("%d", &m);
    for (int i = 0; i < m; ++i) {
        scanf("%s", buffer);
        pc = 0;
        current = 0;
        expr();
        prog_length = pc;
        set<int> ans;
        for (int j = 0; j < n; ++j) {
            auto &record = records[j];
 
            if (run(record)) {
                ans.insert(record.dn);
            }
        }
        for (const auto& e: ans) {
            printf("%d ", e);
        }
        putchar('\n');
    }
    return 0;
}