总结

刷题 评论

全排列\DFS(深度优先搜索算法)\堆排序算法

枚举法

C(m,n)

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
int n;//共计N个数
int m;//选m个数
vector<int> chosen;
void calc(int x) {
    if (chosen.size() > m || chosen.size() + (n - x + 1) < m) //剪枝:超过m和选不够m
        return;
    if (x == n + 1) { //选够了m个数输出
        for (int i = 0; i < chosen.size(); i++)
            printf("%d ", chosen[i]);
            //也可以不输出，存放起来也是可以的，主要是看题目。
        puts("");
        return;
    }
    //选x
    calc(x + 1);
    chosen.push_back(x);
    //不选x
    calc(x + 1);
    chosen.pop_back();//消除痕迹
}
int main()
{
    cin>>n>>m;
     calc(1);
}

A(m,n)

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
int n; //共计N个数
int order[20];
bool chosen[20];
void calc(int k)
{
    if (k == n + 1)
    {
        for (int i = 1; i <= n; i++)
            cout << order[i] << " ";

        puts("");

        return;
    }
    for (int i = 1; i <= n; i++)
    {
        if (chosen[i])//选过跳过
            continue;
        order[k] = i;
        chosen[i] = 1;//标准搜索方式
        calc(k + 1);//回溯并恢复现场
        chosen[i] = 0;
        order[k] = 0;
    }
}
int main()
{
    cin >> n;
    calc(1);
}

常用STL库

stack模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
top()：

返回一个栈顶元素的引用，类型为 T&。如果栈为空，返回值未定义。

push(const T& obj)：

可以将对象副本压入栈顶。这是通过调用底层容器的 push_back() 函数完成的。

push(T&& obj)：

以移动对象的方式将对象压入栈顶。这是通过调用底层容器的有右值引用参数的 push_back() 函数完成的。

pop()：

弹出栈顶元素。

size()：

返回栈中元素的个数。

vector容器

1
2
3
4
5
6
7
8
9
#include <vector>   //头文件
vector<int> a;      //定义了一个int类型的vector容器a
vector<int> b[100]; //定义了一个int类型的vector容器b组
struct rec
{
    ···
};
vector<rec> c;            //定义了一个rec类型的vector容器c
vector<int>::iterator it; //vector的迭代器，与指针类似
1
2
3
4
5
6
7
8
9
a.size()           //返回实际长度（元素个数），O(1)复杂度
a.empty()      //容器为空返回1，否则返回0，O(1)复杂度
a.clear()      //把vector清空
a.begin()      //返回指向第一个元素的迭代器，*a.begin()与a[0]作用相同
a.end()        //越界访问，指向vector尾部，指向第n个元素再往后的边界
a.front()      //返回第一个元素的值，等价于*a.begin和a[0]
a.back()       //返回最后一个元素的值，等价于*--a.end()和a[size()-1]
a.push_back(x) //把元素x插入vector尾部
a.pop_back()   //删除vector中最后一个元素
1
2
3
4
for ( vector<int>::iterator it=a.begin() ; it!=a.end() ; it++ )
cout<<*iterator<<endl;

for( int i=0;i<a.size();i++) cout<<a[i]<<endl;

队列 Queue

1
2
queue<string> myqueue;
queue<int> myqueue_int;
1
2
3
4
5
6
front()：返回 queue 中第一个元素的引用。
back()：返回 queue 中最后一个元素的引用。
push(const T& obj)：在 queue 的尾部添加一个元素的副本。
pop()：删除 queue 中的第一个元素。
size()：返回 queue 中元素的个数。
empty()：如果 queue 中没有元素的话，返回 true。

Map 映射

1
2
map<char, int> mymap1;
map<string, int> mymap2;
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
1.看容量
int map.size();//查询map中有多少对元素
bool empty();// 查询map是否为空
2.插入
map.insert(make_pair(key,value));
//或者
map.insert(pair<char, int>(key, value))
//或者
map[key]=value
3.取值
map<int, string> map;
//如果map中没有关键字2233，使用[]取值会导致插入
//因此，下面语句不会报错，但会使得输出结果结果为空
cout<<map[2233]<<endl;
//但是使用使用at会进行关键字检查，因此下面语句会报错
map.at(2016) = "Bob";
4.遍历操作
map<string, string>::iterator it;
for (it = mapSet.begin(); it != mapSet.end(); ++it)
{
    cout << "key" << it->first << endl;
    cout << "value" << it->second << endl;
}
5.查找操作
m.count(key)：//由于map不包含重复的key，因此m.count(key)取值为0，或者1，表示是否包含。
m.find(key)：//返回迭代器，判断是否存在。

差分与前缀和

差分与前缀和是一对互逆的操作，常常用于处理区间问题，差分法是解决区间加减问题，前缀和是解决区间求和问题的常用办法。

差分法的应用主要是用于处理区间问题。当某一个数组要在很多不确定的区间，加上相同的一个数。

如果我们采用差分法，将数组拆分，构造出一个新的拆分数组，通过对数组区间的端点进行加减操作，最后将数组和并就能完成原来的操作。

image-20220406221345009

b[1]=a[1]

b[i] = a[i]-a[i-1]

b[l,r] + N = b[l]+N, b[r+1]-N

b[1]=b[1]

b[i] = b[i]+b[i-1];

前缀和是指某序列的前 n 项和，可以把它理解为数学上的数列的前 n 项和。

如果我们采用前缀和，构造出一个前缀和数组，通过对于端点的值的减法操作就能 O(1) 的求出 [l,r] 的和。然后 N 次查询的,就将复杂度降低为 O(n)

image-20220406221449329

a[1]=a[1];

sum[i] += sum[i-1]+a[i]; 或 a[i]+=a[i-1];

sum[l,r] = sum[r] - sum[l - 1]

哈希

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
const long long h = 999983;
int b = 131;

int Hx(string s)
{

    int n = s.size();
    int sum1 = 0;

    for (int i = 0; i < n; i++)
    {
        sum1 = sum1 * 131 % h + (s[i] - 'a' + 1) % h;
    }

    return (sum1 + h) % h;
}

递推和递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//递推开始:从尾部开始

    for (int i=n-1; i>=1; i--)//从最后一层逆推
    { 
        for (int j=1; j<=i; j++)
        {

            if (a[i+1][j]>=a[i+1][j+1])
                a[i][j]+=a[i+1][j];     //路径选择

            else  
                a[i][j]+=a[i+1][j+1];
        }
    }

    cout<<a[1][1]<<endl;

二分法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 在单调递增序列a中查找>=x的数中最小的一个（即x或x的后继）
while (low < high)
{
    int mid = (low + high) / 2;
    if (a[mid] >= x)
        high = mid;

    else
        low = mid + 1;
}

// 在单调递增序列a中查找<=x的数中最大的一个（即x或x的前驱）
while (low < high)
{
    int mid = (low + high + 1) / 2;

    if (a[mid] <= x)
        low = mid;

    else
        high = mid - 1;
}

其他

1
2
3
4
5
6
7
8
9
#include<iomanip> //用于浮点数输出
cout<<fixed<<setprecision(7)<<l;

    //一般使用print
    //printf("%x.yf",n)
    //其中X是固定整数长度，小数点前的整数位数不够，会在前面补0
    //y是保留小数位数，不够补零

    //printf("%.7f",l);
1
2
3
4
5
6
7
8
9
10
#include <iostream>
#include <numeric>
using namespace std;
int main(){
	int array[]={1,2,3,4,5,6,7,8,9};//定义数组array
	int sum = accumulate(array,array+size(array),0);
	cout << "数组的和 = " << sum << endl;
	system("pause");
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<string.h>
//数组全部置0
memset(move, 0, sizeof(move));

#include<algorithm>
bool judge(Cach a,Cach b)
{
    return a.avg>b.avg;
}
sort(cash,cash+n,judge);

#include<iomanip>
cout<<fixed<<setprecision(7)<<l;

    //一般使用print
    //printf("%x.yf",n)
    //其中X是固定整数长度，小数点前的整数位数不够，会在前面补0
    //y是保留小数位数，不够补零

    //printf("%.7f",l);
1
2
3
//映射：对称的奇偶可以有一样的值
from = (from - 1)/2;
to = (to - 1)/2;

EurekaStudy Notes & Supplement

Strong is beautiful!