算法竞赛从入门到进阶

时间:2021-08-30 09:15:53   收藏:0   阅读:9

算法竞赛从入门到进阶

1.算法竞赛概述

1.1 C语言中输入输出函数

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是双向链表

函数原型:

功能描述:

函数原型:

功能描述:

函数原型:

功能描述:

函数原型:

 

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

简介:

本质:

优点:

功能描述:

函数原型:

功能描述:

函数原型:

 

学习目标:

主要技术点:

示例:

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

总结:

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.搜索技术

原文:https://www.cnblogs.com/g0rez/p/15202860.html

评论(0)
© 2014 bubuko.com 版权所有 - 联系我们:wmxa8@hotmail.com
打开技术之扣,分享程序人生!