目录

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

太弱小了! 没有力量!

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

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

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

n×nn \times n 的网格, 其中 mm 个格子需要填上非负数, 其他格子不能填数. 而且需要满足, 第 ii 行最大值为 rir_i, 第 ii 列最大值为 cic_i, 且这些数不超过 kk. 问这些数加起来最小是多少. 保证有解.

1n2×103,1m8×105,1k1061 \le n \le 2 \times 10^3, 1 \le m \le 8 \times 10^5, 1 \le k \le 10^6

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

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

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

cpp

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;
}

长度为 nn 的序列 aa, qq 次操作, 每次如下一种:

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

\oplus 是按位异或.

求所有操作后的数组.

1n6×105,1q4×105,0ai<2301 \le n \le 6 \times 10^5, 1 \le q \le 4 \times 10^5, 0 \le a_i < 2^30

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

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

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

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

0000,0001,0010,0011,0100,0101,0110,0111,1000,1001,1010,1011,1100,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

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

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

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

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

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

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

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

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

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

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

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

cpp

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;
}
评论
  • 按正序
  • 按倒序
  • 按热度
Powered by Waline v3.5.6