学习笔记

第一次训练

第一次训练主要讲了一下基础的东西。

时间复杂度

• 时间复杂度

  栈和队列

• 栈和队列
  • 栈 First in last out(FILO)
    • 1.栈的头文件 #include<stack>
    • 2.栈的定义 stack<变量类型(int,char...)> s(栈的名字可以自定义)
    • 3.常用函数
      • s.pop() 删掉栈顶的元素
      • s.top() 返回值为栈顶元素的值
      • s.push() 向栈中输入新的元素
  • 队列 First in first out(FIFO)
    • 1.队列的头文件#include<queue>
    • 2.队列的定义 queue<变量类型(int,char...)> q(队列的名字可以自定义)
    • 3常用函数
      • q.pop() 删掉队列最前面的元素
      • q.front() 返回值为栈顶元素的值
      • q.push() 在队尾压入新元素
      • q.back() 返回值为队列最后一个元素

        栈和队列的通用函数

    • 栈和队列的通用函数
      • q/s.empty() 如果栈(队列)为空返回true，否则返回false
      • q/s.size()返回栈(队列)中元素的个数

sort排序(默认为升序)

    #include<bits/stdc++.h>  //sort的头文件为algorithm,此处的头文件为万能头文件
    using namespace std;
    int main()
    {
        int n,a[100];
        cin>>n;
        for(int i=0;i<n;i++)
        cin>>a[i];
        sort(a,a+n);
        for(int i=0;i<n;i++)
        cout<<a[i]<<" ";
        puts("");
        return 0;
    }

若想更改成降序排列，需要添加一个自定义函数

    #include<bits/stdc++.h>
    using namespace std;
    bool cmp(int a,int b) //变成降序
    {
        return a>b;
    }
    int main()
    {
        int n,a[100];
        cin>>n;
        for(int i=0;i<n;i++)
        cin>>a[i];
        sort(a,a+n,cmp);
        for(int i=0;i<n;i++)
        cout<<a[i]<<" ";
        puts("");
        return 0;
    }

2018-11-30

第二次训练

第二次训练主要讲了二分查找，二分答案等。

二分法的使用条件

• 答案区间上下限确定，即最终答案在哪个范围是容易知道的。
• 检验某值是否可行是个简单活，即给你个值，你能很容易的判断是不是符合题目要求。
• 可行解满足区间单调性，即若x是可行解，则在答案区间内x+1（也可能是x-1）也可行。

  几个关于二分查找的函数

  因为二分查找的显著优越性，c++的库中封装了几个于二分查找有关的函数。

  1.lower_bound(起始地址，结束地址，要查找的数值) 返回的是大于或等于val的第一个元素位置。
  2.upper_bound(起始地址，结束地址，要查找的数值) 返回的是大于val的第一个元素位置。
  3.binary_search(起始地址，结束地址，要查找的数值) 返回的是是否存在这么一个数，是一个bool值。

  第三次训练

  第三次训练我们讲了一些特殊容器(STL)的用法.(stl内容太复杂了,我就先不总结了，以后补上）

快速幂(自学)

代码实现

    int poww(int a,int b){
    int ans=1,base=a;
    while(b!=0){
        if(b&1!=0)//判断每次循环a的奇偶
        　　ans*=base;
        base*=base;
        b>>=1;//去除b的二进制数中的最后一位
　 }
    return ans;
}

快速幂的时间复杂度： O(log₂N)