Contest Info

date: 2019.03.18 18:40-23:40

practice link

Solutions

A. A Place For My Head

题目大意：给定了 \(n(1\le n\le 2\cdot 10^5)\) 个元素的可选位置区间 \([l_i, r_i]\)，让你找到字典序最小的满足限制的排列。

题解：首先判断无解，我们从左往右填数字，每次选择 \(l_i\) 小于等于当前位置的最小的 \(r_i\) 填。如果有解，我们考虑从左往右贪心的填尽可能小的数字，同时保证剩余的元素有解。

我们将元素和位置视为二分图的两部，元素向位置连边，因为当前已经有解，所以满足 hall 定理。因为我们是从左往右在填数字，所以每次影响到的位置区间是一个前缀，同时很容易证明只有连续的位置区间，才能取到 hall 定理中 \(|N_G(W)|-|W|\) 的最小值（我们要保证这个最小值一直不小于 \(0\)）。

所以我们只需要维护当前还未填的位置的前缀，设其长度为 \(i\)，区间完全在这个前缀里（\(r_i\) 小于等于前缀）的元素个数 \(a_i\)，那么我们就是要维护 \(i-a_i\) 的最小值。假设当前填的位置为 \(j\)，所有未填位置的 \(i\) 会 \(-1\)，同时区间 \([r, n]\) 的 \(a_i\) 会 \(-1\)，所以区间 \([j + 1, r)\) 维护的 \(i-a_i\) 会 \(-1\)。

那么做法就是每次找到 \(i-a_i\) 的最左的最小值，如果其为 \(0\)，那么就限制了元素 \(r\) 的选择；如果不为 \(0\) 就没有限制。这里也用线段树维护，下表为元素，值为其 \(r\)。

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\) 即可。

C. Lying From You

题目大意：给你若干条平面上的直线 \(y=a_{i}x+b_{i}\)，要求你修改这些直线为 \(y=a_{i}'x+b_{i}'\) 使得它们相交于一点，代价为 \(\sum |a_{i}-a_{i}'|+|b_{i}-b_{i}'|\)。求最小代价。

题解：设直线交于 \((x_{0},y_{0})\)，那么对于一条直线，代价为 \(|y_{0}-a_{i}'x_{0}-b_{i}|+|a_{i}'-a_{i}|\)。

• 若 \(x_{0}=0\)，那么上式的最小值为 \(|y_{0}-b_{i}|\)
• 否则上式的最小值为 \(\min(|y_{0}-a_{i}x_{0}-b_{i}|,|\frac{y_{0}-b_{i}}{x_{0}}-a_{i}|)=\frac{|y_{0}-a_{i}x_{0}-b_{i}|}{\max(1,|x_{0}|)}\)

第一种情况也可以用第二种情况概括。

我们固定一个 \(x_{0}\)，那么显然 \(a_{i}x_{0}+b_{i}\) 是常数，所以 \(y_{0}\) 一定是这些值的中位数。容易发现，在两个交点之间，\(y_{0}\) 一定在同一条线段上取得。下面分 \(x_{0}\in[-1,1]\) 和 \(x_{0}\in[1,+\infty)\) 两种情况讨论。另外一侧对称一下即可。

对于第一种情况，最小值是一个分段的一次函数 \(y=ax+b\)，那么 \(y'=a\)。我们不妨设有奇数条直线，那么有 \(a=-\sum_{i=1}^{\frac{n-1}{2}}a_{i}+0a_{\frac{n+1}{2}}+\sum_{\frac{n+3}{2}}^{n}a_{i}\)。其中，\(a_{i}\) 按照直线从下方到上方排序。\(x_{0}\) 增大，经过一个交点时，一定是一条斜率大的直线跑到一条斜率小的直线上方，观察上式可知，\(a\) 一定会变大。所以在 \([-1,1]\) 上是一个凸函数。

对于第一种情况，最小值是一个分段的反比例函数 \(y=a+\frac{b}{x}\)，那么 \(y'=-\frac{b}{x^{2}}\)。类似可知，\(b\) 一定会递减。所以在 \([1,+\infty)\) 上也是一个凸函数。

所以我们可以三分解决这个问题。三分的右边界只需要超过最右边可能的交点即可。另外第二种情况下有可能会一直单调减，所以我们需要求一下 \(x\to+\infty\) 的极限。这个极限是到所有 \(a_{i}\) 的距离和的最小值。

D. Don’t Stay

题解：有一个无限长的灯泡序列。定义一段程序，包括 LRX 三种指令，分别意为向左、向右移动一格，以及改变当前位置的灯泡状态。开始时在 \(0\)。现在有一段程序 \(S\)，要求你构造一段程序 \(T\)，使得执行 \(TST'\) 后，灯泡的状态和给定的一样。\(T'\) 的意思是，把 \(T\) 左右倒过来，然后再把 LR 互换。

题解：先考虑 \(T\) 和 \(T'\) 会改变哪些位置的状态。假设 \(T\) 改变了 \(a_{1},\cdots,a_{n}\) 位置的状态，最后到了位置 \(l\)。那么 \(T'\) 就会改变 \(a_{n}-l,a_{n-1}-l,\cdots,a_{1}-l\) 位置的状态，最后到达位置 \(-l\)。可见，\(T'\) 的实质是将 \(T\) 的操作向左平移 \(l\)，最后到达的位置向左平移 \(2l\)。

如果 \(S\) 的位置偏移量是 \(0\)，容易发现 \(T\) 和 \(T'\) 的操作会相互抵消。那么只要判断一下 \(S\) 是否能够经过平移（显然用 \(T\) 很容易做平移操作）得到目标状态，这个 KMP 一下即可。这个似乎平移一下就好了，不需要 KMP。

否则，设 \(S\) 的位置偏移量是 \(s\)。容易发现，\(T\) 和 \(T'\) 的操作合并起来，所有模 \(s\) 同余的位置都有偶数盏灯是亮的，因而 \(T\) 的偏移量必须使得 \(S\) 操作后，所有模 \(s\) 相同的位置亮的灯的数量的奇偶性和目标状态相同。这可以用 KMP 得到。可以证明，满足这个条件时一定能构造出解，这里就不赘述了。

E. In The End

题目大意：有一个 \(n\times m\) 的网格（\(n\le 6\)），现在每一列会随机恰好一行出现一个蛋糕，每行的概率给定。一个机器人从第一列任意一格开始走，每一步可以向右上、右、右下走一步。机器人会收集路上的所有蛋糕。设 \(f(m)\) 为所有局面下机器人最多收集的蛋糕数的期望。求 \(\lim_{m\to+\infty}\frac{f(m)}{m}\)。

题解：固定一个局面后，显然是一个经典的 \(dp\)。我们考虑记录 \(dp\) 的状态，即用一个至多六维的向量来表示当前的 \(dp\)（当然要减掉 \(offset\) 使得最小值为 \(0\)）。由于向左至多三格的状态的任意一行就可以转移到当前状态的所有行，所以任意状态的任意两维的差不会超过 \(3\)。打表可知实际的状态只有 \(400\) 多种。

注意到这个随机过程是一个马尔可夫链，而出题人说他们保证了在题目数据下这个马尔可夫链一定会收敛。设 \(A\vec{v}=\vec{v}\)，其中 \(A\) 是状态转移矩阵，\(\vec{v}\) 是收敛时各状态的概率。用高消即可解出 \(\vec{v}\)。然后简单算一下转移时最大值增长的情况即可。

F. From The Inside

题目大意：给你一个 \(n\times m\) 的网格，两个人玩游戏，每次从中切割一个 \(k\times k\) 的正方形网格扔掉，不能操作者输。保证 \(k\le n,m\le 3k\)。问先手有多少种操作可以获胜。

题解：这里仅给出各种情况下的胜负，具体证明略。不妨设 \(n\le m\)。

• 若 \(k=1\)，那么答案很简单。

• 若 \(n=m=3k\)，那么先手只有放在正中间才能获胜。答案为 \(1\)。

• 若放置之后四周的宽度都小于 \(k\)，那么先手胜。

• 若放置后只有一边宽度在 \([k,2k)\) 之间，不妨设这边在 \(m\) 上
  • 若 \(n\le3k-2\)，那么先手负。
  • 若 \(n=3k-1\)，那么先手胜。
• 若放置后有一边宽度为 \(2k\)，那么这条边只能是 \(m=3k\)
  • 若 \(n\le3k-2\)，那么先手负。
  • 若 \(n=3k-1\)，那么先手胜。
• 若放置后 \(m=3k\) 的两边宽度均为 \(k\)，那么先手胜。
• 若放置后 \(n,m\) 各有一边宽度在 \([k,2k)\) 之间，那么先手负。
• 若放置后 \(n\) 有一边宽度在 \([k,2k)\) 之间，\(m\) 有一边宽度为 \(2k\)
  • 若 \(n\le3k-2\)，那么先手胜。
  • 若 \(n=3k-1\)，那么先手负。

• 若放置后 \(n\) 有一边宽度在 \([k,2k)\) 之间，\(m\) 的两边宽度均为 \(k\)，那么先手负。

G. Numb

题目大意：\(n(2\le n\le 1000)\) 是一个偶数，构造一个二进制数 \(a = \overline{a_1a_2\cdots a_n}\)，满足 \(n\mid a\)，且 \(\overline{a_1a_2\cdots a_i}(i = 1, 2, \dots, n)\) 模 \(n\) 余数互不相同。不允许前导 \(0\)，可以证明在给定限制下一定有解。

题解：

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})\).

J. Leave Out All The Rest

签到题。

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)\) 计算。