列表、字符串及字典——Python基本数据结构

Python 的强大之处就在于它有丰富的库以及各种方便的特性。这篇文章将会介绍 Python 中的几个内置类型——列表、元组、字符串及字典。

我是按照 Python3 来介绍,如果和 Python2 有不同的地方会特别指出的。并且,文中的代码如果有输出的部分,都是按照 Python3 语法进行。另外,如果代码中是以 >>> 开头的,就说明这段代码是我直接在交互模式下运行的,并且包含了输出。

List——列表类型

首先,我们来介绍列表类型。什么是列表呢?你可以认为列表是多个变量的集合,并且这个集合是有序的。你在以前遇到的类型可能都只是涉及单个元素,比如说 intfloat 之类的,这都只涉及了一个数字。但是列表不同,它可以用一个变量存储多个元素,如果你了解过其它语言,列表和数组是十分类似的。

一个列表是用一个方括号包围的,列表中的元素使用逗号分隔,例如下面这几个变量都是一个列表:

值得注意的是,一个列表可以不包含任何元素,就像变量 c 存储的列表一样,这样的列表叫做空列表

另外,一个列表内的元素不一定要有相同的类型,甚至列表本身也可以作为元素存储在一个列表中:

比如说上面第一个列表,它存储着三个不同类型的元素,一个是整数,一个是浮点数,另外一个是字符串。

至于第二个列表,它包含四个元素,第一个元素是一个整数 233 ,第二个元素是先前的列表 x ,第三个元素是一个空列表 [] ,最后一个元素是另外一个仅包含一个字符串作为元素的列表。

(more…)

Read More

CodeChef上一道有趣的网络流题目

这是一道2016年二月CodeChef上的一道题目,叫做Call Center Schedule

题目大意是这样的:

一个电话公司有 P 个员工,一个星期有 D 天,每天需要工作 H 个小时。每个员工在每个小时只能做参加会议和与客户通话两件事情中的一件,或者不做。

现在要为安排一个和客户通话的时间表,要求满足

  • 每个人每天最多花费 N 个小时在参加会议和通话上
  • 第 i 个人每周最多花费 Li 个小时和客户通话
  • 每个人每天在 LTbegin 到 LTend 的时间内至少要有 1 小时没有被安排任务
  • 对于第 i 天第 j 个小时,恰好有 Ri, j 个人可以和客户通话

另外,开会的时间表已经安排完成,如果 Fk, i, j 是 0 则表示第 k 个人在第 i 天的第 j 个小时开会,如果是 1 则表示他可以被安排去和客户通话。

时限是 2s,最多 5 组数据,并且 1 \leq N \leq H \leq 70, 1 \leq D, P \leq 70, 1 \leq L_i \leq ND, 0 \leq R_{i, j} \leq 15, F_{k, i, j} \in \{0, 1\}, 1 \leq LT_{begin} \leq LT_{end} \leq N

(more…)

Read More

Tarjan算法寻找有向图的强连通分量

在图论中,一个有向图被成为是强连通的(strongly connected)当且仅当每一对不相同结点 u 和 v 间既存在从 u 到 v 的路径也存在从 v 到 u 的路径。有向图的极大强连通子图(这里指点数极大)被称为强连通分量(strongly connected component)。

tarjan-graph

比如说这个有向图中,点 1, 2, 4, 5, 6, 7, 8 和相应边组成的子图就是一个强连通分量,另外点 3, 9 单独构成强连通分量。

Tarjan 算法是由 Robert Tarjan 提出的用于寻找有向图的强连通分量的算法。它可以在\mathcal O(|V|+|E|)的时间内得出结果。

Tarjan 算法主要是利用 DFS 来寻找强连通分量的。在介绍该算法之前,我们先来介绍一下搜索树。先前那个有向图的搜索树是这样的:

search-tree

有向图的搜索树主要有 4 种边(这张图只有 3 种),其中用实线画出来的是树边(tree edge),每次搜索找到一个还没有访问过的结点的时候就形成了一条树边。用长虚线画出来的是反祖边(back edge),也被叫做回边。用短虚线画出来的是横叉边(cross edge),它主要是在搜索的时候遇到了一个已经访问过的结点,但是这个结点并不是当前节点的祖先时形成的。除此之外,像从结点1到结点6这样的边叫做前向边(forward edge),它是在搜索的时候遇到子树中的结点的时候形成的。

(more…)

Read More

CodeChef February 2016. Weird Sum 题解

这是 CodChef February Challenge 2016 上的一题,题目链接在这里:WRDSUM

给定一个整数 n(n \geq 2),考虑其质因子分解 n = p_1^{k_1}p_2^{k_2}\cdots p_r^{k_r}

g = \text{gcd}(k_1, k_2, \cdots, k_r)m_i = \frac{k_i}{g}

定义函数 F(n) = p_1^{m_1}p_2^{m_2}\cdots p_r^{m_r}

现在给定一个整数 N(N \leq 10^{2016}),你需要计算

 S = F(2) + F(3) + \cdots + F(N)

答案对 998244353 取模

(more…)

Read More

反演魔术:反演原理及二项式反演

首先我来说说什么是反演(inversion),对于一个数列\{f_n\}来说,如果我们知道另外一个数列\{g_n\},满足如下条件

 g_n = \sum_{i=0}^n a_{ni}f_i

反演过程就是利用 g_0, g_1, \cdots, g_n 来表示出 f_n

 f_n = \sum_{i = 0}^n b_{ni}g_i

本质上来说,反演其实是一个解线性方程组的过程,但是你观察后发现,这个矩阵实际上是一个三角矩阵,那必然存在着快捷的方法。对于使得这两个反演公式成立的这些系数应该满足什么条件呢?我们现在就来探讨一番!

我们首先讨论一下在什么情况下能够比较容易建立反演公式,之后介绍二项式反演以及它的两个应用,其中一个是错位排列问题

(more…)

Read More

Vim代码自动补全的神器:YouCompleteMe

YouCompleteMe 是一款非常强大的代码自动补全插件。我原先用的是 clang-complete,然后在最近有好几个月没有写东西了,系统一直更新更新到后面 clang-complete 出了一些问题,于是就开始找有什么其它的自动补全插件,然后就听说了 YouCompleteMe 的大名,如果想有比较详细的了解,可以参考它的官方文档,我在这里只是介绍一部分内容以及如何安装。

首先我们来看一段它的演示,你马上就会了解到这是有多强大了!

cpp-demo-of-youcompleteme

(more…)

Read More

特殊多项式在整点上的线性插值方法

首先我来解释一下题目是什么东西,假如给你一个 k 次多项式 P(x),并且已知了 P(0), P(1), \cdots, P(k),要求计算出 P(n), n \in \mathbb N 的值,由于已经知道了 k + 1 个点值,那么要插值出系数是可以在 \mathcal O(k^2) 完成,如果使用 FFT 的话是可以在 \mathcal O(k \log^3 k) 的时间内完成的[1],但是对于这个特别的问题,我们有一个 \mathcal O(k) 的算法!这好像是杜教先提出来的,然后还有这篇文章

(more…)

Read More

Catalan 数列及其应用

卡特兰数(Catalan number)是组合数学中一个重要的计数数列,在很多看似毫不相关地方都能见到它的身影

这篇文章介绍卡特兰数的几个应用以及它的推导过程,从组合推理和生成函数两个方面来推导出 Catalan 数的公式

带限制条件的路径总数

首先我们来看一个问题:

在一个平面直角坐标系中,只能往右或往上走一个单位长度,问有多少种不同的路径可以从左下角 (1, 1) 走到右上角 (n, n),并且要求路径不能经过直线 y = x 上方的点,下图中的路径都是合法的(图片来源 Wikipedia)

450px-Catalan_number_4x4_grid_example.svg

如果没有限制条件,那么从左下角走到右上角一共有 2n 步,有 n 步是往右,另外 n 步是往上,那么路径方案数就是 2n 步中选择 n 步往右,一共有 {2n} \choose {n} (即 C_{2n}^n)种方案

那么我们考虑一下这里面有多少种方案是不合法的

首先对于每一种不合法的方案,它的路径一定与 y = x + 1 有交。我们找到它与 y = x + 1 的第一个交点,然后将这个点后面部分的路径关于 y = x + 1 做一个对称。由于原来路径到达 (n, n),新的对称之后的路径就会到达 (n - 1, n + 1)。这样我们把每一种不合法方案都对应到了一条从 (1, 1)(n - 1, n + 1) 的路径,现在再来看是否每一条这样的路径都能对应到一种不合法方案,如果是,那么这就建立了一个一一映射的关系,也就是它们的方案总数相同。这是肯定的,因为每一条这样的路径必定与 y = x + 1 有交,那么对称回去,就得到一条不合法方案

由于从 (1, 1)(n - 1, n + 1) 的路径有 {n - 1 + n + 1} \choose {n - 1} 条,那么合法的方案就是

 C_n = {{2n} \choose {n}} - {{2n} \choose {n - 1}} = \frac{1}{n + 1} {{2n} \choose {n}}

我们把这个方案数记为 C_n,这就是著名的 Catalan 数

(more…)

Read More

Codeforces 上的一些组合计数问题

Codeforces 15E. Triangles

Problem:给出一个有规律的金字塔(如图),黑色的边是可以走路径,要求求出包含 H 点的简单回路(不经过一个顶点两次)的条数,并且这个回路围住的部分不可以包含灰色的三角形,答案对 10^9+9 取模,其中 n \leq 10^6,并且一定是一个偶数

5945210be972aa5fe947f3b8a3a0378a4cade844

Example:当 n = 2 时,一共有 10 种方案,其中 5 种是这样,另外的是顺时针顺序地走

5E-triangles

Solution:首先第 1 层是最特殊的,因为这里没有灰色的三角形,然后注意到灰色的部分把整个金字塔分成了左部和右部

5E-triangles-level1

路径现在可以分成三个部分

  • 在第一层移动,这一共 10 种(见样例)
  • 进入左部或右部后直接回到 H
  • 进入左部(右部)后经过 E 点进入右部(左部)

对于第二种情况,在第一层的部分走法可以是(只有逆时针部分,实际上有 8 种)

  • A \rightarrow B \rightarrow D \rightarrow \text{LeftPart} \rightarrow E \rightarrow C \rightarrow A
  • A \rightarrow B \rightarrow D \rightarrow \text{LeftPart} \rightarrow E \rightarrow F \rightarrow C \rightarrow A
  • A \rightarrow B \rightarrow E \rightarrow \text{RightPart} \rightarrow F \rightarrow C \rightarrow A
  • A \rightarrow B \rightarrow D \rightarrow E \rightarrow \text{RightPart} \rightarrow F \rightarrow C \rightarrow A

对于第三种情况,在第一层(原来图中的两层现在算一层,也就是下面的 n 是题目中 n\frac{1}{2})的部分走法有 2 种,左部到右部和右部到左部

现在要统计的就是在左部和右部内有多少种方案,因为左部右部对称,所以答案是一样的,我们来考虑左部

S_n 表示在有 n 层的金字塔中,走左部的方案数,因为走进左部后每一层都会遇到凹进去的部分,这部分只要枚举一下走了多远可以统计出第 n 层一共有 2\sum_{i=1}^{n-2} 2^i + 1 = 2^n - 3 这么多的情况

然后要走到第 n 层后就是 \prod_{i=2}^{n} (2^i - 3) 种情况,然后走回去的路径有 4 种选择,因此

 S_n = \sum_{i=2}^{n} 4\prod_{j=2}^i (2^j - 3)

答案是 2S_n^2 + 8S_n + 10 (more…)

Read More

牛顿迭代法在多项式运算的应用

总算是快把 FFT 和生成函数的各种东西补了好多,膜拜策爷的论文和 Picks 的博客 QAQ

这篇文章大概就是说如何用牛顿迭代法来解满足 G(F(z)) \equiv 0 \pmod {z^n}F(z)

然后这东西可以比较方便地计算 \sqrt{A(z)}e^{A(z)},也就是多项式开根、求指数对数之类鬼畜的东西,在生成函数计数中十分有用

顺便一提,这里说的“多项式”实际上你可以直接理解为生成函数或者形式幂级数

(more…)

Read More