ZROI WC Round5 题解

Problem A

题意

给定一个长度为 \(n\) 的序列，操作是交换两个相邻的数，要求将序列变成先单调不降再单调不升，求最小操作数，注意可以完全单调不降或者完全单调不升

想法

发现最小的数一定在最左侧或者最右侧

有一个暴力的做法是按照从小到大的顺序，每次看向哪边比较近就交换到哪一侧，由于不管交换到哪一个剩下的序列都是一样的，所以这个做法是正确的

下面就是优化这个算法，不难发现一个数如果移动到最左侧，那么它左侧的比它小的数肯定都移动到左侧，所以可以用树状数组算出每个数向左或者向右最终的位置，统计一下即可得到答案

Review

有一个错误的直观想法就是认为一定存在一条分界线，然后把两边的数排序

它的错误在于不能处理一边排序，一边仍旧是一个山峰形状但是山峰和排好序的一边能够平起来的情况

这种题一般都考虑最大或最小值的最终位置，考场上我一直在考虑最大值的位置，事实上最大值并不能将序列分成两部分，所以应当考虑最小值的位置

Problem B

题意

有一个 \(01\) 矩阵，求 \(\sum_{i=1}^{n}\sum_{j=1}^{m}i\times j \times rank(T(A,i,j))\) 对 \(998244353\) 取模的值，其中 \(rank\) 表示矩阵的秩，\(T(A, i, j)\) 表示矩阵 \(A\) 把 \((i,j)\) 这一位翻转之后的矩阵

题解

有两种做法，暂时只写会的一种

考虑暴力怎么写，就是直接枚举每一行，然后把除了这一行以外的玩意全部压进线性基里面，然后枚举这一行每一个位置，把它翻转，然后往线性基里面扔，复杂度 \(O(\frac {n^4m} {32})\)　（竟然能过 \(n=100\) 的点）

首先不难发现可以分治，这样就把一个 \(O(n)\) 变成了 \(O(\log n)\)，\(solve(l, r)\) 表示询问第 \(l\) 行到第 \(r\) 行之间的答案，然后就可以先修改一半询问另一半再撤回修改操作（基础分治）

这样复杂度 \(O(\frac {n^3m \log n} {32})\)，还是不行，需要跑 \(4\) 到 \(5\) 秒

然后只能考虑在询问某一行上减少复杂度

我们发现对于某一行，翻转不同的两个位置，差距实际上很小

所以我们考虑先不翻转任何一位，直接塞进线性基里，然后修改第 \(j\) 位的时候直接和线性基里面的第 \(j\) 个异或即可

但是这样可能会错误，观察发现错误原因是你和第 \(j\) 位直接异或会导致第 \(j\) 位后面的某些位又变成 \(1\) 了，所以我们需要一个最简线性基，这并不难实现，我们在每一次插入数的时候，假设插入 \(x\) 在第 \(j\) 位上，我们先把它化简，就是把这一位之后的位置在线性基里面跑一遍，尽量异或成零，然后把这一位之前的数化简，就是如果存在一个更高位对应的数里面这一位是 \(1\)，就跟现在这个数异或，这样保证每一个位置对应的数都已经尽量满足除了那个位置都是零，保证了正确性

代码很简单



inline void fuck(int dep, int p) {

  rrep(i, p - 1, 1) if (b[dep][p][i] && b[dep][i].any()) b[dep][p] ^= b[dep][i];

  rrep(i, m, p + 1) if (b[dep][i][p]) b[dep][i] ^= b[dep][p];

}

这样的话，我们没有办法撤销操作，所以我们记录下每一层的线性基，也就是上面代码中的 \(b[dep]\)

综上所述，复杂度 \(O(\frac {n^2m\log n} {32})\)，实际上跑的很快，\(n=1000\) 大概跑 \(300 \sim 400ms\)

Review

每个部分都不难，但是合起来有些难度

想法很自然，每个修改内部做到线性的方法很巧妙

Problem C

题意

给定一些集合 \(A_1,A_2,A_3,\dots,A_k\)，定义一个集合 \(A\) 能将两个集合 \(X,Y\) 分离当且仅当满足以下两个条件之一：

\(X \subseteq A\) 且 \(Y \cap A = \emptyset\)
\(Y \subseteq A\) 且 \(X \cap A = \emptyset\)

求有多少个 \(X,Y\)　满足 \(X,Y \subseteq \{1,2,3,\dots, n\}\) 且满足至少存在一个 \(A_i\) 能够将 \(X,Y\) 分离

题解

不难发现是一道容斥题

如果直接暴力枚举哪些 \(A\) 能够将两个集合分离，会存在问题，就是当 \(X \subseteq A\) 且 \(Y \cap A = \emptyset\) 的时候会存在另外一个 \(A\) 未被选择但是满足 \(Y \subseteq A\) 且 \(X \cap A = \emptyset\)，这样并没有办法去重

所以我们得枚举哪些集合是 \(X\) 的超集，哪些集合是 \(Y\) 的超集，并且满足所有 \(X\) 的超集都与 \(Y\) 无交，\(Y\) 的超集与 \(X\) 无交

这样枚举完了之后扫一遍看哪些数还能被 \(X\) 选，哪些数还能被 \(Y\) 选，然后算一下就好了，复杂度 \(O(3^m n)\)，期望得分 \(70\) 分

我们假设将所有的 \(A_i\) 分成 \(U\) 和 \(V\)，满足 \(U\) 里面的 \(A_i\) 都是 \(X\) 的超集，\(V\) 里面的 \(A_i\) 都是 \(Y\) 的超集，也就是说，如果某个数 \(a\) 是 \(X\) 的一个元素，则 \(a\) 满足是所有 \(U\) 中集合的元素，而且不是任何一个 \(V\) 中集合的元素，瓶颈在于枚举 \(U,V\)

我们考虑枚举 \(a\)，对于每一个元素 \(a\)，我们预处理出包含 \(a\) 的所有 \(A_i\) 为 \(f(a)\)

这时候我们枚举 \(S=U+V\)，之前的瓶颈在于还得枚举一个 \(U\) 是 \(S\) 的子集，但是我们发现这样的 \(U\) 必须满足是某个元素的 \(f\) 值，所以这样的 \(U\) 最多只能有 \(n\) 个，同样 \(V\) 最多也只能有 \(n\) 个，所以复杂度 \(O(2^mn)\)，可以通过此题

Review

容易陷入枚举哪些 \(A\) 能够将两个集合分离的误区，事实上正解也是这个，但是实际上是在枚举 \(U+V\)，本质不同

所以需要先想出 \(70\) 分的暴力，才有希望想到正解，暴力还是比较自然的