5.并查集

并查集是一種樹型的數(shù)據(jù)結(jié)構(gòu)，用于處理一些不相交集合的合并及查詢問題。

1. 將兩個(gè)集合合并

2. 詢問兩個(gè)元素是否在一個(gè)集合當(dāng)中。

基本原理：每隔幾何用一棵樹來表示，樹根的編號(hào)就是一整個(gè)集合的編號(hào)。每個(gè)節(jié)點(diǎn)存儲(chǔ)它的父節(jié)點(diǎn)，p[x]表示x的父節(jié)點(diǎn)。

問題1：如何判斷樹根：if(p[x] == x);

問題2：如何求x的集合編號(hào)：while(p[x] != x) x = p[x];

問題3：如何合并兩個(gè)集合：px是x的集合編號(hào)，py是y的集合編號(hào)。p[x] = y

基本上來說是O(1)的時(shí)間復(fù)雜度

合并集合：

一共有n個(gè)數(shù)，編號(hào)是1~n，最開始每個(gè)數(shù)各自在一個(gè)集合中。

現(xiàn)在要進(jìn)行m個(gè)操作，操作一共有兩種

1. 將編號(hào)為a，b的兩個(gè)數(shù)所在集合進(jìn)行合并，如果兩個(gè)數(shù)已經(jīng)在集合中，即忽略這個(gè)操作

2. 詢問編號(hào)為a，b的兩個(gè)數(shù)是否在同一個(gè)集合中

#include<iostream>
using namespace std;
?
const int N = 1e5 + 10;
?
int n, m;
int p[N];
?
int find(int x)//返回x的祖宗結(jié)點(diǎn)+路徑壓縮
{
 ? ?if(p[x] != x) p[x] = find(p[x]);
 ? ?return p[x];
}
?
void merge(int a, int b)
{
 ? ?p[find(a)] = find(b);
}
?
int main()
{
 ? ?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[0] == 'M')
 ? ? ? ? ? ?merge(a, b);
 ? ? ? ?else
 ? ? ?  {
 ? ? ? ? ? ?if(find(a) == find(b))
 ? ? ? ? ? ? ? ?printf("Yes\n");
 ? ? ? ? ? ?else
 ? ? ? ? ? ? ? ?printf("No\n");
 ? ? ?  }
 ?  }
 ? ?
 ? ?return 0;
}

近乎O(1)的時(shí)間

連通塊中點(diǎn)的數(shù)量：

給定一個(gè)包含n個(gè)點(diǎn)（編號(hào)為1~n）的無向圖，初始時(shí)圖中沒有邊。

現(xiàn)在要進(jìn)行m個(gè)操作，操作一共有三個(gè)：

1. “Cab”，在點(diǎn)a和點(diǎn)b之間連一條邊，a和b可能相等

2. “Q1ab”，詢問點(diǎn)a和點(diǎn)b是否在同一連通塊內(nèi)，a和b可能相等

3. “Q2ab”，詢問點(diǎn)a所在的聯(lián)通快中點(diǎn)的個(gè)數(shù)。

#include<iostream>
using namespace std;
?
const int N = 1e5 + 10;
?
int n, m;
int p[N], size[N];
?
int find(int x)
{
 ? ?if(p[x] != x) p[x] = find(p[x]);
 ? ?return p[x];
}
?
void merge(int a, int b)
{
 ? ?p[find(a)] = find(b);
}
?
int main()
{
 ? ?scanf("%d%d", &n, &m);
 ? ?
 ? ?for(int i = 1;i <= n; i++)
 ?  {
 ? ? ? ?p[i] = i;
 ? ? ? ?size[i] = 1;
 ?  }
 ? ?
 ? ?while(m--)
 ?  {
 ? ? ? ?char op[5];
 ? ? ? ?int a, b;
 ? ? ? ?
 ? ? ? ?scanf("%s", op);
 ? ? ? ?
 ? ? ? ?if(op[0] == 'C')
 ? ? ?  {
 ? ? ? ? ? ?scanf("%d%d", &a, &b);
 ? ? ? ? ? ?if(find(a) == find(b)) continue;
 ? ? ? ? ? ?size[find(b)] += size[find(a)];
 ? ? ? ? ? ?merge(a, b);
 ? ? ?  }
 ? ? ? ?else if(op[1] == '1')
 ? ? ?  {
 ? ? ? ? ? ?scanf("%d%d", &a, &b);
 ? ? ? ? ? ?if(find(a) == find(b))
 ? ? ? ? ? ? ? ?printf("Yes\n");
 ? ? ? ? ? ?else
 ? ? ? ? ? ? ? ?printf("No\n");
 ? ? ?  }
 ? ? ? ?else
 ? ? ?  {
 ? ? ? ? ? ?scanf("%d", &a);
 ? ? ? ? ? ?printf("%d\n", size[find(a)]);
 ? ? ?  }
 ? ? ? ?
 ?  }
 ? ?return 0;
}

食物鏈

動(dòng)物王國中有三類動(dòng)物A,B,C，這三類動(dòng)物的食物鏈構(gòu)成了有趣的環(huán)形。

A吃B， B吃C，C吃A。

現(xiàn)有N個(gè)動(dòng)物，以1－N編號(hào)。

每個(gè)動(dòng)物都是A,B,C中的一種，但是我們并不知道它到底是哪一種。

有人用兩種說法對這N個(gè)動(dòng)物所構(gòu)成的食物鏈關(guān)系進(jìn)行描述：

第一種說法是”1 X Y”，表示X和Y是同類。

第二種說法是”2 X Y”，表示X吃Y。

此人對N個(gè)動(dòng)物，用上述兩種說法，一句接一句地說出K句話，這K句話有的是真的，有的是假的。

當(dāng)一句話滿足下列三條之一時(shí)，這句話就是假話，否則就是真話。

1） 當(dāng)前的話與前面的某些真的話沖突，就是假話； 2） 當(dāng)前的話中X或Y比N大，就是假話； 3） 當(dāng)前的話表示X吃X，就是假話。

你的任務(wù)是根據(jù)給定的N和K句話，輸出假話的總數(shù)。

#include<iostream>
using namespace std;
?
int main()
{
 ? ?return 0;
}

6.堆

如何手寫一個(gè)堆？

堆是維護(hù)數(shù)與集合。

堆是一種數(shù)據(jù)結(jié)構(gòu)，它滿足以下兩個(gè)條件：

1. 完全二叉樹：堆的總是一棵完全二叉樹，即除了最后一層外，其他層都是滿的，并且最后一層的節(jié)點(diǎn)都集中在左側(cè)。

2. 堆性質(zhì)：對于每個(gè)節(jié)點(diǎn)X，其父節(jié)點(diǎn)的值小于等于（或大于等于，稱為最小堆）其子節(jié)點(diǎn)的值。

堆通常用于實(shí)現(xiàn)優(yōu)先隊(duì)列，其中每個(gè)節(jié)點(diǎn)代表一個(gè)事件或任務(wù)，節(jié)點(diǎn)的值表示任務(wù)的優(yōu)先級(jí)。通過將任務(wù)按照優(yōu)先級(jí)從上到下放置在堆中，可以保證優(yōu)先級(jí)最高的任務(wù)總是最先被執(zhí)行。

在實(shí)現(xiàn)上，堆可以使用數(shù)組來表示。對于一個(gè)節(jié)點(diǎn)X，其父節(jié)點(diǎn)和子節(jié)點(diǎn)的位置可以通過簡單的數(shù)學(xué)計(jì)算來確定。例如，對于一個(gè)最小堆，節(jié)點(diǎn)X的父節(jié)點(diǎn)和左子節(jié)點(diǎn)的位置可以通過以下公式計(jì)算：

• 父節(jié)點(diǎn)位置：parent(X) = (X-1)/2

• 左子節(jié)點(diǎn)位置：left_child(X) = 2*X + 1

堆也可以用來實(shí)現(xiàn)優(yōu)先級(jí)調(diào)度、任務(wù)調(diào)度等應(yīng)用。

1. 插入一個(gè)數(shù) heap[++size] = x; up(size);

2. 求集合當(dāng)中的最小值 heap[1];

3. 刪除最小值 用最后一個(gè)元素覆蓋根節(jié)點(diǎn) heap[1] = heap[size];size--;down(1);

4. 刪除任意元素 heap[k] = heap[size];size--;

5. 修改任意元素 heap[k] = x; down(k); up(k);

838.堆排序：

輸入一個(gè)長度為n的整數(shù)數(shù)列，從小到大輸出前m小的數(shù)。

輸入格式：第一行包含整數(shù)n和m，第二行包含n個(gè)整數(shù)，表示整數(shù)數(shù)列。

輸出格式：共一行，包含m個(gè)整數(shù)，表示整數(shù)數(shù)列中前m小的數(shù)。

5 3 \n 4 5 1 3 2

1 2 3

代碼：

#include<iostream>
#include<algorithm>
?
using namespace std;
?
const int N = 1e5 + 10;
?
int n, m;
int h[N], size;
?
void down(int u)
{
 ? ?int t = u;
 ? ?if(u * 2 <= size && h[u * 2] < h[t]) t = u * 2;
 ? ?if(u * 2 + 1 <= size && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
 ? ?if(u != t)
 ?  {
 ? ? ? ?swap(h[u], h[t]);
 ? ? ? ?down(t);
 ?  }
}
?
int main()
{
 ? ?scanf("%d%d", &n, &m);
 ? ?for(int i = 1;i <= n; i++)
 ? ? ? ?scanf("%d", &h[i]);
 ? ?size = n;
 ? ?
 ? ?for(int i = n / 2; i; i--)
 ?      down(i);
 ? ?
 ? ?while(m--)
 ?  {
 ? ? ? ?printf("%d ", h[1]);
 ? ? ? ?h[1] = h[size];
 ? ? ? ?size--;
 ? ? ? ?down(1);
 ?  }
 ? ?
 ? ?return 0;
}

839.模擬堆：

維護(hù)一個(gè)集合，初始時(shí)集合為空，支持如下幾種操作：

1. "lx"，插入一個(gè)數(shù)x；

2. “PM”，輸出當(dāng)前集合中的最小值；

3. “DM”，刪除當(dāng)前集合的最小值（當(dāng)最小值不唯一時(shí)，刪除最早插入的最小值）；

4. “Dk”，刪除第k個(gè)插入的數(shù)；

5. “Ckx”，修改第k個(gè)插入的數(shù)，將其變?yōu)閤；

現(xiàn)在要進(jìn)行N次操作。對于所有第2個(gè)操作，輸出當(dāng)前集合的是小值。

#include<iostream>
#include<algorithm>
#include<string.h>
?
using namespace std;
?
const int N = 1e5 + 10;
?
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;
 ? ?if(u * 2 <= size && h[u * 2] < h[t]) t = u * 2;
 ? ?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 / 2] > h[u])
 ?  {
 ? ? ? ?heap_swap(u / 2, u);
 ? ? ? ?u /= 2;
 ?  }
}
?
int main()
{
 ? ?int n, m = 0;
 ? ?scanf("%d", &n);
 ? ?
 ? ?while(n--)
 ?  {
 ? ? ? ?char op[10];
 ? ? ? ?int k, x;
 ? ? ? ?
 ? ? ? ?scanf("%s", op);
 ? ? ? ?if(!strcmp(op, "I"))
 ? ? ?  {
 ? ? ? ? ? ?scanf("%d", &x);
 ? ? ? ? ? ?size++;
 ? ? ? ? ? ?m++;
 ? ? ? ? ? ?ph[m] = size, hp[size] = m;
 ? ? ? ? ? ?h[size] = x;
 ? ? ? ? ? ?up(size);
 ? ? ?  }
 ? ? ? ?else if(!strcmp(op, "PM")) printf("%d\n", h[1]);
 ? ? ? ?else if(!strcmp(op, "DM"))
 ? ? ?  {
 ? ? ? ? ? ?heap_swap(1, size);
 ? ? ? ? ? ?size--;
 ? ? ? ? ? ?down(1);
 ? ? ?  }
 ? ? ? ?else if(!strcmp(op, "D"))
 ? ? ?  {
 ? ? ? ? ? ?scanf("%d", &k);
 ? ? ? ? ? ?k = ph[k];
 ? ? ? ? ? ?heap_swap(k, size);
 ? ? ? ? ? ?size--;
 ? ? ? ? ? ?down(k), up(k);
 ? ? ?  }
 ? ? ? ?else
 ? ? ?  {
 ? ? ? ? ? ?scanf("%d%d", &k, &x);
 ? ? ? ? ? ?k = ph[k];
 ? ? ? ? ? ?h[k] = x;
 ? ? ? ? ? ?down(k), up(k);
 ? ? ?  }
 ?  }
 ? ?
 ? ?return 0;
}

7.Hash表

哈希表是一種使用哈希函數(shù)組織數(shù)據(jù)，以支持快速插入和搜索的數(shù)據(jù)結(jié)構(gòu)。

哈希表可以用來實(shí)現(xiàn)動(dòng)態(tài)集合。它支持以下操作：

• 插入：將一個(gè)元素插入到哈希表中。

• 刪除：將一個(gè)元素從哈希表中刪除。

• 搜索：在哈希表中查找一個(gè)元素。

哈希表的實(shí)現(xiàn)基于哈希函數(shù)，它將鍵映射到存儲(chǔ)桶（bucket）中。每個(gè)存儲(chǔ)桶是一個(gè)鏈表，鏈表中的每個(gè)節(jié)點(diǎn)都包含一個(gè)鍵值對。當(dāng)插入一個(gè)元素時(shí)，哈希函數(shù)將鍵映射到一個(gè)存儲(chǔ)桶，然后將元素添加到該存儲(chǔ)桶的鏈表中。當(dāng)搜索一個(gè)元素時(shí)，哈希函數(shù)將鍵映射到相應(yīng)的存儲(chǔ)桶，然后在該存儲(chǔ)桶的鏈表中查找元素。

哈希表有多種實(shí)現(xiàn)方式，其中最常用的是開放地址法和相聯(lián)數(shù)組法。開放地址法在哈希表中使用一個(gè)數(shù)組來存儲(chǔ)存儲(chǔ)桶，當(dāng)發(fā)生哈希沖突時(shí)，它使用線性探測、二次探測、雙重散列等方法來找到空槽位。相聯(lián)數(shù)組法在哈希表中直接使用一個(gè)數(shù)組來存儲(chǔ)鍵值對，當(dāng)發(fā)生哈希沖突時(shí)，它將新元素添加到數(shù)組的末尾。

哈希表在計(jì)算機(jī)科學(xué)中廣泛應(yīng)用，例如在數(shù)據(jù)庫、操作系統(tǒng)、網(wǎng)絡(luò)通信等領(lǐng)域。它能夠提供常數(shù)級(jí)別的查找效率，比其他數(shù)據(jù)結(jié)構(gòu)更高效。

7.1哈希表的存儲(chǔ)結(jié)構(gòu)

1.開放尋址法 2.拉鏈法

840.模擬散列表

維護(hù)一個(gè)集合，支持如下幾種操作：

1. “l(fā)x”，插入一個(gè)數(shù)

2. “Qx”，詢問數(shù)x是否在集合中出現(xiàn)過

現(xiàn)在要進(jìn)行N次操作，對于每個(gè)詢問操作輸出對應(yīng)的結(jié)果

一般情況下，對哈希函數(shù)進(jìn)行取模，但是由于取模的原因，可能會(huì)有沖突，若干不同的數(shù)可能會(huì)映射在同一個(gè)位置。

開放尋址法：

#include<iostream>
#include<cstring>
?
using namespace std;
?
cosnt int N = 200003, null = 0x3f3f3f3f;
?
int h[N];
?
int find(int n)
{
 ? ?int t = (x % N + N) % N;
 ? ?
 ? ?while(h[t] != null && h[t] != x)
 ?  {
 ? ? ? ?t++;
 ? ? ? ?if(t == N)
 ? ? ? ? ? ?t = 0;
 ?  }
 ? ?
 ? ?return t;
}
?
int main()
{
 ? ?int n;
 ? ?scanf("%d", &n);
 ? ?merset(h, 0x3f, sizeof(h));
 ? ?
 ? ?while(n--)
 ?  {
 ? ? ? ?char op[2];
 ? ? ? ?int x;
 ? ? ? ?scanf("%s%d", op, &x);
 ? ? ? ?
 ? ? ? ?int k = find(x);
 ? ? ? ?if (op == 'I')
 ? ? ?  {
 ? ? ? ? ? ?h[k] = x;
 ? ? ?  }
 ? ? ? ?else
 ? ? ?  {
 ? ? ? ? ? ?if (h[k] != null) 
 ? ? ? ? ? ? ? ?puts("Yes");
 ? ? ? ? ? ?else
 ? ? ? ? ? ? ? ?puts("No");
 ? ? ?  }
 ?  }
 ? ?return 0;
}

拉鏈法：

#include<iostream>
#include<cstring>
?
using namespace std;
?
const int N = 100003;
?
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;
 ?      else
 ? ? ? ? ? ?return false;
}
?
int main()
{
 ? ?int n;
 ? ?scanf("%d", &n);
 ? ?
 ? ?memset(h, -1, sizeof(h));
 ? ?
 ? ?while(n--)
 ?  {
 ? ? ? ?char op[2];
 ? ? ? ?int x;
 ? ? ? ?scanf("%s%d", op, &x);
 ? ? ? ?
 ? ? ? ?if(op == "I") insert(x);
 ? ? ? ?else
 ? ? ?  {
 ? ? ? ? ? ?if(find(x)) puts("Yes");
 ? ? ? ? ? ?else puts("No");
 ? ? ?  }
 ?  }
 ? ?return 0;
}

7.2.字符串前綴哈希方法

str = "ABCDEFADCYUGHJJDFDGKHJK"

預(yù)處理：特殊h[0] = 0

h[1] = "A"的對應(yīng)的哈希值，后面的一樣 h[2] = "AB" h[3] = "ABC".....

1. 不能映射為0

2. Rp足夠好，不產(chǎn)生沖突

841.字符串哈希

給定個(gè)長度為的字符串，再給定m個(gè)詢問，每個(gè)詢問包含四個(gè)整數(shù)l1，r1，l2，r2，請你判斷[l1,r1]和[l2,r2]這兩個(gè)區(qū)間所包含的字符串子串是否完全相同。

字符串中只包含大小寫英文字母和數(shù)字。

#include<iostream>
using namespace std;
?
typedef unsigned long long ULL;
?
const int N = 100010;
?
int n, m;
char str[N];
ULL h[N], p[N];
?
ULL get(int l, int r)
{
 ? ?return h[r] - h[l - 1] * p[r - l + 1];
}
?
int main()
{
 ? ?scanf("%d%d%s", &n, &m, str + 1);
 ? ?
 ? ?p[0] = 1;
 ? ?for(int i = 1;i <= n; i++)
 ?  {
 ? ? ? ?p[i] = p[i-1] * p;
 ? ? ? ?h[i] = h[i-1] * p + str[i];
 ?  }
 ? ?
 ? ?while(m--)
 ?  {
 ? ? ? ?int l1, r1, l2, r2;
 ? ? ? ?scanf("%d%d%d%d",&l1, &r1, &l2, &r2);
 ? ? ? ?
 ? ? ? ?if(get(l1, r1) == get(l2, r2))
 ? ? ? ? ? ?puts("Yes");
 ? ? ? ?else
 ? ? ? ? ? ?puts("No");
 ?  }
 ? ?return 0;
}

8.C++STL使用技巧

vector：變長數(shù)組，倍增的思想

string：字符串，substr()，c_str()

queue：隊(duì)列，push(), front(), pop()

priority_queue：優(yōu)先隊(duì)列，push()， top()，pop()

stack：棧，push(), top(), pop()

deque：雙增隊(duì)列

set, map, multiset和multimap：基于平衡二叉樹，動(dòng)態(tài)維護(hù)有序序列

unorder_set、unorder_map、unorder_multiset、unorder_multimap：基于哈希表

bitset：壓位

list

#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
#include<cstdio>
?
using namespace std;
?
int main()
{
 ? ?vector<int> a(10, 3);
 ? ?//vector<int> a[10];
 ? ?a.size();//返回元素個(gè)數(shù)
 ? ?a.empty();//返回是否為空
 ? ?a.clear();//清空
 ? ?a.front();//返回第一個(gè)數(shù)
 ? ?a.back();//返回最后一個(gè)數(shù)
 ? ?a.push_back();//尾插
 ? ?a.pop_back();//尾部釋放
 ? ?a.begin()/a.end();//vector的迭代器
 ? ?
 ? ?for(int i = 0;i < 10; i++)
 ? ? ? ?a.push_back();
 ? ?
 ? ?for(int i = 0;i < a.size(); i++)
 ? ? ? ?cout << a[i] << ' ';
 ? ?cout << endl;
 ? ?
 ? ?for(vector<int>::iterator i = a.begin();i != a.end(); i++)
 ? ? ? ?cout << a[i] << ' ';
 ? ?cout << endl;
 ? ?
 ?  //支持比較運(yùn)算
 ? ?vector<int> a(4, 3), b(3, 4);
 ? ?if(a > b) cout << "a > b" << endl;
 ? ?
 ? ?return 0;
}

系統(tǒng)內(nèi)某一程序分配空間時(shí)，所需時(shí)間，與空間大小無關(guān)，與中間次數(shù)有關(guān)

pair<int, int>：存儲(chǔ)一個(gè)二元組

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<vector>
?
using namespace std;
?
int main()
{
 ? ?pair<int, string>p;
 ? ?
 ? ?p.first;
 ? ?p.second;
 ? ?//支持比較運(yùn)算
 ? ?//以first為第一關(guān)鍵詞，以second為第二關(guān)鍵詞
 ? ?
 ? ?p = make_pair(10, "yxc");
 ? ?p = {20, "abc"};
 ? ?
 ? ?pair<int, pair<int>>w;
 ? ?return 0;
}

string

#include<iostream>
#include<cstring>
#include<algorithm>
?
using namespace std;
?
int main()
{
 ? ?string a = "yxc";
 ? ?
 ? ?a += "def";
 ? ?a += "c";
 ? ?
 ? ?cout << a << endl;
 ? ?cout << a.substr(2, 3) << endl;
 ? ?
 ? ?return 0;
}

queue隊(duì)列

#include<iostream>
#include<queue>
#include<algorithm>
#include<vector>
?
using namespace std;
?
int main()
{
 ? ?queue<int> q;
 ? ?
 ? ?q = queue<int>;
 ? ?
 ? ?//優(yōu)先隊(duì)列
 ? ?priority_queue<int> heap;
 ? ?heap.clear();
 ? ?
 ? ?priority_queue<int, vector<int>, greater<int>> heap;//定義一個(gè)小根堆
 ? ?return 0;
}

stack棧

deque雙端隊(duì)列

size() empty() clear() front() back() push_front() pop_front() push_back pop_back() begin() end()

缺點(diǎn)就是deque比較慢

set

#include<iostream>
#include<vector>
#include<set>
#include<algorithm>
?
using namespace std;
?
int main()
{
 ? ?set<int> S;
 ? ?multiset<int> S1;//可以有重復(fù)元素，set不允許
 ? ?
 ? ?S.insert(1);//插入一個(gè)數(shù)
 ? ?S.find();//查找一個(gè)數(shù)
 ? ?S.count();//返回某一個(gè)數(shù)的個(gè)數(shù)
 ? ?S.erase();//1.輸入的是一個(gè)數(shù)，就刪除該數(shù)的所有存儲(chǔ) 2.輸入一個(gè)迭代器，就刪除這個(gè)迭代器
 ? ?S.lower_bound(x);//返回大于等于x的最小的數(shù)的迭代器
 ? ?S.upper_bound(x);//返回大于x的最小數(shù)的迭代器
 ? ?
 ? ?return 0;
}

map/multimap

insert()插入的數(shù)是一個(gè)pair erase()輸入的參數(shù)是pair或者是迭代器 find()

[] 時(shí)間復(fù)雜度是O(nlogn) lower_bound() upper_bound()

unordered_set, unordered_map, unordered_multiset, unordered_multimap

哈希表 和上面的類似，增刪查改的時(shí)間復(fù)雜度是O(1)

不支持lower_bound()和upper_bound()，迭代器的++、--

bitset，壓位

bitset<10000>S;~, &, |, ^, >>, <<, ==, !=,

count()返回有多少個(gè)1

any()判斷是否至少有一個(gè)1

none()判斷是否為0

set()把所有位置都換成1

reset()把所有位都變成0

flip()等價(jià)~ flip(k)把第k位反轉(zhuǎn)。

?文章來源地址http://www.zghlxwxcb.cn/news/detail-600811.html

到了這里，關(guān)于算法競賽備賽之經(jīng)典數(shù)據(jù)結(jié)構(gòu)訓(xùn)練提升，暑期集訓(xùn)營培訓(xùn)的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！