CCF CSP 202303-3 LDAP题解

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

`

//
// Created by 11067 on 2023/5/11.
//
#include 
#include 
#include 
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 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();}
}// runnerint 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 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;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！