有没有大佬做过CCF CSP201912-3 化学方程式
  • 板块题目总版
  • 楼主autohe
  • 当前回复0
  • 已保存回复1
  • 发布时间2024/3/29 02:13
  • 上次更新2024/3/29 15:50:40
查看原帖
有没有大佬做过CCF CSP201912-3 化学方程式
352299
autohe楼主2024/3/29 02:13

我做的题解总是90分,我实在找不出来错在哪儿了,求大佬们救救,感激不尽。 CCF官网的题目贴不出来不好意思,是CCF计算机职业资格认证考试的201912-3。

这是我的题解:

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <memory>
#include <vector>
#include <stack>
#include <unordered_map>
#include <utility>

#define MAX_LEN 1024

// H2+O2=H2O
// 2H2+O2=2H2O
// H2+Cl2=2NaCl
// H2+Cl2=2HCl
// CH4+2O2=CO2+2H2O
// CaCl2+2AgNO3=Ca(NO3)2+2AgCl
// 3Ba(OH)2+2H3PO4=6H2O+Ba3(PO4)2
// 3Ba(OH)2+2H3PO4=Ba3(PO4)2+6H2O
// 4Zn+10HNO3=4Zn(NO3)2+NH4NO3+3H2O
// 4Au+8NaCN+2H2O+O2=4Na(Au(CN)2)+4NaOH
// Cu+As=Cs+Au

using std::vector;
using std::stack;
using std::unordered_map;
using std::pair;
using std::hash;

enum TokenKind {
    Element,
    Number,
    Plus,
    EQ,
    OpenParen,
    CloseParen,
    End
};

struct Token {
    char str[50] = {0};
    int tokenLen = 1;
    TokenKind kind;
    int cnt = 0;

    bool operator==(const Token & token) const {
        bool result = kind == token.kind && tokenLen == token.tokenLen && strncmp(str, token.str, tokenLen) == 0;
        return result;
    }
};

struct HashToken{
	size_t operator()(const Token & token) const{
        size_t h = 0;
        const int mod = (1e9 + 7);
        for (int idx = 0; idx < token.tokenLen; idx++) {
            h = (hash<char>()(token.str[idx]) + h * 233) % mod;
        }
		return h;
	}
};

struct Analyzer {
    char source[MAX_LEN] = { 0 };
    int sourceLen = 0;
    int scanOffset = -1;
    int parseOffset = -1;
    int curEquationIndex = 0;

    vector<Token> tokenStream;
    vector<Token*> elements;
    vector<int> numbers;
    unordered_map<Token, int, HashToken> equations[2];

    void scan() {
        scanf("%s", source);
        sourceLen = strlen(source);
        tokensize();
    }

    void reset() {
        memset(source, 0, MAX_LEN);
        equations[0].clear();
        equations[1].clear();
        sourceLen = 0;
        scanOffset = -1;
        parseOffset = -1;
        curEquationIndex = 0;
        elements.resize(0);
        numbers.resize(0);
        tokenStream.resize(0);
    }

    void parse() {
        parseExpr();
        parseEQ();
        parseExpr();
        calcPrefixCoef();
    }

    inline void parseEQ() {
        calcPrefixCoef();
        curEquationIndex = 1;
    }

    void parseExpr() {
        parseCoef();
        parseFormula();
        parseExprSub();
    }

    void parseExprSub() {
        parseAdvance();
        if (curToken().kind == Plus) {
            parsePlus();
            parseCoef();
            parseFormula();
            parseExprSub();
        }
    }

    inline void parsePlus() {
        calcPrefixCoef();
    }

    void parseCoef() {
        parseAdvance();
        Token& cur = curToken();
        if (cur.kind == Number) {
            int number = atoi(cur.str);
            numbers.emplace_back(number);
        } else {
            numbers.emplace_back(1);
            parseBack();
        }
    }

    void parseFormula() {
        parseTerm();
        parseCoef();
        calcSufixCoef();
        parseFormulaSub();
    }

    void parseTerm() {
        parseAdvance();
        Token& cur = curToken();
        if (curToken().kind == Element) {
            elements.emplace_back(&cur);
        } else {
            parseOpen();
            parseFormula();
            parseClose();
        }
    }
    
    void parseFormulaSub() {
        parseAdvance();
        if (curToken().kind == Element || curToken().kind == OpenParen) {
            parseBack();
            parseTerm();
            parseCoef();
            calcSufixCoef();
            parseFormulaSub();
        } else {
            parseBack();
        }
    }

    void tokensize() {
        while(!atEnd()) {
            char next = scanAdvance();
            while(!isTerminal(next)) {
                next = judge(next);
            }
        }
        Token token;
        token.kind = End;
        tokenStream.emplace_back(token);
    }

    inline void parseOpen() {
        elements.emplace_back(&curToken());
    }

    inline void parseClose() {
        parseAdvance();
        elements.emplace_back(&curToken());
    }

    void calcSufixCoef() {
        Token* element = elements.back();
        int number = numbers.back();
        numbers.pop_back();

        if (element->kind == CloseParen) {
            elements.pop_back();
            stack<Token*> store;
            while (elements.back()->kind != OpenParen) {
                element = elements.back();
                elements.pop_back();
                element->cnt *= number;
                store.push(element);
            }

            elements.pop_back();

            while(!store.empty()) {
                elements.emplace_back(store.top());
                store.pop();
            }
        } else {
            element->cnt = number;
        }
    }

    void calcPrefixCoef() {
        int number = numbers.back();
        numbers.pop_back();

        while (!elements.empty()) {
            Token* element = elements.back();
            int cnt = element->cnt;
            elements.pop_back();
            equations[curEquationIndex][*element] += number * cnt;
        }
    }

    char judge(char next) {
        if (next >= '0' && next <= '9') {
            return tokenizeNumber(next);
        }

        if (next >= 'A' && next <= 'Z') {
            return tokenizeElement(next);
        }

        if (next == '+') {
            return tokenizePlus(next);
        }

        if (next == '=') {
            return tokenizeEQ(next);
        }

        if (next == '(') {
            return tokenizeOpenParen(next);
        }

        if (next == ')') {
            return tokenizeCloseParen(next);
        }
        
        return next;
    }

    char tokenizeOpenParen(char next) {
        Token token;
        token.str[0] = '(';
        token.kind = OpenParen;
        tokenStream.emplace_back(token);

        next = scanAdvance();
        return next;
    }

    char tokenizeCloseParen(char next) {
        Token token;
        token.str[0] = ')';
        token.kind = CloseParen;
        tokenStream.emplace_back(token);

        next = scanAdvance();
        return next;
    }

    char tokenizePlus(char next) {
        Token token;
        token.str[0] = '+';
        token.kind = Plus;
        tokenStream.emplace_back(token);


        next = scanAdvance();
        return next;
    }

    char tokenizeEQ(char next) {
        Token token;
        token.str[0] = '=';
        token.kind = EQ;
        tokenStream.emplace_back(token);

        next = scanAdvance();
        return next;
    }

    char tokenizeElement(char next) {
        int start = scanOffset;
        next = scanAdvance();
        if ('a' <= next && next <= 'z') {
            next = scanAdvance();
        }

        Token token;
        token.tokenLen = scanOffset - start;
        strncpy(token.str, source + start, scanOffset - start);
        token.kind = Element;
        tokenStream.emplace_back(token);
        return next;
    }

    char tokenizeNumber(char next) {
        int start = scanOffset;
        while(true) {
            next = scanAdvance();
            if (next >= '0' && next <= '9') {
                continue;
            } else {
                Token token;
                token.tokenLen = scanOffset - start;
                strncpy(token.str, source + start, token.tokenLen);
                token.kind = Number;
                tokenStream.emplace_back(token);
                return next;
            }
        }
    }

    inline bool isTerminal(const char& chr) {
        return chr == 0;
    }

    inline char scanAdvance() {
        return source[++scanOffset];
    }

    inline void parseAdvance() {
        ++parseOffset;
    }

    inline void parseBack() {
        --parseOffset;
    }

    inline Token& curToken() {
        return tokenStream[parseOffset];
    }

    inline bool atEnd() {
        return scanOffset >= sourceLen - 1;
    }
};

int main() {
    int n;
    scanf("%d", &n);

    Analyzer analyzer;
    for (int idx = 0; idx < n; idx++) {
        analyzer.scan();
        analyzer.parse();

        for(const pair<Token, int>& kv: analyzer.equations[0]){
            if (analyzer.equations[1].find(kv.first) == analyzer.equations[1].end() ||
                analyzer.equations[1][kv.first] != kv.second
            ) {
                printf("N\n");
                goto out;
            }
        }

        printf("Y\n");
out:
        analyzer.reset();
    }
}
2024/3/29 02:13
加载中...