C++笔记汇总4

本专题为记录做题中的一些补充用法，持续更新ing

1.STL unique函数

定义

unique函数属于STL中比较常用函数，它的功能是元素去重。即**”删除”序列中所有相邻的重复元素(只保留一个)。此处的删除，并不是真的删除，而是指重复元素的位置被不重复的元素给占领了(详细情况，下面会讲)。由于它”删除”的是相邻的重复元素，所以在使用unique函数之前，一般都会将目标序列进行排序。**

函数原型

unique函数的函数原型如下：

1.只有两个参数，且参数类型都是迭代器：

1

iterator unique(iterator it_1,iterator it_2);

这种类型的unique函数是我们最常用的形式。其中这两个参数表示对容器中[it_1，it_2)范围的元素进行去重 (注：区间是前闭后开，即不包含it_2所指的元素),返回值是一个迭代器，它指向的是去重后容器中不重复序列的最后一个元素的下一个元素。

unique函数的去重过程实际上就是不停的把后面不重复的元素移到前面来，也可以说是用不重复的元素占领重复元素的位置。

unique并不是真正地将重复元素进行了删除，而是不断将不重复的元素移动到数组的前面，最后返回的是返回的是去重后的不重复数列中最后一个元素的下一个元素的地址，如果需要计算该地址所对应的下标，则利用unique(a,a+n)-a即可。

2.unique函数通常和erase函数一起使用，来达到删除重复元素的目的。(注：此处的删除是真正的删除，即从容器中去除重复的元素，容器的长度也发生了变换；而单纯的使用unique函数的话，容器的长度并没有发生变化，只是元素的位置发生了变化).

关于erase函数的用法，可以参考：STL中erase()的用法 - Excaliburer - 博客园 (cnblogs.com)

下面是一个具体的实例：

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

#include<iostream>
#include<algorithm>
#include<cassert>
using namespace std;

int main()
{
    vector<int> a ={1,3,3,4,5,6,6,7};
    vector<int>::iterator it_1 = a.begin();
    vector<int>::iterator it_2 = a.end();
    vector<int>::iterator new_end;
    new_end = unique(it_1,it_2); //注意unique的返回值
    a.erase(new_end,it_2);
    cout<<"删除重复元素后的 a : ";
    for(int i = 0 ; i < a.size(); i++)
        cout<<a[i];
    cout<<endl;
}

这里，他的返回值是去重后序列（这个序列不含有重复数值）的末尾的下一个元素，在上边代码中，

unique后，数组顺序为：1,3,4,5,6,7,X(代表重复数字，具体哪个不重要）,X。他的返回值就是第一个重复数字的地址，所以，

能用erase 实现彻底去重。

模板题

车的攻击

题目描述

$N \times N$ 的国际象棋棋盘上有$K$ 个车，第$i$个车位于第$R_i$行，第$C_i$ 列。求至少被一个车攻击的格子数量。

车可以攻击所有同一行或者同一列的地方。

输入格式

第1 行，2 个整数$N,K$。

接下来K 行，每行2 个整数$R_i,C_i$。

输出格式

1 个整数，表示被攻击的格子数量。

样例 #1

样例输入 #1

1
2
3

3 2
1 2
2 2

样例输出 #1

1

7

提示

• 对于30% 的数据，$1 \le N \le 10^3; 1 \le K \le 10^3$；

• 对于60% 的数据，$1 \le N \le 10^6; 1 \le K \le 10^6$；

• 对于100% 的数据，$1 \le N \le 10^9; 1 \le K \le 10^6; 1 \le R_i , C_i \le N$。

AC代码

注：本题使用unordered_set同样可以AC

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

#include <bits/stdc++.h>
using namespace std;
#define M 100007
#define N 1007
#define INF 0x3f3f3f3f
#define ll long long
#define db double
ll n, k, x, y;
vector<int> row, line;
int main() {
    ios::sync_with_stdio(false);
    cout.tie(NULL);
    cin >> n >> k;
    for (int i = 1; i <= k; i++) {
        cin >> x >> y;
        row.push_back(x);
        line.push_back(y);
    }
    sort(row.begin(), row.end());
    sort(line.begin(), line.end());
    ll size_row = unique(row.begin(), row.end()) - row.begin();
    ll size_line = unique(line.begin(), line.end()) - line.begin();
    cout << n * n - (n - size_row) * (n - size_line);
    return 0;
}

2.STL heap模拟

priority_queue的介绍

优先级队列默认使用vector作为其底层存储数据的容器，在vector上又使用了堆算法将vector中的元素构造成堆的结构，因此priority_queue就是堆，所有需要用到堆的位置，都可以考虑使用priority_queue。

注意： 默认情况下priority_queue是大堆。

priority_queue的定义方式

方式一： 使用vector作为底层容器，内部构造大堆结构。

1

priority_queue<int, vector<int>, less<int>> q1;

方式二： 使用vector作为底层容器，内部构造小堆结构。

1

priority_queue<int, vector<int>, greater<int>> q2;

方式三： 不指定底层容器和内部需要构造的堆结构。

1

priority_queue<int> q;

注意：

1.使用方式三时默认使用vector作为底层容器，内部默认构造大堆结构。

2.使用方式一、方式二构造时，less为大顶堆，greater为小顶堆。

priority_queue的模拟实现

priority_queue的底层实际上就是堆结构，实现priority_queue之前，我们先认识两个重要的堆算法。（下面这两种算法我们均以大堆为例）

堆的向上调整算法

调整的基本思想如下：
1、将目标结点与其父结点进行比较。
2、若目标结点的值比父结点的值大，则交换目标结点与其父结点的位置，并将原目标结点的父结点当作新的目标结点继续进行向上调整；若目标结点的值比其父结点的值小，则停止向上调整，此时该树已经是大堆了。

堆的向下调整算法

调整的基本思想如下：
1、将目标结点与其较大的子结点进行比较。
2、若目标结点的值比其较大的子结点的值小，则交换目标结点与其较大的子结点的位置，并将原目标结点的较大子结点当作新的目标结点继续进行向下调整；若目标结点的值比其较大子结点的值大，则停止向下调整，此时该树已经是大堆了。

一些其他tips

1、优先队列是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的(默认是建大堆)。
2、此上下文类似于堆，在堆中可以随时插入元素，并且只能检索最大堆元素(优先队列中位于顶部的元素)。
3、优先队列被实现为容器适配器，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从特定容器的“尾部”弹出，其称为优先队列的顶部。
4、底层容器可以是任何标准容器类模板，也可以是其他特定设计的容器类。容器应该可以通过随机访问迭代器访问，并支持以下操作：
empty()：检测容器是否为空
size()：返回容器中有效元素个数
front()：返回容器中第一个元素的引用
push_back()：在容器尾部插入元素
pop_back()：删除容器尾部元素
5、 标准容器类vector和deque满足这些需求。默认情况下，如果没有为特定的priority_queue类实例化指定容器类，则使用vector。
6、 需要支持随机访问迭代器，以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数make_heap、push_heap和pop_heap来自动完成此操作。
7、利用一个大根堆一个小根堆来维护第k小，并没有强制在线不强制在线，所以我们直接读入所有元素，枚举询问，因为要询问第k小，所以把前面的第k个元素都放进大根堆里面，然后如果元素数量大于k，就把堆顶弹掉放到小根堆里面，使大根堆的元素严格等于k，这样这次询问的结果就是小根堆的堆顶了（前面k-1小的元素都在大根堆里面了）。记得在完成这次询问后重新把小根堆的堆顶放到大根堆里面就好。
8、堆的题目可以直接重载<来实现。

模板题

黑匣子

题目描述

Black Box 是一种原始的数据库。它可以储存一个整数数组，还有一个特别的变量 $i$。最开始的时候 Black Box 是空的．而 $i=0$。这个 Black Box 要处理一串命令。

命令只有两种：

• ADD(x)：把 $x$ 元素放进 Black Box;

• GET：$i$ 加 $1$，然后输出 Black Box 中第 $i$ 小的数。

记住：第 $i$ 小的数，就是 Black Box 里的数的按从小到大的顺序排序后的第 $i$ 个元素。

我们来演示一下一个有11个命令的命令串。（如下表所示）

现在要求找出对于给定的命令串的最好的处理方法。ADD 命令共有 $m$ 个，GET 命令共有 $n$ 个。现在用两个整数数组来表示命令串：

1. $a_1,a_2,\cdots,a_m$：一串将要被放进 Black Box 的元素。例如上面的例子中 $a=[3,1,-4,2,8,-1000,2]$。

2. $u_1,u_2,\cdots,u_n$：表示第 $u_i$ 个元素被放进了 Black Box 里后就出现一个 GET 命令。例如上面的例子中 $u=[1,2,6,6]$ 。输入数据不用判错。

输入格式

第一行两个整数 $m$ 和 $n$，表示元素的个数和 GET 命令的个数。

第二行共 $m$ 个整数，从左至右第 $i$ 个整数为 $a_i$，用空格隔开。

第三行共 $n$ 个整数，从左至右第 $i$ 个整数为 $u_i$，用空格隔开。

输出格式

输出 Black Box 根据命令串所得出的输出串，一个数字一行。

样例 #1

样例输入 #1

1
2
3

7 4
3 1 -4 2 8 -1000 2
1 2 6 6

样例输出 #1

1
2
3
4

3
3
1
2

提示

数据规模与约定

• 对于 $30%$ 的数据，$1 \leq n,m \leq 10^{4}$。
• 对于 $50%$ 的数据，$1 \leq n,m \leq 10^{5}$。
• 对于 $100%$ 的数据，$1 \leq n,m \leq 2 \times 10^{5},|a_i| \leq 2 \times 10^{9}$，保证 $u$ 序列单调不降。

AC代码

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

#include <bits/stdc++.h>
using namespace std;
#define M 200007
#define N 1007
#define INF 0x3f3f3f3f
#define ll long long
#define db double
int a[M];
int m, n;
priority_queue<int, vector<int>, greater<int>> min_que;
priority_queue<int, vector<int>, less<int>> max_que;
int main() {
    ios::sync_with_stdio(false);
    cout.tie(NULL);
    cin >> m >> n;
    for (int i = 1; i <= m; i++) {
        cin >> a[i];
    }
    int u, dst = 0;
    for (int i = 1; i <= n; i++) {
        cin >> u;
        while (dst < u) {
            max_que.push(a[++dst]);
            min_que.push(max_que.top());
            max_que.pop();
        }
        cout << min_que.top() << endl;
        max_que.push(min_que.top());
        min_que.pop();
    }
    return 0;
}

3.pair

pair的应用

pair是将2个数据组合成一组数据，当需要这样的需求时就可以使用pair，如stl中的map就是将key和value放在一起来保存。另一个应用是，当一个函数需要返回2个数据的时候，可以选择pair。 pair的实现是一个结构体，主要的两个成员变量是first second 因为是使用struct不是class，所以可以直接使用pair的成员变量。

其标准库类型–pair类型定义在#include <utility>头文件中，定义如下：

类模板：template<class T1,class T2> struct pair

参数：T1是第一个值的数据类型，T2是第二个值的数据类型。

功能：pair将一对值(T1和T2)组合成一个值，这一对值可以具有不同的数据类型（T1和T2），两个值可以分别用pair的两个公有函数first和second访问。

pair定义(构造函数)：

1
2
3
4
5
6
7

pair<T1, T2> p1;            //创建一个空的pair对象（使用默认构造），它的两个元素分别是T1和T2类型，采用值初始化。
pair<T1, T2> p1(v1, v2);    //创建一个pair对象，它的两个元素分别是T1和T2类型，其中first成员初始化为v1，second成员初始化为v2。
make_pair(v1, v2);          // 以v1和v2的值创建一个新的pair对象，其元素类型分别是v1和v2的类型。
p1 < p2;                    // 两个pair对象间的小于运算，其定义遵循字典次序：如 p1.first < p2.first 或者 !(p2.first < p1.first) && (p1.second < p2.second) 则返回true。
p1 == p2；                  // 如果两个对象的first和second依次相等，则这两个对象相等；该运算使用元素的==操作符。
p1.first;                   // 返回对象p1中名为first的公有数据成员
p1.second;                 // 返回对象p1中名为second的公有数据成员

pair包含两个数值，与容器一样，pair也是一种模板类型。但是又与之前介绍的容器不同；

在创建pair对象时，必须提供两个类型名，两个对应的类型名的类型不必相同

1
2
3

pair<string, string> anon;        // 创建一个空对象anon，两个元素类型都是string
pair<string, int> word_count;     // 创建一个空对象 word_count, 两个元素类型分别是string和int类型
pair<string, vector<int> > line;  // 创建一个空对象line，两个元素类型分别是string和vector类型

当然也可以在定义时进行成员初始化：

1
2
3

pair<string, string> author("James","Joy");    // 创建一个author对象，两个元素类型分别为string类型，并默认初始值为James和Joy。
pair<string, int> name_age("Tom", 18);
pair<string, int> name_age2(name_age);    // 拷贝构造初始化

pair类型的使用相当的繁琐，如果定义多个相同的pair类型对象，可以使用typedef简化声明：

1
2
3

typedef pair<string,string> Author;
Author proust("March","Proust");
Author Joy("James","Joy");

变量间赋值：

1
2
3
4

pair<int, double> p1(1, 1.2);
pair<int, double> p2 = p1;     // copy construction to initialize object
pair<int, double> p3；
p3 = p1;    // operator =

pair对象的操作

访问两个元素操作可以通过first和second访问：

1
2
3
4
5
6
7
8

pair<int ,double> p1;
p1.first = 1;
p1.second = 2.5;
cout<<p1.first<<' '<<p1.second<<endl;
//输出结果：1 2.5
string firstBook;
if(author.first=="James" && author.second=="Joy")
    firstBook="Stephen Hero";

生成新的pair对象

还可以利用make_pair创建新的pair对象：

1
2
3
4
5
6
7
8
9
10

pair<int, double> p1;
p1 = make_pair(1, 1.2);
cout << p1.first << p1.second << endl;
//output: 1 1.2
int a = 8;
string m = "James";
pair<int, string> newone;
newone = make_pair(a, m);
cout << newone.first << newone.second << endl;
//output: 8 James

通过tie获取pair元素值

在某些清况函数会以pair对象作为返回值时，可以直接通过std::tie进行接收。比如：

1
2
3
4
5
6
7
8
9
10

std::pair<std::string, int> getPreson() {
    return std::make_pair("Sven", 25);
}
int main(int argc, char **argv) {
    std::string name;
    int ages;
    std::tie(name, ages) = getPreson();
    std::cout << "name: " << name << ", ages: " << ages << std::endl;
    return 0;
}

pair交换

pair类模板提供一个 swap() 成员函数，能够互换 2 个 pair 对象的键值对，其操作成功的前提是这 2 个 pair 对象的键和值的类型要相同。

1
2

pair1.swap(pair2);
//swap(pair1, pair2);

pair比较

<utility>头文件中除了提供创建 pair 对象的方法之外，还为 pair 对象重载了 <、<=、>、>=、==、!= 这 6 的运算符，其运算规则是：对于进行比较的 2 个 pair 对象，先比较 pair.first 元素的大小，如果相等则继续比较 pair.second 元素的大小。
 注意，对于进行比较的 2 个 pair 对象，其对应的键和值的类型相同，否则将没有可比性，同时编译器提示没有相匹配的运算符，即找不到合适的重载运算符。

1
2
3
4
5

if(pair1 == pair2){
	cout<<"pair1 == pair2"<<endl;
}else{
	cout<<"pair1 != pair2"<<endl;
}

4.prev_permutation()/next_permutation()

tips:这两个函数在使用起来可以仿照着sort()函数，使用方法基本相同。

next_permutation()

函数介绍

将[first, last)范围内的元素重新排序，并将其排列成为下一个字典序更大的一个排序。通常第三个参数comp可以省略, 也可以自定义排序方式进行排序。如果存在下一个字典序排列，将数组进行排列并返回true, 否则返回false。

prev_permutation()

函数介绍

将[first, last)范围内的元素重新排序，并将其排列成为上一个字典序更小的一个排序。通常第三个参数comp可以省略, 也可以自定义排序方式进行排序。如果紧接着的上一个字典序排列存在，将数组进行排列并返回true, 否则返回false。

5.low_bound()/upper_bound()

函数使用

参数

1.一个数组元素的地址（或者数组名来表示这个数组的首地址，用来表示这个数组的开头比较的元素的地址，不一定要是首地址，只是用于比较的“首”地址）。
2.一个数组元素的地址（对应的这个数组里边任意一个元素的地址，表示这个二分里边的比较的"结尾’地址）。
3.就是一个你要二分查找的那个数。

返回值

返回第一次出现大于等于那个要查找的数的地址，

注意事项

第一，是地址，不是指那个要查找的数的下标，所以就注定了在这个函数的后边就要减去一个尾巴，那就是这个数组的数组名，即这个数组的首地址,只有这样才代表那个要查找的数字的下标，当然如果没有找到那个数，也是会返回的。

第二点，那就是要大于等于那个数，等于好理解，大于怎么理解呢，比如说我并没有找到那个数，加入一个的数组里边就有5个数，分别是1,1,1,3,5,而我需要找的那个数就是2，怎么返回呢？小编告诉你哦，就是返回那个第一个大于2的数的地址，就是返回3的地址，那么再有一组数据就是5个数1,1,1,3,3，还是需要找寻2，那么该返回什么呢？那就是第一个3的地址。

• low_bound(a+i,a+j,x)-a //返回的是第一个大于等于x的数的位置

1
2
3
4
5
6
7
8
9

void low_bound(int l, int r, int x) {
    while (l < r) {
        int mid = (r - l) / 2;
        if (a[mid] >= x)
            r = mid;
        else
            l = mid + 1;
    }
}

upper_bound函数的用法lower_bound函数的用法相似，不过这个唯一的不同就是返回的是第一个比我要找的那个数大的数的地址，注意，这里并没有等于，也就是说如果在5个数1,1,2,2,4，里边寻找3，那么就会返回4的地址，下边代码实现：

• upper_bound(a+i,a+j,x)-a //返回第一个大于x的数的位置

1
2
3
4
5
6
7
8
9

void upper_bound(int l, int r, int x) {
    while (l < r) {
        int mid = (r - l) / 2;
        if (a[mid] > x)
            r = mid;
        else
            l = mid + 1;
    }
}

还是一样，参考sort很容易就明白了。

6.bitset

bitset我愿称为状态压缩dp的神器。

定义

bitset可以说是一个多位二进制数，每八位占用一个字节，因为支持基本的位运算，所以可用于状态压缩，n位bitset执行一次位运算的时间复杂度可视为n/32.

基本操作

1.定义：

bitset< n > s;
表示一个n位的二进制数，<>中填写位数；

2.位运算操作符：

~s: 返回对s每一位取反后的结果；
&，|，^：返回对两个位数相同的bitset执行按位与、或、异或运算的结果；
<<, >>:返回把一个bitset左移，右移若干位的结果.（补零）；

==，！=：比较两个位数相同的bitset代表的二进制数是否相等；

3.[ ]操作符：

s[k] :表示s的第k位，即可取值也可赋值，编号从0开始；

4.count:

s.count() 返回二进制串中有多少个1；

5.any/none

若s所有位都为0，则s.any()返回false，s.none()返回true；
若s至少有一位为1，则s.any()返回true，s.none()返回false；

6.set/rest/flip

s.set()把s所有位变为1；
s.set(k,v)把s的第k位改为v,即s[k]=v；
s.reset()把s的所有位变为0.
s.reset(k)把s的第k位改为0,即s[k]=0；
s.flip()把s所有位取反.即s=~s；
s.flip(k)把s的第k位取反，即s[k]^=1；

模板题

砝码称重

题目描述

现有 $n$ 个砝码，重量分别为 $a_i$，在去掉 $m$ 个砝码后，问最多能称量出多少不同的重量（不包括 $0$）。

请注意，砝码只能放在其中一边。

输入格式

第 $1$ 行为有两个整数 $n$ 和 $m$，用空格分隔。

第 $2$ 行有 $n$ 个正整数 $a_1, a_2, a_3,\ldots , a_n$，表示每个砝码的重量。

输出格式

仅包括 $1$ 个整数，为最多能称量出的重量数量。

样例 #1

样例输入 #1

1
2

3 1
1 2 2

样例输出 #1

1

3

提示

【样例说明】

在去掉一个重量为 $2$ 的砝码后，能称量出 $1, 2, 3$ 共 $3$ 种重量。

【数据规模】

对于 $20%$ 的数据，$m=0$。

对于 $50%$ 的数据，$m\leq 1$。

对于 $50%$ 的数据，$n\leq 10$。

对于 $100%$ 的数据，$n\leq 20$， $m\leq 4$，$m < n$，$a_i\leq 100$。

AC代码

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 <bits/stdc++.h>
using namespace std;
#define M 100007
#define N 1007
#define INF 0x3f3f3f3f
#define mod 1000000007
#define ll long long
#define db double
#define pii pair<int, int>
int a[M];
int n, m, ans;
int check(int val) {
    int ans = 0;
    while (val) {
        ans++;
        val &= (val - 1);
    }
    return ans;
}
int calc(int val) {
    bitset<2010> s;
    s[0] = 1;
    for (int j = 1; j <= n; j++) {
        if (val & (1 << (j - 1))) {
            s |= s << a[j];
        }
    }
    return s.count() - 1;
}
int main() {
    ios::sync_with_stdio(false);
    cout.tie(NULL);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i < (1 << n); i++) {
        if (check(i) == n - m) {
            ans = max(ans, calc(i));
        }
    }
    cout << ans;
    return 0;
}