CSP集训笔记

henpolor_cyc · 2022-10-04 13:18:12 · 个人记录

解题过程：

(1)贪心 -> (2)暴力枚举（不含DFS）-> (3)优化

(2）枚举： 条件，答案（+check）-> 二分, 从而分解/转化问题（将求解转化为check）

优化方法：

1. 找关系式
2. 换枚举角度

3. 二分

   lower_bound代码\downarrow

   int a[10005];
   int p = lower_bound(a, a+n, x)-a;

   注意：

   • a数组的类型与x一致
   • lower_bound(a+1, a+n+1, x) - a;
   • 找不到：p = 终点坐标加一

   以上upper_bound同理

   二分答案：整数二分， 浮点二分

   整数二分模版

   int L, R;
     while(L <= R) {
     int mid = (L+R) >> 1;
     if(check(mid)) {
         l = mid+1;或R = mid-1;
        res = mid;
    }else {
        l = mid+1;或R=mid-1;
    }
   }
   cout<<res<<endl;

   注意：

   • 仅当mid可能为答案是check(mid)=true
   • 题目必须符合二分性
   • L, R必须越过mid
   • 注意多个相同值的影响

   浮点二分模版

   int L, R;
   while(abs(L-R) >= 10e-8) {
    int mid = (L+R)/2;
    if(check(mid)) {
        L = mid;
    }else {
        R = mid;
    }
   }

   double 判0: abs(a-b) < 1e-8

   优先队列：

   
   priority_queue<int> pq;
   //取队首： pq.top
   //默认返回最大值
   //类型支持小于号
   //不能删除任意数字(只能在队首删)
   //应用场景：不断新增数据，且无任意的删除，可以删最值，不断求最值
   //小根堆
   priority_queue<int, vector<int>, greater<int>> q;
   
   前缀和：静态区间和 = 前缀和之差
   区间加值，1次查询：
   ```cpp
   p[l] += x, p[r+1]-=x;