注意：

  • 整型越界

    #define int long long&&signed main(){}，但这样宏定义可能导致TLE/MLE

    或typedef long long ll

[toc]

常用STL

algorithm

#include<algorithm>

1
2
3
4
5
6
7
8
9
10
11
//algorithm 在STL中的应用主要是: sort()   swap()   reverse()   find()
max(), min(), abs();
swap();
reverse();  //reverse(vi.begin(), vi.end());
sort();     // sort(a, a+4);
find();     // find(vi.begin(), vi.end(), 3);
next_permutation();    // 可以获取全排列
fill();     // fill(a, a+5, 233);
*min_element(num,num+6);
*max_element(num,num+6);
lower_bound和upper_bound();

sort()

sort()

二分查找binary_search()

unique()

“删除”序列中所有相邻的重复元素(只保留一个)

此处的删除，并不是真的删除，而是指重复元素的位置被不重复的元素给占领了

由于它”删除”的是相邻的重复元素，所以在使用unique函数之前，一般都会将目标序列进行排序

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

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<iostream>  
#include<vector>  
#include<algorithm>  //unique头文件 
using namespace std;  
vector<int>a;  
int main()  
{  
    for(int i=1;i<10;i++)  
        for(int j=0;j<3;j++)  
            a.push_back(i);  

    sort(a.begin(),a.end());      
    a.erase(unique(a.begin(),a.end()),a.end());//unique函数通常和erase函数一起使用，来达到真正地删除重复元素的目的
    //单纯的使用unique函数的话，容器的长度并没有发生变化，只是元素的位置发生了变化

    for(int i=0;i<a.size();i++)
        cout<<a[i]; 
    return 0;  
}  
/*也可以这样：
int count=unique(a,a+n)-a;
    for (int i=0; i<count;i++)
        printf("%d\n", a[i]);
*/

find()

该函数会返回一个输入迭代器，当 find() 函数查找成功时，其指向的是在 [first, last) 区域内查找到的第一个目标元素；如果查找失败，则该迭代器的指向和 last 相同

值得一提的是，find() 函数的底层实现，其实就是用==运算符将 val 和 [first, last) 区域内的元素逐个进行比对。这也就意味着，[first, last) 区域内的元素必须支持==运算符

1
2
string = "hello";
find(s.begin(), s.end(), 'o') == s.end()

next_permutation()

next_permutation(num,num+n)函数是对数组num中的前n个元素进行全排列，同时并改变num数组的值

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
#include<iostream>
#include<algorithm>
using namespace std;

int main()
{
    int a[3]={1,2,3};
    do
    {
        cout<<a[0]<<" "<<a[1]<<" "<<a[2]<<endl;
    }while(next_permutation(a,a+3));
    return 0;
}
//输出

// 1 2 3
// 1 3 2
// 2 1 3
// 2 3 1
// 3 1 2
// 3 2 1

//如果改成 while(next_permutation(a,a+2));

//则输出：
// 1 2 3
// 2 1 3

fill()

fill函数可以为数组或者vector中的每个元素赋以相同的值，通常用于初始化

与memset()比较，memset()一般用于整个初始化：void *memset(void *s, int ch, size_t n);

1
2
3
//fill()给多维数组赋值
int v[10][10];
fill(v[0],v[0]+10*10,-1);

min_element() & max_element()

返回容器[begin, end）段中最小/大元素所在的第一个迭代器

1
2
3
4
5
6
7
8
9
10
11
12
13
#include<vector>
#include<iostream>
#include<algorithm>
using namespace std;

int main() {
	vector<int> nums = { 10, 90,20,32,89,40,45 };
	auto maxIt = max_element(nums.begin(), nums.end());//寻找nums中最大元素的迭代器
	auto minIt = min_element(nums.begin(), nums.end());//寻找nums中最小元素的迭代器
	cout << "最大元素：" << *maxIt << endl;
	cout << "最小元素：" << *minIt << endl;
	return 0;
}

lower_bound() & upper_bound()

lower_bound(first,last,val)：first和last中的前闭后开区间进行二分查找，返回【大于或等于】val的iterator位置。如果所有元素都小于val，则返回last的位置

upper_bound(first,last,val)：返回的在前闭后开区间查找的关键字的上界，返回【大于】val的iterator位置

math

#include<cmath> // #include<math.h>

使用时需要注意：输入参数绝大多数要求double双浮点类型

1
2
3
4
5
6
7
　　double log (double); 　　　　  //以e为底的对数
　　double log10 (double);　　　　 //以10为底的对数
　　double pow(double x,double y);//计算x的y次幂
　　double exp (double);　　　　　	//求取自然数e的幂
　　double sqrt (double);　　　　	//开平方
　　int 　 abs(int i); 　　　　　  //求整型的绝对值
　　double fabs (double);　　　　  //求实型的绝对值

vector

#include<vector>

vector构造方式：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 1、无参构造（默认构造）
vector<int> v1;

// 2、通过区间方式构造
vector<int> v2(v1.begin(), v1.end());

// 3、n个0方式构造
vector<int> v3(5);

// 4、n个element方式构造
vector<int> v4(5, 131);

// 5、拷贝构造
vector<int> v5(v4);
1
2
3
4
5
6
7
8
9
push_back();	//在最后添加一个元素，参数为要添加的值
pop_back();		//删除最后一个元素
begin();
end();
insert();
erase();
find();
at();
size();

insert()

三种用法：

1.在指定位置loc前插入值为val的元素，返回指向这个元素的迭代器

2.在指定位置loc前插入num个值为val的元素

3.在指定位置loc前插入区间[start, end)的所有元素 ，返回元素的大小个数

a.insert(a.begin(),b,begin(),b.end());//在a的前面插入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
#include <iostream>
#include <vector>
int main ()
{
  std::vector<int> myvector (3,100);
  std::vector<int>::iterator it;
 
  it = myvector.begin();
//------------ 1 ------------
  it = myvector.insert ( it , 200 );
//------------ 2 ------------
  myvector.insert (it,2,300);
 
  // "it" no longer valid, get a new one:
  it = myvector.begin();
 
  std::vector<int> anothervector (2,400);
//------------ 3 ------------
  myvector.insert (it+2,anothervector.begin(),anothervector.end());
 
  int myarray [] = { 501,502,503 };
//------------ 3 ------------
  myvector.insert (myvector.begin(), myarray, myarray+3);
 
  std::cout << "myvector contains:";
  for (it=myvector.begin(); it<myvector.end(); it++)
    std::cout << ' ' << *it;
  std::cout << '\n';
 
  return 0;
}
//最终输出：myvector contains: 501 502 503 300 300 400 400 200 100 100 100

erase()

两个函数原型：

iterator erase(iterator position);

iterator erase(iterator first, iterator last); // 返回指向下一个元素的迭代器

1
2
3
4
5
6
7
8
9
10
11
for (auto p1 = v1.begin(); p1 != v1.end();)//auto p1 = v1.begin()
{
    if (*p1 == 9)
    {
        p1=v1.erase(p1);
    }
    else
    {
        p1++;
    }
}

string

#include<string>

1
2
3
4
5
6
7
8
9
10
data();       // 返回指向自己的第一个字符的const char*指针，指向的内存最后以空字符结尾
			 // c_str()与data()类似，但指针指向的内存最后 无 空字符		
+=            // 连接操作符
append();
insert();
find();       // if not include, return iterator::end()
replace();
size();
substr();	 //子串拷贝
swap();

data()

append()

常用函数原型：

1
2
3
4
5
6
7
8
9
10
basic_string &append( const basic_string &str );
basic_string &append( const char *str );

basic_string &append( const basic_string &str, size_type index, size_type len );

basic_string &append( const char *str, size_type num );

basic_string &append( size_type num, char ch );

basic_string &append( input_iterator start, input_iterator end );

append() 函数可以完成以下工作：

在字符串的末尾添加str

在字符串的末尾添加str的子串，子串以index索引开始，长度为len

在字符串的末尾添加str中的num个字符

在字符串的末尾添加num个字符ch

在字符串的末尾添加以迭代器start和end表示的字符序列

insert()

大概与vector的insert()类似

find()

1
2
3
4
5
6
7
8
9
string str1, str2;
char c;
str1.find(str2);//从串str1中查找时str2，返回str2中首个字符在str1中的地址

str1.find(str2,5);//从str1的第5个字符开始查找str2

str1.find(c);//在str1中查找字符c并返回第一个查找到的地址

   str1.find("str2",2 , 2);//从str1中的第二个字符开始查找of big的前两个字符

查找字符

1
2
3
4
5
//string.find()返回值
//std::string 的方法 find，返回值类型是std::string::size_type， 对应的是查找对象在字符串中的位置（从0开始）

//如果未查找到，该返回值是一个很大的数据（4294967295），判断时与std::string::npos 进行对比
if(guess.find(secret[i],0)!=string::npos)

string类find()

replace()

所有用法举例如下：

1
2
3
4
5
6
7
8
9
str=str.replace(str.find("a"),2,"abc");  
//用str替换指定字符串从起始位置pos开始长度为len的字符              
//string& replace (size_t pos, size_t len, const string& str); 
str=str.replace(str.begin(),str.begin()+5,"abc"); 
//用str替换 迭代器起始位置 和 结束位置 之间的字符 
//string& replace (const_iterator i1, const_iterator i2, const string& str);
str = str.replace(0,6,3,'!');
//用重复n次的c字符替换从指定位置pos长度为len的内容 
//string& replace (size_t pos, size_t len, size_t n, char c);

substr()

C++ 中substr()函数有三种用法，如下所示：

1
2
3
string x=s.substr()                 //默认时的长度为从开始位置到尾
string y=s.substr(5)               //获得字符串s中 从第5位开始到尾的字符串
string z=s.substr(5,3);         //获得字符串s中 从第5位开始的长度为3的字符串

string->number

1
2
std::string str;
int i = std::stoi(str);

同样, 可以使用 stol(long), stof(float), stod(double) 等

number->string

string to_string (int val);参数可以是任意数字类型

set

#include<set>

1
2
3
// set的特性是，所有元素都会根据元素的键值自动排序.
// set的元素不像map那样可以同时拥有实值(value)和键值(key),set元素的键值就是实值，实值就是键值。
// set不允许两个元素有相同的键值.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
	set<int> numSet;
//遍历
	numSet.insert(numList[i]);
//查找，find 返回一个迭代器，如果查找失败会返回end()元素，否则成功
	if(numSet.find(findNum)!=numSet.end());
//删除，erase的返回值总是０和１，若返回０，表示删除的元素不在set中,如
	 int eraseReturn=numSet.erase(1);
//set.earse返回值是删除的迭代器的下一个，所以可以使用 iter = set.earse(iter)，也可以使用 set.earse(iter++)
	for(set<int>::iterator it=numSet.begin() ;it!=numSet.end();)
    {
        cout<<*it<<" occurs "<<endl;
        if(2==*it)
        {
            cout<<*it <<"delete"<<endl;
            it=numSet.erase(it);
            //numSet.earse(it++)
        }
        else
            it++;
    }
//赋值，set支持'='运算符赋值

取取并集，交集，差集

1
2
3
4
5
6
7
8
9
10
//set_union			取并集运算
set_union(A.begin(),A.end(),B.begin(),B.end(),inserter( C1 , C1.begin() ) );    
//set_intersection	 取交集运算
set_intersection(A.begin(),A.end(),B.begin(),B.end(),inserter( C2 , C2.begin() ));
//set_difference     取差集运算
set_difference( A.begin(), A.end(),B.begin(), B.end(),inserter( C3, C3.begin() ) );
//上述三种函数结果均保存在C1/C2/C3中
//还有一种写法如下：
set_union(A.begin(),A.end(),B.begin(),B.end(),ostream_iterator(cout," "));
//这里的第五个参数的意思是将A、B取并集后的结果直接输出，（cout," "）双引号里面是：用于间隔集合元素的符号（如这里的空格）

map

#include<map>

map<string, int> mapStudent;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
begin()         //返回指向map头部的迭代器
clear(）        //删除所有元素
count()         //返回指定元素出现的次数, (帮助评论区理解： 因为key值不会重复，所以只能是1 or 0)
empty()         //如果map为空则返回true
end()           //返回指向map末尾的迭代器
equal_range()   //返回特殊条目的迭代器对
erase()         //删除一个元素
find()          //查找一个元素
get_allocator() //返回map的配置器
insert()        //插入元素
key_comp()      //返回比较元素key的函数
lower_bound()   //返回键值>=给定元素的第一个位置
max_size()      //返回可以容纳的最大元素个数
rbegin()        //返回一个指向map尾部的逆向迭代器
rend()          //返回一个指向map头部的逆向迭代器
size()          //返回map中元素的个数
swap()          //交换两个map
upper_bound()   //返回键值>给定元素的第一个位置
value_comp()    //返回比较元素value的函数

插入元素：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 定义一个map对象
map<int, string> mapStudent;
 
// 第一种 用insert函數插入pair
mapStudent.insert(pair<int, string>(000, "student_zero"));
 
// 第二种 用insert函数插入value_type数据
mapStudent.insert(map<int, string>::value_type(001, "student_one"));
 
// 第三种 用"array"方式插入
mapStudent[123] = "student_first";
mapStudent[456] = "student_second";

//前两种在插入的key为map内已有key时会失败，第三种会修改对应value的值

简短的遍历方式

1
2
3
4
for (auto & [key,val] : mapSum) 
    if (key.substr(0, prefix.size()) == prefix) 
        ans += val;
return ans;

查找元素：

1
2
3
4
5
6
7
// find 返回迭代器指向当前查找元素的位置否则返回map::end()位置
iter = mapStudent.find("123");
 
if(iter != mapStudent.end())
       cout<<"Find, the value is"<<iter->second<<endl;
else
   cout<<"Do not Find"<<endl;

删除与清空元素：

1
2
3
4
5
6
7
8
9
10
//迭代器刪除
iter = mapStudent.find("123");
mapStudent.erase(iter);
 
//用关键字刪除
int n = mapStudent.erase("123"); //如果刪除了會返回1，否則返回0
 
//用迭代器范围刪除 : 把整个map清空
mapStudent.erase(mapStudent.begin(), mapStudent.end());
//等同于mapStudent.clear()

stack&queue

priority_queue

STL 在头文件中提供优先队列 priority_queue，在任意时间都能取出队列中的最大值，队列首部总是最大值

使用 push() 向优先队列中加入元素，其时间复杂度为O(logn)

使用 top() 获取优先队列中最大的元素（并不删除），其时间复杂度为O(1)

使用 pop() 删除优先队列中最大元素，其时间复杂度为O(logn)

使用 empty() 判断优先队列是否为空

也可以定义为优先最小值：

1
priority_queue< T,vector<T>,greater<T> >q;//注意greater<int>后面要加空格，否则计算机会当右移运算符.

greater 和 less是 std 实现的两个仿函数（就是使一个类的使用看上去像一个函数。其实现就是类中实现一个operator()，这个类就有了类似函数的行为，就是一个仿函数类了）

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
//对于字符串按照字典序排序

//对于pair先比较第一个元素，第一个相等比较第二个

//对于自定义类型
#include <iostream>
#include <queue>
using namespace std;

//方法1
struct tmp1 //运算符重载<
{
    int x;
    tmp1(int a) {x = a;}
    bool operator<(const tmp1& a) const
    {
        return x < a.x; //大顶堆
    }
};

//方法2
struct tmp2 //重写仿函数
{
    bool operator() (tmp1 a, tmp1 b) 
    {
        return a.x < b.x; //大顶堆
    }
};

int main() 
{
    priority_queue<int> a; 
    //等同于 priority_queue<int, vector<int>, less<int> > a;
    
    tmp1 a(1);
    tmp1 b(2);
    tmp1 c(3);
    priority_queue<tmp1> d;
    d.push(b);
    d.push(c);
    d.push(a);
    while (!d.empty()) 
    {
        cout << d.top().x << '\n';
        d.pop();
    }
    cout << endl;

    priority_queue<tmp1, vector<tmp1>, tmp2> f;
    f.push(c);
    f.push(b);
    f.push(a);
    while (!f.empty()) 
    {
        cout << f.top().x << '\n';
        f.pop();
    }
}

deque

#include <deque>双端队列

1
2
3
4
5
6
7
8
size()
empty()
clear()
front()/back()
push_back()/pop_back()
push_front()/pop_front()
begin()/end()
[]

构造

1
2
3
4
5
6
7
deque():创建一个空deque

deque(int nSize):创建一个deque,元素个数为nSize

deque(int nSize,const T& t):创建一个deque,元素个数为nSize,且值均为t

deque(const deque &):复制构造函数

增加

1
2
3
4
5
6
7
8
9
void push_front(const T& x):双端队列头部增加一个元素X

void push_back(const T& x):双端队列尾部增加一个元素x

iterator insert(iterator it,const T& x):双端队列中某一元素前增加一个元素x

void insert(iterator it,int n,const T& x):双端队列中某一元素前增加n个相同的元素x

void insert(iterator it,const_iterator first,const_iteratorlast):双端队列中某一元素前插入另一个相同类型向量的[forst,last)间的数据

删除

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
dec.pop_back();  //尾部删除
dec.pop_front();  //头部删除
    
//erase操作
//iterator erase (iterator position);
dec.erase(dec.begin());
//iterator erase (iterator first, iterator last);
dec.erase(dec.end()-3, dec.end());

//删除指定元素
deque<string>::iterator iter;
for(iter = dec.begin(); iter != dec.end(); )
{
    if(*iter == "bbb")
        iter = dec.erase(iter);
    else
        ++iter;
} 

dec.back();  //返回最后一个元素
dec.front();  //返回第一个元素
dec.empty();  //判断是否为空
 
//调整容器大小，不足以参数2补充
dec.resize(5);
dec.resize(5,"hello");
  
dec.size();  //容器大小
deque<string> s_dec;
swap(s_dec, dec);  //交换容器内容
s_dec.swap(dec);   //交换容器内容
dec.clear();  //清空

//反序输出
deque<string>::reverse_iterator rit;
for(rit = dec.rbegin(); rit != dec.rend(); ++rit)
{
    cout<<*rit<<endl;
}

list

构造函数：

list() 声明一个空列表；

list(n) 声明一个有n个元素的列表，每个元素都是由其默认构造函数T()构造出来的

list(n,val) 声明一个由n个元素的列表，每个元素都是由其复制构造函数T(val)得来的

list(n,val) 声明一个和上面一样的列表

list(first,last) 声明一个列表，其元素的初始值来源于由区间所指定的序列中的元素

begin()和end()：通过调用list容器的成员函数begin()得到一个指向容器起始位置的iterator，可以调用list容器的 end() 函数来得到list末端下一位置，相当于：int a[n]中的第n+1个位置a[n]，实际上是不存在的，不能访问，经常作为循环结束判断结束条件使用。

push_back() 和push_front()：使用list的成员函数push_back和push_front插入一个元素到list中。其中push_back()从list的末端插入，而 push_front()实现的从list的头部插入。

empty()：利用empty() 判断list是否为空。

resize()： 如果调用resize(n)将list的长度改为只容纳n个元素，超出的元素将被删除，如果需要扩展那么调用默认构造函数T()将元素加到list末端。如果调用resize(n,val)，则扩展元素要调用构造函数T(val)函数进行元素构造，其余部分相同。

clear()： 清空list中的所有元素。

front()和back()： 通过front()可以获得list容器中的头部元素，通过back()可以获得list容器的最后一个元素。但是有一点要注意，就是list中元素是空的时候，这时候调用front()和back()会发生什么呢？实际上会发生不能正常读取数据的情况，但是这并不报错，那我们编程序时就要注意了，个人觉得在使用之前最好先调用empty()函数判断list是否为空。

pop_back和pop_front()：通过删除最后一个元素，通过pop_front()删除第一个元素；序列必须不为空，如果当list为空的时候调用pop_back()和pop_front()会使程序崩掉。

assign()：具体和vector中的操作类似，也是有两种情况，第一种是：l1.assign(n,val)将 l1中元素变为n个T(val）。第二种情况是：l1.assign(l2.begin(),l2.end())将l2中的从l2.begin()到l2.end()之间的数值赋值给l1。

swap()：交换两个链表(两个重载)，一个是l1.swap(l2); 另外一个是swap(l1,l2)，都可能完成连个链表的交换。

reverse()：通过reverse()完成list的逆置。

merge()：合并两个链表并使之默认升序(也可改)，l1.merge(l2，greater()); 调用结束后l2变为空，l1中元素包含原来l1 和 l2中的元素，并且排好序，升序。其实默认是升序，greater()可以省略，另外greater()是可以变的，也可以不按升序排列。

看一下下面的程序：

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

using namespace std;

int main()
{
    list<int> l1;
    list<int> l2(2,0);
    list<int>::iterator iter;
    l1.push_back(1);
    l1.push_back(2);
    l2.push_back(3);
    l1.merge(l2,greater<int>());//合并后升序排列，实际上默认就是升序
    for(iter = l1.begin() ; iter != l1.end() ; iter++)
    {
        cout<<*iter<<" ";
    }
    cout<<endl<<endl;
    if(l2.empty())
    {
        cout<<"l2 变为空 ！！";
    }
    cout<<endl<<endl;
    return 0;
}

运行结果：

img

insert()：在指定位置插入一个或多个元素(三个重载)：

l1.insert(l1.begin(),100); 在l1的开始位置插入100。

l1.insert(l1.begin(),2,200); 在l1的开始位置插入2个100。

l1.insert(l1.begin(),l2.begin(),l2.end());在l1的开始位置插入l2的从开始到结束的所有位置的元素。

erase()：删除一个元素或一个区域的元素(两个重载)

l1.erase(l1.begin()); 将l1的第一个元素删除。

l1.erase(l1.begin(),l1.end()); 将l1的从begin()到end()之间的元素删除。

vector-list-deque

三个序列STL比较

「ctype.h」

isalpha()用来判断一个字符是否为字母

isalnum()用来判断一个字符是否为数字或者字母，也就是说判断一个字符是否属于a到z/A到Z/0~9

islower()用来判断一个字符是否为小写字母，也就是是否属于a~z

isupper()用来判断一个字符是否为大写字母

isdigit() 用来检测一个字符是否是十进制数字。十进制数字包括：0 1 2 3 4 5 6 7 8 9

tolower()
将大写字母转换为小写字母，成功返回对应的小写字母，失败返回大写字母本身，返回值为int类型

toupper()
将小写字母转换为大写字母，成功返回对应的大写字母，失败返回小写字母本身，返回值为int类型

板子

random number

1
2
3
4
5
6
7
8
9
10
11
12
#include <stdlib.h>
#include <iostream>
#include <time.h>
#define MAX 100
using namespace std;
int  main()
{
    srand( (unsigned)time(NULL) );
    for(int i=0; i<10; i++)
        cout<<rand()%MAX<<endl;
    return 0;
}

字符串filter分词

  • 使用字符串流stringstream，它将流与存储在内存中的string对象绑定起来

    上代码：

    默认分词分隔符为：空格、换行符\n、缩进符\t

    stringstream

    用指定分隔符分词：

    指定字符

gcd（求x，y的最大公约数）

#include<algorithm>

__gcd(a,b)//a和b均为整型，注意是两个下划线__

1
2
3
4
5
6
7
8
9
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
	int a,b;
	cin>>a>>b;
	cout<<__gcd(a,b)<<endl;
}

基础算法

快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
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);
}

归并排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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];
}

整数二分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
bool check(int x) {/* ... */} // 检查x是否满足某种性质

// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：
int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;    // check()判断mid是否满足性质
        else l = mid + 1;
    }
    return l;
}
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：
int bsearch_2(int l, int r)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

浮点数二分

1
2
3
4
5
6
7
8
9
10
11
12
13
bool check(double x) {/* ... */} // 检查x是否满足某种性质

double bsearch_3(double l, double r)
{
    const double eps = 1e-6;   // eps 表示精度，取决于题目对精度的要求
    while (r - l > eps)
    {
        double mid = (l + r) / 2;
        if (check(mid)) r = mid;
        else l = mid;
    }
    return l;
}

高精度加法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// C = A + B, A >= 0, B >= 0
vector<int> add(vector<int> &A, vector<int> &B)
{
    if (A.size() < B.size()) return add(B, A);

    vector<int> C;
    int t = 0;
    for (int i = 0; i < A.size(); i ++ )
    {
        t += A[i];
        if (i < B.size()) t += B[i];
        C.push_back(t % 10);
        t /= 10;
    }

    if (t) C.push_back(t);
    return C;
}

或者用__int128实现

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
#include <bits/stdc++.h>
using namespace std;
inline __int128 read()
{
    __int128 x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}

inline void write(__int128 x)
{
    if(x<0)
    {
        putchar('-');
        x=-x;
    }
    if(x>9)
        write(x/10);
    putchar(x%10+'0');
}

int main()
{
    __int128 a = read();
    __int128 b = read();
    write(a + b);
    return 0;
}

高精度减法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// C = A - B, 满足A >= B, A >= 0, B >= 0
vector<int> sub(vector<int> &A, vector<int> &B)
{
    vector<int> C;
    for (int i = 0, t = 0; i < A.size(); i ++ )
    {
        t = A[i] - t;
        if (i < B.size()) t -= B[i];
        C.push_back((t + 10) % 10);
        if (t < 0) t = 1;
        else t = 0;
    }

    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

高精度乘低精度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// C = A * b, A >= 0, b >= 0
vector<int> mul(vector<int> &A, int b)
{
    vector<int> C;

    int t = 0;
    for (int i = 0; i < A.size() || t; i ++ )
    {
        if (i < A.size()) t += A[i] * b;
        C.push_back(t % 10);
        t /= 10;
    }

    while (C.size() > 1 && C.back() == 0) C.pop_back();

    return C;
}

高精度除以低精度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// A / b = C ... r, A >= 0, b > 0
vector<int> div(vector<int> &A, int b, int &r)
{
    vector<int> C;
    r = 0;
    for (int i = A.size() - 1; i >= 0; i -- )
    {
        r = r * 10 + A[i];
        C.push_back(r / b);
        r %= b;
    }
    reverse(C.begin(), C.end());
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

数据结构

KMP

用例题说明

给定两个串P和S及他们的长度，求P在S中出现的所有下标（从0开始）

KMP

上题使用string.find()性能会比KMP差一点

使用find()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<bits/stdc++.h>
using namespace std;

int main() {
    int n, m, idx;
    string s, p;
    cin >> n >> p >> m >> s;
    idx = s.find(p);
    while(idx != std::string::npos) {
        cout << idx << ' ';
        idx = s.find(p, idx + 1);//在s中，从idx+1位置开始，查找字符串p出现的位置
    }
    return 0;
}

手撕KMP

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
#include <iostream>
using namespace std;
const int N = 100010, M = 1000010;

int n, m;
int ne[N];
char s[M], p[N];

int main()
{
	cin >> n >> p >> m >> s;
    /*计算next数组*/
	for (int i = 1, j = 0; i < n; i++)
	{
		while (j && p[i] != p[j])
			j = ne[j - 1];
		if (p[i] == p[j])
			j++;
		ne[i] = j;
	}
	/*计算next数组*/
	
	// for (int i = 0; i < n; i ++ )
	//     cout<<ne[i];

    /*字符串匹配*/
	for (int i = 0, j = 0; i < m; i++)
	{
		while (j && s[i] != p[j])
			j = ne[j - 1];
		if (s[i] == p[j])
			j++;
	
		if (j == n)
		{
		    /*匹配成功后的逻辑*/
			printf("%d ", i - n + 1);
			/*匹配成功后的逻辑*/
			j = ne[j - 1];
		}
	}
	/*字符串匹配*/

	return 0;
}

搜索与图论

树与图的存储

树是一种特殊的图，与图的存储方式相同。
对于无向图中的边ab，存储两条有向边a->b, b->a。
因此我们可以只考虑有向图的存储。

(1) 邻接矩阵：g[a][b] 存储边a->b

(2) 邻接表：

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);

树与图的遍历

时间复杂度 O(n+m)， n 表示点数，m 表示边数

DFS：

1
2
3
4
5
6
7
8
9
10
int dfs(int u)
{
    st[u] = true; // st[u] 表示点u已经被遍历过

    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!st[j]) dfs(j);
    }
}

BFS：

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);
        }
    }
}

拓扑排序

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
//时间复杂度 O(n+m), n 表示点数，m 表示边数
    queue<int>q;
    vector<int>edge[n];
    for(int i=0;i<n;i++)  //n  节点的总数
        if(in[i]==0) q.push(i);  //将入度为0的点入队列
    vector<int>ans;   //ans 为拓扑序列
    while(!q.empty())
    {
        int p=q.front(); q.pop(); // 选一个入度为0的点，出队列
        ans.push_back(p);
        for(int i=0;i<edge[p].size();i++)
        {
            int y=edge[p][i];
            in[y]--;
            if(in[y]==0)
                q.push(y);  
        }
    }
    if(ans.size()==n)   
    {
        for(int i=0;i<ans.size();i++)
            printf( "%d ",ans[i] );
        printf("\n");
    }
    else printf("No Answer!\n");   //  ans 中的长度与n不相等，就说明无拓扑序列

其他

cin cout优化

1
2
3
ios::sync_with_stdio(false);
cin.tie(0);
//注意：添加这两条语句之后就只能使用cin cout进行输入输出 而不能使用printf和scanf

tips

  • 较大的数要用long long存
  • ans = (ans + MOD) % MOD;//避免负数取模