小工具知识网

当前位置: 首页 > 行业知识 > 【蓝桥杯】蓝桥杯算法复习(一)

行业知识

【蓝桥杯】蓝桥杯算法复习(一)

2026-11-20 21:52:09 来源:互联网转载

大家好,���是白晨,一个不是很能熬夜,但是也想日更的人✈。如果喜欢这篇文章,点个赞,关注一下白晨吧!你的支持就是我最大的动力!

文章目录

  • 前言
  • 蓝桥杯复习(一)
    • 一、二分
      • 复习
      • 练习
      • 二、前缀和
        • 复习
        • 练习
        • 三、差分
          • 复习
          • 练习
          • 四、双指针
            • 复习
            • 练习
            • 五、归并
              • 复习
              • 练习
              • 六、多路归并
                • 复习
                • 练习
                • 七、贡献法
                  • 复习
                  • 练习

                    前言


                    本文适合有一定算法基础,但是由于各种原因已经很久没有敲代码的同学。本文以复习+练习为主,旨在通过练习算法题快速复习已经遗忘的算法。即使不是参加蓝桥杯的同学,如果符合上面的条件,依然可以参考本文进行复习。

                    如果你是新手,可以参考白晨的算法专栏进行学习。


                    蓝桥杯复习(一)


                    一、二分


                    复习

                    // 模板一// 求满足check条件的最左下标#include using namespace std;templateint binary_search1(T* v, int l, int r){while (l > 1;if (check(v[mid])) // check中 v[mid] 永远放在前面,eg. v[mid] >= ar = mid;elsel = mid + 1;}return mid;}// 模板二// 求满足check条件的最右下标#include using namespace std;templateint binary_search1(T* v, int l, int r){while (l > 1; // 必须加一,避免***循环if (check(v[mid])) // eg.v[mid]     memset(b, 0, sizeof b);    // 先差分,求出分配前mid订单后的差分数组    for (int i = 1; i         b[s[i]] += d[i];        b[t[i] + 1] -= d[i];    }        // 判断此时是否满足条件    LL cnt = 0;    for (int i = 1; i         cnt += b[i];        if (cnt  w[i]) return false;    }    return true;}int main(){    scanf("%d%d", &n, &m);        for (int i = 1; i         int mid = l + r + 1  1;        if (check(mid)) l = mid;        else r = mid - 1;    }        if (r == m) printf("0");    else printf("-1\n%d", r + 1);        return 0;}    scanf("%d", &t); // 输入测试用例数量        for (int i = 1; i         scanf("%d", &n); // 输入字符串长度        scanf("%s", s + 1); // 输入字符串                int res = 0;        int cnt = (n + 1) / 2; // 滑动窗口的大小,取n的一半向上取整        for (int j = 1; j             a[j] = a[j - 1] + s[j] - '0'; // 计算前缀和,即当前位置之前的数字和            if (j = cnt)                 res = std::max(res, a[j] - a[j - cnt]); // 更新结果,保证滑动窗口内数字的和最大        }                printf("Case #%d: %d\n", i, res); // 输出结果    }    return 0;}    b[l] += e;    b[r + 1] -= e;}int main(){    scanf("%d", &n);        for (int i = 1; i         // 求温差        int a = p[i] - t[i];        insert(a, i, i);    }        int pos = 0, neg = 0;    for (int i = 1; i         if (b[i]  0) pos += b[i];        else neg -= b[i];    }        printf("%d", max(pos, neg));        return 0;}    scanf("%d%d", &n, &L);        for (int i = 1; i         while (j && a[j]  

                    最后,回到原问题,如果是a[]不是升序序列,那么应该怎么办?

                    我们可以对a[]做一个映射,将其映射为升序序列,再以对a[]做的映射为规则,对b[]做映射,只用求出b[]中的逆序对数量,就是最小的交换次数。

                    但是,这里有一个问题,a[]和b[]的数不相同呀,怎么进行映射?由于本题目并不涉及数组中的具体值,只涉及到数组间的相对大小(逆序对),所以可以将其进行离散化,按照其数组中的相对大小将其离散化到1~10000上,这样就可以保证a[]和b[]可以相互映射。

                    具体实现:

                    #include #include #include using namespace std;const int N = 100010, mod = 99999997;int n;int a[N], b[N];int q[N], map[N];int merge_sort(int l, int r) {    if (l >= r) return 0;    int mid = l + r >> 1;    int res = (merge_sort(l, mid) + merge_sort(mid + 1, r)) % mod;        int i = l, j = mid + 1, k = 0;    while (i         // 统计逆序对个数        if (b[i]  b[j]) q[k++] = b[j++], res = (res + mid - i + 1) % mod;        else q[k++] = b[i++];    }        while (i     for (int i = 1; i         return t[x] 

上一篇:连接家用服务器怎么连接?

下一篇:服务器购买之后怎么办?