Contest Info

date 2017.07.27 12:00-17:00

practice link

Solutions

A. Is Derek lying?

题目大意：有 \(n\) 道选择题，给出两个人的分数和他们每道题选择的选项，问是否有一种答案的分布方式使它合法。

题解：统计出两人选项相同的题目有多少道，让这些题目尽可能都正确，再判断剩下的题目是否能让两人正确的题数足够多。

B. hash

题目大意：给出一个由给定的 \(hash\) 函数确定的随机生成的 \(1000000 \times 1000000\) 的 \(01\) 矩阵，输入其中一个 \(1000 \times 1000\) 的子矩阵，求这个子矩阵在矩阵中的位置（左上角对应的坐标）。

题解：(官方题解做法）在原矩阵中选取一些 \(L \times L\) 的子矩阵，从左上角 \((0,0)\) 开始，横坐标或者纵坐标每隔 \(K\) 个位置取一个子矩阵，当 \(2L+K \leq 1000\) 时，由鸽巢原理知，至少有一个 \(L \times L\) 子矩阵会被输入的 \(1000 \times 1000\) 的矩阵完全包含。我们再使用一个 \(hash\) 来快速比较两个 \(L \times L\) 的矩阵是否相同，我们可以取 \(L=7\) ，这样就能将矩阵压到一个 \(long long\) 型的整数里，然后枚举输入的 \(1000 \times 1000\) 的矩阵中的所有 \(L \times L\) 的子矩阵，记录下它们的 \(hash\) 值和在矩阵中位置信息，通过排序和二分来实现快速查找。最后，枚举原矩阵中的那些 \(L \times L\) 的子矩阵，计算 \(hash\) 值，如果查找成功，就去暴力判断是否是答案。

C. Maximum Sequence

题目大意：给出长度为 \(n\) 的两个数列 \(\{ a_i \}\) 和 \(\{ b_i \}\)，\(1 \leq b_i \leq n\)，已知 \(a_i \leq \max\limits_{b_k \leq j < i} \{ a_j - j\}\)，\(n+1 \leq i \leq 2n\)，其中 \(b_k\) 不能两次选择同一个 \(b_i\)，要求 \(\max \sum_{n+1}^{2n} a_i\)，输出时对 \(1000000007\) 取模。

题解：\(a_i \leq \max\limits_{b_k \leq j < i} \{ a_j - j\}\) 可以拆为 \(a_i \leq \max\limits_{b_k \leq j \leq n } \{ a_j - j\}\) 和 \(a_i \leq \max\limits_{n+1 \leq j < i} \{ a_j - j\ \}\)，第一部分对于每个 \(b_k\) ，都有一个确定的值，且关于 \(b_k\) 递减，因此，最优的方案需要使 \(a_i \leq \max\limits_{n+1 \leq j < i} \{ a_j - j\ \}\) 尽可能大，我们让 \(a_{n+1}\) 取最大，则后面的所有数的第二部分都可以取到 \(a_{n+1} - (n+1)\) 这个位置的贡献，这个方案就是最优的。如果有个位置 \(i>n+1\) 满足 \(a_i-i>a_{n+1}-(n+1)\)，那么交换 \(i\) 和 \(n+1\) 使用的 \(b_k\) 一定会更优。

D. Puzzle

题目大意：给了你一个 \(n \times m\) 的矩形，按照题目给的构造方法填数字 \(1, \dots, nm - 1\)，右下角为空格。问你是否能移动为从左到右从上到下依次为数字 \(1, \dots, nm - 1\)，同样要求右下角为空格。

题解：给出如下三个性质：

性质一：排列相邻互换改变逆序对奇偶性。

性质二：去掉空格，将矩形从左到右从上到下看做一个排列，移动操作不改变逆序对的奇偶性。

证明：空格左右移动显然不改变数列，也不改变逆序对奇偶性。空格上下移动，相等于生成的数列中发生 \(m-1\) 次相邻互换。最后要求右下角为空格，所以空格上下移动的次数为偶数，也不改变奇偶性。 \(\Box\)

性质三：所有局面都可以通过一定的操作得到右下角为如下图的局面。以 \(4\times 7\) 为例。

因为对于任意一个 \(2\times 3\) 或者 \(3\times 2\) 的局面，我们可以分情况讨论，发现都可以转移到下图中左上角的局面。很容易推广到 \(n\times m\) 的情况。

我们距离目标状态就只剩下了最后一个 \(2\times 2\) 的区域。

我们暴力枚举 \(6\) 种情况，可以发现按上述定义的相同逆序对奇偶性的局面可以相互到达。于是我们只需要计算出原序列的逆序对奇偶性即可。直接计算 \(O(nlogn)\) 不能承受，我们分析构造的过程，计算每个数字的贡献即可，复杂度 \(O(n)\)。

E. Sdjpx Is Happy

题目大意：给你一个排列，你需要将它分成若干个划分。每个划分内部排序，允许选择两个划分交换。最后要求整个序列升序排列。问最多分成多少个划分。

题解：动态规划。\(f[i][j]\) 表示区间 \([i, j]\) 在不交换的情况下，能被分成多少个划分。显然 \(f[i][j]\) 只有在 \(max[i][j]-min[i][j]=j-i\) 的前提下才合法。\(f[i][j]\) 可以 \(O(n^2)\) 得到，具体方法为：最外层枚举区间长度，内层枚举区间左端点，记录一下该左端点最后一个合法的右端点转移。

然后考虑交换两个划分。我们 \(O(n^2)\) 枚举第一个划分的左右端点 \([l1, r1]\)，可以由 \(max[l1, r1]\) 得到第二个区间右端点 \(r2\)。然后枚举 \(l2 \in (r1, r2]\)。实际上中途有很多无用的状态，所以是很快的。

F. Funny Function

题目大意：算个式子。

题解：为便于讨论，先将第二维下标减 \(1\) ，用特征方程易求得 \(F_{1,i} = \frac{1}{3}\cdot(-1)^{i}+\frac{2}{3}\cdot2^{i}\) ，然后用类似生成函数的方法发现 \(F_{m,0}\) 用 \(F_{1,i}\) 表示的话，第 \(i\) 项的系数恰好就是 \((1+x+\dots+x^{n-1})^{m-1}\) 的第 \(i\) 项系数，故答案为 \(\frac{1}{3}[\frac{1-(-1)^{n}}{2}]^{m-1}+\frac{2}{3}(2^{n}-1)^{m-1}\) 。

G. If the starlight never fade

题目大意：算个式子。

题解：设 \(g\) 为 \(p\) 的一个原根，\(x = g^{u}, y = g^{v}\) ，则原条件相当于：

\[ \begin{aligned}\\ (x+y)^{i}&\equiv x^{i}(mod\ p)\\ (g^{u}+g^{v})^{i}&\equiv g^{ui}(mod\ p)\\ (1+g^{v-u})^{i}&\equiv 1(mod\ p)\\ 设1+g^{v-u}&\equiv g^{k}(mod\ p)\\ 注意到1+g^{v-u}&\not\equiv 0(mod\ p)\\ 并且 g^{v-u}&\not\equiv 0(mod\ p)\\ 故有 &0 < k < \phi(p)\\ \therefore g^{ki}&\equiv 1(mod\ p)\\ \therefore ki&\equiv 0(mod\ \phi(p))\\ \end{aligned}\\ \]

易知 \(k\) 有 \(gcd(i,\phi(p))-1\) 种取值，且对于每个 \(k\) 和每个 \(y\) 都恰有一个对应的 \(x\) ，故最后答案为：

\[ \begin{aligned}\\ ans&=m\sum_{i=1}^{p-1}(igcd(i,\phi(p)) - i)\\ &=m\sum_{d|(p-1)}d^{2}\sum_{k=1}^{\frac{p-1}{d}}k[gcd(k,\frac{p-1}{d})==1]-\frac{mp(p-1)}{2}\\ &=m\sum_{d|(p-1)}d^{2}\frac{\frac{p-1}{d}\phi(\frac{p-1}{d})+[\frac{p-1}{d}==1]}{2}-\frac{mp(p-1)}{2}\\ \end{aligned}\\ \]

H. To my boyfriend

题目大意：给你一个 \(n\times m\) 的矩形，每个格子有一种颜色。一个子矩形的价值为子矩形中颜色种类数，问等概率选择一个子矩形，价值的期望。

题解：

法一：

对每种颜色单独考虑，计算有多少个子矩形不含该颜色，每种颜色可以 \(O(n^2)\) 求解。这样总复杂度为 \(O(n^4)\)，不能承受。显然我们在计算的时候，会出现很多空行（该行不含某种颜色），我们稍微观察一下下图，可以发现空行与之前的行的状态可以 \(O(1)\) 转移。下图中，每个格子的数字，表示以该格子为右下角的子矩形个数。对于含有颜色的某行，我们用一个单调栈 \(O(n)\) 维护一下这个位置往上最多扩展多少个格子即可得到下图中的数字。

假设颜色 \(i\) 的格子占据了 \(x_i\) 行，那么有 \(\sum x_i \leq nm\)，我们的复杂度为 \(O(m\sum x_i) = O(n^3)\)。

C++ Code

法二：

出现次数超过 \(10\) 次的颜色，我们直接用未优化的上述方法 \(O(n^2)\) 暴力计算。出现次数小于 \(10\) 次的颜色，我们对每种颜色做关于次数的容斥。总复杂度为 \(O(\frac{n^2}{10}\cdot n^2 + n^2\cdot 2^{10})\)。

I. TrickGCD

题目大意：给你一个长度为 \(n\) 的数列 \(\{a_{i}\}\) ，问满足 \(1 \le b_{i} \le a_{i}\) ，且所有区间的 \(gcd\) 都大于 \(1\) 的数列 \(\{b_{i}\}\) 有多少个。

题解：显然题目中的条件等价于整个数列 \(b\) 的 \(gcd\) 大于 \(1\) ，设 \(f(i):\) 所有 \(b_{j}\) 被 \(i\) 整除的 \(\{b_{i}\}\) 的数量，根据容斥原理有 \(ans = -\sum_{i=2}\mu(i)f(i)\) 且 \(f(i) = \prod_{j = 1}^{n}\lfloor\frac{a_{j}}{i}\rfloor\) 。计算 \(f(i)\) 时，注意到除 \(i\) 等于某个数的 \(a_{j}\) 都在一个区间内，譬如除 \(3\) 为 \(1\) 的区间为 \([3, 5]\) ，所以可以用一个前缀数组来快速计算 \(f(i)\) ，复杂度 \(O(nlog^{2}n)\) 。

J. String and String

题目大意：给出两个字符串 \(S\) 和 \(T\)，\(T\) 串中的每个位置对应了一个权值 \(f_i\) ，接下来要求维护 \(q\) 次操作。每次操作分为两种：

\(1.\) 将 \(T\) 串中某个位置的权值 \(f_x\) 修改为 \(y\)；

\(2.\) 给出两个区间 \([a,b]\) 和 \([c,d]\) ，对\(S\) 串中位置 \([a,b]\) 对应的子串在 \(T\) 串中位置 \([c,d]\) 内出现的位置 \([x_1,y_1]\)，\(\cdots\)，\([x_k,y_k]\)，\(c \leq x_i,y_i \leq d\)，求 \(\sum f_{y_k}\).

题目要求强制在线。

题解：

如果不考虑第一种操作的话，就直接建立 \(S +@+T\) 的后缀自动机， \(f_i\) 是和 right 集合有关的信息，可以在 parent 树上用可持久化线段树合并维护，然后询问的时候就先找到 \(S\) 中 right 位置 \(b\) 对应的节点，通过倍增找到长度为 \(b-a+1\) 的节点，在这个节点的可持久化线段树上询问 \(T\) 中 right 在区间 \([c+b-a+1,d+1]\) 内的信息。

然后我们再考虑如何进行修改，修改一个位置，会对 parent 链上所有的节点都造成影响，换言之，对某一个点而言，它受到的影响就是它在 parent 树中的子树中所有的修改操作。因此，我们可以对 parent 树进行 dfs，记录下入栈序，就转换为了一个序列上单点修改，区间查询的问题，用树状数组套上一个动态开点的权值线段树就可以维护了。

K. Regular polygon

题目大意：给你平面上的 \(n\) 个整点，问它们组成了多少个不同的正多边形。

题解：显然整点只能组成正四边形（正方形），我们枚举其中两个点，然后对剩下两个点的相对位置分上侧，下侧，两侧三种情况讨论，并用 std::set 维护。复杂度 \(O(n^{2}logn)\) 。