没有秘密的秘密小屋

一个什么都没有的网站

0%

发表于 分类于
本文字数： 1.1k 阅读时长 ≈ 1 分钟

二分图

一个图是二分图 当且仅当图中不含奇数环

染色法

o(m+n)
判断二分图

代码流程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
int n;      // n表示点数
int h[N], e[M], ne[M], idx;     // 邻接表存储图
int color[N];       // 表示每个点的颜色，-1表示未染色，0表示白色，1表示黑色

// 参数：u表示当前节点，c表示当前点的颜色
bool dfs(int u, int c)
{
    color[u] = c;
    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (color[j] == -1)
        {
            if (!dfs(j, !c)) return false;
        }
        else if (color[j] == c) return false;
    }

    return true;
}

bool check()
{
    memset(color, -1, sizeof color);
    bool flag = true;
    for (int i = 1; i <= n; i ++ )
        if (color[i] == -1)
            if (!dfs(i, 0))
            {
                flag = false;
                break;
            }
    return flag;
}


匈牙利算法

最坏o(mn)
最大匹配

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
int n1, n2;     // n1表示第一个集合中的点数，n2表示第二个集合中的点数
int h[N], e[M], ne[M], idx;     // 邻接表存储所有边，匈牙利算法中只会用到从第一个集合指向第二个集合的边，所以这里只用存一个方向的边
int match[N];       // 存储第二个集合中的每个点当前匹配的第一个集合中的点是哪个
bool st[N];     // 表示第二个集合中的每个点是否已经被遍历过

bool find(int x)
{
    for (int i = h[x]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!st[j])
        {
            st[j] = true;
            if (match[j] == 0 || find(match[j]))
            {
                match[j] = x;
                return true;
            }
        }
    }

    return false;
}

// 求最大匹配数，依次枚举第一个集合中的每个点能否匹配第二个集合中的点
int res = 0;
for (int i = 1; i <= n1; i ++ )
{
    memset(st, false, sizeof st);
    if (find(i)) res ++ ;
}


发表于 分类于
本文字数： 1.2k 阅读时长 ≈ 1 分钟

最小生成树

prim算法 (稠密图)

朴素版prim算法 （常用）

代码短
稠密图
经常用
o(n^2)
算法流程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
int n;      // n表示点数
int g[N][N];        // 邻接矩阵，存储所有边
int dist[N];        // 存储其他点到当前最小生成树的距离
bool st[N];     // 存储每个点是否已经在生成树中


// 如果图不连通，则返回INF(值是0x3f3f3f3f), 否则返回最小生成树的树边权重之和
int prim()
{
    memset(dist, 0x3f, sizeof dist);

    int res = 0;
    for (int i = 0; i < n; i ++ )
    {
        int t = -1;
        for (int j = 1; j <= n; j ++ )
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;

        if (i && dist[t] == INF) return INF;

        if (i) res += dist[t];
        st[t] = true;

        for (int j = 1; j <= n; j ++ ) dist[j] = min(dist[j], g[t][j]);
    }

    return res;
}


堆优化版prim算法 （不常用）

不经常用
o(mlogn)

克鲁斯卡尔(kruskal)算法 (稀疏图)

o(mlogm)

算法流程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

int n, m;       // n是点数，m是边数
int p[N];       // 并查集的父节点数组

struct Edge     // 存储边
{
    int a, b, w;

    bool operator< (const Edge &W)const
    {
        return w < W.w;
    }
}edges[M];

int find(int x)     // 并查集核心操作
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int kruskal()
{
    sort(edges, edges + m);

    for (int i = 1; i <= n; i ++ ) p[i] = i;    // 初始化并查集

    int res = 0, cnt = 0;
    for (int i = 0; i < m; i ++ )
    {
        int a = edges[i].a, b = edges[i].b, w = edges[i].w;

        a = find(a), b = find(b);
        if (a != b)     // 如果两个连通块不连通，则将这两个连通块合并
        {
            p[a] = b;
            res += w;
            cnt ++ ;
        }
    }

    if (cnt < n - 1) return INF;
    return res;
}


发表于 更新于 分类于
本文字数： 3.6k 阅读时长 ≈ 3 分钟

单源（起点）最短路

只有一个起点
n m都很大

所有边都是正数

朴素Dijkstra算法

o(n^2) 点数^2
稠密图
邻接矩阵

20220116171410

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
int g[N][N];  // 存储每条边
int dist[N];  // 存储1号点到每个点的最短距离
bool st[N];   // 存储每个点的最短路是否已经确定

// 求1号点到n号点的最短路，如果不存在则返回-1
int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    for (int i = 0; i < n - 1; i ++ )
    {
        int t = -1;     // 在还未确定最短路的点中，寻找距离最小的点
        for (int j = 1; j <= n; j ++ )
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;

        // 用t更新其他点的距离
        for (int j = 1; j <= n; j ++ )
            dist[j] = min(dist[j], dist[t] + g[t][j]);

        st[t] = true;
    }

    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}



堆优化版Dijkstra算法

o(mlogn) 边数 * log点数
稀疏图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
typedef pair<int, int> PII;

int n;      // 点的数量
int h[N], w[N], e[N], ne[N], idx;       // 邻接表存储所有边
int dist[N];        // 存储所有点到1号点的距离
bool st[N];     // 存储每个点的最短距离是否已确定

// 求1号点到n号点的最短距离，如果不存在，则返回-1
int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, 1});      // first存储距离，second存储节点编号

    while (heap.size())
    {
        auto t = heap.top();
        heap.pop();

        int ver = t.second, distance = t.first;

        if (st[ver]) continue;
        st[ver] = true;

        for (int i = h[ver]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > distance + w[i])
            {
                dist[j] = distance + w[i];
                heap.push({dist[j], j});
            }
        }
    }

    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}


存在负权边

Bellman-Ford

o(nm)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
int n, m;       // n表示点数，m表示边数
int dist[N];        // dist[x]存储1到x的最短路距离

struct Edge     // 边，a表示出点，b表示入点，w表示边的权重
{
    int a, b, w;
}edges[M];

// 求1到n的最短路距离，如果无法从1走到n，则返回-1。
int bellman_ford()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    // 如果第n次迭代仍然会松弛三角不等式，就说明存在一条长度是n+1的最短路径，由抽屉原理，路径中至少存在两个相同的点，说明图中存在负权回路。
    for (int i = 0; i < n; i ++ )
    {
        for (int j = 0; j < m; j ++ )
        {
            int a = edges[j].a, b = edges[j].b, w = edges[j].w;
           /*
            if (dist[b] > dist[a] + w)
                dist[b] = dist[a] + w;
            */
            //松弛操作
            dist[b] = min(dist[b],dist[a]+w)
        }
    }

    if (dist[n] > 0x3f3f3f3f / 2) return -1;
    return dist[n];
}



20220124142822

SPFA

一般o(m),最坏o(mn)
没有负环就可以用
99%的题目都可以用
都是正边有时也能用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
int n;      // 总点数
int h[N], w[N], e[N], ne[N], idx;       // 邻接表存储所有边
int dist[N];        // 存储每个点到1号点的最短距离
bool st[N];     // 存储每个点是否在队列中

// 求1号点到n号点的最短路距离，如果从1号点无法走到n号点则返回-1
int spfa()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    queue<int> q;
    q.push(1);
    st[1] = true;

    while (q.size())
    {
        auto t = q.front();
        q.pop();

        st[t] = false;

        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                if (!st[j])     // 如果队列中已存在j，则不需要将j重复插入
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }

    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}


判断是否存在负环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
int n;      // 总点数
int h[N], w[N], e[N], ne[N], idx;       // 邻接表存储所有边
int dist[N], cnt[N];        // dist[x]存储1号点到x的最短距离，cnt[x]存储1到x的最短路中经过的点数
bool st[N];     // 存储每个点是否在队列中

// 如果存在负环，则返回true，否则返回false。
bool spfa()
{
    // 不需要初始化dist数组
    // 原理：如果某条最短路径上有n个点（除了自己），那么加上自己之后一共有n+1个点，由抽屉原理一定有两个点相同，所以存在环。

    queue<int> q;
    for (int i = 1; i <= n; i ++ )
    {
        q.push(i);
        st[i] = true;
    }

    while (q.size())
    {
        auto t = q.front();
        q.pop();

        st[t] = false;

        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                cnt[j] = cnt[t] + 1;
                if (cnt[j] >= n) return true;       // 如果从1号点到x的最短路中包含至少n个点（不包括自己），则说明存在环
                if (!st[j])
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }

    return false;
}


多源（起点）汇最短路

起点终点都不确定
n很小，m很大

Floyd算法

o(n^3)

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

初始化：
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ )
            if (i == j) d[i][j] = 0;
            else d[i][j] = INF;

// 算法结束后，d[a][b]表示a到b的最短距离
void floyd()
{
    for (int k = 1; k <= n; k ++ )
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= n; j ++ )
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}



20220124164427

发表于 分类于
本文字数： 2.2k 阅读时长 ≈ 2 分钟

树

是一种特殊的图

图

无向图

特殊的有向图

有向图的存储

邻接矩阵

二维数组
g[a][b] 表示a->b

邻接表（用的最多）

单链表
每一个点都是一个单链表
存储的是每个点可以到达哪些点

对于每一个节点，都开一个单链表（类似拉链法）存储该节点可以访问到的点，存储次序无关紧要。

20220115195751

插入边：

20220115195807

插入操作：

不带权值

1
2
3
4
5
6
7
8
9
10
//邻接表
int h[N], e[M], ne[M], idx;// M = 2 * N

//插入边a ---> b
void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}


带权值：

1
2
3
4
5
6
7
int h[N], w[N], e[N], ne[N], idx;

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

1
2
3
4
5
6
7
8
9
10
11
12
// 对于每个点k，开一个单链表，存储k所有可以走到的点。h[k]存储这个单链表的头结点
int h[N], e[N], ne[N], idx;

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

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

遍历方式

深度优先搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
bool st[N];//true表示已经用过

int dfs(int u)
{
    st[u] = true; // st[u] 表示点u已经被遍历过

    //遍历u的邻接点
    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];//拿到出边的对应的节点编号
        if (!st[j]) dfs(j);//如果没有被访问过，继续递归深搜
    }
}

树的重心：

20220115200244

20220115191737

宽度优先搜索

图宽搜的框架和前面BFS的框架基本一模一样，只是将图的结构扩展到宽搜框架里。前面的BFS是根据具体题目来扩展点，图的话采用邻接表存储图，从1号节点编号开始，扩展的是每一个点的临边。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

1. queue <---- 1号点

2. while(队列不为空)
 { 	
    
	t <---队头
	弹出队头

   	扩展队头元素（扩展t的所有邻接点j）
   	{
        获取邻接点（编号）j
   		if(j未遍历，符合条件)// 第一次遍历才是最短路径
   		{
   			queue  <----- j入队// （邻接节点）
   			更新距离 //d[x] = d[t]++
   		 }
   	}

}

3. 最后队为空，结束

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
queue<int> q;
st[1] = true; // 表示1号点已经被遍历过
q.push(1);

while (q.size())
{
    int t = q.front();
    q.pop();

    for (int i = h[t]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!st[j])
        {
            st[j] = true; // 表示点j已经被遍历过
            q.push(j);
        }
    }
}

拓扑排序

有向图
不存在环 即 有向无环图
宽搜

拓扑序列：在一个有向图无环中，对所有的节点进行排序，要求没有一个节点指向它前面的节点。即，所有的边从前指向后！

重要结论性质：一个有向无环图至少存在一个入度为0的节点！

求解步骤：

（1）先统计好图中所有点的入度情况

（2）找到图中入度为0的节点，将它删去，由它发射出来的所有边也要删掉，即它指向的邻接节点度数-1

（3）将删去节点后剩下的图，继续按（2）的规则继续删节点。

按照节点被删除的顺序，依次把这些被删除的节点记录要一个序列里边，当图中所有节点被删除后，那么这个序列就是一个拓扑序列了！

20220115200539

注：当同时出现两个或以上入度为0的节点时，拓扑序列结果不唯一！

20220115200558

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
bool topsort()
{
	1. queue <---- 所有度为0的点

	2. while queue不为空
	{
		t <---- 队头
		弹出队头
			
		枚举t所有的出边 t ---> j
		{
			删掉出边 t ---> j: d[j] --;// 入度-1
			
			if(d[j] == 0)// 当节点j入度为0时，入队 
			queue <---- j
		}
	}
    
    如果有n - 1个节点入队的话，说明是拓扑序列返回true，否则不是返回false
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

bool topsort()
{
    int hh = 0, tt = -1;

    // d[i] 存储点i的入度
    for (int i = 1; i <= n; i ++ )
        if (!d[i])
            q[ ++ tt] = i;

    while (hh <= tt)
    {
        int t = q[hh ++ ];

        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (-- d[j] == 0)
                q[ ++ tt] = j;
        }
    }

    // 如果所有点都入队了，说明存在拓扑序列；否则不存在拓扑序列。
    return tt == n - 1;
}


发表于 更新于 分类于
本文字数： 1.8k 阅读时长 ≈ 2 分钟

DFS深度优先搜索

栈实现
空间o(h)
不具有最短路性质
演示图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Void DFS（deep，...）{
  if(找到解 || 走不下去了){
   ......//根据题意添加
    return; 
  }

  //for循环遍历每一种情况，例如：每一列都可能出现；1，2，3，4···每一个数字都可能出现
  //对这些可能出现的进行for循环遍历
  for(扩展方式){
   if(扩展方式所能达到的状态合法){
      修改操作；//根据题意添加
      标记；
      DFS(deep+1,...);
      //根据题意是否要还原
    }  
  }
 
}

例题

排列组合

20220115153422

八皇后

n-皇后

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <iostream>

using namespace std;

const int N = 20;

int n;
char g[N][N];
bool col[N],dg[N],udg[N];//记录是否用过,列，正反对角线

inline void dfs(int u) 
{

    if(u==n)
    {
        for(int i=0;i<n;i++) puts(g[i]);
            puts("");
            return;
    }
    for(int i=0;i<n;i++)//遍历该层的每一种情况，一共n列 n种情况
        if(!col[i] && !dg[u+i] && !udg[n-u+i])
        {
            g[u][i]='Q';
            
            col[i]=dg[u+i]=udg[n-u+i]=true;
            dfs(u+1);
            col[i]=dg[u+i]=udg[n-u+i]=false;//恢复现场
            g[u][i]='.';
        }
        

}

int main()
{
    cin >> n;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            g[i][j]='.';
    dfs(0);


    return 0;
}

BFS深度优先搜索

队列实现
空间o(2^h)
最短路

演示图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void BFS(){
  初始化队列Q;
  起点S入队;
  标记S已经访问;
  while(Q非空){
    取Q的队首元素U;
    U出队列;
    if(u==目标状态){
      返回结果；
     }
    for(所有与U相邻的元素){
      if(相邻的元素合法 && 未访问){
         入队;
         标记访问;
        }
    }
  }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
typedef pair<int, int> PII;
queue<PII> q;

const int N = 110;
int g[N][N];
int d[N][N]; //存放各个点到起点的距离（最短）

int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

int n, m;

int bfs()
{
    memset(d, -1, sizeof d);//初始距离全部设置为-1 表示该点未被访问过（记录距离的同时，起到了st数组的作用）
    q.push({0, 0});
    d[0][0] = 0;
    
    while(q.size())
    {
        auto t = q.front();
        q.pop();
        
        for(int i = 0; i < 4; i ++)
        {
            int a = t.first + dx[i], b = t.second + dy[i];
            if(a < 0 || a >= n || b < 0 || b >= m) continue;//越界
            if(g[a][b]) continue;//撞墙
            if(d[a][b] != -1) continue;//该点被访问过
            
            q.push({a, b});
            d[a][b] = d[t.first][t.second] + 1;//更新距离
            
        }
    }
    
    //返回到终点的最短距离
    return d[n - 1][m - 1];
}

发表于 分类于
本文字数： 2.9k 阅读时长 ≈ 3 分钟

#include
vector a
vector 变长数组，倍增思想
size()
empty()
clear()
front()/back()
push_back()/pop_back()
begin()/end()
[]
支持比较运算，按字典序

pair<int, int>

first 第一个元素
second 第二个元素
支持比较运算,以first为第一关键字，second第二关键字(字典序)

#include
string 字符串

substr(起始下标, 长度) 返回子串
size()/length() 返回字符串长度
c_str() 返回字符串的首地址
empty()
clear()
to_string(x)

#include
queue 队列 

size()
empty()
push() 向队尾插入一个
front() 返回队头
back() 返回队尾
pop() 弹出队头

#include
priority_queue 优先队列（堆）默认大根堆 

push() 插入一个元素
top() 返回堆顶
pop() 弹出堆顶

定义成小根堆方式：
priority_queue<int , vector<int>,greater<int>> heap;//创建小根堆
priority_queue<int> heap
heap.push(-x)//创建小根堆

#include
stack 栈

size() 栈的大小/长度
empty() 是否为空
push() 向栈顶插入一个元素
top() 返回栈顶元素
pop() 弹出栈顶元素

#include
deque 双端队列，队头队尾都可以插入删除

size()
empty()
clear()
front()
back()
push_back()/pop_back()
push_front()/pop_front()
begin()/end()
[]
很少用，速度太慢了

set,map,multiset,multimap 基于平衡二叉树（红黑树），动态维护有序序列

size()
empty()
clear()
begin()/end() ++ -- 返回前驱后继  O(logn)


set/multiset
    insert() 插入一个数
    find() 查找一个数
    count() 返回某个数的个数
    erase()
        输入是一个数x，删除所有x  O(k+log n)
        输入一个迭代器，删除这个迭代器
    lower_bound()/upper_bound()
        lower_bound(x) 返回大于等于x的最小的数
        upper_bound(x) 返回大于x的最小的数

map/multimap
    insert() 插入的数是一个pair
    erase() 输入的参数是pair或者迭代器
    find()
    []  像数组一样使用 O(logn)
    lower_bound()/upper_bound()

unordered_set,unordered_map,unordered_multiset,unordered_multimap，哈希表

和上面类似，增删改查的时间复杂度是O(1)
不支持lower_bound()/upper_bound() 因为内部是无序的
不支持迭代器的++ --

bitset，压位
用于存储bool量
bitset<10000> S;
~s,&,|,^
>>,<<
==,!=
[]
count() 返回有多少个1

any() 判断是否至少有一个1
none() 判断全为0

set() 把所有位置变为1
set(k,v) 将第K位变成V
reset() 把所有位变为0
flip() 等价于~
flip() 把第K位取反

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main()
{
    vector<int> a;//定义一个vector
    vector<int> a(10);//定义长度为10的vector
    vector<int> a(10,3);//定义长度为10的vector，并初始化值为3
    a.size();//返回元素个数---所有容器都有
    a.empty();//判断是否为空---所有容器都有
    a.clear();//清空---队列没有这个函数


    a.front();//返回第一个数
    a.back();//返回最后一个数
    a.push_back();//向最后插入一个数
    a.pop_back();//删掉最后一个元素

    a.begin()//第一个数
    a.end()//最后一个数的后面一个
    for(vector<int>::iterator i=a.begin() ; i!=a.end(); i++)
    {
        cout<< *i <<" ";
    }

    //支持比较运算





    //常用于存不同属性，按照某一种属性进行排序
    pair<int, string> p;
     pair<int, pair<int, string>> p;//存3个
    p.first ,第一个元素
    p.second，第二个元素
    支持比较运算，以first为第一关键字，second第二关键字
    p = make_pair(10,"xiaoming")
    p ={20,"xiaohong"}





//----
    string a="aaa";
    a=a+"bbb";
    a+="c";

    size()/length()
    cout<< a.substr(1,2)<<endl;//从下标1开始返回两个
    a.substr(1)//从下标1开始的一个子串

    printf("%s\s",a.c_str());//字符串a的起始地址
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

#include <set>

#include <map>
using namespace std;

int main()
{

    set<int> S;//不允许重复元素
    multiset<int> MS;//允许重复元素
    return 0;


    map<string,int> m;
    m["aaa"]=1;
    cout<<a["aaa"]<<endl;

}

发表于 更新于 分类于
本文字数： 929 阅读时长 ≈ 1 分钟

哈希表

哈希函数，把一个大的范围，映射为一个小的范围
离散化是一种特殊的哈希方式
用于对数据的快速插入和读取

存储结构（处理冲突）

拉链法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int h[N], e[N], ne[N], idx;

// 向哈希表中插入一个数
void insert(int x)
{
    int k = (x % N + N) % N;//保证余数是正数
    e[idx] = x;
    ne[idx] = h[k];
    h[k] = idx ++ ;
}

// 在哈希表中查询某个数是否存在
bool find(int x)
{
    int k = (x % N + N) % N;
    for (int i = h[k]; i != -1; i = ne[i])
        if (e[i] == x)
            return true;

    return false;
}


20220113161351
20220113161312

开放寻址法（常用）

开数组时要大2~3倍

1
2
3
4
5
6
7
8
9
10
11
12
13
int h[N];

// 如果x在哈希表中，返回x的下标；如果x不在哈希表中，返回x应该插入的位置
int find(int x)
{
    int t = (x % N + N) % N;
    while (h[t] != null && h[t] != x)//坑位有人，并且不是x
    {
        t ++ ;//向后找
        if (t == N) t = 0;//到最后，t=0，从头开始循环
    }
    return t;
}

开放寻址法

字符串哈希

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
核心思想：将字符串看成P进制数，P的经验值是131或13331，取这两个值的冲突概率低
小技巧：取模的数用2^64，这样直接用unsigned long long存储，溢出的结果就是取模的结果

typedef unsigned long long ULL;
ULL h[N], p[N]; // h[k]存储字符串前k个字母的哈希值, p[k]存储 P^k mod 2^64

// 初始化
p[0] = 1;
for (int i = 1; i <= n; i ++ )
{
    h[i] = h[i - 1] * P + str[i];
    p[i] = p[i - 1] * P;
}

// 计算子串 str[l ~ r] 的哈希值
ULL get(int l, int r)
{
    return h[r] - h[l - 1] * p[r - l + 1];
}


20220113172122

发表于 分类于
本文字数： 674 阅读时长 ≈ 1 分钟

堆

完全二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
// 下标从1开始
// h[N]存储堆中的值, h[1]是堆顶，x的左儿子是2x, 右儿子是2x + 1
// ph[k]存储第k个插入的点在堆中的位置（下标）
// hp[k]存储堆中下标是k的点是第几个插入的
int h[N], ph[N], hp[N], size;

// 交换两个点，及其映射关系
void heap_swap(int a, int b)
{
    swap(ph[hp[a]],ph[hp[b]]);
    swap(hp[a], hp[b]);
    swap(h[a], h[b]);
}

void down(int u)
{
    int t = u;
    //左儿子小，t等于左儿子
    if (u * 2 <= size && h[u * 2] < h[t]) t = u * 2;
    //右儿子小，t等于右儿子
    if (u * 2 + 1 <= size && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
    //说明根节点不是最小的
    if (u != t)
    {
        //把根节点和最小的进行交换
        heap_swap(u, t);
        down(t);
    }
}

void up(int u)
{
    while (u / 2 && h[u] < h[u / 2])
    {
        heap_swap(u, u / 2);
        u >>= 1;
    }
}

// O(n)建堆
for (int i = n / 2; i; i -- ) down(i);


20220112192917

发表于 分类于
本文字数： 3.6k 阅读时长 ≈ 3 分钟

并查集

将两个集合合并–》例如连通分支合并一个

询问两个元素是否在一个集合当中

近乎O（1）

简单理解（转载）

为了解释并查集的原理，我将举一个更有爱的例子。 话说江湖上散落着各式各样的大侠，有上千个之多。他们没有什么正当职业，整天背着剑在外面走来走去，碰到和自己不是一路人的，就免不了要打一架。但大侠们有一个优点就是讲义气，绝对不打自己的朋友。而且他们信奉“朋友的朋友就是我的朋友”，只要是能通过朋友关系串联起来的，不管拐了多少个弯，都认为是自己人。这样一来，江湖上就形成了一个一个的群落，通过两两之间的朋友关系串联起来。而不在同一个群落的人，无论如何都无法通过朋友关系连起来，于是就可以放心往死了打。但是两个原本互不相识的人，如何判断是否属于一个朋友圈呢？

我们可以在每个朋友圈内推举出一个比较有名望的人，作为该圈子的代表人物，这样，每个圈子就可以这样命名“齐达内朋友之队”“罗纳尔多朋友之队”……两人只要互相对一下自己的队长是不是同一个人，就可以确定敌友关系了。

但是还有问题啊，大侠们只知道自己直接的朋友是谁，很多人压根就不认识队长，要判断自己的队长是谁，只能漫无目的的通过朋友的朋友关系问下去：“你是不是队长？你是不是队长？”这样一来，队长面子上挂不住了，而且效率太低，还有可能陷入无限循环中。于是队长下令，重新组队。队内所有人实行分等级制度，形成树状结构，我队长就是根节点，下面分别是二级队员、三级队员。每个人只要记住自己的上级是谁就行了。遇到判断敌友的时候，只要一层层向上问，直到最高层，就可以在短时间内确定队长是谁了。由于我们关心的只是两个人之间是否连通，至于他们是如何连通的，以及每个圈子内部的结构是怎样的，甚至队长是谁，并不重要。所以我们可以放任队长随意重新组队，只要不搞错敌友关系就好了。于是，门派产生了。

20210803124721

下面我们来看并查集的实现。 int pre[1000]; 这个数组，记录了每个大侠的上级是谁。大侠们从1或者0开始编号（依据题意而定），pre[15]=3就表示15号大侠的上级是3号大侠。如果一个人的上级就是他自己，那说明他就是掌门人了，查找到此为止。也有孤家寡人自成一派的，比如欧阳锋，那么他的上级就是他自己。每个人都只认自己的上级。比如胡青牛同学只知道自己的上级是杨左使。张无忌是谁？不认识！要想知道自己的掌门是谁，只能一级级查上去。 find这个函数就是找掌门用的，意义再清楚不过了（路径压缩算法先不论，后面再说）。

1
2
3
4
5
6
7
int find(int x)                    //查找我（x）的掌门
{
    int r=x;                      //委托 r 去找掌门
    while (pre[r]!=r)           //如果r的上级不是r自己（也就是说找到的大侠他不是掌门 = =）
    r=pre[r] ;                 // r 就接着找他的上级，直到找到掌门为止。
    return r;                //掌门驾到~~~
}

再来看看路径压缩算法。建立门派的过程是用join函数两个人两个人地连接起来的，谁当谁的手下完全随机。最后的树状结构会变成什么胎唇样，我也完全无法预计，一字长蛇阵也有可能。这样查找的效率就会比较低下。最理想的情况就是所有人的直接上级都是掌门，一共就两级结构，只要找一次就找到掌门了。哪怕不能完全做到，也最好尽量接近。这样就产生了路径压缩算法。 设想这样一个场景：两个互不相识的大侠碰面了，想知道能不能揍。 于是赶紧打电话问自己的上级：“你是不是掌门？” 上级说：“我不是呀，我的上级是谁谁谁，你问问他看看。” 一路问下去，原来两人的最终boss都是东厂曹公公。 “哎呀呀，原来是记己人，西礼西礼，在下三营六组白面葫芦娃!” “幸会幸会，在下九营十八组仙子狗尾巴花！” 两人高高兴兴地手拉手喝酒去了。 “等等等等，两位同学请留步，还有事情没完成呢！”我叫住他俩。 “哦，对了，还要做路径压缩。”两人醒悟。 白面葫芦娃打电话给他的上级六组长：“组长啊，我查过了，其习偶们的掌门是曹公公。不如偶们一起及接拜在曹公公手下吧，省得级别太低，以后查找掌门麻环。” “唔，有道理。” 白面葫芦娃接着打电话给刚才拜访过的三营长……仙子狗尾巴花也做了同样的事情。 这样，查询中所有涉及到的人物都聚集在曹公公的直接领导下。每次查询都做了优化处理，所以整个门派树的层数都会维持在比较低的水平上。路径压缩的代码，看得懂很好，看不懂也没关系，直接抄上用就行了。总之它所实现的功能就是这么个意思。

20210803124845

acwing模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
原模板:

int find (int x)
{
    if(x != p[x]) p[x] = find(p[x]);
    return p[x];
}
可以把y总的模板拆分一下，会方便理解些

int find (int x)
{
    if(x != p[x])
    {
        int t = find(p[x]); //寻找根结点，找到后回溯
        p[x] = t; //路径压缩
    }
    return p[x];
}


 p[find(a)]=find(b);//集合合并操作
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

#include<iostream>

using namespace std;

const int N=100010;
int p[N];//定义多个集合

int find(int x)
{
    if(p[x]!=x) p[x]=find(p[x]);
    /*
    经上述可以发现,每个集合中只有祖宗节点的p[x]值等于他自己,即:
    p[x]=x;
    */
    return p[x];
    //找到了便返回祖宗节点的值
}

int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) p[i]=i;
    while(m--)
    {
        char op[2];
        int a,b;
        scanf("%s%d%d",op,&a,&b);
        if(*op=='M') p[find(a)]=find(b);//集合合并操作
        else
        if(find(a)==find(b))
        //如果祖宗节点一样,就输出yes
        printf("Yes\n");
        else
        printf("No\n");
    }
    return 0;
}

20220112173034

ACWING模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
(1)朴素并查集：

    int p[N]; //存储每个点的祖宗节点

    // 返回x的祖宗节点
    int find(int x)
    {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }

    // 初始化，假定节点编号是1~n
    for (int i = 1; i <= n; i ++ ) p[i] = i;

    // 合并a和b所在的两个集合：
    p[find(a)] = find(b);


(2)维护size的并查集：

    int p[N], size[N];
    //p[]存储每个点的祖宗节点, size[]只有祖宗节点的有意义，表示祖宗节点所在集合中的点的数量

    // 返回x的祖宗节点
    int find(int x)
    {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }

    // 初始化，假定节点编号是1~n
    for (int i = 1; i <= n; i ++ )
    {
        p[i] = i;
        size[i] = 1;
    }

    // 合并a和b所在的两个集合：
    size[find(b)] += size[find(a)];
    p[find(a)] = find(b);


(3)维护到祖宗节点距离的并查集：

    int p[N], d[N];
    //p[]存储每个点的祖宗节点, d[x]存储x到p[x]的距离

    // 返回x的祖宗节点
    int find(int x)
    {
        if (p[x] != x)
        {
            int u = find(p[x]);
            d[x] += d[p[x]];
            p[x] = u;
        }
        return p[x];
    }

    // 初始化，假定节点编号是1~n
    for (int i = 1; i <= n; i ++ )
    {
        p[i] = i;
        d[i] = 0;
    }

    // 合并a和b所在的两个集合：
    p[find(a)] = find(b);
    d[find(a)] = distance; // 根据具体问题，初始化find(a)的偏移量



发表于 分类于
本文字数： 506 阅读时长 ≈ 1 分钟

trie树（前缀树）

高效快速的存储和查找字符串集合的数据结构

20220112144921

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
int son[N][26], cnt[N], idx;
// 0号点既是根节点，又是空节点
// son[][]存储树中每个节点的子节点
// cnt[]存储以每个节点结尾的单词数量

// 插入一个字符串
void insert(char *str)
{
    int p = 0;
    for (int i = 0; str[i]; i ++ )
    {
        int u = str[i] - 'a';//把字母a-z映射为0-25
        if (!son[p][u]) son[p][u] = ++ idx;//不存在子节点
        p = son[p][u];
    }
    cnt[p] ++ ;
}

// 查询字符串出现的次数
int query(char *str)
{
    int p = 0;
    for (int i = 0; str[i]; i ++ )
    {
        int u = str[i] - 'a';
        if (!son[p][u]) return 0;
        p = son[p][u];
    }
    return cnt[p];
}