Contest Info

date: 2017.08.09 10:00-15:00

practice link

Solutions

A. Lucky Number

题目大意：给出一个数列 \(\{T_i\}\)，定义每个位置 \(i\) 的 Lucky Number 为 \(\max\limits_{T_j>T_i,j>i} (j-i)\)。如果不存在这样的 \(j\) ，那么 \(i\) 的 Lucky Number 为 \(0\)，求出最大的 Lucky Number。

题解：预处理一下数列的后缀最大值，然后枚举 \(i\) ，去二分找到最大的满足条件的 \(j\)。

B. Flow Game

题目大意：输入一个 \(n\times n\) 的棋盘，在边框上有两对不同颜色的点。求两条不相交的路径分别连通两种颜色，并且路径之和尽可能短。

题解：记两种颜色分别为 \(1\) 和 \(2\)。绕着边框走一遍，如果颜色序列为 \(1212\) 或者 \(2121\)，那么显然无解。否则就是最短曼哈顿距离，注意特殊处理 \(1221\) 和 \(2112\) 时四种颜色在同一行（列）上的情况。

C. Toy Boxes

题目大意：给你 \(n\) 个玩具和 \(3\) 个箱子。每个玩具有一个正的质量，要求把所有玩具塞进箱子里，不能有空箱子。定义每个箱子的代价为总质量乘以玩具个数，问最小总代价。

题解：假如我们给定了每个箱子的玩具个数，那么由排序不等式容易知道，重的玩具应该放进个数少的箱子里。我们把玩具从小到大排序，枚举最小的箱子，然后容易发现，第二个分界点是可以三分的，由于是整数，所以二分导数即可。复杂度 \(\mathcal{O}(n\log n)\)。

D. Computing Inverses

题目大意：定义一个有限域 \(GF(2^{m})\) ，求其中非零元素的乘法逆元。

题解：我们用 \(GF(2^{m})\) 中的非零元和它里面的乘法可以构造一个 \(2^{m}-1\) 阶有限交换群，而有限交换群里的所有元素的阶数次（\(2^{m}-1\) 次）幂都是单位元。所以答案就是该元素的 \(2^{m}-2\) 次幂，快速幂就完了。复杂度 \(\mathcal{O}(m^{3})\) （所以 \(m=20\) 是什么鬼？）。

E. A Generalized N-Queens Problem

题目大意：给定一个 \(n\times n(0<n\leq 10)\) 的棋盘，初始一些格子摆放了黑棋子。现在想在棋盘上摆放尽可能多的白棋子，且它们两两互不攻击。两个白棋子互相攻击当且仅当它们处于同一行、列、对角线，并且中间没有黑棋子隔开。

题解：我们将相互攻击的格子连边，这就是一个最大独立集问题。我们求出反图的最大团即可。

建图有一种很好写的方法。我们在棋盘外面加上一圈黑棋子，将所有的黑棋重新编号。记录每个点四个方向最近的黑棋编号。那么两个点不互相攻击，当且仅当它们四个方向的黑棋编号都不同。

F. Homework Evaluation

题目大意：给你一个文本串和一个模式串，长度分别为 \(n,m\)。模式串的每个字母可以跟文本串的相同字母精确匹配（\(+8'\)），不同字母错误匹配（\(-5'\)），跳过模式串中的一段或者文本串的一段（每个字母 \(-3'\)，每段额外 \(-4'\)）。求最大得分。

题解：显然是一个 dp。下标从 \(1\) 开始，我们设 \(dp[i][j]\) 表示文本串的第 \(i\) 个字母与模式串的第 \(j\) 个字母匹配（不能跳过）的最大得分。那么答案为 \(\displaystyle \text{max}_{i,j}\left( dp[i][j]+(m-j)*(-3)+[j\neq m]*(-4) \right)\)。

枚举 \(i'\) 从 \(dp[i'][j-1]\)，以及枚举 \(j'\) 从 \(dp[i-1][j']\) 转移而来即可。为了方便转移，初值将 \(dp[i][1], dp[1][j]\) 先算好。

G. Sightseeing Bus Drivers

签到题

H. Surrounding a house

题目大意：给出一个 \(n\times m \leq 40000\) 的网格图，每个格子上有一个非负整数表示修建围栏的代价。要求修一个围栏，将 \((1,1)\) （行列都从 \(0\) 开始标号）围起来（不能经过）。围栏是四连通，首尾相连，不中断，没有缺口。还要求外部的格子（如果存在）都属于同一个连通块。求最小花费。

题解：要将 \((1,1)\) 围起来，\((0,0)\)，\((0,1)\)，\((0,2)\)，\((1,0)\)，\((2,0)\) 这五个点是必须要包括的，而围栏上其它的点构成了一条从 \((0,2)\) 到 \((2,0)\) 的路径，就转化为了最短路问题。

考虑围栏外有多个连通块的情况，一定是因为路径中出现了两次以上从不是边界的点走到边界的点的情况。所以合法的情况只有两种：一种是从 \((0,2)\) 出发，沿着边界走，一直走到 \((2,0)\)；一种是从 \((0,2)\) 出发，沿着边界走，离开边界恰一次，再回到边界恰一次，再一路走到 \((2,0)\)。

我们令 \(f[i][j]\) 表示从 \((0,2)\) 出发，只沿着边界走到 \((i,j)\) 的距离（\((i,j)\) 是边界上的点，且 \((i,j) \not\in\{ (0,0),(0,1),(1,0) \}\)）。那么第一种情况就是 \(f[2][0]\)。我们再做一次 spfa，计算出从 \((2,0)\) 出发，并且不能走进边界的最短路 \(dis[i][j]\)。然后我们枚举从 \((0,2)\) 出发离开边界的点，把两条路径拼一下，就是从 \((0,2)\) 到 \((2,0)\) 的一条合法路径了。

I. Robin Hood Transformation

题目大意：给你两个非负整数组成的列向量 \(\boldsymbol{a}\) 和 \(\boldsymbol{b}\) 。问是否存在一个矩阵 \(D\) 满足 \(\boldsymbol{a} = D \boldsymbol{b}\) ，且 \(D\) 的元素都是非负实数，各行各列之和均为 \(1\) 。

题解：显然把 \(\boldsymbol{a}\) 和 \(\boldsymbol{b}\) 排序之后不影响解的存在性。如果它们的最大值相等，则显然 \(\boldsymbol{a}\) 的最大值这一项只能用 \(\boldsymbol{b}\) 的最大值一项乘上系数 \(1\) 来表示，故两个数列均去掉这一项不影响解的存在性，最小值同理。进行完这些操作之后，如果 \(\boldsymbol{a}\) 的最大值大于 \(\boldsymbol{b}\) 的最大值，或者 \(\boldsymbol{a}\) 的最小值小于 \(\boldsymbol{b}\) 的最小值，显然无解，否则有解（这一步不会证）。复杂度 \(\mathcal{O}(n\log n)\) 。