2017-2018 问题求解(四)上机考试题解

Day1

A 差异度

题意:给$n (1 \leq n \leq 10^5)$个20位的01串,求两两之间hamming距离的最小值。

解法:此题解法甚多。下面列举3个常见的解法:

  1. 注意到当$n$很大时,最终答案不会太大(考虑一个01串hamming距离为$d$的邻域大小随$d$是指数增长的,然后用鸽巢原理即可)。所以,从小到大枚举答案$d$,并在每个串的$d$-邻域内搜索即可。
  2. 建图。将所有20位的01串视为顶点,相差1位的两个串连边。问题就变成了:给定一个顶点子集,求这个子集中两两距离的最小值。这用多线程bfs就可以解决。时间复杂度为$2^{20}*20$。
  3. 用FWT处理出所有可能的异或值,取popcount最小的那个即可。(FWT课内没学,用了感觉有点犯规,但写起来方便是真的

B 工作安排

题意:某人有$T (0 \leq T \leq 100)$时间,$N (0 \leq N \leq 100)$组工作。每组工作有3种类型:至多选一个做,至少选一个做,无限制。每组工作中最多有100个工作,每个工作有完成的时间和所能得到的收益值。求所能获得的最大收益。

题解:较为复杂的背包问题。用常规的dp就可以解决。对于每组工作的附加限制,在更新dp值的时候需要特殊处理。

Day2

A 矩阵分割游戏

题面:NOI1999 棋盘分割

题意:给一个8*8的矩阵,每次可以横着或竖着掰成两半并舍弃一块,最后得到$n$块子矩阵。求子矩阵数字和的标准差的最小值。

题解:由gay率论相关知识,要使标准差取得最小值,只要让平方和最小即可(因为和是固定的)。然后dp或者记忆化爆搜即可。

B 旅行箱

题意:有$n \leq 42$个数,取出它的一个子集,使得子集和在不超过$W$的前提下,使得子集和最大。(简单背包问题)

题解:用meet-in-the-middle思想。将集合分成两部分,预处理出每部分的所有子集和。然后将这些子集和排序,对于一部分的某个子集和$S$,在另一部分中找出不超过$W-S$的最大子集和,然后取最大值即可。复杂度$O(n2^{n/2})$。

发表评论

电子邮件地址不会被公开。 必填项已用*标注