注意：1.一定要每个条件都检查，不要写后忘前，先把所有要求都写下来！！
2.写完后一定要在检查一下，是否与最后求的一致，防止调试过程中改代码，不当输入输出
以及拿样例写题，忘记换成变量了！！！！！
3.注意无向图的 用邻接表存，要开二倍空间

1. 未知字符串个数输入

#include<string>
    string s;
    while (cin>>s){
        for(int i=3;i>=0;i--) cout<<s[i];
        cout<<endl;
    }

    //输入一行带空格的字符
        while (gets(s)){
        cout<<s;
        cout<<endl;
    }

2.文件读写

    freopen("G:\\in.txt","r",stdin);//输入重定向 
    freopen("G:\\out.txt","w",stdout); //输出重定向 

    fclose(stdin); //关闭输入重定向 
    fclose(stdout); //关闭输出重定向 

3.sort的重载

typedef long long LL;
struct node {
    LL xue; //存储学生的学号 
    LL scode; //存储学生成绩 
}S[110];

typedef node nodes;

bool cmp(nodes a,nodes b){
    if(a.scode<b.scode) return true;
    else if(a.scode>b.scode) return false;
    else if(a.xue<b.xue)return true;
    else return false;
}//bool 型

sort(S,S+n,cmp);

//大小一致就用 pair vector

补充：sort 是不稳定的，用的是快排

方法一：
stable_sort的实现是基于归并排序的，它的时间复杂度为O(nlogn)，一般情况下，它比快速排序稍慢。但是它是一种稳定排序，所谓稳定排序，就是说相同大小的元素，在排序前后的相对位置不会发生改变

方法二：
在结构体中在定义个序号 scode值相同的时候，序号升序排序

struct nod{
    string user;
    int scode;
};


bool asc(node a,node b){
    if(a.scode<b.scode) return true; //升序
    else return false;
}

//其实只有一个元素 可以直接写成
  retrun a.scode<b.scode   //升序
  return  a.scode>b.scode  //降序


//自定义后依然是稳定的
  stable_sort(numb,numb+n,asc);

4.vector

#include<vector>


typedef long long LL;
typedef pair<LL,LL>PLL;
vector<PLL>q;

q.push_back({scode,num}) ;
sort(q.begin(),q.end());

注：

• vector 的 q.pop_back()只把 size-1，实际数据还在vector中
• vector 遍历 用for(int i=0;i<q.size();i++)

int型数据的取值范围、32位、 -2^31 — 2^31-1

5.map
map<string,int>msi; 会按照键（即第一个元素）的值排序
注意迭代器定义 iterator
第一、二个元素怎么表示的iter->first 、iter->second

  //迭代器的类型要和上面定义的对应,
    //上面定义的是mp<string,int>mp，下面的迭代器也是要map<string,int>::iterator
    map<string, int>::iterator iter;

        for (iter = mp.begin(); iter != mp.end(); iter++) { 
        //iter->first指向第一个即string,iter->指向第二个即int    
        cout << iter->first << "  " << iter->second << endl;   
    }

6.栈 stack

#include<iostream>
#include<stack> //栈的头文件

using namespace std;

int main(){
    stack<int> a; //创建一个栈
    a.push(2); //将2放到栈里，即压栈
    a.push(5);
    a.push(9);
    a.top(); //访问栈顶
    a.pop();//将栈顶的数送出栈
    a.top();

    a.size();//获取栈长度

    //栈是后进后出，并不能通过迭代器遍历的方法访问整个数组

}

7.优先队列priority_queue

    priority_queue<int> q; //大顶堆
    priority_queue<int,vecot<int>,greater<int>>q;//升序排序，小堆顶
    priority_queue<int,vector<int>,less<int>> q;//降序排序 大堆顶
    q.top()//访问栈顶

    pop()　　//　　删除对顶元素，删除第一个元素   注意删除的时候是不会再将栈顶元素输出了
    push() 　　   //加入一个元素
    size() 　　　 // 返回优先队列中拥有的元素个数
    top() 　　　//　返回优先队列对顶元素，返回优先队列中有最高优先级的元素

基础算法：
1离散化：

    //排序完  最好是要去重一下
    sort(q.begin(),q.end());
    q.erase(unique(q.begin(),q.end()),q.end()); 

    //可以用自带的find 函数找位置 但是时间复杂度比较高 O(n)
    int x=find(q.begin(),q.end(),aa)-q.begin();  //注意减去首地址

    //  在保证正确的情况下 可以写二分   
    // 二分可以 0...n

    scanf("%d%d",&aa,&bb); 

5.2筛素数
质数就是素数

 //同时 注意M的值的设置 因为大于 9991的最大质数是10007 所以即使n<1e4,M的设置要大一些！！！

bool st[N]; //标记每个数是不是素数，false是素数，true不是素数；

void choice(){
    st[1]=true;  //千万注意1不是素数！！！！
    for(int i=2;i*i<M;i++)   //注意这里的判断条件是i*i<M
    {
        if(!st[i]){
            for(int j=2;i*j<M;j++) //注意这里的判断条件是i*j<M
            st[i*j]=true;
        }
    }
} 

掌握前缀和、差分、离散化并查集等基础算法，了解动态规划、图论等高阶算法

问题项的：
堆排序问题了
1. 栈和队列

• 栈 先进后出 一端插入删除 ； 队列 先进先出 一端插入一端删除

• 【应用】 栈：函数调用、表达式求值、匹配括号 队列 ：图的层次遍历（广度优先搜索）、对于缓冲区的工作（是先进先出的）

• 关于最短路和最小生成树
  最小生成树：把连通的图的所有顶点连起来路径之和最小的问题，即生成树总权值之和最小。
  最短路：把两点之间路径最短。
  【即最小生成树两点的最短路径长度；最小生成树是每个点到集合的最短路路径之和】

  最短路算法： dijkstra Floyd
  最小生成树：prim kruskal

  • dijkstra 能解决单源最短路问题，且所有边权都应该是正值，通常是O(n^2) 若用堆优化，即通过优先队列时间复杂度为O(mlogn) 【why？ 因为用堆优化能快速找到距离原点最近的节点】
    [不能解决负权边问题]

  • Floyd 解决多源最短路,而且可以处理负权边 但是不能处理负权回路 时间是O(n^3)
    算法思路:本身是一个动态规划的算法 1. dis[i][j] 用于保存i到j的距离，初始设为i到j的边权，如果没有边则设置为无穷。
    2.尝试找到一个k 看从i到k再到j 的距离近 还是从i到j的距离近
    3.知道n轮循环结束后确定 i到j 的最小值。

  注释：其实prim算法 和dijkstra算法本质一样，但是prim是到集合最近的距离，dijkstra是到开始的点最近的距离，因此把dijkstra中dis 到原点的距离修改成到集合的距离 不就可以了吗？ 是的，但是要注意 prim已经加入到集合点的距离值不能在被修改了 ，dijkstra记录到的是原点的距离只会增加了，不会出现该问题。

  • prim [同dijkstra一样] 通常是O(n^2) 若用堆优化，即通过优先队列时间复杂度为O(mlogn).

  • kruskal O(mlogm)
    算法思路：将所有边排序，从小到大遍历每个边，如果边连接的两点不在一个集合中，就连接在一起将边权加起来，n个点，n-1条边就可以将其连接通起来
    【注】：这里找一个边连接的两点 是否在一个集合中用的是并查集
    3.dfs、bfs
    bfs（广度优先收索）

  dfs（深度优先搜索）