常用函数

    C++ STL标准库中还提供有 lower_bound()、upper_bound()、equal_range() 以及 binary_search() 这 4 个查找函数，它们的底层实现采用的都是二分查找的方式。

1 lower_bound()函数

#include <iostream>     // std::cout
#include <algorithm>    // std::lower_bound
#include <vector>       // std::vector
using namespace std;
//以普通函数的方式定义查找规则
bool mycomp(int i, int j) { return i > j; }
//以函数对象的形式定义查找规则
class mycomp2 {
public:
    bool operator()(const int& i, const int& j) {
        cout << "=== i: " << i << " === j: " << j << "\n" ;
                return i > j;
    }
};
int main() {
    int a[5] = { 1,2,3,4,5 };
    //从 a 数组中找到第一个不小于 3 的元素
    int* p = lower_bound(a, a + 5, 3);
    cout << "*p = " << *p << endl;
    vector<int> myvector{ 4,5,3,1,2 };
    //根据 mycomp2 规则，从 myvector 容器中找到第一个违背 mycomp2 规则的元素
    vector<int>::iterator iter = lower_bound(myvector.begin(), myvector.end(), 3, mycomp2());
    cout << "*iter = " << *iter;
    return 0;
}

2 upper_bound()函数

#include <iostream>     // std::cout
#include <algorithm>    // std::upper_bound
#include <vector>       // std::vector
using namespace std;
//以普通函数的方式定义查找规则
bool mycomp(int i, int j) { return i > j; }
//以函数对象的形式定义查找规则
class mycomp2 {
public:
    bool operator()(const int& i, const int& j) {
        cout << "=== i: " << i << " === j: " << j << "\n";
        return i > j;
    }
};
int main() {
    int a[5] = { 1,2,3,4,5 };
    //从 a 数组中找到第一个大于 3 的元素
    int* p = upper_bound(a, a + 5, 3);
    cout << "*p = " << *p << endl;
    vector<int> myvector{ 4,5,3,1,2 };
    //根据 mycomp2 规则，从 myvector 容器中找到第一个违背 mycomp2 规则的元素
    vector<int>::iterator iter = upper_bound(myvector.begin(), myvector.end(), 3, mycomp2());
    cout << "*iter = " << *iter;
    return 0;
}

此程序中演示了 upper_bound() 函数的 2 种适用场景，其中 a[5] 数组中存储的为升序序列；而 myvector 容器中存储的序列虽然整体是乱序的，但对于目标元素 3 来说，所有符合 mycomp2(3, element) 规则的元素都位于其左侧，不符合的元素都位于其右侧，因此 upper_bound() 函数仍可正常执行。

3 equel_range()函数

#include <iostream>     // std::cout
#include <algorithm>    // std::equal_range
#include <vector>       // std::vector
using namespace std;
//以普通函数的方式定义查找规则
bool mycomp(int i, int j) { return i > j; }
//以函数对象的形式定义查找规则
class mycomp2 {
public:
    bool operator()(const int& i, const int& j) {
        cout << "=== i: " << i << " === j: " << j << "\n";
        return i > j;
    }
};
int main() {
    int a[9] = { 1,2,3,4,4,4,5,6,7 };
    //从 a 数组中找到所有的元素 4
    pair<int*, int*> range = equal_range(a, a + 9, 4);
    cout << "a[9]：";
    for (int* p = range.first; p < range.second; ++p) {
        cout << *p << " ";
    }
    vector<int>myvector{ 7,8,5,4,3,3,3,3,2,1 };
    pair<vector<int>::iterator, vector<int>::iterator> range2;
    //在 myvector 容器中找到所有的元素 3
    range2 = equal_range(myvector.begin(), myvector.end(), 3, mycomp2());
    cout << "\nmyvector：";
    for (auto it = range2.first; it != range2.second; ++it) {
        cout << *it << " ";
    }
    return 0;
}

4 binary_search()函数

#include <iostream>     // std::cout
#include <algorithm>    // std::binary_search
#include <vector>       // std::vector
using namespace std;
//以普通函数的方式定义查找规则
bool mycomp(int i, int j) { return i > j; }
//以函数对象的形式定义查找规则
class mycomp2 {
public:
    bool operator()(const int& i, const int& j) {
        cout << "=== i: " << i << " === j: " << j << "\n";
        return i > j;
    }
};
int main() {
    int a[7] = { 1,2,3,4,5,6,7 };
    //从 a 数组中查找元素 4
    bool haselem = binary_search(a, a + 9, 4);
    cout << "haselem：" << haselem << endl;
    vector<int>myvector{ 4,5,3,1,2 };
    //从 myvector 容器查找元素 3
    bool haselem2 = binary_search(myvector.begin(), myvector.end(), 3, mycomp2());
    cout << "haselem2：" << haselem2;
    return 0;
}

5 全排列函数

next_permutation()

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
string s=“bca”;
sort(s.begin(),s.end());//字符串内部排序,得到最小的排列"abc"
do{
cout<<s<<" ";
}while(next_permutation(s.begin(),s.end()));
//s.end()指向最后一个字符的下一个位置

#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
    int a[3]={1,2,3};
    do
    {
        for(int i=0;i<3;i++)
            cout<<a[i]<<' ';
        cout<<endl;;
    }
     while(next_permutation(a,a+3));

自定义排序

大小写字母排序

题目：您将要编写一个程序，该程序必须根据给定的字母集生成所有可能的单词。
示例：给定单词“ abc”，您的程序应-通过探索三个字母的所有不同组合-输出单词“ abc”，“ acb”，“ bac”，“ bca”，“ cab”和“ cba”。
在从输入文件中提取的单词中，某些字母可能会出现多次。 对于给定的单词，您的程序不应多次产生相同的单词，并且单词应按字母升序输出。
输入：输入由几个词组成。 第一行包含一个数字，给出要跟随的单词数。 接下来的每一行包含一个单词。 单词由A到Z的大写或小写字母组成。大写和小写字母应被视为不同。 每个单词的长度小于13。
Sample Input：
3
aAb
abc
acba
输出：对于输入中的每个单词，输出应包含可以使用给定单词的字母生成的所有不同单词。 由相同输入单词生成的单词应按字母升序输出。 大写字母位于相应的小写字母之前。
Sample Output
Aab
Aba
aAb
abA
bAa
baA
abc
acb
bac
bca
cab
cba
aabc
aacb
abac
abca
acab
acba
baac
baca
bcaa
caab
caba
cbaa

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
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>

using namespace std;

int cmp(char a, char b)            //自定义函数,实现字母大写排在小写前面的功能
{
	if (tolower(a) != tolower(b)) //tolower是将大写转化为小写,A-Z 65-90       a-z 97-122
		return tolower(a) < tolower(b);
	else
		return a < b;
}
int main()
{
	int n;
	cin >> n;
	string s="";
	while (n--)
	{
		cin >> s;
		int len = s.size();
		sort(s.begin(), s.end(), cmp);
		do
		{
			cout << s << endl;
		} while (next_permutation(s.begin(), s.end(), cmp)); //自定义函数的使用
	}
	system("pause");
	return 0;
}

prev_permutation()

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

include<iostream>
#include<algorithm>
using namespace std;
int a[] = {2, 1, 3};
int main(){
    // 首先输出其所有全排列展示
    sort(a, a + 3);
    do{
        cout << a[0] << ' ' << a[1] << ' ' << a[2] << endl;
    }while(next_permutation(a, a + 3));
    /* 输出结果
    1 2 3
    1 3 2
    2 1 3
    2 3 1
    3 1 2
    3 2 1
    */
}

6 实数函数及运算符

求幂次

pow(x,y);数据类型下x,y应为double型

移位运算符

x<<y == x*(2^y)
x>>y == x/(2^y)

STL排序sort函数

void sort(first,last);
void sort(first,last,comp);
复杂度为O(nlogn)，排序的范围为[first,last)，包括first不包括last。

初始化函数memset()

例如：memset(a,0,sizeof(a))

算法模板

1.排序算法

最常见，也是大一学生算法小白最浪费时间的去写的算法
在比赛中尽量使用Java，C++自带的排序算法，此类算法平均效率比初学者所学的冒泡排序和选择排序算法高，也可以减少很多写代码的时间。

//在c++中使用模板函数sort()
int x[10]= {9,6,3,8,5,2,7,4,1,0};
sort(x,x + 10);

排序算法的分类：
1插入：插入，折半插入，希尔
2交换：冒泡，快速
3选择：简单选择，堆
4归并：归并（不只二路归并）
5基数：

sort.png

  1插入排序

void insert_sort()
{
    for (int i = 1; i < n; i ++ )
    {
        int x = a[i];
        int j = i-1;
  while (j >= 0 && x < a[j])
    {
        a[j+1] = a[j];
        j -- ;
    }
    a[j+1] = x;
}
}

2选择排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void select_sort()
{
    for (int i = 0; i < n; i ++ )
    {
        int k = i;
        for (int j = i+1; j < n; j ++ )
        {
            if (a[j] < a[k])
                k = j;
        }
        swap(a[i], a[k]);
    }

}

3冒泡排序

void bubble_sort()
{
for (int i = n-1; i >= 1; i – )
{
bool flag = true;
for (int j = 1; j <= i; j ++ )
if (a[j-1] > a[j])
{
swap(a[j-1], a[j]);
flag = false;
}
if (flag) return;
}
}

4希尔排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void shell_sort()
{
    for (int gap = n >> 1; gap; gap >>= 1)
    {
        for (int i = gap; i < n; i ++ )
        {
            int x = a[i];
            int j;
            for (j = i; j >= gap && a[j-gap] > x; j -= gap)
                a[j] = a[j-gap];
            a[j] = x;
        }
    }
}

5快速排序（最快）

void quick_sort(int l, int r)
{
    if (l >= r) return ;
int x = a[l+r>>1], i = l-1, j = r+1;
while (i < j)
{
    while (a[++ i] < x);
    while (a[-- j] > x);
    if (i < j) swap(a[i], a[j]);
}
sort(l, j), sort(j+1, r);
}

6归并排序

void merge_sort(int l, int r)
{
    if (l >= r) return;
    int temp[N];
    int mid = l+r>>1;
    merge_sort(l, mid), merge_sort(mid+1, r);
    int k = 0, i = l, j = mid+1;
    while (i <= mid && j <= r)
    {
        if (a[i] < a[j]) temp[k ++ ] = a[i ++ ];
        else temp[k ++ ] = a[j ++ ];
}
while (i <= mid) temp[k ++ ] = a[i ++ ];
while (j <= r) temp[k ++ ] = a[j ++ ];
for (int i = l, j = 0; i <= r; i ++ , j ++ ) a[i] = temp[j];
}

7堆排序（须知此排序为使用了模拟堆，为了使最后一个非叶子节点的编号为n/2，数组编号从1开始）
https://www.cnblogs.com/wanglei5205/p/8733524.html

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
void down(int u)
{
    int t = u;
    if (u<<1 <= n && h[u<<1] < h[t]) t = u<<1;
    if ((u<<1|1) <= n && h[u<<1|1] < h[t]) t = u<<1|1;
    if (u != t)
    {
        swap(h[u], h[t]);
        down(t);
    }
}

int main()
{
    for (int i = 1; i <= n; i ++ ) cin >> h[i];
    for (int i = n/2; i; i -- ) down(i);
    while (true)
    {
        if (!n) break;
        cout << h[1] << ' ';
        h[1] = h[n];
        n -- ;
        down(1);
    }
    return 0;
}

8基数排序

int maxbit()
{
    int maxv = a[0];
    for (int i = 1; i < n; i ++ )
        if (maxv < a[i])
            maxv = a[i];
    int cnt = 1;
    while (maxv >= 10) maxv /= 10, cnt ++ ;
return cnt;
}
void radixsort()
{
    int t = maxbit();
    int radix = 1;for (int i = 1; i <= t; i ++ )
{
    for (int j = 0; j < 10; j ++ ) count[j] = 0;
    for (int j = 0; j < n; j ++ )
    {
        int k = (a[j] / radix) % 10;
        count[k] ++ ;
    }
    for (int j = 1; j < 10; j ++ ) count[j] += count[j-1];
    for (int j = n-1; j >= 0; j -- )
    {
        int k = (a[j] / radix) % 10;
        temp[count[k]-1] = a[j];
        count[k] -- ;
    }
    for (int j = 0; j < n; j ++ ) a[j] = temp[j];
    radix *= 10;
}
}

9计数排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void counting_sort()
{
    int sorted[N];
    int maxv = a[0];
    for (int i = 1; i < n; i ++ )
        if (maxv < a[i])
            maxv = a[i];
    int count[maxv+1];
    for (int i = 0; i < n; i ++ ) count[a[i]] ++ ;
    for (int i = 1; i <= maxv; i ++ ) count[i] += count[i-1];
    for (int i = n-1; i >= 0; i -- )
    {
        sorted[count[a[i]]-1] = a[i];
        count[a[i]] -- ;
    }
    for (int i = 0; i < n; i ++ ) a[i] = sorted[i];
}

10桶排序（基数排序是桶排序的特例，优势是可以处理浮点数和负数，劣势是还要配合别的排序函数）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
vector<int> bucketSort(vector<int>& nums) {
    int n = nums.size();
    int maxv = *max_element(nums.begin(), nums.end());
    int minv = *min_element(nums.begin(), nums.end());
    int bs = 1000;
    int m = (maxv-minv)/bs+1;
    vector<vector<int> > bucket(m);
    for (int i = 0; i < n; ++i) {
        bucket[(nums[i]-minv)/bs].push_back(nums[i]);
    }
    int idx = 0;
    for (int i = 0; i < m; ++i) {
        int sz = bucket[i].size();
        bucket[i] = quickSort(bucket[i]);
        for (int j = 0; j < sz; ++j) {
            nums[idx++] = bucket[i][j];
        }
    }
    return nums;
}

2.数论

GCD(最大公约数)和LCM(最小公倍数)

1
2
3
4
5
6
7
8
9
int gcd(int a,int b)
{
	return b?gcd(b,a%b):a;
} 
1234
int lcm(int a,int b)
{
	return a/gcb(a,b)*b;
}

素数判断

1
2
3
4
5
6
7
8
bool is_prime(long long n){
  If(n<=1) return false;
  For(long long i=2;i<=sqrt(n);i++)
{
If(n%i==0) return false;
}
Return true;
}

质数

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
bool isPrime(int a){	// 判断是否为质数
	if(a == 2){
		return true;
	}
	if(a < 2 || a % 2 == 0){
		return false;
	}
	for(int i = 3;i * i <= a;i += 2){
		if(a % i == 0){
			return false;
		}
	}
	return true;
}
bool isRealPrime(int a){	// 判断是否为纯质数
	if(!isPrime(a)){
		return false;
	}
	do{
		if(!isPrime(a % 10)){
			return false;
		}
		a /= 10;
	}while(a != 0);
	return true;
}

快速幂

采用倍增的原理

1
2
3
4
5
6
7
8
9
10
int fastpow(int a,int b)//计算a的n次方
{
  Int ans=1;
  while(n){
    If(n&1) ans*=a; 
    a*=a;
    n>>=1;//n右移一位，把刚处理过的n的最后一位去掉 
	}
  return ans;
}

幂运算的结果往往很大，一般题目会要求先取模再输出。根据取模的性质有:

1
a^n mod m = (a mod m)^n mod m。
1
2
3
4
5
6
7
8
9
10
11
Ll fastpow(ll a,ll b)
{
  Ll ans=1;
  A%=mod;
  while(n){
    If(n&1) ans=(ans*a)%mod;
    A=a*a%modl
    N>>=1;
}
Return ans;
}

//如保留后四位数,则需要%10000
//往往这种题都会跟随大量的for循环
for(int i = 0; i < N; i++){
sum = (sum + n) % 10000;
}

日期闰年：

if((i%4==0&&i%100!=0)||(i%400==0)){//闰年2月29天}

判断是否合法

1
2
3
4
5
6
7
8
9
10
11
12
int months[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

if (!month || month >= 13 || !day) return false;

    if (month != 2 && day > months[month]) return false;
    if (month == 2)
    {
        bool leap = year % 4 == 0 && year % 100 || year % 400 == 0;
        if (day > 28 + leap) return false;
    }

    return true;

进制转换:

九进制转十进制,111=199+19+11=;

前缀和：

输入一个n 行 m 列的整数矩阵，再输入 q 个询问，每个询问包含四个整数 x1,y1,x2,y2

，表示一个子矩阵的左上角坐标和右下角坐标。对于每个询问输出子矩阵中所有数的和。

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
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N = 1010;
int array[N][N];
int n,m,q;
int st[N][N];
int x1,x2,y1,y2;
int main(){
    cin>>n>>m>>q;
    for(int i = 1;i<=n;i++)
        {
            for(int j = 1;j<=m;j++)
            {
                cin>>array[i][j];
                st[i][j] =st[i - 1][j] + st[i][j - 1] - st[i - 1][j - 1]+st[i][j]+array[i][j];
                // cout<<st[i][j]<<" ";
            }
            // cout << endl;
        }
    for(int i =0;i<q;i++){
        cin>>x1;
        cin>>y1;
        cin>>x2;
        cin>>y2;
        int sum = st[x2][y2] - st[x1-1][y2]-st[x2][y1-1]+st[x1-1][y1-1];
        cout<<sum<<endl;   
    }
    return 0;
}

3.数据结构

选择合适的数据结构解题可以提高算法效率，减少代码复杂度。
若要想取得比较好的成绩, 必须熟悉几种数据结构

//比赛中常用的数据结构（Java）
Hashmap //最常用
ArrayList //可以替代数组,底层为可动态扩容数组
Queue //队列,bfs算法时使用
Deque Stack //栈

4.String

输入输出

1
scanf("%d:%d:%d %d:%d:%d (+%d)", &h1, &m1, &s1, &h2, &m2, &s2, &d); // scanf 超棒

第一行包含整数 N，表示后面共有N行数据。接下来 N 行，每行包含空格分开的若干个（不大于100个）正整数（不大于100000），每个整数代表一个ID号。

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<bits/stdc++.h>
using namespace std;
#define ios\
    ios::sync_with_stdio(false);\
    cin.tie(nullptr);\
    cout.tie(nullptr)
const int N = 100;
const int M = 1e5;
int n;
int nums[M];
int cnt[M];
int main(){
    cin>>n;
    int a =0;
    int que=-1,chong=-1;
    int minnum=M+1,maxnum=-1;
    for(int i=0;i<n;i++) {
        while(true){
            cin>>nums[a];
            minnum = min(minnum,nums[a]);
            maxnum = max(maxnum,nums[a]);
            cnt[nums[a]]++;

            a++;
            
            char c = getchar();
            if(c!=' ') break;
        }
    }
    for(int i=minnum;i<=maxnum;i++){
        // cout<<cnt[i]<<" ";
        if(cnt[i]==0) que = i;
        if(cnt[i]>1)   chong = i;
    }
    // cout<<endl;
    cout<<que<<" "<<chong<<endl;
    return 0;
}

C++字符串函数

find()函数：查找
substr()函数：查子串

按字典序反序排序

1
2
3
bool cmp(string a,string b){
  return a+b>b+a;
}

5.递推

前面的选择影响后面的结果

费解的开关

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
#include<bits/stdc++.h>
using namespace std;
int n;
const int N = 6;
char lamp[N][N], backup[N][N];
string status[5];
int dx[5] = { 0,1,-1,0,0 }, dy[5] = { 0,0,0,1,-1 };
void turnlamp(int x, int y) {
    for (int i = 0; i < 5; i++) {
        int a = x + dx[i], b = y + dy[i];
        if (a < 0 || a >= 5 || b < 0 || b >= 5) continue;
        lamp[a][b] ^= 1;
    }
}

int main() {

    cin >> n;
    for (int c = 0; c < n; c++) {
        for (int i = 0; i < 5; i++)
                cin >> lamp[i];
        
        int step = 7;
        for (int i = 0; i < 1 << 5; i++)
        {
            int count = 0;
            memcpy(backup, lamp, sizeof lamp);
            for (int j = 0; j < 5; j++)
            {
                if (i >> j & 1) {
                    turnlamp(0, j);
                    count++;
                }
            }
            // cout<< count<<" ";
            for (int k = 0; k < 4; k++)
            {
                for (int z = 0; z < 5; z++) {
                    if (lamp[k][z]=='0') {
                        turnlamp(k + 1, z);
                        count++;
                    }
                }
            }
            // cout<< count<<" ";
            bool dark=false;
            for (int k = 0; k < 5; k++) {
                if (lamp[4][k] == '0') {
                    dark = true;
                    break;
                }
            }
            if(!dark) step = min(step, count);
            memcpy(lamp, backup, sizeof lamp);
            // cout<< count<<" ";
            // cout<<endl;
        }
        if(step>6) step=-1;
        cout<<step<<endl;
    }
    return 0;

6.深度优先搜索（DFS）和广度优先搜索（BFS）

dfs： 剪枝优化

void   dfs(){
    if()   //收获结果
    for(){
        if()   continue;           //剪枝
        //选择
        dfs();   //递归
        //回溯
    }

}

水果糖包成4颗一包和7颗一包的两种。糖果不能拆包卖。当然有些糖果数目是无法组合出来的，比如要买 10 颗糖。你可以用计算机测试一下，在这种包装情况下，最大不能买到的数量是17。大于17的任何数字都可以用4和7组合出来。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<bits/stdc++.h>
using namespace std;
int n,m;
bool dfs(int m,int p,int q){
    if(m==0) return true;
    else{
        if(m>=p&&dfs(m-p,p,q)) return true;
        if(m>=q&&dfs(m-q,p,q)) return true;
        return false;
    }
}

int main(){
    cin>>n>>m;
    int res;
    int min1 = min(n,m);
    for(int i=min1;i<=1000;i++)
        if(!dfs(i,m,n)) res = i;
    
    cout<<res<<endl;
    
}

bfs： 去重优化

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

void  bfs(x){
	queue<int> q;
	q.push(x);
	while(q.size()){
	int t=q.front();
	q.pop();
    //操作...                               
    }
}
经典应用：   八数码问题，从一个状态到另一个状态所需要最短步骤
map<string,int> mp;   使用mp去重优化     string用来存状态，int存操作步数
queue<string> q;     //bfs必备队列
1 2 3
x 4 6         => "123x46758"
7 5 8
int  bfs(s){
    q.push(s)；
    mp[s]=0;   
    while(q.size()){
        string t=q.front();
        q.pop();
        if(t==tar) return mp[t];        //找到目标，返回结果
        int idx= t.find('.');    // 可移动的位置
        int x=idx/3;   int y=idx%3;   //装换成   
        int temp=mp[t];    //保存移动次数
        for(int i=0;i<4;i++){
            int  cur=(x+next[i][0])*3+(y+next[i][1]);
            swap(t[cur],t[idx]);
            if(!mp[t])          mp[t]=temp+1, q.push(t);
            swap(t[cur],t[idx]);     //回复状态，进行下一次查找
        }
        return -1；
    }
}

小白鼠走迷宫
#include<bits/stdc++.h>
using namespace std;
const int N = 200;
int t,r,c;
char a[N][N];
typedef pair<int,int> PII;
int dx[4]={1,-1,0,0},dy[4] = {0,0,1,-1};
int bfs(int x00,int y00,int r,int c){
    bool st[r][c];
    int step[r][c];
    queue<PII> que;
    memset(st,false,sizeof(st));
    memset(step,0,sizeof(step));
    step[x00][y00] = 0;
    st[x00][y00]=true;
    que.push({x00,y00});
    while(!que.empty()){
            PII t = que.front();
            int x0 = t.first,y0 = t.second;
            que.pop();            
            for(int i=0;i<4;i++){
                int x1 = x0+dx[i],y1 = y0+dy[i];                
                if(a[x1][y1] !='#'&&!st[x1][y1] &&(x1 >= 0 && x1 < r&&y1 >= 0&&y1 < c)){                   
                    step[x1][y1] =  step[x0][y0]+1;
                    // cout<<x1<<" " <<y1<<" "<<step[x1][y1]<<endl;
                    st[x1][y1] = true;
                    if(a[x1][y1]=='E') return step[x1][y1];
                    que.push({x1,y1});                     
                }
            }            
        }
    return -1;        
}
int main(){
    cin>>t;    
    while(t--){
        cin>>r>>c;
        int x0,y0,xn,yn;
        for(int i=0;i<r;i++) 
        for(int j=0;j<c;j++){
            cin>>a[i][j];
            if(a[i][j]=='S') {                   
                x0 = i;
                y0 = j;            
            }
            if(a[i][j]=='E') {
                xn = i;
                yn = j;
            }
        }
        int distance = bfs(x0,y0,r,c);
        if (distance==-1) printf("oop!\n");
        else printf("%d\n", distance);
    }
    return 0;

全排列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
全排列几乎在每年的比赛中都有出现。
全排列的定义为
从n个不同元素中任取m（m≤n）个元素，按照一定的顺序排列起来，叫做从n个不同元素中取出m个元素的一个排列。当m=n时所有的排列情况叫全排列。

公式：全排列数f(n)=n!(定义0!=1)，如1,2,3三个元素的全排列为：
1, 2, 3
1, 3, 2
2, 1, 3
2, 3, 1
3, 1, 2
3, 2, 1
共3 * 2 * 1 = 6种

算法模板(以18年Java组国赛"最大乘积"为例)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//全排列:(递归回溯生成全排列,适用于无重复元素的情况)(考虑第k位,前面已经排定)
int[] a; int n; f(0);
public static void f(int k){
	if(k == n){	//一种全排列已经产生
		if(check()){
			ans++;
		}
		return;
	}
	for(int i = k; i < n; i++){
		{int t = a[i]; a[i] = a[k]; a[k] = t;}
		f(k + 1);
		{int t = a[i]; a[i] = a[k]; a[k] = t;}
	}
}

7.动态规划

状态dp

计数类型的递推或者递归:
整数拼接：dp优化

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;

ll a[N], num[15];
bool vis[15];

ll connect(ll a, ll b)
{
    ll bb = b;
    while (bb != 0) {
        a *= 10;
        bb /= 10;
    }
    a += b;
    
    return a;
} 

int main(void)
{
    int n, k, res = 0;
    cin >> n >> k;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    
    for (int i = 0; i <= 9; i++)
        vis[(i * k) % 10] = 1;
    
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            ll x = a[i], y = a[j];
            if (vis[y % 10] && connect(x, y) % k == 0)
                res++;
            if (vis[x % 10] && connect(y, x) % k == 0)
                res++;
        }
    }
    cout << res << endl;
    
    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
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1005;
int v[MAXN];    // 体积
int w[MAXN];    // 价值 
int f[MAXN][MAXN];  // f[i][j], j体积下前i个物品的最大价值 
int main() 
{
    int n, m;   
    cin >> n >> m;
    for(int i = 1; i <= n; i++) 
        cin >> v[i] >> w[i];
    for(int i = 1; i <= n; i++) 
        for(int j = 1; j <= m; j++)
        {
            //  当前背包容量装不进第i个物品，则价值等于前i-1个物品
            if(j < v[i]) 
                f[i][j] = f[i - 1][j];
            // 能装，需进行决策是否选择第i个物品
            else    
                f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);
        }           
    cout << f[n][m] << endl;
    return 0;
}

摘花生

状态表示
集合：定义f[i][j]为从(1, 1)到达(i, j)的所有方案
属性：最大值
状态转移
(i, j)从(i-1, j)即上方过来
(i, j)从(i, j-1)即左方过来
空间压缩
f[i][j]只需要用到这一层和上一层的f元素，所以可以压缩成滚动数组。在此之上，还可以直接压缩成一维数组。

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<iostream>
using namespace std;
const int N = 105;
int a[N][N], f[N][N];
int q, row, col;
int main()
{
    cin >> q;
    while(q--){
        cin >> row >> col;
        for(int i = 1; i <= row; i++){
            for(int j = 1; j <= col; j++){
                cin >> a[i][j];
            }
        }
         // f[i][j]指的是到(i, j)的最大花生数
        for(int i = 1; i <= row; i++){
            for(int j = 1; j <= col; j++){
                f[i][j] = max(f[i-1][j], f[i][j-1]) + a[i][j];
            }
        }
    cout << f[row][col] << endl;
   }
   return 0;
}

最长上升子序列

状态表示：f[i]表示从第一个数字开始算，以w[i]结尾的最大的上升序列。(以w[i]结尾的所有上升序列中属性为最大值的那一个)
状态计算（集合划分）：j∈(0,1,2,..,i-1), 在w[i] > w[j]时，
f[i] = max(f[i], f[j] + 1)。
有一个边界，若前面没有比i小的，f[i]为1（自己为结尾）。
最后在找f[i]的最大值。

时间复杂度：O(n2)

状态数(n) * 转移数(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
using namespace std;
const int N = 1010;
int n;
int w[N], f[N];
int main() {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> w[i];

    int mx = 1;    // 找出所计算的f[i]之中的最大值，边算边找
    for (int i = 0; i < n; i++) {
        f[i] = 1;    // 设f[i]默认为1，找不到前面数字小于自己的时候就为1
        for (int j = 0; j < i; j++) {
            if (w[i] > w[j]) f[i] = max(f[i], f[j] + 1);    // 前一个小于自己的数结尾的最大上升子序列加上自己，即+1
        }
        mx = max(mx, f[i]);
    }
    cout << mx << endl;
    return 0;
}

8.二分法

用于优化代码，可以用来提高检索效率，但用二分法查找需要保证是有序的数组

1
2
3
4
5
6
7
8
9
10
11
12
int r=100001;
int l=1;
int ans=0;
while(l <= r){
	int mid=(l+r)/2;
	if(true && >){
		l=mid+1;
		ans=mid;
	}else{
		r=mid-1;
	}
}
Int L=1，R=N;
//第一种写法
While(L<R){
Int mid=(L+R+1)/2;
If(check(mid)) L=mid;
Else R=mid-1;
}
Cout<<L;
//第二种写法
While(L<R){
Int mid=(L+R)/2;
If(check(mid)) L=mid+1;
Else R=mid;
}
Cout<<L-1;

10.大数运算

编程题中尤其喜欢考大数运算，如测试数据超过Java的long型或者C++的longlong型。
C++解决则相对复杂一下，需要使用数组模拟
Java中则相对简单，使用BigerInteger(大数据运算)或BigDecimal(大浮点数运算)。
若时间充足，则有必要看看题目结尾数据最大规模判断是否需要进行优化，使用大数据运算。如果数据规模不会超出基本类型限制则不需要使用。

1、头文件问题

#define x first   //宏定义
#define y second
typedef pair<int, int> PII;  //二维组习惯用pair存,typedef可以数据类型重定义
typedef long long LL;  // typedef可以数据类型重定义
const int N = 500010;  //定义常量，比#define安全

若只用到scanf()和printf()可以只写 cstdio，不写 namespace

iostream 中有<string>头文件，有abs()绝对值函数
因为c++标准一直在更新，一些在cmath里的函数在iostream里直接被包含了
cmath  中有sqrt()
c++里max和min函数被<algorithm>和<iostream>同时包含了

<string.h>、<cstring>、<string>三者关系
    1、c++的<cstring>兼容c的<string.h>，而<string>是c++标准模板库（STL）中的内容，可以定义string 对象，
        如string str="acwing",使用string相关函数。<cstring>和<string>不同。
    2、string.h,是C风格字符串操作的一个函数库，strlen，strcpy，strcat，strcmp，puts……都在这里面了。
    3、string，是C++定义的std::string所使用的文件，是string类的头文件，属于STL范畴,
        包含substr(),length(),size(),insert(),find(),replace(),erase()等函数。

const可以写在函数内部

2、变量相关
bool false/true 1 byte
char ‘a’、’c’ 1 byte
int -2147483648～+2147483647 4 byte int的最大值是个以二开头的十位数
long long [int] -9223372036854775808 ～+9223372036854775807 8 byte long long的最大值是一个以9开头的十九位的数
float 1.23 2.63 4 byte 6-7位有效数字
double 3.123456789123 8 byte 15-16位有效数字
long double 12byte 18-19位有效数，很少用到

写算法99%的情况会用double不用float，因为float精度6-7位,double精度15-16位,位数有300多位，有些LL相乘，也可以用double。

c++中 double也可 自增，如1.2 自增 变为2.2

3、输入输出相关

scanf("%*d%d%d", &n, &m); //忽略第一个整数的读入方法
scanf("A = %d, B = %d",&a, &b); // f代表格式化输入输出
scanf("%d\n%c") //读入跨行的数字和字符

scanf() 不能一次读入一个整数数组，只能一个一个读
string 只能用cin 来读，不能用scanf

scanf("%d%d %c",&a,&b,&c);  //%d 后加个空格,防止把空格当字符读入
cin >> a >> b >> c;         //cin会自动过滤空格

关于整行读入问题

    gets()函数在新版C++中被移除了，因为不安全。

    //第1个函数：fgets(),只能读入到字符数组中

    //fgets不会删除行末的回车字符，也就是说
    //你输完一行    点击回车时，  会把回车读进来，用cout输出str字符数组时，光标会停在 下一行；
    //你输完一行  不点击回车时，不会把回车读进来，用cout输出str字符数组时，光标会停在 本行末尾；
    fgets(str字符数组,读入个数size, stdin); //注意最多读入size-1个到字符数组str中

    //第二个函数：getline()
    //读入到字符数组和string字符串中， getline写法不同。读入整行到string中，只能用getline
    string s; 
    getline(cin,s);
    char  c[100];
    cin.getline(c,101); //注意最多读入100个到字符数组或string中


cin >> str;             // 输入字符串时，遇到空格或者回车就会停止
cout << str << endl;    // 输出字符串时，遇到空格或者回车不会停止，遇到'\0'停止

while (cin >> x && x) //while (cin >> x, x)  //在条件表达式中，逗号表达式的值等于最后的值
不告诉个数时，统计输入数据的个数时，循环判断条件可写为 while(scanf(“%d”,x)  !=  -1) cnt++;
                                                //或者 while(scanf(“%d”,x)  !=  -1) cnt++;
c++中EOF 为-1

对应的占位符
    int         : %d
    float       : %f
    double      : %lf
    char        : %c
    long long   : %lld

C++中取模结果正负只与%前面的数的正负有关系
    cout << 5%2 << endl;   输出  1
    cout << 5%-2 << endl;  输出  1
    cout << -5%2 << endl;  输出 -1
    cout << -5%-2 << endl; 输出 -1

C++中除法是向0取整
    cout << 5/2 << endl;    输出  2
    cout << -5/2 << endl;   输出 -2

C++中强制类型转换是向0取整 
    cout << (int)2.5 << endl;  输出  2
    cout << (int)-2.5 << endl; 输出 -2


printf("%-5d",23); //%-5d向左对齐，%5d向右对齐
printf("%8.3f",23.44); //%8.3f 表示这个浮点数最小宽度为8，保留三位小数，宽度不足时前面补0.
printf("%.0lf  ", 0.15 * 100);   //保留0位小数，输出15
printf(%s,str_arr);//str_arr为存有字符串的数组，则输出字符串结束标记'\0'前的内容.同cout
%%输出%，比较特殊的转义

不能用printf直接输出string，需要写成：printf(“%s”, str.c_str());或者puts(str.c_str()); 
cout可以输出带有空格的字符数组、字符串和string，puts能输出char类型字符数组或字符串，不能输出string类型

4、数组初始化

int c[5] = {0, 1, 2};   // 函数里未被初始化的部分为0. 等价于c[] = {0, 1, 2, 0, 0} ，
int a[5] = {0};         // 全部为0

char a1[] = {'C', '+', '+'};           // 列表初始化，没有空字符
char a2[] = {'C', '+', '+', '\0'};       // 列表初始化，含有显示的空字符
char a3[] = "C++";               // 自动添加表示字符串结尾的空字符
char a4[6] = "Daniel";            // 错误：没有空间可以存放空字符
char str[5]={'s','s','d'}; //还是一个字符串

5、函数相关

函数声明可写在main中。如 int fun(int);
strcpy这个函数只能给char数组赋值，string直接用+=即可
fabs() 是浮点数求绝对值，abs()是整数求绝对值 
sort()函数是插入排序和快排的结合,数据个数小时用插入排序，大时用快排
swap函数，在<algorithm>中，可以交换任意类型
str.substr(string串开始下标，[长度])；//返回string字符串
strlen 等函数只能用于 字符数组或字符串，不能比较string。

//为什么编译器会报错
//min 比较的时候得是两个相同的类型，string的size，的返回值类型是size_type，强转一下int就可以了
int len=0;
string str="adsd";
len = min(len, str.size());//报错


有返回值的函数可以不写return， 会返回随机值；
函数内的static静态变量相当于在函数内部开了一个只有该函数能用的全局变量，有默认值，如0，储存在堆中，这样
可以避免一定的重名问题；
多维数组传参时，只有第一维的长度可省略不写，这个和数组内部实现方式有关，且后边的维数的长度需和形参大小相同；
数组不能给数组赋值，可以使用<cstring>中的memcpy(要填充的数组b,被复制的数组a, 元素个数* 4);
inline 函数，在被调用的地方，换成函数体内的代码，对递归函数在时间效率上不明显。

void swaps(int &a,int &b);//函数声明要和函数定义的第一行保持一致，包括引用符号

6、算法相关

判断闰年方法
    闰年分为普通闰年和世纪闰年，其判断方法为
    公历年份是4的倍数，但不是100的倍数，为普通闰年；
    公历年份是整百数，且必须是400的倍数，为世纪闰年。
    归结起来就是：四年一闰；百年不闰；四百年在闰。
    if(year%400==0||year%4==0&&year%100!=0)
        cout<<"yes"<<endl;
    else 
        cout<<"no"<<endl;

秦九韶算法 求p^0+p^1+...+p^n ，时间复杂度O（N）
LL calc(string n, LL r)// 秦九韶算法求r进制转换为十进制（递推思想）
{
    LL res = 0;
    for (auto c : n)
    {
        res = res * r + get(c);
    }
    return res;
}
int get(char c) //获取36进制下字符c代表的数字
{
    if (c <= '9') return c - '0';
    return c - 'a' + 10;
}
//打印100以内所有质数
#include <iostream>
using namespace std;
int main()
{
    for (int i = 2; i <= 100; i ++ )
    {
        bool is_prime = true;
        for (int j = 2; j < i; j ++ )
        {
            if (i % j == 0)
            {
                is_prime = false;
                break;
            }
        }
        if (is_prime) cout << i << endl;
    }
    return 0;
}

//判断一个数是不是质数
bool is_prime(int n)
{
    if (n == 1) return false;

    for (int i = 2; i * i <= n; i ++ )
        if (n % i == 0)
            return false;
    return true;
}
曼哈顿距离：|x1-x2|+|y1-y2|,可用于打印菱形或者方格相关问题
欧几里得距离：sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2))    
//第一类双指针算法
//如统计字符串中最长的连续的相同字符
    string str;
    cin >> str;
    int cnt = 0;
    char c;
    for (int i = 0; i < str.size(); i ++ )
    {
        int j = i;
        while (j < str.size() && str[j] == str[i]) j ++ ;
        if (j - i > cnt) cnt = j - i, c = str[i];
        i = j - 1;
    }
    cout << c << ' ' << cnt << endl;

7、技巧相关

~i 表示 对i二进制取反，i=-1的时候，取反刚好是0
string 可以做的char a[]不一定能做，80%用string

8、课外知识

外存和内存进制不一样，外存是10的3次方，如硬盘，内存是2的10次方
网线带宽 8Mb=1MB（实际上）
99%的评测器会自动过滤掉程序最后的一个回车和每一行末尾的多余空格，但是PAT不是

9、结构体—
结构体排序方法参见我的《结构体排序的四种方法【推荐】》这篇分享
//结构体类型定义：固定大小空间的内存块
struct teacher
{
char name[62];//64
int age;//4
};

void main()
{
    //结构体变量的定义及初始化
    //在c编译环境下和.cpp环境下变量定义方法有所区别
    //struct teacher t1;//C语言需要加上struct关键字
    //teacher t2;//C++中则不必
    struct teacher t1={"daiwen",22};
    //结构体变量作为函数的参数时，若需要修改 结构体变量，则函数的形参要加上指针或引用
    //结构体数组作为函数的参数时，若需要修改 结构体数组，则函数的形参写成
    //struct Teacher *tarray 或struct Teacher tarray[]来接收 结构体数组即可
}

10、补充知识点
1、字符‘0’~‘9’转数字就是减‘0’，例如：ch=‘3’，n=ch-‘0’，n就会被赋值为整数3。
2、取个位使用对10取余（%10），取每一位数字可以在循环中先对10取余（%10）再除以10（/10）。
例如：n=123，在循环中使用a=n%10，n=n/10，就可以让a分别取到3，2，1
3、交换两个变量的值，不一定需要第三个变量，可以用表达式计算，例如：a=2，b=3，交换a和b的值，
可以用a=a+b，b=a-b，a=a-b，一套操作下来，a和b的值就交换啦！