Vim模式

Vim 具有 6 种基本模式和 5 种派生模式，先学三种

• 普通模式(Normal mode)

在普通模式中，用的编辑器命令，比如移动光标，删除文本等等。这也是 Vim 启动后的默认模式。这正好和许多新用户期待的操作方式相反（大多数编辑器默认模式为插入模式）。

• 插入模式(Insert mode)

在这个模式中，大多数按键都会向文本缓冲中插入文本。大多数新用户希望文本编辑器编辑过程中一直保持这个模式。

在插入模式中，可以按 ESC 键回到普通模式。

• 命令行模式(Command line mode)

在命令行模式中可以输入会被解释成并执行的文本。例如执行命令（:键），搜索（/和?键）或者过滤命令（!键）。在命令执行之后，Vim 返回到命令行模式之前的模式，通常是普通模式。

泛型

• 如果Foo是 Bar的一个子类型（子类或者子接口），而 G是具有泛型声明的类或接口，G<Foo>并不是G<Bar>的子类型
• 数组和泛型有所不同，假设Foo是Bar 的一个子类型（子类或者子接口），那么Foo[]依然是 Bar[]的子类型;但 G<Foo>不是 G<Bar>的子类型。

其他

1.平衡三进制 :mark一下，放砝码问题，梦回计组pre

2.一个正整数n本身和他各位之和模9同余

数论

质数

定义

在大于1的整数中，只包含1和本身这两个约数，就被称为质数，或者叫素数

完全背包问题

每种物品无限个

• 状态转移

以前一直对完全背包的状态转移方程**f[i][j]=max(f[i-1][j],f[i][j-v[i]]+w[i])里面的f[i][j-v[i]]+w[i]**似懂非懂，今天看到一个比较好的解释

1.已知完全背包还有状态转移方程

f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i],f[i-1][j-2*v[i]]+2*w[i],...,f[i-1][j-k*v[i]]+k*w[i]) (j-k*v[i]>=0)

2.故可得f[i][j-v[i]] = max(f[i-1][j-v[i]],f[i-1][j-2*v[i]]+*w[i],...,f[i-1][j-k*v[i]]+(k-1)*w[i])

3.第二步的式子左右加上w[i]，右边带入一式即可得**f[i][j]=max(f[i-1][j],f[i][j-v[i]]+w[i])**

• 排列型背包和组合型背包

  • 排列型背包外层循环价值，内层循环物品
  • 组合型背包外层循环物品，内层循环价值

二分法

整数二分

本质

• 二分法的本质不是单调性而是二段性，一段满足性质，一段不满足性质。两个模板分别在满足性质的区间里寻找最左边的答案(一)和最右边的答案(二)
• 有单调性一定可以二分，能二分不一定要有单调性
• 每次二分要保证mid处于答案的区间内
• 二分模板在有解的情况用，无解下二分的输出根据题目确定

考的是怎么从题目条件抽象出图(建图)

树与图存储

邻接表（前向星）

1
2
3
4
5
6
7
8
9
10
11
12

// 对于每个点k，开一个单链表，存储k所有可以走到的点。h[k]存储这个单链表的头结点，e[k]存储箭头指向的点,we[k]存储该边权值
int h[N], e[N], ne[N],we[N] idx;

// 添加一条边a->b z为权值
void add(int a, int b, int z)
{
    we[idx] = z, e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

// 初始化
idx = 0;
memset(h, -1, sizeof h);

对于每个顶点，添加与其相连的边时按照头插法添加,

双指针算法

1
2
3
4
5
6

for (int i = 0, j = 0; i < n; i ++ )
{
    while (j < i && check(i, j)) j ++ ;

    // 具体问题的逻辑
}

常见问题分类：
(1) 对于一个序列，用两个指针维护一段区间
(2) 对于两个序列，维护某种次序，比如归并排序中合并两个有序序列的操作

前缀和与差分

前缀和

一维前缀和

s[i]代表前i个数的和

1
2
3
4
5
6

S[i] = a[1] + a[2] + ... a[i] //前缀和初始化,边界s[0]=0
a[l] + ... + a[r] = S[r] - S[l - 1] //求区间[l,r]的和，O(1)时间

for (int i = 1; i <= n; i++){
	s[i]=s[i-1]+a[i];
}

零碎知识点

• “Shell”——也可称为"壳"，充当的是人与内核（硬件）的翻译官，用户将一些命令"告诉"Shell，它就会调用相应的程序服务执行工作
• 若一个命令太长一行放不下，可在行尾输入"\"并按回车，可转到下一行输入
• .开头的隐藏文件，用 ls -a才能查看
• 定义别名、shell变量赋值时“=”两端不能有空格

正则表达式基础