CF题解

E. Rearrange Brackets 2100 括号树 gq!

https://codeforces.com/contest/1821/problem/E
题解：若我们把序列看作是一个由匹配括号组成的森林，外层括号是内层括号的父亲，则整个正则括号序列的cost可以看作是森林中所有点的深度之和，根节点深度为0，故每次操作可以看作是将某棵树的父节点单独作为一棵树，其子节点作为新的树，即每次操作会使得总cost-(树的大小-1),故我们可以将所有子树大小放入大根堆，贪心地取出最大的k个使得cost最小。

E. Preorder 2100 dsu gq!

https://codeforces.com/contest/1671/problem/E
题解：对于一棵完全二叉树，我们可以通过dp得到一颗树的答案，如果两个子树不能互相转化，则f(u)=2f(v1)f(v2),否则f(u)=f(v1)f(v2)，问题关键在于如何判断两字符串是否可以互相转换。我们可以用dsu或映射来解决这个问题。我们可以将每个串归类到其所能转化的最小字典序的集合中，而如果我们得到了v1 v2的最小字典序，则可得到u的最小字典序，比较是否同集合即可。由于每个点至多被遍历n次，故复杂度为n2^n。

D. Maximum AND 1800 math

https://codeforces.com/contest/1721/problem/D
题解：我们想要得到与和最大，显然我们要优先使得高位在每个a[i]xorb[j]上存在。我们从高到低遍历，若确定了某个位在之前存在的位存在的前提下可以表示，则保留，否则跳过，我们可以通过保留掩码位的方式维护a和b,此时对于a中每一个数只有唯一的对应值，考虑a和b是否能完全对应，若可以则保留否则跳过，复杂度为logNnlogn。

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false); cin.tie(0);
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    vector<int> a(n), b(n);
    for (int& x : a) cin >> x;
    for (int& x : b) cin >> x;
    
    auto check = [&](int ans) {
      map<int, int> cnt;
      for (int x : a) ++cnt[x & ans];
      for (int x : b) --cnt[~x & ans];
      bool ok = true;
      for (auto it : cnt) ok &= it.second == 0;
      return ok;
    };
    
    int ans = 0;
    for (int bit = 29; bit >= 0; --bit) 
      if (check(ans | (1 << bit)))
        ans |= 1 << bit;
    
    cout << ans << '\n';
  }
}