CodeForces 1562D Two Hundred Twenty One

给定一个长度为 $n$ 的字符串表示一个序列 $a_{i}$ ，字符串中只有 '+'、'-'，第 $i$ 个字符为 '+' 表示 $a_{i} = 1$ ，为 '-' 表示 $a_{i} = - 1$ 。 $q$ 组询问，每组询问给定两个整数 $l, r (1 \leq l \leq r \leq n)$ ，将 $a_{l \sim r}$ 单独取出后，求最少删除多少个数字，使得所成长度为 $m$ 的序列 ${b_{i}}$ 满足 $\sum_{i = 1}^{m} (- 1)^{i - 1} b_{i} = 0$ 。

D1 仅要求出最少删除多少个数字，D2 需要求出删除哪些数字（多解输出任意一组即可）。

$T$ 组数据， $1 \leq T \leq 10^{3}, 1 \leq n, q \leq 3 \cdot 10^{5}$ 。

先考虑没有多组询问。

窝萌首先发现一个性质，那就是如果有两个连续的相同字符，那么这两个字符对答案无贡献，我们可以直接删掉。那我们一次删掉之后，最后得到的序列只能是正负交替的了。于是我们只要考虑此种情况即可。我们发现如果删完的序列长度为奇数的话，我们只要删除最中间那个数就可以了。我们考虑偶数，如果长度已经为 $0$ ，那显然就不用删除了，如果不为 $0$ 的话，考虑到们此相同字符消除一定是两个两个删的，所以至少要删两个数，有考虑到如果随便删一个数，那么序列长度就变成奇数了，所以我们只需要删两个数即可。

于是我们发现，如果是询问系列长度为奇数，那答案最多是 $1$ ，如果是偶数，我们可以维护前缀和 $S_{i} = \sum_{j = 1}^{i} (- 1)^{j - 1} a_{j}$ ，如果 $S_{r} - S_{l - 1}$ 是 $0$ ，那答案就是 $0$ ，否则是 $2$ 。

这样 D1 就做完了。

我们考虑 D2，我们先考虑奇数的情况，我们假设要删掉的数是第 $k$ 个，那我们有 $\sum_{i = l}^{k - 1} (- 1)^{i - 1} a_{i} + (- 1) \cdot \sum_{i = k + 1}^{r} (- 1)^{i - 1} a_{i} = 0$ 也即 $S_{k - 1} - S_{l - 1} = S_{r} - S_{k}$ 也即 $S_{k - 1} + S_{k} = S_{l - 1} + S_{r}$ ，于是我们对每个 $S_{k - 1} + S_{k}$ 相同的开个 set，之后对每组询问 $⟨ l, r ⟩$ ，我们只要在所有 $S_{k - 1} + S_{k} = S_{l - 1} + S_{r}$ 数中 lower_bound 出一个在 $[l, r]$ 中的答案即可。

长度为偶数就直接随便删掉最左边或是最右边的数，然后按照奇数的方法做即可。

cpp

const int maxn = 300005;

int qzh[maxn];
char s[maxn];

void solve() {
  int n, q;
  scanf("%d%d%s", &n, &q, s + 1);
  std::map<int, std::set<int>> mp;
  for (int i = 1; i <= n; ++i) {
    qzh[i] = qzh[i - 1] + (((i & 1) == (s[i] == '+')) ? 1 : -1);
    mp[qzh[i - 1] + qzh[i]].insert(i);
  }
  while (q--) {
    int l, r;
    scanf("%d%d", &l, &r);
    if (qzh[r] - qzh[l - 1]) {
      if ((r - l) & 1) {
        puts("2");
        writesp(r);
        r--;
      } else {
        puts("1");
      }
      writeln(*mp[qzh[l - 1] + qzh[r]].lower_bound(l));
    } else {
      puts("0");
    }
  }
}

int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    solve();
  }
  return 0;
}

Cite this post