CF1718A2 Burenka and Traditions (hard version)

Alex_Wei · 2022-08-17 10:09:32 · 题解

CF1718A2 Burenka and Traditions (hard version)

考察长度除以 2 上取整的性质，我们发现一次长度为 L 的操作可以拆成 \lfloor L / 2\rfloor 个长度为 2 的操作和 L\bmod 2 个长度为 1 的操作。

如果长度为 2 的操作包含长度为 1 的操作，则可以拆成两个长度为 1 的操作。因此得到如下性质：

• 操作长度 1 或 2。
• 长度为 1 的操作和长度为 2 的操作不重叠。
• 长度为 1 的操作之间不重叠，长度为 2 的操作之间不完全重合，但可以相交。

考虑一段相邻相交的极长的连续的长度为 2 的操作，设操作共有 L - 1 次，则它覆盖了长度为 L 的 a_i。易知操作合法当且仅当这段 a_i 异或和为 0。

因此，从原序列中选出若干段异或和为 0 的不相交的子段，则总代价即 n 减去子段数量。只需最大化子段数量，简单贪心即可。

时间复杂度 \mathcal{O}(n\log n)。

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 1e5 + 5;
int n, a[N];
void solve() {
  cin >> n;
  for(int i = 1; i <= n; i++) cin >> a[i];
  int ans = n, S = 0;
  map<int, int> mp;
  mp[0] = 1;
  for(int i = 1; i <= n; i++) {
    S ^= a[i];
    if(mp.find(S) != mp.end()) {
      ans--;
      mp.clear();
      mp[S = 0] = 1;
    }
    else mp[S] = 1;
  }
  cout << ans << "\n";
}
int main() {
  ios::sync_with_stdio(0);
  int T = 1;
  cin >> T;
  while(T--) solve();
  return 0;
}