noip基础复习

· · 个人记录

tip：难度无先后顺序，按楼主自己的复习顺序为标准

1 并查集

初始化

void init(int n){
    for(int i=1;i<=n;i++){
        fa[i]=i;
    }
}

查询（路径压缩版）

int find(int n){
    return n==fa[n]?n:(fa[n]=find(fa[n]));
}

合并

void merge(int i, int j) {
    fa[find(i)]=find(j);
}

按序合并（启发式合并）

void merge(int i, int j) {
    int x = find(i), y = find(j);
    if (rank[x] <= rank[y])
        fa[x] = y;
    else
        fa[y] = x;
    if (rank[x] == rank[y] && x != y)
        rank[y]++;
}

2二分

二分查找

int find(int q){
  int l=0,r=n+1;//开区间
  while(l+1<r){ //l+1=r时结束
    int mid=l+r>>1;
    if(a[mid]>=q) r=mid; //最小化
    else l=mid;
  }
  return a[r]==q ? r : -1;
}

二分答案

主要是在二分查找上加了一个check函数用来判断答案的合法性，每个题目都不一样，要复习的话以刷题为主这里贴几道经典的题目

P2440 木材加工

P2678 [NOIP2015 提高组] 跳石头

P1314 [NOIP2011 提高组] 聪明的质监员

3区间dp和dp的单调队列优化

单调队列基本操作

empty()//为空返回真
pop()  //删队顶元素
push() //入队一个元素
size() //返回个数
top() //返回队顶元素

大根堆

priority_queue<int> q;

小根堆

priority_queue<int,vector<int>,greater<int>>

find：

顺序查找。find(v.begin(), v.end(), value)，其中 value 为需要查找的值。

reverse：

翻转数组、字符串。reverse(v.begin(), v.end()) 或 reverse(a + begin, a + end)。

unique ：

去除容器中相邻的重复元素。unique(ForwardIterator first, ForwardIterator last)，返回值为指向 去重后 容器结尾的迭代器，原容器大小不变。与 sort 结合使用可以实现完整容器去重。

dp要说什么，自己刷呗.....

*不定期更新