求助
查看原帖
求助
437893
ScottSuperb楼主2023/4/1 22:33

只对了三个点,退役这么久真的菜多了

// Handle: ScottSuperb
// Time: 2023-04-01 21:12:36
// Problem: P3719 [AHOI2017初中组]rexp
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3719
// Memory Limit: 125 MB
// Time Limit: 1000 ms

#include <bits/stdc++.h>

using namespace std;

template <class T>
struct stk {
  T a[100005];
  int size = 0;
  void push(T x) { a[size++] = x; }
  void pop() { --size; }
  T& top() { return a[size - 1]; }
};
string s;
int p, a, b;
stk<char> op;
stk<int> num;

int getn() {
  int c = 0;
  while (s[p] == 'a') ++c, ++p;
  --p;
  return c;
}
inline void cal() {
  a = num.top(), num.pop();
  b = num.top(), num.pop();
  num.push(max(a, b)), op.pop();
}

int main() {
  cin >> s;
  for (int si = s.size(); p < si; ++p) {
    if (s[p] == 'a') {
      if (p > 0 && s[p - 1] == ')')
        a = getn() + num.top(), num.top() = a;
      else
        num.push(getn());
    } else if (s[p] == '(')
      op.push(p > 0 && s[p - 1] == 'a' ? '[' : '(');
    else if (s[p] == '|') {
      while (op.size && op.top() != '(' && op.top() != '[') cal();
      op.push('|');
    } else if (s[p] == ')') {
      while (op.top() != '(' && op.top() != '[') cal();
      if (op.top() == '[')
        a = num.top(), num.pop(), a += num.top(), num.top() = a;
      op.pop();
    }
  }
  if (op.size) cal();
  cout << num.top() << endl;
  return 0;
}
2023/4/1 22:33
加载中...