排序

sort()

推荐直接使用本函数，无后顾之忧，在使用之前，需要调用头文件<algorithm>

它有三个参数sort(begin, end, cmp)，其中begin为指向待sort()的数组的第一个元素的指针，end为指向待sort()的数组的最后一个元素的下一个位置的指针，cmp参数为排序准则，cmp参数可以不写，如果不写的话，默认从小到大进行排序。如果我们想从大到小排序可以将cmp参数写为greater<int>()就是对int数组进行排序，当然<>中我们也可以写double、long、float等等。如果我们需要按照其他的排序准则，那么就需要我们自己定义一个bool类型的函数来传入。在对结构体排序时，经常会用到自己写一个排序规则。

写法如下

1
2
3
4
5
6
7
8
int cmp(int x,int y)
{
    return x>y;
}
int main()
{
    sort(a,a+n,cmp);
}

当然，工作室不乏有变态要求手写排序，接下来有几个排序的代码可以看一下。

快速排序

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
#include <iostream>

using namespace std;

const int N = 100010;

int q[N];

void quick_sort(int q[], int l, int r)
{
    if (l >= r) return;

    int i = l - 1, j = r + 1, x = q[l + r >> 1];
    while (i < j)
    {
        do i ++ ; while (q[i] < x);
        do j -- ; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
    }

    quick_sort(q, l, j);
    quick_sort(q, j + 1, r);
}

int main()
{
    int n;
    scanf("%d", &n);

    for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]);

    quick_sort(q, 0, n - 1);

    for (int i = 0; i < n; i ++ ) printf("%d ", q[i]);

    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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>

using namespace std;

const int N = 1e5 + 10;

int a[N], tmp[N];

void merge_sort(int q[], int l, int r)
{
    if (l >= r) return;

    int mid = l + r >> 1;

    merge_sort(q, l, mid), merge_sort(q, mid + 1, r);

    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r)
        if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
        else tmp[k ++ ] = q[j ++ ];
    while (i <= mid) tmp[k ++ ] = q[i ++ ];
    while (j <= r) tmp[k ++ ] = q[j ++ ];

    for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);

    merge_sort(a, 0, n - 1);

    for (int i = 0; i < n; i ++ ) printf("%d ", a[i]);

    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
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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
namespace BigInteger
{
#define maxn 10005
using std::sprintf;
using std::string;
using std::max;
using std::istream;
using std::ostream;

struct Big_integer{  
    int d[maxn], len;  
  
    void clean() 
	{ 
	while(len > 1 && !d[len-1]) 
	len--;
	}  
  
    Big_integer()          { memset(d, 0, sizeof(d)); len = 1; }  
    Big_integer(int num)   { *this = num; }   
    Big_integer(char* num) { *this = num; }  
    Big_integer operator = (const char* num){  
        memset(d, 0, sizeof(d)); len = strlen(num);  
        for(int i = 0; i < len; i++) d[i] = num[len-1-i] - '0';  
        clean();  
        return *this;  
    }  
    
    Big_integer operator = (int num){  
        char s[10005]; sprintf(s, "%d", num);  
        *this = s;  
        return *this;  
    }  
  
    Big_integer operator + (const Big_integer& b){  
        Big_integer c = *this; int i;  
        for (i = 0; i < b.len; i++){  
            c.d[i] += b.d[i];  
            if (c.d[i] > 9) c.d[i]%=10, c.d[i+1]++;  
        }  
        while (c.d[i] > 9) c.d[i++]%=10, c.d[i]++;  
        c.len = max(len, b.len);  
        if (c.d[i] && c.len <= i) c.len = i+1;  
        return c;  
    }  
    
    Big_integer operator - (const Big_integer& b){  
        Big_integer c = *this; int i;  
        for (i = 0; i < b.len; i++){  
            c.d[i] -= b.d[i];  
            if (c.d[i] < 0) c.d[i]+=10, c.d[i+1]--;  
        }  
        while (c.d[i] < 0) c.d[i++]+=10, c.d[i]--;  
        c.clean();  
        return c;  
    }  
    
    Big_integer operator * (const Big_integer& b)const{  
        int i, j; Big_integer c; c.len = len + b.len;   
        for(j = 0; j < b.len; j++) for(i = 0; i < len; i++)   
            c.d[i+j] += d[i] * b.d[j];  
        for(i = 0; i < c.len-1; i++)  
            c.d[i+1] += c.d[i]/10, c.d[i] %= 10;  
        c.clean();  
        return c;  
    }  
    
    Big_integer operator / (const Big_integer& b){  
        int i, j;  
        Big_integer c = *this, a = 0;  
        for (i = len - 1; i >= 0; i--)  
        {  
            a = a*10 + d[i];  
            for (j = 0; j < 10; j++) if (a < b*(j+1)) break;  
            c.d[i] = j;  
            a = a - b*j;  
        }  
        c.clean();  
        return c;  
    }  
    
    Big_integer operator % (const Big_integer& b){  
        int i, j;  
        Big_integer a = 0;  
        for (i = len - 1; i >= 0; i--)  
        {  
            a = a*10 + d[i];  
            for (j = 0; j < 10; j++) if (a < b*(j+1)) break;  
            a = a - b*j;  
        }  
        return a;  
    }  
    
    Big_integer operator += (const Big_integer& b){  
        *this = *this + b;  
        return *this;  
    }  
  
    bool operator <(const Big_integer& b) const{  
        if(len != b.len) return len < b.len;  
        for(int i = len-1; i >= 0; i--)  
            if(d[i] != b.d[i]) return d[i] < b.d[i];  
        return false;  
    }  
    bool operator >(const Big_integer& b) const{return b < *this;}  
    bool operator<=(const Big_integer& b) const{return !(b < *this);}  
    bool operator>=(const Big_integer& b) const{return !(*this < b);}  
    bool operator!=(const Big_integer& b) const{return b < *this || *this < b;}  
    bool operator==(const Big_integer& b) const{return !(b < *this) && !(b > *this);}  
  
    string str() const{  
        char s[maxn]={};  
        for(int i = 0; i < len; i++) s[len-1-i] = d[i]+'0';  
        return s;  
    }  
};  
  
istream& operator >> (istream& in, Big_integer& x)  
{  
    string s;  
    in >> s;  
    x = s.c_str();  
    return in;  
}  
  
ostream& operator << (ostream& out, const Big_integer& x)  
{  
    out << x.str();  
    return out;  
}  
}
using namespace BigInteger;
using namespace std;
struct use
{
	Big_integer a;
	int num;
	bool operator < (const use &x)const
	{
		return a < x.a;
	}
};
use data[21];
int main()
{
	int cnt;
	scanf("%d", & cnt);
	for (int i = 1; i <= cnt; ++i)
		cin >> data[i - 1].a, data[i - 1].num = i;
	sort(data, data + cnt);
	printf("%d\n", data[cnt - 1].num), cout << data[cnt - 1].a;
	return 0;
}

二分

二分查找

二分通常指的是二分查找，你还在为找不清数据范围而痛苦吗，快来试试下面的模板。温馨提示：使用二分之前，记得给数据排序哦。

模板一

只要是往左找答案，就用第一个模板，mid不用加一，r=mid，l加一

1
2
3
4
5
6
7
int l = 0, r = n - 1;
       while (l < r)
       {
           int mid = l + r >> 1;
           if (q[mid] >= x) r = mid;//q[mid]>=x 指的就是判断需要的条件
           else l = mid + 1;
       }

模板二

只要是往右找答案，就用第二个模板，mid要加一，l=mid，r要减一；

1
2
3
4
5
6
7
int l = 0, r = n - 1;
       while (l < r)
       {
           int mid = l + r+1 >> 1;
           if (q[mid] >= x) l = mid;
           else r = mid - 1;
       }

浮点二分

因为没有了整数相除会向下取整操作，因此浮点二分不需要考虑±1。

1
2
3
4
5
6
while(r-l>1e-5) //需要一个精度保证
{
    double mid = (l+r)/2;
    if(check(mid)) l=mid; //或r=mid;
    else r=mid; //或l=mid;
}

lower_bound( )和upper_bound( )

在从小到大的排序数组中，

lower_bound( begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于或等于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

upper_bound( begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

在从大到小的排序数组中，重载lower_bound()和upper_bound()

lower_bound( begin,end,num,greater<type>() ):从数组的begin位置到end-1位置二分查找第一个小于或等于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

upper_bound( begin,end,num,greater<type>() ):从数组的begin位置到end-1位置二分查找第一个小于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

二分答案

二分查找与二分答案有何区别?

二分查找：在一个已知的有序数据集上进行二分地查找
二分答案：答案有一个区间，在这个区间中二分，直到找到最优答案

如何判断一个题是不是用二分答案做的呢?

1、答案在一个区间内（一般情况下，区间会很大，暴力超时）
2、直接搜索不好搜，但是容易判断一个答案可行不可行
3、该区间对题目具有单调性，即：在区间中的值越大或越小，题目中的某个量对应增加或减少。

此外，可能还会有一个典型的特征：求...最大值的最小 、 求...最小值的最大。
1、求...最大值的最小，我们二分答案（即二分最大值）的时候，判断条件满足后，尽量让答案往前来（即：让r=mid），对应模板1；
2、同样，求...最小值的最大时，我们二分答案（即二分最小值）的时候，判断条件满足后，尽量让答案往后走（即：让l=mid），对应模板2；

前缀和

前缀和

很显然如果我们要从左侧也就是l一直加到右侧也就是r，很显然需要从头到尾循环一遍，时间复杂度也就是O(n)。

而使用

这样时间复杂度就是O(1)

上模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 #include <iostream>
using namespace std;
const int N = 100010;
int n, m;
int a[N], s[N];
int main()
{
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; i++)s[i] = s[i - 1] + a[i];
	while (m--)
	{
		int l, r;
		cin >> l >> r;
		cout << s[r] - s[l - 1];
	}
	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
25
26
27
28
29
30
#include <iostream>

using namespace std;

const int N = 1010;

int n, m, q;
int s[N][N];

int main()
{
    scanf("%d%d%d", &n, &m, &q);

    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            scanf("%d", &s[i][j]);

    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];

    while (q -- )
    {
        int x1, y1, x2, y2;
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        printf("%d\n", s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]);
    }

    return 0;
}

差分

http://t.csdn.cn/PJJ2p看看这个人的博客，有详细解释

DFS（深度优先搜索）

简而言之，把每一个枝都走完，再走第二根。

注意回溯与恢复

下面是未剪枝（全排列也不涉及剪枝）的版本

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
#include <iostream>
#include <cstdio>
using namespace std;
const int N = 100010;
int n;
int path[N];
bool st[N];
void dfs(int u)
{
	if (u == n)
	{
		for (int i = 0; i < n; i++)printf("%5d", path[i]);
		cout << '\n';
		return;
	}
	for (int i = 0; i < n; i++)//回溯
	{
		if (!st[i])
		{
			path[u] = i;
			st[i] = true;
			dfs(u + 1);
			st[i] = false;//恢复
		}
	}
}

int main()
{
	cin >> n;
	dfs(0);
	return 0;

}

next_permutation(全排列函数)

引用头文件<algorithm>

函数原型

1
bool next_permutation(iterator start,iterator end,cmp)//cmp同样可以自定义

当当前序列不存在下一个排列时，函数返回false，否则返回true

1
2
3
4
5
6
7
8
9
10
11
12
#include <iostream>  
#include <algorithm>  
using namespace std;  
int main()  
{  
    int num[3]={1,2,3};  
    do  
    {  
        cout<<num[0]<<" "<<num[1]<<" "<<num[2]<<endl;  
    }while(next_permutation(num,num+3));  
    return 0;  
}

计算被2整除的次数

在二进制下，如果最靠右的一位为0，则这个数为偶数，因此，一个二进制数末尾0的个数即为这个数能被2整除的次数。

代码如下

1
y&-y;//其结果就为被2整除的次数

纯粹关联式容器

set

set 中不会出现值相同的元素。如果需要有相同元素的集合，需要使用 multiset。multiset 的使用方法与 set 的使用方法基本相同。

插入删除

  • insert(x) 当容器中没有等价元素的时候，将元素 x 插入到 set 中。
  • erase(x) 删除值为 x 的 所有 元素，返回删除元素的个数。
  • erase(pos) 删除迭代器为 pos 的元素，要求迭代器必须合法。
  • erase(first,last) 删除迭代器在 $[first,last)$范围内的所有元素。
  • clear() 清空 set。

insert 函数的返回值类型为 pair<iterator, bool>，其中 iterator 是一个指向所插入元素（或者是指向等于所插入值的原本就在容器中的元素）的迭代器，而 bool 则代表元素是否插入成功，由于 set 中的元素具有唯一性质，所以如果在 set 中已有等值元素，则插入会失败，返回 false，否则插入成功，返回 true；map 中的 insert 也是如此。

迭代器

set 提供了以下几种迭代器：

  1. begin()/cbegin()
    返回指向首元素的迭代器，其中 *begin = front。
  2. end()/cend()
    返回指向数组尾端占位符的迭代器，注意是没有元素的。
  3. rbegin()/crbegin()
    返回指向逆向数组的首元素的逆向迭代器，可以理解为正向容器的末元素。
  4. rend()/crend()
    返回指向逆向数组末元素后一位置的迭代器，对应容器首的前一个位置，没有元素。

以上列出的迭代器中，含有字符 c 的为只读迭代器，你不能通过只读迭代器去修改 set 中的元素的值。如果一个 set 本身就是只读的，那么它的一般迭代器和只读迭代器完全等价。

查找操作

  • count(x) 返回 set 内键为 x 的元素数量。
  • find(x) 在 set 内存在键为 x 的元素时会返回该元素的迭代器，否则返回 end()。
  • lower_bound(x) 返回指向首个不小于给定键的元素的迭代器。如果不存在这样的元素，返回 end()。
  • upper_bound(x) 返回指向首个大于给定键的元素的迭代器。如果不存在这样的元素，返回 end()。
  • empty() 返回容器是否为空。
  • size() 返回容器内元素个数。
lower_bound 和 upper_bound 的时间复杂度

set 自带的 lower_bound 和 upper_bound 的时间复杂度为O(logn) 。

但使用 algorithm 库中的 lower_bound 和 upper_bound 函数对 set 中的元素进行查询，时间复杂度为O(n) 。

nth_element 的时间复杂度

set 没有提供自带的 nth_element。使用 algorithm 库中的 nth_element 查找第  大的元素时间复杂度为O(n) 。

如果需要实现平衡二叉树所具备的O(logn)  查找第k  大元素的功能，需要自己手写平衡二叉树或权值线段树，或者选择使用 pb_ds 库中的平衡二叉树。

遍历容器

可以利用迭代器来遍历关联式容器的所有元素。

1
2
3
set<int> s;
typedef set<int>::iterator si;
for (si it = s.begin(); it != s.end(); it++) cout << *it << endl;

map

map 是有序键值对容器，它的元素的键是唯一的。搜索、移除和插入操作拥有对数复杂度。map 通常实现为红黑树。

你可能需要存储一些键值对，例如存储学生姓名对应的分数：Tom 0，Bob 100，Alan 100。但是由于数组下标只能为非负整数，所以无法用姓名作为下标来存储，这个时候最简单的办法就是使用 STL 中的 map 了！

map 重载了 operator[]，可以用任意定义了 operator < 的类型作为下标（在 map 中叫做 key，也就是索引）：

1
map<Key, T> yourMap;

其中，Key 是键的类型，T 是值的类型，下面是使用 map 的实例：

1
map<string, int> mp;

map 中不会存在键相同的元素，multimap 中允许多个元素拥有同一键。multimap 的使用方法与 map 的使用方法基本相同。

正是因为 multimap 允许多个元素拥有同一键的特点，multimap 并没有提供给出键访问其对应值的方法。

插入与删除操作

  • 可以直接通过下标访问来进行查询或插入操作。例如 mp["Alan"]=100。
  • 通过向 map 中插入一个类型为 pair<Key, T> 的值可以达到插入元素的目的，例如 mp.insert(pair<string,int>("Alan",100));；
  • erase(key) 函数会删除键为 key 的 所有 元素。返回值为删除元素的数量。
  • erase(pos): 删除迭代器为 pos 的元素，要求迭代器必须合法。
  • erase(first,last): 删除迭代器在 $[first,last)$范围内的所有元素。
  • clear() 函数会清空整个容器。

在利用下标访问 map 中的某个元素时，如果 map 中不存在相应键的元素，会自动在 map 中插入一个新元素，并将其值设置为默认值（对于整数，值为零；对于有默认构造函数的类型，会调用默认构造函数进行初始化）。

当下标访问操作过于频繁时，容器中会出现大量无意义元素，影响 map 的效率。因此一般情况下推荐使用 find() 函数来寻找特定键的元素。

查询操作

  • count(x): 返回容器内键为 x 的元素数量。复杂度为 $O(log(size)+ans)$关于容器大小对数复杂度，加上匹配个数)。
  • find(x): 若容器内存在键为 x 的元素，会返回该元素的迭代器；否则返回 end()。
  • lower_bound(x): 返回指向首个不小于给定键的元素的迭代器。
  • upper_bound(x): 返回指向首个大于给定键的元素的迭代器。若容器内所有元素均小于或等于给定键，返回 end()。
  • empty(): 返回容器是否为空。
  • size(): 返回容器内元素个数。

map 用于存储复杂状态

在搜索中，我们有时需要存储一些较为复杂的状态（如坐标，无法离散化的数值，字符串等）以及与之有关的答案（如到达此状态的最小步数）。map 可以用来实现此功能。其中的键是状态，而值是与之相关的答案。下面的示例展示了如何使用 map 存储以 string 表示的状态。

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

// 存储状态与对应的答案
map<string, int> record;

// 新搜索到的状态与对应答案
string status;
int ans;
// 查找对应的状态是否出现过
map<string, int>::iterator it = record.find(status);
if (it == record.end()) {
  // 尚未搜索过该状态，将其加入状态记录中
  record[status] = ans;
  // 进行相应操作……
} else {
  // 已经搜索过该状态，进行相应操作……
}

遍历map

需要注意的是，对 map 的迭代器解引用后，得到的是类型为 pair<Key, T> 的键值对。

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<iostream>
#include<string>
#include<map>
using namespace std;
int main(){
    map<int,string> m{};
    m[0]="aaa";
    m[1]="bbb";
    m[2]="ccc";

    map<int,string>::iterator it;

    //方式一
    cout<<"方式一："<<endl;
    for(auto &t : m){
        cout<<"key:"<<t.first<<" value:"<<t.second<<endl;
    }
    
    //方式二
    cout<<"方式二："<<endl;
    for(map<int,string>::iterator iter = m.begin(); iter != m.end(); ++iter){
        cout<<"key:"<<iter->first<<" value:"<<iter->second<<endl;
    }
    //第三种
    cout<<"方式三："<<endl;
    map<int,string>::iterator iter=m.begin();
    while(iter != m.end()){
        cout<<"key:"<<iter->first<<" value:"<<iter->second<<endl;
        ++iter;
    }

}

无序关联式容器 - OI Wiki

详情请见本篇博客

格式化输入的小寄巧

sscanf

函数定义

1
int sscanf(const char *str, const char * format, ...);

函数说明

sscanf()定义于头文件stdio.h。sscanf()会将参数str的字符串根据参数format字符串来转换并格式化数据。格式转换形式请参考scanf()。转换后的结果存于对应的参数内。

返回值

成功则返回参数数目，失败则返回-1（也即EOF）。

参数中format的说明

format中可以包含一个或多个`