Contest Info

date: 2019.02.21 10:00-15:00

practice link

Solutions

A. Magic

题目大意：有 \(n\) 个盒子，开始某个盒子有一个球。snuke 可以开盒子来找球，看完之后需要关闭盒子，第 \(i\) 个盒子最多开 \(a_{i}\) 次。有一个魔术师，可以在 snuke 开启某个盒子前（并且不能在某个盒子开启的时候）把球转移到另外一个盒子，最多可以转移 \(k\) 次。求一个 snuke 必然能找到球的开启顺序（即不论球开始在哪个盒子，魔术师怎么操作），或判断不存在这样的顺序。

题解：我们先固定 snuke 的操作顺序，考虑魔术师的最优行动。显然魔术师开始时会把球放在 \(1\sim n\) 中最后一个出现的盒子里。例如 \(1,2,\cdots,n\)，他会将球放入 \(n\) 中。在 snuke 开启 \(n\) 之前，魔术师需要把球移动到别的盒子里，显然应该是算上本次的 \(n\) 在内， \(1\sim n\) 中最后一个出现的盒子里。例如 \(1,2,\cdots,n,n-1,\cdots,1\)，应该移动到 \(1\) 中。

这样一来 snuke 的行动就比较好分析了，他第一轮一定是先打开 \(1\sim n\) 的某个排列，之后每一轮打开 \(n-1\) 个盒子，每一轮与上一轮的最后一个盒子组成一个 \(1\sim n\) 的排列。如果能够构造出 \(k+1\) 轮，那么 snuke 赢。

对于大于等于 \(k+1\) 的 \(a_{i}\)，不管怎样都可以凑够 \(k+1\) 轮，而对于小于 \(k+1\) 的 \(a_{i}\)，我们就需要利用每轮重复的那个元素来减少 \(i\) 的出现次数。这个比较简单，只需要注意同一个元素不能在连续两轮重复即可。

B. Multiple of Nine

题目大意：要求你统计满足下列要求的数字串 \(s\) 的数量：

• \(s\) 的长度为 \(n\)
• \(s\) 由 '0'-'9' 组成
• 给你 \(Q\le15\) 个区间，\(s[l_{i}...r_{i}]\) 必须是 \(9\) 的倍数

题解：我们把序列求个前缀和，那么要求就变成了 \(S_{r_{i}}\) 和 \(S_{l_{i}-1}\) 应该同余，我们把 \(l_{i}-1\) 和 \(r_{i}\) 称做关键点。首先把相关的限制合并一下，可以得到若干个关键点的连通块。

考虑朴素的 \(dp\)，记录之前每个关键点模 \(9\) 的余数。转移时会发现，长为 \(x\)，模 \(9\) 余 \(m\) 的串的方案数，在 \(m\neq0\) 时都是一样的。也就是说，我们只关心每对相邻的关键点模 \(9\) 的余数是否相等。

不妨先把所有相邻的关键点模 \(9\) 的余数都看做不等，这样我们可以得到一个初始的答案，只要我们把所有模 \(9\) 相等的区间 \(dp\) 出来，修正一下初始答案即可。我们设 \(dp[i][S]\) 表示模 \(9\) 余 \(0\sim i\) 的连通块集合为 \(S\)，初始答案需要乘的修正系数。转移时，我们枚举模 \(9\) 余 \(i+1\) 的连通块集合，那么我们就能知道模 \(9\) 同为 \(i+1\) 的相邻的关键点有哪些，也就可以计算修正系数了。

时间复杂度 \(\mathcal{O}(9\cdot3^{Q})\)。

C. Triangular Lamps

题目大意：在平面直角坐标系上，每个整点是黑的或白的。定义一种操作：对某个整点 \((x,y)\)，翻转 \((x,y),(x+1,y),(x,y+1)\) 的颜色。给你一个状态，有 \(n\) 个黑点，保证这个状态是由某个恰有一个黑点的状态，通过若干次操作得到的。求这个黑点的坐标。

题解：首先我们把操作限制一下：只有 \((x,y+1)\) 是黑色时，我们才能操作。这样我们可以把新操作视为将 \((x,y+1)\) 转移到 \((x,y),(x+1,y)\) 上。我们把给出的黑点用新操作全部转移到 \(x\) 轴上，可以证明即使允许使用原操作，\(x\) 轴上的序列也是唯一的。

如果我们将 \((x,y)\) 转移到 \(x\) 轴上，我们很容易观察出，从 \((x,0)\) 开始，恰好是杨辉三角的第 \(y\) 层对 \(2\) 取模。反过来，如果我们知道了转移后 \(x\) 轴上的某个黑点，就可以找出 \(x\) 轴上最左和最右的黑点，这样我们就求出了答案。具体地说，寻找最左黑点时，我们依次尝试询问 \(\displaystyle{{n\choose m-2^{60}},{n\choose m-2^{59}},\cdots}\)，如果减去后二项式系数仍为 \(1\)，那么就说明 \(m\) 的该位为 \(1\)（否则减去后 \(m\) 为负数，矛盾），我们可以把这个 \(2\) 的幂减掉，再接着询问。寻找最右黑点时，注意到 \(\displaystyle{{n\choose m}=1}\)，当且仅当 \(m\subset n\)，我们依次尝试询问 \(\displaystyle{{n\choose m+2^{60}},{n\choose m+2^{59}},\cdots}\)，如果加上后二项式系数仍为 \(1\)，那么就说明 \(m\) 的该位为 \(0\)，\(n\) 的该位为 \(1\)（否则加上后 \(m>n\)，矛盾），我们可以把这个 \(2\) 的幂加上，再接着询问。

最后的问题是如何找出一个黑点。我们可以证明：\(\displaystyle{\sum_{k}{n\choose 3k},\sum_{k}{n\choose 3k+1},\sum_{k}{n\choose 3k+2}}\) 中至少有一个奇数，不妨设模 \(3\) 余 \(i\)。那么我们在模 \(3\) 余 \(i\) 的前提下二分即可，显然总是有一半有奇数个黑点。

I. Union 2SAT

题目大意：有\(m\le10^5\)条原子 2-sat 公式，给出一个合并的顺序，要求输出每次合并后是否可以满足这个集合的全部公式。

题解：将合并的树轻重链剖分，每条重链二分，对整个子树用tarjan判断，时间复杂度\(O(n\log^2{n})\).