avatar

光和尘

有花满渚、有酒盈瓯

目录检索关于我

🔖 算法精确覆盖DLX 算法

前言

很早就想要补一下舞蹈链和精确覆盖算法,却一直各种拖延,趁着最近有空,又重新翻开了刘汝佳的书。大学的时候看过几次,甚至照着书里的思路手敲了一遍并通过了例题,但对于算法的原理一直有些不求甚解。很早以前,一位同学告诉我说“现在看不懂的东西不用勉强,以后慢慢就会懂了”,后来也真的在不断印证这句话;但我很担心随着年纪的增长,记忆力和学习能力不断退化之后,恐怕这个 flag 会逐渐倒下。所以趁着眼下尚能理解进去,尽量用自己的语言做一下记录。

精确覆盖问题

有一些由整数 1 \sim n 中的数字组成的集合 S_1, S_2, \cdots, S_m,要求选择若干个集合 S_i,使得 1 \sim n 中每个整数都在选出的集合中的某个出现且恰好仅出现一次。举个栗子:

🔖 shuffleknuth-shuffle约瑟夫环

对于给定的 N 个数,将其公平地随机打乱,使得每个位置上每个数出现的概率相等。

约瑟夫环

遍历位置 i,每次从剩余的数中随机取一个放到该位置上。由此可以将问题归约到 不定步长约瑟夫环问题,即:N 个人围坐一圈,从 1 开始报数,每次随机一个数 x,报到 x 的人从圈中离开,然后进入下一轮游戏。因为需要求离开的顺序,所以不能使用递推法,只能用树状数组+二分,复杂度为:

  • 时间复杂度: O(N \cdot \log^2 N)
  • 额外空间复杂度: O(N)

knuth-shuffle

进一步考虑,在 shuffle 问题中,我们并不需要保证每个“人”的相对位置不变,也不必每次从上一个被踢的位置开始继续报数,而是只需要保证剩下的“人”被选出来的概率相同即可;如果能让剩下的人始终紧密地聚集到一起,那么利用数组的索引特性,每次

🔖 quiz扫描线前缀和树状数组线段树

一维区间

问题简述

坐标轴上存在 N 条线段,有 Q 次查询,每次查询询问与给定区间 [a_q, b_q] 相交的线段数量。(相交指存在重叠的区域,包括相互包含的情况)

问题简析

先对线段进行排序:左端点小的排在前面,左端点相同时,右端点小的排在前面。

f(x) 为左端点在点 x 上的线段条数,g(x) 为右端点在 x 上的线段条数。计算 f(x)g(x) 可以通过扫描排好序的线段,不妨记当前扫描到的线段为 [x1, x2],并执行下述操作:

  • f(x1) = f(x1) + 1
  • g(x2) = g(x2) + 1

在扫描的过程中,不难有:

  • 区间左侧 [-\infty, a_q-1] 与当前区间不相交的数量为线段右端点个数,即 \displaystyle \sum_{x=-\infty}^{a_q - 1} f(x)

🔖 quiz经典问题约瑟夫环

经典约瑟夫环问题

N 个人围坐成一圈,任选某个人将其编号为 0,其右手边的人编号为 1,以此类推,将全部 N 个人进行唯一编号。由编号为 0 的人从 1 开始报数,其右手边的人报下一个数,以此类推。报到 M 的人起身离开,TA 右手边的人又从 1 开始报数,直到所有人起身离开,求最后一个起身离开的人的编号。

暴力法

使用链表进行模拟,起身离开的复杂度为 O(1),报数的复杂度为 O(M),故总复杂度为:

  • 时间复杂度: O(M \cdot N)
  • 额外空间复杂度: O(N)

树状数组

用一个数组 A 表示这 N 个人当前的游戏状态:

  • A[i] = 1: 编号为 i 的人还坐在那里
  • A[i] = 0: 编号为 0 的人已经起身离开

则可以使用树状数组维护前缀和

🔖 专题训练解题报告

前言

这两天奶奶做手术,我在医院里陪护,奶奶不会说普通话所以只好一直陪在旁边。实在有些闲得慌,正好在刷知乎的时候看到了《剑指offer》的推荐,搜了下发现有 OJ 收录了原书中的题目,于是开始尝试手机写代码23333(没有带电脑)。 强迫症晚期,一上手就非要做完不可,还好题目量少。使用低效率的方式做一件并不紧要的事情实在是太浪费生命了。(不过也有人说,生命就是用来浪费的2333

为了偷懒节约篇幅,将过于基础的题放在了 附录 中。

01 二维数组的查找

题目链接

题意简述

有一个 R \times C 的矩阵,每行从左至右数值递增,每列从上至下数值递增,求矩阵中是否包含给定的数值。

题目简析

注意到矩阵中任意一个子矩阵仍然满足此特性,则可以二分子矩阵,直到子矩阵的大小为

© 2017-2022 光和尘有花满渚、有酒盈瓯