Petrozavodsk Summer-2017. Moscow IPT Contest

Contest Info

date: 2019.03.18 18:40-23:40

practice link

Solutions

B. New Divide

题目大意:定义数组 \(b\) 上的操作为:

\[ LP(b)=\max\limits_{i=0,1,\dots,k}(b_1\oplus \dots \oplus b_i)+(b_{i+1}\oplus \dots \oplus b_k) \]

现在给了你一个长度为 \(n\)\(1\le n\le 10^6\))的数组 \(a\)\(0\le a_i\le 10^6\)),让你求 \(LP(a_1),LP(a_1,a_2),\dots,LP(a_1,a_2,\dots, a_n)\)

题解\(dp[S]\) 表示数组 \(a\) 的最小的前缀 \(i\),其异或和是数字 \(S\) 的父集。dp 的初值为 \(dp[\oplus _{j\le i} a_j]=i\)(如果多个相同的 \(\oplus_{j\le i}a_j\),取较小的 \(i\))。

对某一个前缀 \(k\),设它的前缀异或和 \(t\),我们只考虑为 \(0\) 的位(为 \(1\) 的位贡献是固定的)。我们希望找到前缀 \(k\) 的一个前缀 \(i\),它的异或和 \(x\) 尽可能在上述 \(0\) 的位上取 \(1\)。那么我们只需要贪心的确定 \(x\),时刻保证 \(dp[x]\le k\) 即可。

H. One Step Closer

题目大意:给你一个 \(n\times m\) 的表格,由 +- 组成。一步操作可以选取一个位置,把它所在的行和列翻转,该元素本身仅被翻转一次。现在进行如下的操作:每轮把所有 + 的位置记录下来,然后对每个记录下来的位置进行一步操作,直到所有元素都为 -。问要进行多少操作。

题解:每一轮操作等价于,把整个表格置为 -,然后对所有记录下来的行和列分别翻转(记录下来的元素要翻转两次)。因此可以发现两个性质:如果不关心行间、列间的顺序,每一轮表格的形态仅取决于上一轮中有奇数个 + 的行,奇数个 + 的列的数量;如果某一轮奇数个 + 的行、列都有偶数个,那么下一轮游戏就会结束。

假设初始有 \(x,y\) 个奇数行、列,可以注意到不管怎么操作,奇数行的数量都只会是 \(0,x,n-x,n\),奇数列同理。也就是说至多只有 \(16\) 种不同的状态,如果开始循环而游戏还没有结束,那么游戏就会无限进行下去。

实现时用扫描线求出初始的奇数行、列,然后直接模拟即可。

I. Invisible

题目大意:假交互题,真强制在线。给出一个序列\(a_1,\cdots,a_n\)\(n,a_i\le10^5\).若干次询问,每次要么修改一个位置,要么询问区间\([l,r]\)是否存在一个出现次数为奇数的数,是则输出任意一个,否则输出-1.

题解:分块,设块的大小为\(T\),每一个块用一个bitset,维护块前缀的数出现次数的奇偶性。则修改的时间复杂度为\(O(nT)\)。询问时中间的整块用两个前缀异或起来,然后零散的点插入进去,然后找最小的\(1\)即可,时间复杂度为\(O(n(\frac{n}{T}+\frac{n}{64}))\)\(T\)可以随便取一个\(\sqrt{n}\),或者取\(T=64\)最小化空间复杂度。时间复杂度为\(O(\frac{n^2}{64})\).

K. Faint

题目大意:将 \(n\) 的所有 k-组合 按字典序从上到下排好,设得到的矩阵为 \(A\)。给出 \(m\),求 \[ \sum_{i=1}^{{n\choose k}-1}|A_{i,m}-A_{i+1,m}| \] 题解:注意到 \(m+1,\cdots,k\) 这些列对答案没有影响,可以把它们删去后再合并相同的行。接下来假定 \(m\) 是最后一列。

对于上升的答案,枚举 \(m-1\) 列的元素,有 \(\sum_{i=1}^{n-1}(n-i-1){i-1\choose m-2}\)

对于下降的答案,枚举最后一段连续的长度,以及前面不连续的那一个元素的值,有 \(\sum_{l=1}^{m-1}\sum_{i=1}^{n-l-1}{i-1\choose m-l-1}\),内层的和式可以 \(\mathcal{O}(1)\) 计算。