C++11(clang++ 3.9) 解法, 执行用时: 347ms, 内存消耗: 604K, 提交时间: 2019-04-14 21:59:31

#include <bits/stdc++.h>

using namespace std;

#define TemplateVersion "3.4.1"
// Useful Marcos
//====================START=====================
// Compile use C++11 and above
#ifdef LOCAL
#define debug(args...)                           \
    {                                            \
        string _s = #args;                       \
        replace(_s.begin(), _s.end(), ',', ' '); \
        stringstream _ss(_s);                    \
        istream_iterator<string> _it(_ss);       \
        err(_it, args);                          \
    }
void err(istream_iterator<string> it)
{
}
template <typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args)
{
    cerr << *it << " = " << a << endl;
    err(++it, args...);
}
#define MSG cout << "Finished" << endl
#else
#define debug(args...)
#define MSG
#endif
#if __cplusplus >= 201703L
template <typename... Args>
void readln(Args &... args)
{
    ((cin >> args), ...);
}
template <typename... Args>
void writeln(Args... args)
{
    ((cout << args << " "), ...);
    cout << endl;
}
#elif __cplusplus >= 201103L
void readln()
{
}
template <typename T, typename... Args>
void readln(T &a, Args &... args)
{
    cin >> a;
    readln(args...);
}
void writeln()
{
    cout << endl;
}
template <typename T, typename... Args>
void writeln(T a, Args... args)
{
    cout << a << " ";
    writeln(args...);
}
#endif
#if __cplusplus >= 201103L
#define FOR(_i, _begin, _end) for (auto _i = _begin; _i < _end; _i++)
#define FORR(_i, _begin, _end) for (auto _i = _begin; _i > _end; _i--)
#else
#define FOR(_i, _begin, _end) for (int _i = (int)_begin; _i < (int)_end; _i++)
#define FORR(_i, _begin, _end) for (int _i = (int)_begin; _i > (int)_end; _i--)
#define nullptr NULL
#endif
#if __cplusplus >= 201103L
#define VIS(_kind, _name, _size) \
    vector<_kind> _name(_size);  \
    for (auto &i : _name)        \
        cin >> i;
#else
#define VIS(_kind, _name, _size)    \
    vector<_kind> _name;            \
    _name.resize(_size);            \
    for (int i = 0; i < _size; i++) \
        cin >> _name[i];
#endif
// alias
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define tcase() \
    int T;      \
    cin >> T;   \
    FOR(kase, 1, T + 1)
// Swap max/min
template <typename T>
bool smax(T &a, const T &b)
{
    if (a > b)
        return false;
    a = b;
    return true;
}
template <typename T>
bool smin(T &a, const T &b)
{
    if (a < b)
        return false;
    a = b;
    return true;
}
// ceil divide
template <typename T>
T cd(T a, T b)
{
    return (a + b - 1) / b;
}
// min exchange
template <typename T>
bool se(T &a, T &b)
{
    if (a < b)
        return false;
    swap(a, b);
    return true;
}
// A better MAX choice
const int INF = 0x3f3f3f3f;
const long long INFLL = 0x3f3f3f3f3f3f3f3fLL;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef set<int> si;
typedef vector<string> cb;
//====================END=====================

// Constants here
map<string, int> table;
string components[] = {" --- ", "|   |", "    |", "|    "};
string numbers[][5] = {
    {components[0], components[1], components[1], components[1], components[0]},
    {components[2], components[2], components[2], components[2], components[2]},
    {components[0], components[2], components[0], components[3], components[0]},
    {components[0], components[2], components[0], components[2], components[0]},
    {components[1], components[1], components[0], components[2], components[2]},
    {components[0], components[3], components[0], components[2], components[0]},
    {components[0], components[3], components[0], components[1], components[0]},
    {components[0], components[2], components[2], components[2], components[2]},
    {components[0], components[1], components[0], components[1], components[0]},
    {components[0], components[1], components[0], components[2], components[0]}};

string operators[][5] = {
    {"  |  ", "  |  ", "--+--", "  |  ", "  |  "},
    {"     ", "     ", "-----", "     ", "     "},
    {"\\   /", " \\ / ", "  x  ", " / \\ ", "/   \\"},
    {"     ", "-----", "     ", "-----", "     "}};

vector<int> trans[] = {
    {8},       // 0
    {7},       // 1
    {},        // 2
    {9},       // 3
    {},        // 4
    {9, 6},    // 5
    {5, 8},    // 6
    {1},       // 7
    {0, 6, 9}, // 8
    {5, 3, 8}, // 9
    {11},      // 10, +
    {10},      // 11, -
    {},        // 12, *
    {},        // 13, =
};

vi l, r;

// Pre-Build Function
inline void build()
{
    for (int i = 0; i < 10; i++)
    {
        string s = "";
        for (auto it : numbers[i])
            s += it;
        table[s] = i;
    }

    for (int i = 0; i < 4; i++)
    {
        string s = "";
        for (auto it : operators[i])
            s += it;
        table[s] = i + 10;
    }
}

int pre(int op)
{
    if (op == 12)
        return 2;
    return 1;
}

ll getVal(vector<int> v)
{
    ll ret = 0;
    int n = v.size();
    bool flag = false;

    int i = 0;

    if (v[i] == 11)
        flag = true, i++;
    else if (v[i] == 10)
        i++;

    for (; i < n; i++)
    {
        ret *= 10LL;
        ret += v[i];
    }

    return flag ? -ret : ret;
}

ll eval(vector<int> v)
{
    stack<int> ops;
    queue<int> rpn;
    for (const auto &i : v)
    {
        if (0 <= i && i <= 9)
            rpn.push(i);
        else
        {
            while (ops.size() && pre(ops.top()) >= pre(i))
            {
                rpn.push(ops.top());
                ops.pop();
            }
            ops.push(i);
        }
    }

    while (ops.size())
    {
        rpn.push(ops.top());
        ops.pop();
    }

    stack<ll> s;

    while (rpn.size())
    {
        int token = rpn.front();
        rpn.pop();

        if (token == 10)
        {
            ll t = s.top();
            s.pop();
            t += s.top();
            s.pop();
            s.push(t);
        }
        else if (token == 11)
        {
            ll t = s.top();
            s.pop();
            t = s.top() - t;
            s.pop();
            s.push(t);
        }
        else if (token == 12)
        {
            ll t = s.top();
            s.pop();
            t *= s.top();
            s.pop();
            s.push(t);
        }
        else
            s.push(token);
    }

    return s.top();
}

bool check(int n, int p)
{
    if (eval(l) == getVal(r))
        return true;

    for (int i = 0; i < n; i++)
    {
        int k = l[i];

        for (const auto &it : trans[k])
        {
            l[i] = it;
            if (eval(l) == getVal(r))
                return true;
        }

        l[i] = k;
    }

    for (int i = 0; i < p; i++)
    {
        int k = r[i];

        for (const auto &it : trans[k])
        {
            r[i] = it;
            if (eval(l) == getVal(r))
                return true;
        }

        r[i] = k;
    }

    return false;
}

void parseEquation(int n, int p, vector<string> &v)
{
    l.clear();
    r.clear();

    for (int i = 0; i < n; i++)
    {
        string elem = "";
        for (int idx = 0; idx < 5; idx++)
            elem += v[idx].substr(6 * i, 5);
        l.pb(table[elem]);
    }

    for (int i = n + 1; i < n + p + 1; i++)
    {
        string elem = "";
        for (int idx = 0; idx < 5; idx++)
            elem += v[idx].substr(6 * i, 5);
        r.pb(table[elem]);
    }
}

// Actual Solver
inline void solve()
{
    tcase()
    {
        cout << "Case #" << kase << ": ";
        int n, p;
        cin >> n >> p;
        vector<string> v(5);
        cin.get();
        for (auto &i : v)
            getline(cin, i);

        parseEquation(n, p, v);

        if (check(n, p))
            cout << "Yes\n";
        else
            cout << "No\n";
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

#ifdef LOCAL
    clock_t _begin = clock();
#endif

    build();
    solve();

#ifdef LOCAL
    cerr << "Time elapsed: " << (double)(clock() - _begin) * 1000 / CLOCKS_PER_SEC << "ms." << endl;
#endif

    return 0;
}