CF2170F Build XOR on a Segment 题解

可能第一个想法会是从不同的起点开始 dp，求出

f[x][y]

表示从某个起点开始，到右端点

x

为止，如果要异或出来

y

，则至少需要选取几个整数。这个 dp 的转移是很简单的，但是询问个数太多了，即使对序列分块，只取每块的左端点作为起点，询问的复杂度也会爆炸。

那么观察一下，根据线性代数的知识，可以发现每个询问的答案不会超过

12

，因为任意

13

个在

[0, 4095]

中的整数，一定存在

1

个整数能被其他

12

个整数的某个子集的异或表示，于是就可以去掉这个整数。然后就可以想到，从左往右 dp，假设当前右端点为

r

，实时维护

f[x][y]

表示如果能使用的整数右边到

r

为止，且希望通过

y

个整数的异或凑出

x

，则左端点的最大值是多少。即

[f[x][y], r]

中存在

y

个整数能异或得出

x

。这样的话离线查询就很简单了，可以在扫描到右端点

r

时处理右端点为

r

的所有询问，找到最小的

y

使得

f[x][y]\geq l

即为答案。转移也是简单的，每次遍历整个

f

数组，然后

\max(f_{\text{old}}[x][y], f_{\text{new}}[x \ \text{xor}\ a[r]][y + 1])\to f_{\text{new}}[x \ \text{xor}\ a[r]][y + 1]

。

算一下更新

f

的复杂度

O(n\times \max{a_i}\times \log \max{a_i})

，大概是

5\times 10^8

，常数很小，一看时间限制 5s，直接冲就完事了。

这场考虑到 dirty 程度 D>>>EF，不好评价。

CPP

#include <bits/stdc++.h>

typedef std::pair<int, int> pii;
int a[10005], n, q, f[4096][13], nf[4096][13], ans[1000005], val[1000005];
std::vector<pii> query[10005];

int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &a[i]);
  }
  scanf("%d", &q);
  for (int i = 1; i <= q; ++i) {
    int l, r;
    scanf("%d%d%d", &l, &r, &val[i]);
    query[r].push_back(pii(l, i));
  }
  memset(f, -1, sizeof(f));
  for (int i = 1; i <= n; ++i) {
    memcpy(nf, f, sizeof(f));
    for (int o = 0; o < 4096; ++o) {
      nf[a[i]][1] = i;
      for (int p = 1; p <= 11; ++p) {
        if (f[o][p] == -1) {
          continue;
        }
        nf[o ^ a[i]][p + 1] = std::max(nf[o ^ a[i]][p + 1], f[o][p]);
      }
    }
    memcpy(f, nf, sizeof(f));
    for (auto [x, y]: query[i]) {
      ans[y] = 0;
      for (int p = 1; p <= 12; ++p) {
        if (f[val[y]][p] >= x) {
          ans[y] = p;
          break;
        }
      }
    }
  }
  for (int i = 1; i <= q; ++i) {
    printf("%d ", ans[i]);
  }
  printf("\n");
  return 0;
}

CF2170F Build XOR on a Segment 题解

文章操作

相关推荐

评论

CF2170F Build XOR on a Segment 题解