Wings 的博客
归档 系列 分类 标签 关于 友链 开往
Wings 的博客

2021 牛客多校第三场 训练记录 暨 补题

Wings  收录于  类别 ACM
     约 2117 字  预计阅读 5 分钟    次阅读     条评论  

太弱小了! 没有力量!

(今天没迟到, 我点了外卖直接在杰哥宿舍边打边吃, 连午餐都有的全真模拟)

看榜 J 过了一片, 大家表示都做过, 但是忘记了. 之后翻了蓝书找到了答案, 33minA. 蒋叶桢开了榜上过题数第二多的数学题, 我和张炀杰去看别的题, 但是一直不会, 甚至过得多的 B 也不会. 想辅助蒋叶桢, 但是完全插补了手因为我不会数学😔. 蒋叶桢说他的方法是偷懒的方法, 可能会T, 果然. 然后写了个不偷懒的应该是正解, 还是T了. 后来张炀杰发现, 蒋叶桢的power直接调用的math里的, 改成快速幂后, 终于 3h6min +2. 然后集火B, 蒋叶桢表示写过, 我也觉得眼熟, 但是就是没人会做. 光荣两题下班.

  1. 可能平常要注意复习? 写完题解后一般就不看了, 可能复习题解会有很大帮助.

$n \times n$ 的网格, 其中 $m$ 个格子需要填上非负数, 其他格子不能填数. 而且需要满足, 第 $i$ 行最大值为 $r_i$, 第 $i$ 列最大值为 $c_i$, 且这些数不超过 $k$. 问这些数加起来最小是多少. 保证有解.

$1 \le n \le 2 \times 10^3, 1 \le m \le 8 \times 10^5, 1 \le k \le 10^6$

一个很重要的套路, 网格填数(或者填其他什么东西), 对行和列构造二分图. 很多题都是这样, 这点以前一直没注意.

然后考虑怎么填数的和才会更小. 那当然是如果某行和某列的最大值相同, 把这个位置的数填成最大值. 对于一个数值 $a$, 我们尝试计算他的贡献. 如果有 $x$ 行的最大值是他, $y$ 列的最大值是他, 那么他的系数就是 $a(x + y - z)$, 其中, $z$ 数 $a$ 填在网格中, 能够同时满足行最大和列最大的个数. 那么对于固定数值 $a$ 来说, 我们的任务就是求 $z$. 这就可以用二分图匹配来做了. 如果某个位置对应的行和列最大值相同且为 $a$, 那就在这一行和这一列之间连一条边. 连完以后跑个最大匹配就做完了. 然后还会发现, 一个格子对应了一条边, 而且因为行和列最大值相等的情况下才会连边, 所以对不同的数值, 构造的二分图是"完全不相交"的, 是独立的, 相互之间不会影响. 所以可以直接把整个二分图构造出来, 然后看如果这一行有匹配到某一列, 那么这一行的最大值对答案的贡献就减去一个.

用匈牙利跑匹配, 总复杂度 $O(n^3 + m)$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

int n, m, k, mxr[MAXN], mxc[MAXN], mx[MAXN], my[MAXN];
bool vis[MAXN];
VI G[MAXN];
LL ans = 0;

bool match(int u) {
  for (int v : G[u]) if (!vis[v]) {
    vis[v] = 1;
    if (!my[v] || match(my[v])) {
      mx[u] = v;
      my[v] = u;
      return true;
    }
  }
  return false;
}

int main() {
  scanf("%d%d%d", &n, &m, &k);
  for (int i = 1; i <= n; i++) {
    scanf("%d", mxr + i);
    ans += mxr[i];
  }
  for (int i = 1; i <= n; i++) {
    scanf("%d", mxc + i);
    ans += mxc[i];
  }
  for (int i = 1; i <= m; i++) {
    int r, c;
    scanf("%d%d", &r, &c);
    if (mxr[r] == mxc[c])
      G[r].push_back(c);
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++)
      vis[j] = 0;
    match(i);
  }
  for (int i = 1; i <= n; i++)
    if (mx[i])
      ans -= mxr[i];
  printf("%lld\n", ans);
  return 0;
}

长度为 $n$ 的序列 $a$, $q$ 次操作, 每次如下一种:

  1. 0 l r x 区间 $[l, r]$, $a_i \leftarrow a_i \oplus x$
  2. 1 l r x 区间 $[l, r]$, $a_i \leftarrow a_i \oplus (x + i - l)$

$\oplus$ 是按位异或.

求所有操作后的数组.

$1 \le n \le 6 \times 10^5, 1 \le q \le 4 \times 10^5, 0 \le a_i < 2^30$

并看不懂dls(还是他学弟?)的做法. 我太菜了

第一个操作直接维护差分数组 $d$, 即 $d_l \leftarrow d_l \oplus x, d_{r+1} \leftarrow d_{r+1} \oplus x$. 只需要对 $d$ 做一次前缀和, 然后异或上对应的 $a_i$ 即可.

考虑第二个操作, 先考虑一个大的"差分", 设一个操作 update(p, x), 为 $a_{p+i} \leftarrow a_{p+i} \oplus (x + i)$, 由于异或的减等于加的性质, 对一个区间做操作1, 就是 update(l, x), update(r+1, x+r-l+1).

位运算的套路是按位做, 那么按位看看会发生什么. 一个从 $0$ 开始的连续的序列, 每次加增加 $2^i$ 个数, 才会改变第 $i$ 位的值. 比如从 $0$ 开始的连续的数在二进制下为:

$$0\color{red}0\color{unset}00, 0\color{red}0\color{unset}01, 0\color{red}0\color{unset}10, 0\color{red}0\color{unset}11, 0\color{red}1\color{unset}00, 0\color{red}1\color{unset}01, 0\color{red}1\color{unset}10, 0\color{red}1\color{unset}11, 1\color{red}0\color{unset}00, 1\color{red}0\color{unset}01, 1\color{red}0\color{unset}10, 1\color{red}0\color{unset}11, 1\color{red}1\color{unset}00, \dots$$

第 $2$ 位在上面已经标出, 拿出来看是这样的:

$$0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, \dots$$

这东西不也是区间异或吗? 那就维护差分数组 $d$. 需要在每一段 $1$ 的开始, 和每一段 $1$ 结束的下一位, 也就是每一段 $0$ 的开始异或上 $1$, 然后就会发现, 对于第 $i$ 位, 需要每隔 $2^i$ 位对 $d$ 的第 $i$ 位异或一下.

但是, 每次操作枚举第 $i$ 每隔 $2^i$ 进行一次异或, 这样复杂度较高. 但是可以记录一下每一个位置的数每一位第一个"需要异或标记". 最后在处理的时候, 将这个标记"向后推" $2^i$ 个数. 这样本来一次操作就要每隔 $2^i$ 进行一次异或, 变成了现在所有操作完成后, 枚举 $i$ 每隔 $2^i$ 进行一次异或.

现在来看具体的 update(p, x) 函数, 首先枚举第 $i$ 位, 由于x并不是0, 会造成类似于这样的东西, 以 $x=3, i=2$ 举例:

$$0, 1, 1, 1, 1, 0, 0, 0, 0, 1, \dots$$

所以需要找到第一个"整块"的 $1$ 或 $0$ 的位置, 在这个位置上打标记. 这个很好解决, 就把连续的数分成 $2^i$ 组, 然后用 $x$ 去模 $2^i$, 就知道他是一组里的第几个, 所以 $x - (x \bmod 2^i)$ 就是找到了第一个整块的 $0$ 或者 $1$, 打上标记. 当然如果碰到这样的情况:

$$1, 1, 0, 0, 0, 0, 1, 1, 1, 1, \dots$$

第个一数是1, 那就需要对差分数组进行异或.

复杂度 $O(n\log a + q\log a)$

连续区间并且和异或有关, 就有"分块"的性质, 要善于挖掘.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

int q, n, a[MAXN], d[MAXN];
bool tag[MAXN][32];

void update(int p, int x) {
  if (p > n)
    return;
  for (int i = 0; i < 30; i++) {
    int pw = 1 << i;
    if (x & pw)
      d[p] ^= pw;
    int first = p + pw - (x % pw);
    if (first <= n)
      tag[first][i] ^= 1;
  }
}

int main() {
  scanf("%d%d", &n, &q);
  for (int i = 1; i <= n; i++)
    scanf("%d", a + i);
  while (q--) {
    int op, l, r, x;
    scanf("%d%d%d%d", &op, &l, &r, &x);
    if (op)
      update(l, x), update(r + 1, r - l + x + 1);
    else
      d[l] ^= x, d[r+1] ^= x;
  }
  for (int j = 0; j < 30; j++)
    for (int i = 1; i <= n; i++) {
      if (tag[i][j])
        d[i] ^= 1 << j;
      int nxt = i + (1 << j);
      if (nxt <= n)
        tag[nxt][j] ^= tag[i][j];
    }
  for (int i = 1; i <= n; i++) {
    d[i] ^= d[i-1];
    a[i] ^= d[i];
  }
  for (int i = 1; i <= n; i++)
    printf("%d%c", a[i], " \n"[i==n]);
  return 0;
}
更新于 2021-08-10
 训练, 牛客多校
返回 | 主页