「NOIP2005」等价表达式

题目链接:洛谷 1054

Descritpion

判断给定的两个表达式是否等价。

Data Range

$n\leq 26, len\leq 50$

Solution

这道题目纯属恶心人。
做法比较直接,就是随机若干个数,判断是否表达式的值相同。
然后。。。。就没有然后了,自己码吧。
反正我码的老长了。

Code

#include <bits/stdc++.h>

using namespace std;

const int MOD = 998244353;

template <typename T> T pw(T x, T y) {
  T res = 1;
  for (; y; y >>= 1, x = 1ll * x * x % MOD) 
    if (y & 1) 
      res = 1ll * res * x % MOD;
  return res;
}

stack<int> stk1;
stack<char> stk2;
string s, t, m;
int cnt0;

int idx(char ch) {
  if (ch == '(') 
    return 0;
  if (ch == '+' || ch == '-') 
    return 1;
  if (ch == '*') 
    return 2;
  if (ch == '^') 
    return 3;
  if (ch == ')') 
    return 4;
  return 233;
}

pair<int, int> read(string s, int pos) {
  int res = 0, i, n = s.size();
  for (i = pos; isdigit(s[i]) && i < n; i++) {
    res = (res * 10 + s[i] - '0') % MOD;
  }
  return {res, i};
}

bool check() {
  vector<int> tmp;
  tmp.clear();
  while (!stk1.empty()) {
    tmp.push_back(stk1.top());
    stk1.pop();
  }
  for (int i = (int) tmp.size() - 1; i >= 0; i--) {
    stk1.push(tmp[i]);
  }
  return tmp.size() < 2;
}

void _calc(char opt) {
  if (check()) {
    return;
  }
  int x, y, z;
  x = stk1.top();
  stk1.pop();
  y = stk1.top();
  stk1.pop();
  if (opt == '+') 
    z = (x + y) % MOD;
  if (opt == '-')
    z = (y - x + MOD) % MOD;
  if (opt == '*')
    z = 1ll * x * y % MOD;
  if (opt == '^') 
    z = pw(y, x);
  stk1.push(z);
}

int calc(string s, int y) {
  cnt0 = 0; 
  while (!stk1.empty()) 
    stk1.pop();
  while (!stk2.empty()) 
    stk2.pop();
  int n = s.size();
  int i = 0;
  while (i < n) {
    char ch = s[i];
    if (ch == ' ' || ch == '\r') {
      i++;
      continue;
    } else if (ch == 'a') {
      stk1.push(y);
      i++;
    } else if (isdigit(ch)) {
      pair<int, int> num = read(s, i);
      stk1.push(num.first);
      i = num.second;
    } else {
      i++;
      if (ch == '+' || ch == '-' || ch == '*' || ch == '^') {
        if (stk2.empty()) 
          stk2.push(ch);
        else {
          while (!stk2.empty()) {
            if (idx(stk2.top()) >= idx(ch)) {
              _calc(stk2.top());
              stk2.pop();
            } else break;
          }
          stk2.push(ch);
        }
      } else {
        if (ch == '(') {
          stk2.push(ch);
          cnt0++;
        }
        else if (cnt0) {
          while (stk2.top() != '(') {
            _calc(stk2.top());
            stk2.pop();
          }
          stk2.pop();
          cnt0--;
        }
      }
    }
  }
  while (!stk2.empty() && !stk1.empty()) {
    _calc(stk2.top());
    stk2.pop();
  }
  return (stk1.top() % MOD + MOD) % MOD;
}

vector<char> Ans;

int main() {
  srand(time(NULL));
  Ans.clear();
  getline(cin, s);
  getline(cin, m);
  pair<int, int> num = read(m, 0);
  for (int i = 0; i < num.first; i++) {
    getline(cin, t);
    bool flg = 1;
    for (int it = 1; it <= 50; it++) {
      int x = rand() % 1000;
      int res1 = calc(t, x);
      int res2 = calc(s, x);
      if (res1 != res2) {
        flg = 0;
        break;
      }
    }
    if (flg) 
      Ans.push_back('A' + i);
  }
  for (int i = 0; i < (int) Ans.size(); i++) 
    cout << Ans[i]; 
  return 0; 
}
最后修改:2019 年 09 月 07 日 10 : 48 PM
如果觉得我的文章对你有用,请随意赞赏

发表评论