2010-1109

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

题意：
给定一些量纲，运算符的优先级和左右结合律，以及量纲之间的关系表达式，求一个量纲集合表达式的运算结果。

解法：
1. 解析表达式（主要设计字符串处理，没什么算法可言，主要需要时间和一些处理字符串的经验）
2. 表达式计算（我用的是逆波兰，复杂度为O（n），shi哥和quark的方法都是构表达式树）
3. 量纲集合之间的运算，因为量纲数量不多，于是直接暴力。

总的说来，题目没什么太难的地方，靠的主要是肉，需要比较快速的编程和debug能力。

代码：
{{{
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <cassert>
#include <cctype>
#include <map>
using namespace std;

const int MAXN = 10 + 1;
const int MAXL = 128 + 1;
const int MAXLL = 100010 + 1;

class Unit {
public:
    bool type;
    vector <int> cnt;
    int idx, p;
    bool lass;

    Unit() {}

    inline void print() {
        printf("type = %d", type);
        if (type) {
            printf(" (");
            for (int i = 0; i < (int)cnt.size(); i++) {
                printf("%d ", cnt[i]);
            }
            putchar(')');
            putchar('\n');
        } else {
            printf(" idx = %d p = %d lass = %d\n", idx, p, lass);
        }
    }
};

int ntype, nop, neq, nexpr, MOD, priority[MAXN], pos;
bool lass[MAXN];
map <string, int> typeMap, opMap;
map < pair <int, int>, int > eqMap[MAXN];
char line[MAXLL];
vector <Unit> rev, opList;

inline void skipSpace() {
    while (isspace(line[pos])) {
        pos++;
    }
}

inline bool isABC123(char ch) {
    return ('a' <= ch && ch <= 'z') || ('A' <= ch && ch <= 'Z') || ('0' <= ch && ch <= '9');
}

inline bool isPunc(char ch) {
    return !isspace(ch) && ch != '\0' && ch != ' ' && ch != '(' && ch != ')' && ch != '\\' && !isABC123(ch);
}

inline string getType() {
    skipSpace();
    char tmpstr[MAXL];
    int len = 0;
    while (isABC123(line[pos])) {
        tmpstr[len++] = line[pos++];
    }
    tmpstr[len] = '\0';
    return tmpstr;
}

inline string getOp() {
    skipSpace();
    if (line[pos] == '(') {
        pos++;
        return "(";
    } else if (line[pos] == ')') {
        pos++;
        return ")";
    } else if (line[pos] == '\\') {
        pos++;
        return "\\";
    }
    char tmpstr[MAXL];
    int len = 0;
    while (isPunc(line[pos])) {
        tmpstr[len++] = line[pos++];
    }
    tmpstr[len] = '\0';
    return tmpstr;
}

int main() {
    while (scanf("%d%d%d%d%d", &ntype, &nop, &neq, &nexpr, &MOD) != EOF) {
        typeMap.clear();
        for (int i = 0; i < ntype; i++) {
            char tmpstr[MAXL];
            scanf("%s", tmpstr);
            typeMap[tmpstr] = i;
        }
        opMap.clear();
        for (int i = 0; i < nop; i++) {
            eqMap[i].clear();
            char tmpstr[MAXL];
            scanf("%s", tmpstr);
            opMap[tmpstr] = i;
            scanf("%d%s", &priority[i], tmpstr);
            lass[i] = tmpstr[0] == 'l';
        }
        gets(line);
        for (int i = 0; i < neq; i++) {
            gets(line);
            pos = 0;
            int x, y, z, op;
            z = typeMap[getType()];
            getOp();
            x = typeMap[getType()];
            op = opMap[getOp()];
            y = typeMap[getType()];
            eqMap[op][make_pair(x, y)] = z;
        }
        for (int o = 0; o < nexpr; o++) {
            gets(line);
            pos = 0;
            rev.clear();
            opList.clear();
            while (true) {
                bool type = true;
                string str = getType();
                if (str.empty()) {
                    type = false;
                    str = getOp();
                    if (str.empty()) break;
                }
                Unit unit;
                unit.type = type;
                if (type) {
                    unit.cnt = vector <int> (ntype);
                    unit.cnt[typeMap[str]] = 1;
                    rev.push_back(unit);
                } else {
                    if (str[0] == ')') {
                        while (!opList.empty() && opList.back().p != -1) {
                            rev.push_back(opList.back());
                            opList.pop_back();
                        }
                        opList.pop_back();
                    } else if (str[0] == '(') {
                        unit.idx = nop;
                        unit.p = -1;
                        opList.push_back(unit);
                    } else {
                        if (str[0] == '\\') {
                            unit.idx = -1;
                            unit.p = 0;
                            unit.lass = true;
                        } else {
                            unit.idx = opMap[str];
                            unit.p = priority[unit.idx];
                            unit.lass = lass[unit.idx];
                        }
                        while (!opList.empty() && opList.back().p < unit.p && opList.back().p != -1) {
                            rev.push_back(opList.back());
                            opList.pop_back();
                        }
                        if (unit.lass) {
                            while (!opList.empty() && opList.back().p == unit.p) {
                                rev.push_back(opList.back());
                                opList.pop_back();
                            }
                        }
                        opList.push_back(unit);
                    }
                }
            }
            while (!opList.empty()) {
                rev.push_back(opList.back());
                opList.pop_back();
            }
            opList.clear();
            for (int i = 0; i < (int)rev.size(); i++) {
                if (rev[i].type) {
                    opList.push_back(rev[i]);
                } else {
                    Unit unit2 = opList.back();
                    opList.pop_back();
                    if (opList.empty()) assert(false);
                    Unit unit, unit1 = opList.back();
                    unit.type = true;
                    unit.cnt = vector <int> (ntype, 0);
                    opList.pop_back();
                    if (rev[i].p == 0) {
                        for (int j = 0; j < ntype; j++) {
                            unit.cnt[j] = (unit1.cnt[j] + unit2.cnt[j]) % MOD;
                        }
                    } else {
                        for (int k = 0; k < ntype; k++) {
                            for (int j = 0; j < ntype; j++) {
                                if (eqMap[rev[i].idx].count(make_pair(k, j))) {
                                    unit.cnt[eqMap[rev[i].idx][make_pair(k, j)]] = (unit.cnt[eqMap[rev[i].idx][make_pair(k, j)]] + (long long)unit1.cnt[k] * unit2.cnt[j]) % MOD;
                                }
                            }
                        }
                    }
                    opList.push_back(unit);
                }
            }
            printf("#%d:\n", o + 1);
            for (int i = 0; i < ntype; i++) {
                for (map <string, int>::iterator iter = typeMap.begin(); iter != typeMap.end(); iter++) {
                    if (iter->second == i) {
                        printf("%s: %d\n", iter->first.c_str(), opList.back().cnt[i]);
                        break;
                    }
                }
            }
        }
        putchar('\n');
    }
    return 0;
}
}}}

题意：

给定一些量纲，运算符的优先级和左右结合律，以及量纲之间的关系表达式，求一个量纲集合表达式的运算结果。

解法：

1. 解析表达式（主要设计字符串处理，没什么算法可言，主要需要时间和一些处理字符串的经验）

2. 表达式计算（我用的是逆波兰，复杂度为O（n），shi哥和quark的方法都是构表达式树）

3. 量纲集合之间的运算，因为量纲数量不多，于是直接暴力。

总的说来，题目没什么太难的地方，靠的主要是肉，需要比较快速的编程和debug能力。

代码：

#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <cassert>
#include <cctype>
#include <map>
using namespace std;
const int MAXN = 10 + 1;
const int MAXL = 128 + 1;
const int MAXLL = 100010 + 1;
class Unit {
public:
    bool type;
    vector <int> cnt;
    int idx, p;
    bool lass;
    Unit() {}
    inline void print() {
        printf("type = %d", type);
        if (type) {
            printf(" (");
            for (int i = 0; i < (int)cnt.size(); i++) {
                printf("%d ", cnt[i]);
            }
            putchar(')');
            putchar('\n');
        } else {
            printf(" idx = %d p = %d lass = %d\n", idx, p, lass);
        }
    }
};
int ntype, nop, neq, nexpr, MOD, priority[MAXN], pos;
bool lass[MAXN];
map <string, int> typeMap, opMap;
map < pair <int, int>, int > eqMap[MAXN];
char line[MAXLL];
vector <Unit> rev, opList;
inline void skipSpace() {
    while (isspace(line[pos])) {
        pos++;
    }
}
inline bool isABC123(char ch) {
    return ('a' <= ch && ch <= 'z') || ('A' <= ch && ch <= 'Z') || ('0' <= ch && ch <= '9');
}
inline bool isPunc(char ch) {
    return !isspace(ch) && ch != '\0' && ch != ' ' && ch != '(' && ch != ')' && ch != '\\' && !isABC123(ch);
}
inline string getType() {
    skipSpace();
    char tmpstr[MAXL];
    int len = 0;
    while (isABC123(line[pos])) {
        tmpstr[len++] = line[pos++];
    }
    tmpstr[len] = '\0';
    return tmpstr;
}
inline string getOp() {
    skipSpace();
    if (line[pos] == '(') {
        pos++;
        return "(";
    } else if (line[pos] == ')') {
        pos++;
        return ")";
    } else if (line[pos] == '\\') {
        pos++;
        return "\\";
    }
    char tmpstr[MAXL];
    int len = 0;
    while (isPunc(line[pos])) {
        tmpstr[len++] = line[pos++];
    }
    tmpstr[len] = '\0';
    return tmpstr;
}
int main() {
    while (scanf("%d%d%d%d%d", &ntype, &nop, &neq, &nexpr, &MOD) != EOF) {
        typeMap.clear();
        for (int i = 0; i < ntype; i++) {
            char tmpstr[MAXL];
            scanf("%s", tmpstr);
            typeMap[tmpstr] = i;
        }
        opMap.clear();
        for (int i = 0; i < nop; i++) {
            eqMap[i].clear();
            char tmpstr[MAXL];
            scanf("%s", tmpstr);
            opMap[tmpstr] = i;
            scanf("%d%s", &priority[i], tmpstr);
            lass[i] = tmpstr[0] == 'l';
        }
        gets(line);
        for (int i = 0; i < neq; i++) {
            gets(line);
            pos = 0;
            int x, y, z, op;
            z = typeMap[getType()];
            getOp();
            x = typeMap[getType()];
            op = opMap[getOp()];
            y = typeMap[getType()];
            eqMap[op][make_pair(x, y)] = z;
        }
        for (int o = 0; o < nexpr; o++) {
            gets(line);
            pos = 0;
            rev.clear();
            opList.clear();
            while (true) {
                bool type = true;
                string str = getType();
                if (str.empty()) {
                    type = false;
                    str = getOp();
                    if (str.empty()) break;
                }
                Unit unit;
                unit.type = type;
                if (type) {
                    unit.cnt = vector <int> (ntype);
                    unit.cnt[typeMap[str]] = 1;
                    rev.push_back(unit);
                } else {
                    if (str[0] == ')') {
                        while (!opList.empty() && opList.back().p != -1) {
                            rev.push_back(opList.back());
                            opList.pop_back();
                        }
                        opList.pop_back();
                    } else if (str[0] == '(') {
                        unit.idx = nop;
                        unit.p = -1;
                        opList.push_back(unit);
                    } else {
                        if (str[0] == '\\') {
                            unit.idx = -1;
                            unit.p = 0;
                            unit.lass = true;
                        } else {
                            unit.idx = opMap[str];
                            unit.p = priority[unit.idx];
                            unit.lass = lass[unit.idx];
                        }
                        while (!opList.empty() && opList.back().p < unit.p && opList.back().p != -1) {
                            rev.push_back(opList.back());
                            opList.pop_back();
                        }
                        if (unit.lass) {
                            while (!opList.empty() && opList.back().p == unit.p) {
                                rev.push_back(opList.back());
                                opList.pop_back();
                            }
                        }
                        opList.push_back(unit);
                    }
                }
            }
            while (!opList.empty()) {
                rev.push_back(opList.back());
                opList.pop_back();
            }
            opList.clear();
            for (int i = 0; i < (int)rev.size(); i++) {
                if (rev[i].type) {
                    opList.push_back(rev[i]);
                } else {
                    Unit unit2 = opList.back();
                    opList.pop_back();
                    if (opList.empty()) assert(false);
                    Unit unit, unit1 = opList.back();
                    unit.type = true;
                    unit.cnt = vector <int> (ntype, 0);
                    opList.pop_back();
                    if (rev[i].p == 0) {
                        for (int j = 0; j < ntype; j++) {
                            unit.cnt[j] = (unit1.cnt[j] + unit2.cnt[j]) % MOD;
                        }
                    } else {
                        for (int k = 0; k < ntype; k++) {
                            for (int j = 0; j < ntype; j++) {
                                if (eqMap[rev[i].idx].count(make_pair(k, j))) {
                                    unit.cnt[eqMap[rev[i].idx][make_pair(k, j)]] = (unit.cnt[eqMap[rev[i].idx][make_pair(k, j)]] + (long long)unit1.cnt[k] * unit2.cnt[j]) % MOD;
                                }
                            }
                        }
                    }
                    opList.push_back(unit);
                }
            }
            printf("#%d:\n", o + 1);
            for (int i = 0; i < ntype; i++) {
                for (map <string, int>::iterator iter = typeMap.begin(); iter != typeMap.end(); iter++) {
                    if (iter->second == i) {
                        printf("%s: %d\n", iter->first.c_str(), opList.back().cnt[i]);
                        break;
                    }
                }
            }
        }
        putchar('\n');
    }
    return 0;
}