CF 暴力过了,O(n^2) 求 Hack
查看原帖
CF 暴力过了,O(n^2) 求 Hack
86576
zlxFTHOvO楼主2024/4/8 14:09
#include <bits/stdc++.h>
using namespace std;

#define debug(...) fprintf(stderr, __VA_ARGS__)

int main() {
  // freopen("se.in", "r", stdin);
  // freopen("se.out", "w", stdout);
  cin.tie(0)->sync_with_stdio(0);
  string s;
  cin >> s;
  int n = s.size();
  auto work = [&](int l, int r)->string {
    // cerr << "work " << l << " " << r << "\n";
    if (l > r) return "";
    int m = r - l + 1;
    string t = s.substr(l, r - l + 1);
    vector<int> st, mh(m);
    for (int i = 0; i < m; ++i) {
      if (t[i] == '(') {
        st.push_back(i);
      } else {
        assert(st.size() != 0);
        int j = st.back();
        st.pop_back();
        mh[j] = i, mh[i] = j;
      }
    }
    vector<string> tt(m);
    int id = 0;
    auto dfs = [&](auto self, int l, int r, string &ss)->void {
      // cerr << "dfs " << l << " " << r << "\n";
      if (r - l + 1 == 2) {
        ss += "()";
        return;
      }
      if (mh[l] == r) {
        ss += "(";
        self(self, l + 1, r - 1, ss);
        ss += ")";
        return;
      }
      vector<int> a;
      for (int i = l; i <= r; i = mh[i] + 1) {
        int cur = id; id++;
        self(self, i, mh[i], tt[cur]);
        // while (a.size() && a.back().first < x) {
        //   a.pop_back();
        // }
        auto pd = [](string &s, string &t) {
          for (int i = 0; i < min(s.size(), t.size()); ++i) {
            if (s[i] > t[i]) return 1;
            if (s[i] < t[i]) return 0;
          }
          return 0;
        };
        while (a.size() && pd(tt[a.back()], tt[cur])) {
          a.pop_back();
        }
        a.push_back(cur);
      }
      for (auto x : a) ss += tt[x];
    };
    string ss;
    dfs(dfs, 0, m - 1, ss);
    return ss;
  };
  string ans;
  auto solve = [&](auto self, int l)->void {
    if (l >= n) return;
    int cur = 0, mn = 1e9, tar = -1;
    for (int i = l; i < n; ++i) {
      cur += (s[i] == '(' ? 1 : -1);
      mn = min(mn, cur);
      if (cur == -1 && tar == -1) {
        tar = i;
        break;
      }
    }
    // cerr << "solve " << l << " " << n - 1 << "\n";
    if (mn >= 0) {
      int cnt = count(s.begin() + l, s.end(), ')');
      for (int i = 0; i < n - l - 2 * cnt; ++i) {
        ans += '(';
      }
    } else {
      ans += work(l, tar - 1) + ")";
      self(self, tar + 1);
    }
  };
  solve(solve, 0);
  cout << ans << "\n";
  return 0;
}
2024/4/8 14:09
加载中...