删括号 题解

注意这是个合法括号序列，所以我们可以看成是两颗有根树，且孩子是有先后关系的。删去一个 () 形状就等价于删去树的一个叶节点。另一个角度就是我们能否将 T2 “嵌入”到树 T1 中去。我们注意到这是一个子序列问题，所以对于 T2 的每个子树，肯定是在 T1 的子树中越靠前放进去越好。因此我们可以简单地写出一个 check 函数：

bool check(int u1, int u2) {
  int j = 0;
  for (int v : T2[u2]) {
    while (j < T1[u1].size() && !check(T1[u1][j], v)) ++j;
    if (j == T1[u1].size()) return false;
    ++j;
  }
  return true;
}

这个函数虽然是个 DFS，但是它其实是线性的，道理很简单，在寻找匹配的过程中，T1 的每个节点只会最多一次尝试与 T2 中的一个节点配对。因此总时间不超过 。综上，复杂度 。

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cctype>

#include <algorithm>
#include <stack>
#include <random>
#include <bitset>
#include <queue>
#include <functional>
#include <set>
#include <map>
#include <vector>
#include <chrono>
#include <iostream>
#include <limits>
#include <numeric>

#define LOG(FMT...) fprintf(stderr, FMT)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

template <class T>
istream& operator>>(istream& is, vector<T>& v) {
  for (T& x : v)
    is >> x;
  return is;
}

template <class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
  if (!v.empty()) {
    os << v.front();
    for (int i = 1; i < v.size(); ++i)
      os << ' ' << v[i];
  }
  return os;
}

const int N = 110;

int m1, m2;
vector<int> T1[N], T2[N];

void build(const string& s, int& m, vector<int> T[]) {
  stack<int> stk;
  stk.push(m = 1);
  for (char c : s)
    if (c == '(') {
      T[stk.top()].push_back(++m);
      stk.push(m);
    } else
      stk.pop();
}

bool check(int u1, int u2) {
  int j = 0;
  for (int v : T2[u2]) {
    while (j < T1[u1].size() && !check(T1[u1][j], v)) ++j;
    if (j == T1[u1].size()) return false;
    ++j;
  }
  return true;
}

int main() {
#ifdef LBT
  freopen("test.in", "r", stdin);
  int nol_cl = clock();
#endif
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  string s;
  cin >> s;
  build(s, m1, T1);
  cin >> s;
  build(s, m2, T2);
  cout << (check(1, 1) ? "Possible" : "Impossible");

#ifdef LBT
  LOG("Time: %dms\n", int ((clock()
          -nol_cl) / (double)CLOCKS_PER_SEC * 1000));
#endif
  return 0;
}