https://www.ciyekua.cn/index.php/category/算法 https://www.ciyekua.cn/index.php/diary/157.html 2024-08-31T13:51:00+08:00 二分搜索函数 C语言：`bsearch()` C++：`binary_search()` 1.C语言：bsearch() 函数原型如下： ``` void* bsearch( const void *key, const void *ptr, size_t count, size_t size, int (*comp)(const void*, const void*) ); ``` 2.C++：binary_search() ``` binary_search(起始地址，结束地址，要查找的数值) 返回的是是否存在这么一个数，是一个bool值。 ``` 3.C++扩展 ``` lower_bound(起始地址，结束地址，要查找的数值) lower_bound()：返回大于或等于目标值的第一个位置 upper_bound(起始地址，结束地址，要查找的数值) upper_bound()：返回大于目标值的第一个位置 ``` ``` 参考资料： https://blog.csdn.net/sinat_31608641/article/details/124975237 https://baijiahao.baidu.com/s?id=1793956676806508127&wfr=spider&for=pc ``` https://www.ciyekua.cn/index.php/diary/153.html 2024-08-15T18:35:00+08:00 1.nth_element() 2024/08/15 作用：找出数组中第k小的数 > https://www.ciyekua.cn/index.php/diary/152.html https://www.ciyekua.cn/index.php/diary/152.html 2024-08-15T18:28:00+08:00 找出一个数组中第k小的数 一、朴素做法 sort() 时间复杂度：O(nlogn) 二、利用STL库函数nth_element() 时间复杂度：O(n) 用法：`nth_element(a,a+k,a+n)` 长度为n的数组a[]中找出第k小的数 https://www.ciyekua.cn/index.php/diary/148.html 2024-08-15T17:09:00+08:00 1.rand() 函数的基本用法 rand() 函数不需要参数，它会返回一个从 0 到最大随机数之间的任意整数。 最大随机数的大小通常是固定的一个大整数，例如 RAND_MAX。 ***注意：***在windows操作系统下最大为2^15-1（即32767），LINUX坏境下最大为2^31-1 如要生成更大范围随机数需要`rand()*rand()`或`(rand() https://www.ciyekua.cn/index.php/diary/138.html 2024-08-14T23:30:00+08:00 一、求区间最大值的各种方法及时间复杂度 1、朴素（即搜索），O(n)-O(qn) online。 2、线段树，O(n)-O(qlogn) online。 3、ST（实质是动态规划），O(nlogn)-O(q) online。 ST算法（Sparse Table），以求最大值为例，设d[i,j]表示[i,i+2^j-1]这个区间内的最大值，那么在询问到[a,b]区间的最大值时答案就是max(d[a,k], d[b-2^k+1,k])，其中k是满足2^k＜=b-a+1(即长度)的最大的k,即k=[ln(b-a+1)/ln(2)]。 d的求法可以用动态规划，d[i, j]=max(d[i, j-1],d[i+2^(j-1), j-1])。 4、RMQ标准算法：先规约成LCA（Lowest Common Ancestor），再规约成约束RMQ，O(n)-O(q) online。 首先根据原数列，建立笛卡尔树，从而将问题在线性时间内规约为LCA问题。LCA问题可以在线性时间内规约为约束RMQ，也就是数列中任意两个相邻的数的差都是+1或-1的RMQ问题。约束RMQ有O(n)-O(1)的在线解法，故整个算法的时间复杂度为O(n)-O(1)。 RMQ算法时间复杂度： ***时间复杂度为O(nlogn),然后可以在O(1)的时间内处理每次查询。*** 二、RMQ模板题 > https://ac.nowcoder.com/acm/contest/88527/H ac代码：`https://ac.nowcoder.com/acm/contest/view-submission?submissionId=70974305` 三、RMQ模板 ``` int n,a[1000005]; int dp[100005][25]; void rmq_init(){ for(int i = 1; i https://www.ciyekua.cn/index.php/diary/136.html 2024-08-05T23:10:00+08:00 gcd：最大公约数 lcm：最小公倍数 **2个数a,b的gcd、lcm：** GCD2=__gcd(a,b) LCM2=a*b/GCD **3个数a,b,c的gcd、lcm：** GCD3=__gcd(GCD2,c) LCM3=LCM2*c/GCD3 代码实现： ``` #include using namespace std; // 求最大公约数 int GCD(int a, int b) { if (b == 0) { return a; } else { return GCD(b, a % b); } } // 求最小公倍数 int LCM(int a, int b) { return a * b / GCD(a, b); } int main() { int a, b, c; cout a >> b >> c; int gcd = GCD(GCD(a, b), c); int lcm = LCM(LCM(a, b), c); cout https://www.ciyekua.cn/index.php/diary/134.html 2024-08-04T21:39:00+08:00 1.滑动窗口 2024/07/23 cf961 b1 `https://codeforces.com/contest/1995/problem/B1` （据说也可用贪心做？但不知道怎么做...） 2.gcd、lcm 2024/08/05 `https://www.ciyekua.cn/index.php/diary/136.html` 3.RMQ（求区间最大值） 2024/08/14 时间复杂度为O(nlogn),然后可以在O(1)的时间内处理每次查询。 `https://ac.nowcoder.com/acm/contest/88527/H` 4.质数筛 2024/08/14 （待补充...） 5.rand()随机化算法 2024/08/15 `https://www.ciyekua.cn/index.php/diary/148.html` https://www.ciyekua.cn/index.php/diary/133.html 2024-05-10T17:36:00+08:00 一、滑动窗口是什么 滑动窗口是双指针算法的一种，基本思路为维护一个窗口，然后从前往后遍历元素进行运算。 二、滑动窗口算法和其他双指针算法的区别 双指针算法常见的为三种： 1.快慢指针算法（常用于链表有环判断） 2.双向指针（两个指针一个从最左，一个从最右出发进行查找），典型应用为二分查找 3.滑动窗口（两个指针一前一后出发，两个指针中间维持一个窗口结构 [点击查看原文][1] [1]: https://blog.csdn.net/qq_54850598/article/details/127863026