算法竞赛从入门到进阶

2022-11-09 14:50:23

算法竞赛从入门到进阶

1.算法竞赛概述

1.1 C语言中输入输出函数

  • putchar()

  • getchar

  • printf()

  • scanf()

  • puts()

  • gets()

  • sscanf()

1.2 输入结束方式

 while(scanf("%d %d",&a,&b) != EOF){
     
 }
 //等价于
 while(~scanf("%d %d",&a,&b)){
     //一般使用这种方式
 }

1.3 编码技巧

把长字符重新定义成段字符 节省编码时间

 typedef long long ll;
 long long a;
 //变为
 ll a;

1.4 最好不要用宏定义 容易出现问题

使用const定义常量 例如

 const int MAX=100005;

把宏函数写成普通函数

2.STL和基本数据结构

2.1 容器

顺序式容器 vector list deque queue priority_queue stack等

关联式容器 set multiset map multimap等

2.1.1 vector

动态数组

定义

 vector<int> a;
 ​
 vector<int> a(100);
 ​
 vector<int> a(100,5);
 ​
 vector<string> b(a.begin(),a.end());

操作

 a.push_back(100);
 int size=a.size();
 bool isEmpty=a.empty();
 count<<a[0]<<endl;
 a.insert(a.begin()+i,k); //在第i个元素前面插入k
 a.insert(a.end(),10,5); //在尾部插入10个值为5的元素
 a.pop_back();
 a.erase(a.begin()+i,a.begin()+j);//删除区间[i，j-1]的元素
 a.erase(a.begin()+2); //删除第三个元素
 a.resize(n);
 a.clear();
 reverse(a.begin(),a.end());
 sort(a.begin(),a.end());
2.1.2 stack

操作

 stack<type> s;
 s.push(item);
 s.top(); //返回栈顶元素 但不会删除
 s.pop(); //删除栈顶元素 但不会返回
 //一般是先返回在删除 所以先top 在pop
 s.size();
 s.empty();
2.1.3 queue

操作

 queue<type> q;
 q.push(item);
 q.pop();
 q.front(); //返回队首元素但不会删除
 q.back();
 q.size();
 q.empty();
2.1.4 priority_queue

优先队列

在STL中，优先队列是用二叉堆来实现的，优先级最高的先出队。每次的push和pop操作，优先队列都会动态的调整，把优先级最高的元素放在前面。

操作

 q.top();//返回优先级最高的元素值 但不删除
 q.pop();
 q.push(item);
2.1.5 链表 list

STL中的list是双向链表

函数原型：

  • list<T> lst; //list采用采用模板类实现,对象的默认构造形式：

  • list(beg,end); //构造函数将[beg, end)区间中的元素拷贝给本身。

  • list(n,elem); //构造函数将n个elem拷贝给本身。

  • list(const list &lst); //拷贝构造函数。

功能描述：

  • 给list容器进行赋值，以及交换list容器

函数原型：

  • assign(beg, end); //将[beg, end)区间中的数据拷贝赋值给本身。

  • assign(n, elem); //将n个elem拷贝赋值给本身。

  • list& operator=(const list &lst); //重载等号操作符

  • swap(lst); //将lst与本身的元素互换。

功能描述：

  • 对list容器的大小进行操作

函数原型：

  • size(); //返回容器中元素的个数

  • empty(); //判断容器是否为空

  • resize(num); //重新指定容器的长度为num，若容器变长，则以默认值填充新位置。

    //如果容器变短，则末尾超出容器长度的元素被删除。

  • resize(num, elem); //重新指定容器的长度为num，若容器变长，则以elem值填充新位置。

    ​ //如果容器变短，则末尾超出容器长度的元素被删除。

功能描述：

  • 对list容器进行数据的插入和删除

函数原型：

  • push_back(elem);//在容器尾部加入一个元素

  • pop_back();//删除容器中最后一个元素

  • push_front(elem);//在容器开头插入一个元素

  • pop_front();//从容器开头移除第一个元素

  • insert(pos,elem);//在pos位置插elem元素的拷贝，返回新数据的位置。

  • insert(pos,n,elem);//在pos位置插入n个elem数据，无返回值。

  • insert(pos,beg,end);//在pos位置插入[beg,end)区间的数据，无返回值。

  • clear();//移除容器的所有数据

  • erase(beg,end);//删除[beg,end)区间的数据，返回下一个数据的位置。

  • erase(pos);//删除pos位置的数据，返回下一个数据的位置。

  • remove(elem);//删除容器中所有与elem值匹配的元素。

 

2.1.6 set

set 就是集合 STL中的set用二叉搜索树实现，集合中的每个元素只出现一次并排好序的。访问元素的时间复杂度是O(nlogn);

操作

 set<type> A;
 A.insert(item);//插入元素
 A.erase(item);//删除元素
 A.clear();
 A.empty();
 A.size();
 A.find(k); //返回一个迭代器，指向键值k
 A.lower_bound(k);//返回一个迭代器，指向键值不小于k的第一个元素
 A.upper_bound();//返回一个迭代器，指向键值大于k的第一个元素
2.1.7 map

简介：

  • map中所有元素都是pair

  • pair中第一个元素为key（键值），起到索引作用，第二个元素为value（实值）

  • 所有元素都会根据元素的键值自动排序

本质：

  • map/multimap属于关联式容器，底层结构是用二叉树实现。

优点：

  • 可以根据key值快速找到value值

功能描述：

  • map容器进行插入数据和删除数据

函数原型：

  • insert(elem); //在容器中插入元素。

  • clear(); //清除所有元素

  • erase(pos); //删除pos迭代器所指的元素，返回下一个元素的迭代器。

  • erase(beg, end); //删除区间[beg,end)的所有元素 ，返回下一个元素的迭代器。

  • erase(key); //删除容器中值为key的元素。

功能描述：

  • 对map容器进行查找数据以及统计数据

函数原型：

  • find(key); //查找key是否存在,若存在，返回该键的元素的迭代器；若不存在，返回set.end();

  • count(key); //统计key的元素个数

 

学习目标：

  • map容器默认排序规则为 按照key值进行 从小到大排序，掌握如何改变排序规则

主要技术点:

  • 利用仿函数，可以改变排序规则

示例：

 #include <map>
 ​
 class MyCompare {
 public:
     bool operator()(int v1, int v2) {
         return v1 > v2;
     }
 };
 ​
 void test01() 
 {
     //默认从小到大排序
     //利用仿函数实现从大到小排序
     map<int, int, MyCompare> m;
 ​
     m.insert(make_pair(1, 10));
     m.insert(make_pair(2, 20));
     m.insert(make_pair(3, 30));
     m.insert(make_pair(4, 40));
     m.insert(make_pair(5, 50));
 ​
     for (map<int, int, MyCompare>::iterator it = m.begin(); it != m.end(); it++) {
         cout << "key:" << it->first << " value:" << it->second << endl;
     }
 }
 int main() {
 ​
     test01();
 ​
     system("pause");
 ​
     return 0;
 }

总结：

  • 利用仿函数可以指定map容器的排序规则

  • 对于自定义数据类型，map必须要指定排序规则,同set容器

2.2 sort()

void sort(RandomAccessItarator first,RandomAccessItarator last); 包括first 但不包括last

void sort(RandomAccessItarator first,RandomAccessItarator last，Compare mycompare); 包括first 但不包括last 自己定义的比较规则

比较规则：less<type>()升序 greater<type>()降序

2.2 next_permutation()

STL提供求下一个排列组合的函数next_permutation() 例如a,b,c三个字符组成的序列，next_permutation()函数能按照字典序返回6个组合 即abc acb......

bool next_permutation(BidrectionalIterator first,BidrectionalIterator last); 包括first 不包括last

bool next_permutation(BidrectionalIterator first,BidrectionalIterator last,Compare mycompare);

有下一种排列组合的话返回true 否则false。

每调用一次，就会把新的排列放到原来的空间里。

复杂度O(n)

一般使用该函数的适合，初始序列一般是一个字典序的最小序列，如果不是，可以调用sort（）函数进行排序得到最小序列，再使用该函数。

 #include <iostream>
 #include<algorithm>
 using namespace std;
 int a[1001];
 int m;
 int main()
 {
    cin.sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>m;
    for (int i = 1; i <= m; i++)  a[i]=i;
    do{
         for (int i = 1; i <= m; i++) cout<<a[i]<<" ";
         cout<<endl;
    }while(next_permutation(a+1,a+m+1));
    return 0;
 }

测试结果

 3                                 
 1 2 3 
 1 3 2
 2 1 3
 2 3 1
 3 1 2
 3 2 1

3.搜索技术

上一篇：1顺序栈


下一篇：STL容器list容器API