"Hello 2018" 题解

liu_cheng_ao 2018-01-03 16:55:31 2018-02-11 13:26:40

A. 奴隶主的游戏

By liu125008 & CommonAnts & qmqmqm & fengchanghn,题解 By fengchanghn

  • 考察选手的基础博弈知识及构造和分类讨论以及猜结论的能力(雾
  • 思维难度:提高
  • 实现难度:普及-

其实你会发现前面两个(所有)的数据范围都是假的,朴素搜索是无法通过 n\ge 4 的 ……

所以下面都以特殊情况来考虑。

情况一

** k=0 **

注意到数独游戏对称性很强,考虑填对称的方法:

  • 如果 n 为偶数,直接在中心对称位置填相同元素。由于两个中心对称的位置必定不在同行同列或同区域,故二者填入时所在行、列及区域的元素必定相同,从而先手可填时后手必定可填,由于格子大小有限,游戏必定在有限步内结束,从而后手必胜。
  • 如果 n 为奇数,那么与之类似地,先手先在中间填上 n^2 ,然后每次在后手所填位置的对称位置填上与其所填数相对的数( i n^2-i 相对, n^2 n^2 相对)即可。故先手必胜。

情况二

** n 为偶数, k\leq 1 **

k=0 的情况相同,只不过交换了先后手,故先手必胜。

然而没有这一点的分

情况三

** n 为奇数, k\leq 1 **

延续情况二的思路,但此时不能直接填中心对称了,因为一开始的数不一定在中间。

但可以发现如果两行或两列均在同一区域那么他们是可以互换位置的,且两个由区域组成的行或列也是可以互换位置的,故可以构造一个置换把初始填的格子换到中间。至于数值,由于我们只关注是否像等,故可以随意置换。

也可以理解为每个点重新找到了一个对称(匹配)点,每个数也如此。

情况三

** k\leq 2 **

如果 n 为奇数,和情况三同样讨论将任意一个填过的格子换到中间即可。

如果 n 为偶数,情况要复杂一些:我们仍然考虑为每个点重新找一个对称(匹配)点,为每个数重新找一个相对的数字。

可以分类构造:

  • 当两格所属区域不在同行或同列时,可以中心对称。

  • 当两格所属区域在同一行(列)但两格不在同一区域且两格属于同行或同列时,可以轴对称。

  • 当两格所属区域在同一行(列)但两格不在同一区域且两格不属于同行或同列时,可以在区域组成的列内中心对称。

  • 当两格在同一区域且两格不属于同行或同列时,可以在区域内中心对称。

  • 当两格在同一区域且两格属于同行或同列时,可以在区域内轴对称。

这样,不管怎么填答案只与 n k 的奇偶性有关。

扩展?

这个结论在 k 更大时成立吗?遗憾的是它在 k 很大时是错误的。但 k 似乎可以比 2 大一些,比如 n=2 时最小的反例出现在 k=6 。有想法的同学欢迎交流。

B. Array Poisonous Suffix Problem

By qmqmqm,题解 By CommonAnts & fengchanghn

  • 考察选手对后缀数组性质的了解和构造。
  • 思维难度:提高+
  • 实现难度:普及/提高-

算法一

枚举长度再枚举所有合法字符串验证。

此处长度只用枚举到 k+1 ,后文证明。

时间复杂度: O((k+1)^{k+1})
期望得分: 7

算法二

我们枚举后缀排名数组(以下也称名次数组,记作 \mathrm{rank} ,后缀数组记作 \mathrm{sa} )。

注意到,对于 1\le i<n ,位置 \mathrm{sa}[i] 可以等于 \mathrm{sa}[i+1] 的充要条件是 \mathrm{rank}[\mathrm{sa}[i]+1]< \mathrm{rank}[\mathrm{sa}[i+1]+1] (设 rank[n+1]=0 )。故我们贪心地填即可取得最小的字符集。

时间复杂度: O((k+1)!)
期望得分: 7

算法三

其实答案不仅一定是 k+1 ,方案也是唯一的。

显然,任意一个长为 n \mathrm{rank}[] 最多需要的字符集大小为 n (只需要对应 \mathrm{rank}[] 位置填对应字符)。我们尝试构造一个字符集恰好为 n 的串。

考虑 \mathrm{rank}[] 未填的最后一个位置,它必定是尚未用过的 \mathrm{rank} 值中最大的( n ),因为若该位置不是最大的,设为 v ,由于 \mathrm{rank}[] 未填的最后一个位置的后一个位置比剩余的任何值都小, \mathrm{rank}[\mathrm{sa}[v+1]+1] 必定比该位置大,那么 \mathrm{sa}[v] \mathrm{sa}[v+1] 可以填相等字符,字符集大小小于 n

接下来,所填的必定是最小的。因为此时它的后一个位置是最大的,故可以用类似的证明方法证得。

归纳即得唯一可能的最小字符集为 n 的串如下:从最后一个位置向前,倒数奇数位置填当前最大值,偶数位置填当前最小值。

验证可知其字符集恰为 n 。故我们解决了该问题。

时间复杂度: O(k)
期望得分: 100

只推出部分性质而使用复杂度较高的方法可以得到部分分。

C. 小埋与游乐场

By Snakes,题解 By Snakes

  • 贪心或网络流
  • 思维难度 NOI-
  • 代码难度 NOI-

算法一

枚举每个在集合 A 中的数与 B 中的哪个数配对或不配对,计算并更新答案。

可通过子任务 1

时间复杂度: O(n^{m+1})
预计得分: 6

算法二

对于子任务 2 B 中元素均不在 A 中且 k=1 ,那挑一对异或之后 \mathrm{lowbit} 减少值最大的异或就可以啦!

但是时间复杂度 O(nm) ,超时。

性质一 a\neq b a,b\neq 0 ,考虑 \mathrm{lowbit}(a\oplus b) ,当 \mathrm{lowbit}(b)<\mathrm{lowbit}(a) \mathrm{lowbit}(a\oplus b)=\mathrm{lowbit}(b) ,否则 \mathrm{lowbit}(a\oplus b)\geq\mathrm{lowbit}(a)

\mathrm{lowbit} 的定义可知,当 \mathrm{lowbit}(a)\neq\mathrm{lowbit}(b) 时, \mathrm{lowbit}(a\oplus b)=\min(\mathrm{lowbit}(a),\mathrm{lowbit}(b)) 。当 \mathrm{lowbit}(a)=\mathrm{lowbit}(b) a\neq b 时,则 a 的最低位在异或 b 之后变为 0 ,所以 \mathrm{lowbit}(a\oplus b)>\mathrm{lowbit}(a) 。对于 \mathrm{lowbit}(a)<\mathrm{lowbit}(b) 的情况同理。

所以我们只需要分别对集合 A 与集合 B 中的元素分别计算其 \mathrm{lowbit} ,当取集合 A \mathrm{lowbit} 最大的元素与集合 B \mathrm{lowbit} 最小的元素异或后,能使解更优时,对其进行操作并更新答案即可。

可通过子任务 2

时间复杂度: O(n+m)
预计得分: 8

算法三

对于子任务 3 ,在算法二的基础上考虑 a=b 的情况。显然当 a=b 时, \mathrm{lowbit}(a\oplus b) 的值为 0 。所以只需要判断集合 A 与集合 B \mathrm{lowbit} 最大的相等元素对答案的贡献,并将其与算法二的答案取最优解即可。

可通过子任务 2,3

时间复杂度: O(n \log n+n+m)
预计得分: 18

结合算法一可得 24 分。

算法四

对于子任务 4 ,集合 A 与集合 B 无相等元素,考虑贪心。

性质二 答案中不存在 a\neq b \mathrm{lowbit}(b)\geq\mathrm{lowbit}(a) 的操作。
否则直接去掉该操作答案不会变劣。

性质三 在最优解中不存在两对 a c b d 的操作,使得 a\neq b,c\neq d,\mathrm{lowbit}(b)\geq\mathrm{lowbit}(c)

否则将 a d 操作会更优。二者答案相差 \mathrm{lowbit}(b)-\mathrm{lowbit}(c) ,即使其为 0 ,在操作次数上也会更优。

\begin{align}\mathrm{lowbit}(a)-\mathrm{lowbit}(d)&=\mathrm{lowbit}(a)-\mathrm{lowbit}(b)\\&+\mathrm{lowbit}(b)-\mathrm{lowbit}(c)\\&+\mathrm{lowbit}(c)-\mathrm{lowbit}(d)\end{align}

性质四 在最优解中满足 a\neq b 的操作,在 a 中每个元素只与 b \mathrm{lowbit} 比它小的元素操作的前提下,与配对方法无关。

证明 不论操作顺序如何,答案均比无操作时答案减少 \sum_{a\in A'}a-\sum_{b\in B'}b ,其中 A',B' A,B 中被操作的子集。

根据性质二至四,我们可以得出以下算法。

每次在 nm 对数中找到一组没有被操作过的 (a,b) ,使得 \mathrm{lowbit}(a)-\mathrm{lowbit}(a\oplus b) 最大,对其进行操作。重复此过程至无剩余操作次数或该操作对答案无贡献。

一个小技巧:找一个 2 的指数(即模意义下满足 2^i=1 的最小正整数 i )不小于 32 的模数即可直接利用对 2^x 取模算出 x 。最小的合法模数是 37

可通过子任务 4

时间复杂度: O(nmk)
预计得分: 9

结合上述算法可得 33 分。

算法五

对于子任务 5 ,在算法四的基础上考虑出现集合 A B 存在相等元素的情况。

假定存在元素 a\in A ,元素 b\in B ,且满足 a=b 。若 a b 操作为当前对答案贡献最大的一组操作,则不会存在问题。若 a 已被操作,且 B 中有剩余 \mathrm{lowbit} b 相等的元素未被操作,则可继续操作,否则不可操作,跳过该组操作。

在算法四的实现基础上,新增对 B 集合 \mathrm{lowbit} 分类的元素个数即可。

可通过子任务 4,5

时间复杂度: O(nmk)
预计得分: 11

结合上述算法可得 44 分。

算法六

对于子任务 6 ,集合 B 中元素相等,直接计算集合 A 中的每个数对 B 中的数操作对答案的贡献,从大到小排序后取前 k 个贡献为正的操作即可。

可通过子任务 6

时间复杂度: O(n\log n)
预计得分: 9

结合上述算法可得 53 分。

也即,一个四合一的程序可以拿到本题一半的分数。

子任务 2,3,4,5 一直在提示正解,但是似乎的确有选手没发现。(其实能过子任务 5 的选手已经可以AC了)

算法七

对于子任务 7 ,考虑暴力最大权匹配。有 k 次操作的限制,不考虑 KM 算法,考虑用费用流实现。将集合 A 中元素视为二分图的一边, B 中元素视为另一边,两两之间连一条从 A B 的边,费用为其操作对答案的贡献,流量为 1 A 侧与 B 侧均向对应的源点与超级汇点连一条费用为 0 ,容量为 1 的边。超级源点与源点连一条费用为 0 ,流量为 k 的边。在构成的二分图上跑最大费用最大流即可。

优化连边,除去贡献为 0 或负数的边,可降低常数。

可通过子任务 1,4,5,7

最坏时间复杂度: O(kn^3)
预计得分: 39

结合上述算法可得 66 分。

算法八

对于子任务 8 ,考虑使用数据结构维护集合并且贪心。

性质五 在集合 A,B 存在相等元素的情况下,若存在 a\in A,b\in B a=b ,存在 c\in A \mathrm{lowbit}(c)>\mathrm{lowbit}(a) ,则 c b 操作比 a b 操作更优。
\mathrm{lowbit}(c)-\mathrm{lowbit}(b)\leq\mathrm{lowbit}(b)=\mathrm{lowbit}(a)-\mathrm{lowbit}(a\oplus b)

性质六 在集合 A,B 存在相等元素的情况下,若存在 a\in A,b,c\in B 满足 a=b \mathrm{lowbit}(c)<\mathrm{lowbit}(a) ,则 a b 操作比 a c 操作更优。

性质七 在集合 A,B 存在相等元素的情况下,根据性质四可得若存在 a,c\in A,b,d\in B 满足 a=b,b\neq d,\mathrm{lowbit}(b)=\mathrm{lowbit}(d),\mathrm{lowbit}(a)<\mathrm{lowbit}(c) ,且 c b 匹配,则可修改操作方案使 a b 操作, c d 操作,答案更优。

证明 根据性质四,可得若与 c 匹配的 B 中元素交换的元素 \mathrm{lowbit} 不变,对当前答案不造成影响,交换后新增一组可操作元素对,答案更优。

性质八 集合 A,B 中的 0 不对答案造成任何影响。

证明 对于集合 A 0 \mathrm{lowbit} 0 ;对于集合 B 0 与任何数操作得到的数依旧为原数,贡献 0

由性质一至八可得以下贪心方案:

删除集合 A,B 中所有 0 后,每次在集合 A 中选择一个 \mathrm{lowbit} 最大的元素,与集合 B \mathrm{lowbit} 最小的元素操作,若在 A \mathrm{lowbit} 最大的元素有多个,则优先考虑在 B 中有相等元素的操作方案。若相等元素已被操作,但还有未操作的与其 \mathrm{lowbit} 相等的元素,则按照性质六交换操作方案。直到 k 次操作机会用完或最大贡献为负。正确性显然。

对于相等元素的查询有多种方法,可使用数据结构维护集合 A,B 。可使用 std::setstd::map 或手写平衡树等数据结构维护,但常数过大。

可通过子任务 1,2,3,4,5,7,8

时间复杂度: O(n+k\log n) ,常数大
预计得分: 72

算法九

对于子任务 9 ,将算法八中的数据结构更换为哈希表、其它数据结构或排序即可。

可通过所有子任务。

时间复杂度: O(n+k) (期望)到 O(n+k\log n)
预计得分: 100

算法十

优化匹配做法。在算法七基础上,考虑优化连边。根据性质四,我们关注的重点在于其 \mathrm{lowbit} ,而非其值本身。考虑对 \mathrm{lowbit} 相同的点分类并记录个数,对集合 A,B 均建立 \log a_i \log b_i 个点并连边,对于相等的情况排序后统计连边或数据结构维护即可。 \log a_i \log b_i 的最大值为 31

可通过所有子任务。

时间复杂度: O(\mathrm{MaxcostMaxflow}+n\log n)
预计得分: 100

D. 网格图

By spj,题解 By spj

  • 考察选手的图论建图能力以及优化建图的知识点。
  • 思维难度 NOI
  • 实现难度 NOI

算法一

对于第 1 个子任务, n,m\le 5 ,数据范围极小,暴力 DFS 以及一些随机/贪心或者写错的高分算法可能均可通过。

期望得分: 0 6

算法二(一)

对于前 4 个子任务, n,m\le 2000 ,意味着网格图不会很大,可以建出整个网格图。记 (x,y) 为第 x 行第 y 列的格子。

对每个非障碍格子 (x,y) 建立 4 个结点 (x,y,d) ,其中 d 为上、下、左、右之一,表示当前机器人位于格子 (x,y) 且方向为 d 的状态。

对每个结点 (x,y,d) ,如果 (x,y) 沿 d 方向的下一格 (x',y') 在网格图内且不是障碍,则 (x,y,d)\rightarrow(x',y',d) 连一条长度为 0 的边;设 d 方向往左、右转 90° 得到的方向分别为 d_1,d_2 ,则 (x,y,d)\rightarrow(x,y,d_1) (x,y,d)\rightarrow(x,y,d_2) 各连一条长度为 1 的边。

以所有方向 d (x_s,y_s,d) 结点为源点集,求一遍单源最短路,那么结点 (x,y,d) 的最短路值 D(x,y,d) 就是到达状态 D(x,y,d) 的最小转向次数,于是每个询问 (x_t,y_t) 的答案就是 \min_d\{D(x_t,y_t,d)\}

时间复杂度: O(nm\log nm)

期望得分: 24

算法二(二)

不难发现 d 这一维只要记两种:水平和竖直。可以减少一半结点数。

注意到边长只有 0 1 ,因此可以用 BFS 求最短路,实现时每层先扩展 0 边,再扩展 1 边。

实现时,并不需要把边显式地建出来。

时间复杂度: O(nm)

期望得分: 29

算法三

对于第 5 个子任务, k\le 1 ,可以通过分类讨论得到答案。

如果起点 (x_s,y_s) 和终点 (x_t,y_t) 在同一水平线或竖直线上:

  1. 若两者之间无障碍,答案为 0
  2. 否则,若 n=1 m=1 ,则起点和终点不连通,答案为 -1
  3. 否则,必可以从起点绕到另一行/列再绕到终点,答案为 2

否则 (x_s,y_s)-(x_s,y_t)-(x_t,y_t) (x_s,y_s)-(x_t,y_s)-(x_t,y_t) 两条路径至少有一条无障碍,答案为 1

时间复杂度 O(q)

期望得分: 7 ,结合算法二期望得分 36

算法四

对于第 5-8 个子任务, k\le 1000 ,即网格图较大而障碍点较少。

不难发现一个性质:

性质 如果有若干连续的行(列)上均没有障碍及起点,则这一段连续的行(列)可以被换成一行(列)。

证明 不妨设第 l 列至第 r 列均没有障碍和起点,设将当前图 G 的第 l 列至第 r 列缩成一列(记为 l )后的图为 G' ,注意终点可能被缩到第 l 列。

以下证明对于任意起点和终点 s,t ,在 G G' 中的最小转弯次数相等,即 D_G(s,t)=D_{G'}(s,t)

1、对于 G s\rightarrow t 最小转弯次数路径 P ,当 P 每次进入列区间 [l,r] 时,设进入 [l,r] 的格子为 (x_1,l) ,离开 [l,r] 前或结束的格子为 (x_2,y_2) (可能是终点),则 (x_1,l)\rightarrow(x_1,y_2)\rightarrow(x_2,y_2) 为最小转弯次数走法。

将该路径段改成 G' 中的 (x_1,l)\rightarrow(x_2,l) 转弯次数相同。于是 D_{G'}(s,t)\le D_G(s,t)

2、对于 G' 中的 s\rightarrow t 最小转弯次数路径 P ,当 P 每次进入列 l 时,设进入 l 的格子为 (x_1,l) ,离开 l 或结束的格子为 (x_2,l) ,则 (x_1,l)\rightarrow(x_2,l) 为最小转弯次数走法。

  • P (x_2,l) 为终点,令 y_2=y_t
  • 否则,若 P (x_2,l) 的下一格为 (x_2,l-1) ,令 y_2=l
  • 否则,令 y_2=r

将路径段改成 G 中的 (x_1,l)\rightarrow(x_1,y_2)\rightarrow(x_2,y_2) 转弯次数相同。于是 D_G(s,t)\le D_{G'}(s,t)

以上 a\rightarrow b 表示走 a b 的最小转弯次数路径。

因此 D_G(s,t)=D_{G'}(s,t) ,对于另一方向同理。证完。

这样我们可以用障碍将网格进行离散化,即将起点障碍一起按 x 排序,将连续的空行缩成一行,再按 y 排序,将连续的空列缩成一列。这样,新的网格图行数和列数均不超过 2k+1

可以套用算法二计算 s 出发的最短路,对于每个询问通过二分查找可以得到终点所在的行列,从而完成询问。

和之前一样,实现时,并不需要把边显式地建出来。

如果使用 Dijkstra 求最短路:

时间复杂度 O(k^2\log k)

期望得分: 48

如果使用 BFS 求最短路:

时间复杂度为 O(k^2)

期望得分: 59

算法五

首先按算法四的方法离散化,在此基础上进一步优化。

\mathrm{H} \mathrm{V} 表示水平和竖直方向,则当格子 (x,y_1) (x,y_2) y_1\le y_2 )之间不存在障碍 (x,y) y_1 < y < y_2 )时,结点 (x,y_1,\mathrm{H}) (x,y_2,\mathrm{H}) 不需要代价。竖直方向类似。

也就是说,可以把每行每列的极长连续段提取出来建点,也就是说,把每行的障碍按 y 排序,将连续的空格段缩成一个新点,再将每列的障碍按 x 排序,将连续的空格缩成一个新点。

这样就缩掉了大量的点——每个连续段或者是一个空行或空列,或者与至少一个障碍点相邻,而在算法四的离散化之后最多只有 k+1 个空行和 k+1 个空列,且每个障碍点最多与 4 个极长连续段相邻,因此新点最多 6k+2 个。

同时也缩掉了所有长度为 0 的边。也就是说,新点构成的图只有一种边:如果水平连续段 v_H 和竖直连续段 v_V 在网格图中交于一点,则 v_H v_V 之间连一条长度为 1 的边。

现在边数仍然是 O(k^2) 的,考虑优化连边。

定义序列 S_x ,其中 S_x[y] 为过 (x,y) 格的竖直连续段(若不存在,则 S_x[y] 的值可以任意),则对于水平连续段 (x_1,y_1)-(x_1,y_2) y_1\le y_2 ),需要从该段往所有 y\in[y_1,y_2] S_x[y] 连一条长度为 1 的边。

注意到 S_x 是由 S_{x-1} 修改了位于第 x 行的障碍 (x,y) 对应的 S_{x-1}[y] 位置的值得到的序列(为了方便可以直接改成 (x,y) 下方的连续段),这样从 S_1 S_n 最多修改了 k 次。

故可以用可持久化线段树处理出序列 S_1,S_2,\cdots,S_n 。对于线段树上每个非叶结点,向其两个子结点连长度为 0 的有向边。之后对于每个水平连续段 (x_1,y_1)-(x_1,y_2) y_1\le y_2 ),向 S_x[y_1,y_2] 在线段树上定位到的每个结点连一条长度为 1 的有向边。

这样就完成了水平连续段向竖直连续段的连边,竖直连续段向水平连续段的连边同理。

现在的结点数和边数都优化到了 O(k\log k) 级别,再用 BFS 求一遍最短路即可。时间复杂度和空间复杂度均为 O(k\log k)

和之前一样,实现时,并不需要把边显式地建出来。

时间复杂度: O(k\log k)