XVIII Open Cup named after E.V. Pankratiev. Grand Prix of Romania

Contest Info

date: 2018.11.09 16:31-21:31

practice link

Solutions

A. Balance

题目大意：有一个 \(n\times n(n\leq 50)\) 的矩阵 \(A[i][j]\)。求一个新的矩阵 \(B[i][j]\)，满足每个位置有 \(B[i][j]\geq A[i][j]\)，且 \(B[i][j]+B[i+1][j+1]=B[i+1][j]+B[i][j+1]\)。最小化 \(\sum B[i][j]-A[i][j]\)。

题解：线性规划：

\[ \begin{aligned} \text{Minimize: }& \sum {a[i]+b[i]}\\ \text{Subject to: }& a[i]+b[j]\geq A[i][j] \end{aligned} \]

B. Entanglement

题目大意：对于长度分别为 \(n,m\) 的序列 \(A,B\)，定义 \(n\times m\) 的矩阵 \(C\) 是 \(A,B\) 的 Entanglement，当且仅当 \(C[i][j]=A[i]\lor C[i][j]=B[j]\) 对 \(\forall i,j\) 成立。现在给出 \(C\)，求合法的 \(A,B\) 的数量。

题解：首先注意到不同的 \(C[i][j]\) 至多只能有 \(n+m\) 种。判掉这种非法情况后离散化 \(C\)。

考虑暴搜 \(A\)，\(A\) 确定之后合法的 \(B\) 的数量就容易知道了。采取如下的策略剪枝：

  • 若某个 \(C[i][j]\neq A[i]\)，那么 \(B[j]\) 就确定了。我们用这个 \(B[j]\) 去 check 第 \(i+1\) 行后的所有 \(C[k][j]\)，若 \(C[k][j]\neq B[j]\)，那么 \(A[k]\) 也就确定了。这个过程中可能出现矛盾。
  • 若 check 的过程中没有出现矛盾，那么不论 \(i+1\) 行后怎么填，第 \(j\) 列都不会非法。也就是说，一旦 \(B[j]\) 确定且 check 后，这一列就不用再管了。
  • 若 \(B\) 已经确定，那么我们就可以直接计算 \(A\) 的方案数，不用继续搜索下去了。
  • 对于所有没有出现在第 \(i\) 行的数字，若 \(A[i]\) 填它，那么 \(B\) 就唯一确定了。此时也可以直接计算。

大致能证明时间复杂度是 \(\mathcal{O}(nm(n+m))\)。但是怎么都找不到一个严谨的证法，这里就不写了。。。

C. Gravity

题目大意：在一个 \(n\times m(n,m\leq 2000)\) 的网格里，有一些木块。这些木块四联通，一个连通块一起运动。问他们下落之后的终止状态。如果一个连通块往下落一格会与其他连通块重合，那么就不能再移动了。

题解：每个连通块视为一个点，每一列下面的连通块向上面的连通块连边，然后求最短路。最短路即为能下落的高度。

D. Infinite Pattern Matching

题目大意：把 \(1\to+\infty\) 的二进制表示排成一个无限长的 \(01\) 串，再给你一个 \(01\) 串 \(s\)，问你 \(s\) 在该串中最早出现的位置。

题解：瞎搞。枚举 \(s\) 是由几个数字拼成的。

  • 若 \(1\) 个，那么如果 \(s\) 没有前导 \(0\)，一定是由它本身组成最优；如果 \(s\) 有前导 \(0\)，由它前面加上一个 \(1\) 最优。
  • 若 \(2\) 个，枚举分界线在什么地方，那么我们就能知道这个数的后缀和前缀。要使结果最优，让前后缀重合的部分尽可能大即可。
  • 若 \(3\) 个以上，那么至少有一个数是完整的，枚举哪个区间是一个完整的数即可。

G. Origami

题目大意：

给出一个由小写字母组成的\(n\times m\)矩阵，可以进行任意次对折操作。

每次对折选一条水平或者竖直的折痕，将较小的一部分折到另一部分上方（相同大小时两个方向均可以操作），要求折叠后重叠的两部分对应位置相同。

问有多少种不同的最终局面，即两个局面不同当且仅当最后剩下部分的坐标不同。

题解：

如果有一个合法的折叠序列，显然将其中水平方向的折叠和竖直方向的折叠单独拿出来也是合法的，因此横纵坐标可以独立处理。

只需要求哪些位置可以作为最后剩下部分的左边界，哪些位置可以作为有边界即可，一对合法的左右边界一定有一个恰当的折叠顺序可以得到。

令\(pref_i\)为前缀\(i\)中可以作为左边界的位置总数，则可以进行递推，如果\(i>1\)可以作为左边界，最后一次折叠一定是以\((i-1,i)\)作为回文中心，只要这个中心的半径之内存在一个合法的左边界，\(i\)也可以作为左边界，前缀和处理一下即可。

令\(suff_i\)为后缀\(i\)中可以作为右边界的位置总数，同理，如果\(i<n\)可以作为右边界，最后一次折叠的中心是\((i,i+1)\)，只要这个中心的半径之内存在一个合法的右边界，\(i\)也可以作为右边界，后缀和处理一下即可。

时间复杂度\(O(nm)​\).

H. Qnp

题目大意：告诉你 \(0\sim9\) 中每个数字分别出现多少次（总次数 \(\le70000\)），求第 \(k\le10^{12}\) 的这样的数，允许有前导 \(0\)。有 \(5000\) 组询问。

题解：比较显然是个数位 \(dp\)，但是直接做复杂度过高。注意到组合数大部分情况下非常大，考虑利用此性质优化。

首先可以二分求出一开始放多少个最小的数字，这个比较简单，不再赘述。

如果剩下的数字已经很少，那么就可以直接暴力做了，这里我取的是 \(100\) 个。

如果剩下的数字很多，那么显然一定是集中在了某一个数字上，不妨以 \(0,2\) 很少，\(1\) 很多的情况来描述算法：

还是采取一位一位填的方法。如果要填的是 \(0\) 或 \(2\)，那么直接填即可。否则要填 \(1\)，考虑二分填入多少个 \(1\)。

注意到 \(11111\cdots\) 对应的是某一段连续区间的数，且这个区间的左右边界分别随着 \(1\) 的增多而向右/向左移动。因此我们只要求出这个区间，即可进行二分的判断。

注意到这个区间的长度可以很容易地用组合数求出。考虑求左边界，显然是要求出所有小于它的数的个数。朴素的想法是枚举第一个 \(0\) 出现的位置，那么 \(0\) 之后的填法就能简单地用组合数求出。观察这些组合数能够发现它们可以用前缀和预处理，\(\mathcal{O}(1)\) 查询。

实现好的话这一算法的复杂度是比较低的。另外还需要稍微注意一下不同地方对 INF 的处理。

I. Salaj

题目大意：给你一个 \(n\) 个点的有向图，初始时没有边。定义一个序列 \(A\) 合法，当且仅当存在一种加边的顺序，使得添加第 \(i\) 条边后，强连通分量的数量为 \(A_{i}\)。对每个 \(i\in[1,\max]\)，求长度为 \(i\) 的合法序列 \(A\) 的数量。

题解：首先来研究要达到 \(x\) 个强连通分量至少和至多能有多少条边。

最少的情况显然是：优先连接 \(1\to2,2\to3,\cdots\)，每当 \(A_{i}\) 减小为 \(x\) 时，就从 \(n-x+1\) 往 \(1\) 连一条边。因此至少需要 \(n-x\) 加上反向边的数量（即 \(A_{i}\) 减小的次数）。

最多的情况即为：连接所有正向边，\(1\) 到 \(n-x+1\) 的强连通分量中连接所有反向边，共 \(\frac{n(n-1)+(n-x+1)(n-x)}{2}\) 条。

设 \(dp[i][j][k]\) 表示第 \(i\) 条边，有 \(j\) 个强连通分量，连接了 \(k\) 条反向边的方案数。根据上述限制简单转移即可。

这样的复杂度是 \(\mathcal{O}(n^{5})\)。注意到 \(i\ge2n\) 时，下界一定能够满足，此时可以省去 \(k\) 这一维。

时间复杂度 \(\mathcal{O}(n^{4})\)。

J. Taxi

题目大意：在 \(n\) 个点边带权的树上，有 \(m\) 个人和 \(m\) 个出租车。每个人如果分配了一辆车，那么代价就是他们之间的路径长度。人和车的分配方案会最大化代价之和。现在问你所有的 \(n^{2m}\) 种局面的代价之和。

题解：枚举一条边，计算它的贡献。枚举子树 \(v\) 中人的个数 \(x\)，那么另外一边有 \(m-x\) 个人。再枚举另一边的车的数量 \(y\)，那么这边有 \(m-y\)。显然边的贡献的两边人数和车数的 \(\min\)。

另 \(t=w\cdot {m \choose x}\cdot \text{sz}[v]^x\cdot (n-\text{sz}[v])^{m-x}\)。

那么 \(1\leq y\leq x\) 的时候，有 \(t\cdot {m\choose y}\cdot \text{sz}[v]^{m-y}\cdot (n-\text{sz}[v])^y\cdot (y+m-x)\)。

那么 \(x<y\leq m\) 的时候，有 \(t\cdot {m \choose y}\cdot \text{sz}[v]^{m-y}\cdot (n-\text{sz}[v])^y\cdot (m-y+x)\)。

对 \(y\) 前缀和优化，复杂度 \(\mathcal{O}(nm)\) 。

K. Tris

题目大意：给你 \(1\times1,1\times2,1\times3\) ，L 型的方块分别 \(a,b,c,d\) 个，要求你将它们拼成一个环。\(a,b,c,d\ge2\)。形状分别如下：

*    **    ***    *
                  **

题解：容易证明可以用前三种形状拼出两个长度差不超过 \(1\) 的条带。另外注意到网格图中只能有偶环，因此 \(2\mid a+2b+3c+3d\)。下面分类讨论：

  • 若 \(2\mid d,d\equiv 0\pmod{4}\)，构造方法如下：
20 20
 0  2  2  2  4  4  4  6  6  7  7  9  9 12  0  0  0  0  0  0
 0 13  0  0  0  0  0  0  0  0  0  0  0 15 15  0  0  0  0  0
13 13  0  0  0  0  0  0  0  0  0  0  0  0 15  0  0  0  0  0
17  0  0  0  0  0  0  0  0  0  0  0  0 19 19  0  0  0  0  0
17 17  0  0  0  0  0  0  0  0  0  0  0 19  0  0  0  0  0  0
 0 14  0  0  0  0  0  0  0  0  0  0  0 16 16  0  0  0  0  0
14 14  0  0  0  0  0  0  0  0  0  0  0  0 16  0  0  0  0  0
18  0  0  0  0  0  0  0  0  0  0  0  0 20 20  0  0  0  0  0
18 18  0  0  0  0  0  0  0  0  0  0  0 20  0  0  0  0  0  0
 0  1  1  1  3  3  3  5  5  5  8  8 10 11  0  0  0  0  0  0
 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
  • 若 \(2\mid d,d\equiv2\pmod{4}\)，构造方法如下：
20 20
 2  2  2  4  4  4  6  6  7  7  9  9 11  0  0  0  0  0  0  0
13  0  0  0  0  0  0  0  0  0  0  0 16 16  0  0  0  0  0  0
13 13  0  0  0  0  0  0  0  0  0  0  0 16  0  0  0  0  0  0
 0 19  0  0  0  0  0  0  0  0  0  0 21 21  0  0  0  0  0  0
19 19  0  0  0  0  0  0  0  0  0  0 21  0  0  0  0  0  0  0
14  0  0  0  0  0  0  0  0  0  0  0 17 17  0  0  0  0  0  0
14 14  0  0  0  0  0  0  0  0  0  0  0 17  0  0  0  0  0  0
 0 20  0  0  0  0  0  0  0  0  0  0 22 22  0  0  0  0  0  0
20 20  0  0  0  0  0  0  0  0  0  0 22  0  0  0  0  0  0  0
15  0  0  0  0  0  0  0  0  0  0  0 18 18  0  0  0  0  0  0
15 15  0  0  0  0  0  0  0  0  0  0  0 18  0  0  0  0  0  0
 0  1  1  1  3  3  3  5  5  5  8  8 10 12  0  0  0  0  0  0
 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
  • 若 \(2\nmid d,d\equiv1\pmod{4}\)，构造方法如下：
20 20
 0 12 12  2  2  2  4  4  4  6  6  8  8 11  0  0  0  0  0  0
 0 12  0  0  0  0  0  0  0  0  0  0  0 16  0  0  0  0  0  0
13 13  0  0  0  0  0  0  0  0  0  0  0 16 16  0  0  0  0  0
13  0  0  0  0  0  0  0  0  0  0  0  0  0 19  0  0  0  0  0
14  0  0  0  0  0  0  0  0  0  0  0  0 19 19  0  0  0  0  0
14 14  0  0  0  0  0  0  0  0  0  0  0 17  0  0  0  0  0  0
 0 18  0  0  0  0  0  0  0  0  0  0  0 17 17  0  0  0  0  0
18 18  0  0  0  0  0  0  0  0  0  0  0  0 20  0  0  0  0  0
15  0  0  0  0  0  0  0  0  0  0  0  0 20 20  0  0  0  0  0
15 15  1  1  1  3  3  3  5  5  7  7  9 10  0  0  0  0  0  0
 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
  • 若 \(2\nmid d,d\equiv3\pmod{4}\)，构造方法如下：
20 20
 0  2  2  2  4  4  4  6  6  8  8 11 15  0  0  0  0  0  0  0
12 12  0  0  0  0  0  0  0  0  0  0 15 15  0  0  0  0  0  0
12  0  0  0  0  0  0  0  0  0  0  0  0 20  0  0  0  0  0  0
18 18  0  0  0  0  0  0  0  0  0  0 20 20  0  0  0  0  0  0
 0 18  0  0  0  0  0  0  0  0  0  0 16  0  0  0  0  0  0  0
13 13  0  0  0  0  0  0  0  0  0  0 16 16  0  0  0  0  0  0
13  0  0  0  0  0  0  0  0  0  0  0  0 21  0  0  0  0  0  0
19 19  0  0  0  0  0  0  0  0  0  0 21 21  0  0  0  0  0  0
 0 19  0  0  0  0  0  0  0  0  0  0 17  0  0  0  0  0  0  0
14 14  0  0  0  0  0  0  0  0  0  0 17 17  0  0  0  0  0  0
14  0  0  0  0  0  0  0  0  0  0  0  0 22  0  0  0  0  0  0
 1  1  1  3  3  3  5  5  7  7  9 10 22 22  0  0  0  0  0  0
 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0

L. Xormites

题目大意：有一个正整数数列 \(\{a_i\}\)，两个人玩游戏，每次从头或者从尾取一个数。收益为所有数的异或和，问先手必胜、后手必胜还是平局。

题解：设 \(s\) 为所有数字的异或和。当且仅当 \(s=0\) 有平局。否则，考虑 \(s\neq 0\)。

如果 \(n\) 是偶数，那么先手必胜。因为先手可以取完所有的偶数位置或者所有的奇数位置。

如果 \(n\) 是奇数，我们先考虑可以把序列转换为 \(0/1\) 序列。我们按照每个数是否有 \(s\) 的最高位 \(1\)，把数列修改为 \(0/1\) 序列。那么此时有奇数个 \(1\)。

如果此时头和尾都是 \(0\)，那么后手面临偶数个数字，且异或和不为 \(0\) 的局面。后手必胜。

否则，我们枚举先手取哪个 \(1\)，接着去验证。此时先手手里已经有一个 \(1\) 了，并且剩下偶数个数字，异或和为 \(0\)。那么先手期望两人在后面拿 \(0\) 和 \(0\)。而后手期望拿 \(1\) 和 \(1\)。

如果某个时候，两者在后面拿的数字异或和不同，那么剩下偶数个数字，异或和为 \(1​\)。后手一定能拿到有利于自己的局面。所以先手要保证每次操作之后，两者异或和相同。最后再判断一下这样拿到最后两人一起拿到了 \(0​\) 还是 \(1​\)。

具体实现验证部分的时候，先把两侧相同的都删掉，然后判断剩下的数列是不是 \(a[i]=a[i+1](i \text{ is odd})\)。