zhanyeye's learning log

常见数据文件存储和读取

• 数据文件类型
• 数据文件读取
• 数据文件存储
• JSON 解析
• 数据分块读取

TCP/IP 背景和介绍

TCP/IP 不是一个协议，而是一个协议族的统称，里面包括了 IP 协议、ICMP 协议、TCP 协议、以及 http、ftp、pop3 协议等。网络中的计算机都采用这套协议族进行互联。

变量和数据类型

python 关键字

下列的标识符是 Python3 的关键字，并且不能用于通常的标识符。关键字必须完全按照下面拼写：

1
2
3
4
5
6
7
8
9

False               def                 if                  raise
None                del                 import              return
True                elif                in                  try
and                 else                is                  while
as                  except              lambda              with
assert              finally             nonlocal            yield
break               for                 not                 
class               from                or                  
continue            global              pass

若元素数量比较小（不超过 20）时，想要存储每个元素取或不取的状态时，可以借助位运算将状态压缩。

需要借助状态压缩过程的动态规划就是状态压缩 DP（很多地方会简称为 状压 DP）。

取若干元素，也就是对应的位置记为 1，其余位置记为 0。例如，一共有 5 个元素 a,b,c,d,e，我们分别用 1,2,4,8,16 表示这五个元素，则集合 {a,c,e} 可以用 $(10101)_2$=21 来表示，而集合 {b,c,d} 可以用 $(01110)_2=14$ 表示。

对于元素个数为 nn 的情况，其空间复杂度为 $\mathcal{O}(2^n)$。

如果不用状态压缩，那么我们状态需要开 5 维的dp[2][2][2][2][2]，这样不仅使得代码的实现变的很复杂，并且当 n 的大小不一样的时候，状态维度也不一样，不是很容易实现。

控件复杂度和状态数量没有变，变的是状态的表达方式

参考链接：https://blog.csdn.net/readlnh/article/details/51058005

问题描述

　　我们把一个数称为有趣的，当且仅当：
　　1. 它的数字只包含0, 1, 2, 3，且这四个数字都出现过至少一次。
　　2. 所有的0都出现在所有的1之前，而所有的2都出现在所有的3之前。
　　3. 最高位数字不为0。
　　因此，符合我们定义的最小的有趣的数是2013。除此以外，4位的有趣的数还有两个：2031和2301。
　　请计算恰好有n位的有趣的数的个数。由于答案可能非常大，只需要输出答案除以1000000007的余数。

输入格式

　　输入只有一行，包括恰好一个正整数n (4 ≤ n ≤ 1000)。

输出格式

　　输出只有一行，包括恰好n 位的整数中有趣的数的个数除以1000000007的余数。

样例输入

4

样例输出

3

从 n 个数中选 k 个数的和为 sum 这个问题。

用二进制枚举的方法解决的题目。

话说大诗人李白，一生好饮。幸好他从不开车。

一天，他提着酒壶，从家里出来，酒壶中有酒两斗。他边走边唱：

• 无事街上走，提壶去打酒。
• 逢店加一倍，遇花喝一斗。

这一路上，他一共遇到店 5 次，遇到花 10 次，已知最后一次遇到的是花，他正好把酒喝光了。请你计算李白遇到店和花的次序，有多少种可能的方案。

二进制枚举是一种写起来非常简洁的解法。我们已知遇店 5 次，遇花 10次，并且最后一次遇到花，正好把酒喝光。那么我们可以把店作为二进制中的 1，把花作为二进制中的 0，因为已经确定最后一次遇到的是花，所以我们需要判断枚举的结果是否刚好有 5 个 1 和 9 个 0。那么我们就枚举出 14 位二进制的所有可能并加以判断即可，判断思路为判断二进制是否有 9 个 0，5 个 1，并且最终酒刚好剩 1 斗。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

int ans = 0;
for (int i = 0; i < (1<<14); ++i) {
    int tot_1 = 0;
    int tot_0 = 0;
    int num = 2;
    for (int j = 0; j < 14; ++j) {
        if (i&(1 << j)) { // 这里判断二进制 i 从右数第 j + 1 位是否为 1
            tot_1++;
            num = num * 2;
        } else {
            tot_0++;
            num = num - 1;
        }  
    }
    if (tot_1 == 5 && tot_0 == 9 && num == 1) {
        ++ans; // 记录合法方案数
    }
}

关于标记：

1. 标记的主要目的：搜索的时候不会往回走
2. 取消标记：让其它路劲也可以访问该点，适用于路径不同产生的效果不同的情况
3. 不取消标记：适用于每个点只需访问一遍的情况：连通性判断

关于返回值：

1. 在递归出口一定要 return, 否则会错误
2. 如果 dfs 返回值是 bool， 在调用 dfs 处也要返回 bool 值

关于参数：

1. 参数用来放置搜索中会发生变化的状态

2. 参数可以表示 dfs 深度

3. 如果要在 dfs 出口处比较这次 选择结果的最大值或最小值，可将其放在参数上

4. 有时为了判断dfs出口，设置一个计数器参数
   （搜索所有可能的情况，选最有解）
   （注意dfs出口处要有return）

概述

若图 G 中存在这样一条路径，使得它恰好通过 G 中每条边一次，则称该路径为 欧拉路径。若该路径是一个环路，则称为 欧拉（Euler）回路。

具有欧拉回路的图称称为 欧拉图。

具有欧拉路径但不具有欧拉回路的图称为 半欧拉图。

概述

对一个 有向无环图（Directed Acyclic Graph, DAG） G 进行拓扑排序，是将 G 中的所有顶点排成一个线性序列，使得图中任意一对顶点 u 和 v，若边 <u,v> $\in E(G)$，则 u 在线性序列中出现在 v 之前。通常，这样的线性序列称为满足 拓扑次序（Topological Order） 的序列，简称 拓扑序列。简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为 拓扑排序。

**在有环的情况下会出现有一些点没有访问到的情况 => ** 可以通过拓扑排序算法判断一个有向图有没有环

拓扑排序每个点一定只会被访问1遍: 每个点的入度只有在一个时刻变为0, 要么一开始就时0, 要么在某个时刻减小为 0, 不可能多次变成 0