搜索结果
查询Tags标签： mid，共有 942条记录-
LeetCode 34. 在排序数组中查找元素的第一个和最后一个位置
34. 在排序数组中查找元素的第一个和最后一个位置 思路： 与AcWing 789一致 class Solution { public:vector<int> searchRange(vector<int>& nums, int target) {if (nums.size() == 0) return {-1, -1};int begin, end;int l = 0, r = nums.size() - 1;…
2022/8/22 23:24:27 人评论 次浏览 -
木材加工
木材加工 思路：二分查找。 从木棍长度的中间分别向两边找，直至找出既满足木棍个数 长度又长的木棍长度。 代码如下： #include<iostream> using namespace std; int n,k; int len[1000010]; bool check(int mid)//mid为木棍长度 {long long sum=0;//sum记录木棍个…
2022/8/22 23:22:58 人评论 次浏览 -
一元三次方程
根的绝对值>=1,可知在区间[i,i+1]内最多只有一个解。将（-100,100）for 循环分成若干区间令l=i,r=i+1;判断f(l)是否为0，再判断f(r)是否为0，如果为0，直接跳过。当左右点都不为0时走到下一步利用二分，判断。 当f(mid)*(r)>0 那么可知根一定在左边区间 即r=mid,否则…
2022/8/22 23:22:45 人评论 次浏览 -
A-想要更多的0_2022河南萌新联赛第（六）场：郑州大学 (nowcoder.com)
A-想要更多的0_2022河南萌新联赛第（六）场：郑州大学 (nowcoder.com) 这个题思路倒是很好想到主要是处理[0,n]区间内0出现的次数 考虑这个问题 比如对3891205举例。我们取到数第四位数，其形式也就可以是xxx0xxx这种情况你前面可以取[1,389]后面可以取[0,999]所以答案就是…
2022/8/20 23:54:50 人评论 次浏览 -
【笔记】IOI2022
「IOI2022」鲶⻥塘 签到题。 如果我们记 \(a_i\) 表示第 \(i\) 列的高度，那么一定不存在 \(a_i\ge a_{i +1}\le a_{i+ 2}(a_{i+1} \neq 0)\) 的情况，假设存在，我们将 \(a_{i + 1}\leftarrow 0\) 答案不会更劣。同理如果 \(a_i\le a_{i + 1} \ge a_{i + 2}\)，我们就将 …
2022/8/16 23:27:30 人评论 次浏览 -
XX Open Cup, Grand Prix of Tokyo D,L
D 二分max值为L，判定能否使用\(\leq L\)的数构造出答案。 暂时不管L的限制。此时如果我们有一组解，表示为\(c_{0},c_{1},...,c_{60}\)，其中\(c_{i}\)是有多少个数在第\(i\)位为\(1\)。那么我们可以将\(c_{i}\)减\(2\)，\(c_{i-1}\)加\(4\)；或者\(c_{i}\)减\(4\)，\(c_…
2022/8/15 6:25:24 人评论 次浏览 -
YbtOJ 「基础算法」第3章 二分算法
例题1.数列分段 二分每段和的最大值。check 时从左往右扫，如果当前段的和大于限制则新开一段。code #include<bits/stdc++.h> using namespace std; const int N=1e5+5; int n,m,a[N]; int maxn,s; int check(int x) {int cnt=1,sum=0;for(int i=1;i<=n;i++){if…
2022/8/15 1:55:03 人评论 次浏览 -
python | 算法大神左神（左程云）算法课程 第二节
针对的是b站视频-算法大神左神（左程云）算法课程第二节相关算法由于python中关于递归有些踩坑，所以不搞对数器，就贴上单个例子验证正确的代码 视频笔记戳这里1. 归并排序归并排序-戳这里 #归并排序-递归class solution():def mergeSort(self, array):"""…
2022/8/11 14:25:54 人评论 次浏览 -
线段树入门
简介 常用来维护区间信息的数据结构，可以在\(Olog(n)\)的时间内实现区间修改，区间信息合并，单点修改。 结构 建树 注意：线段树空间需要开到四倍。 struct Node {int minv; } seg[N * 4];// 根据左右儿子更新父亲节点信息 void update(int id) {seg[id].minv = min(seg…
2022/8/11 6:27:07 人评论 次浏览 -
[AcWing 340] 通信线路
二分 + 双端队列广搜 复杂度 \(m \cdot log(r - l) = 1 \times 10^4 \times log(10^9) = 3 \times 10^5\)点击查看代码 #include<bits/stdc++.h>using namespace std;typedef long long LL;const int N = 1e6 + 10; const int M = 1e3 + 10; const int INF = 0x3f3f…
2022/8/11 6:23:01 人评论 次浏览 -
二分算法
二分的本质不是单调性。 （有单调性一定可以二分，但是二分可以做的题，不一定需要满足单调性。） 二分的本质是二段性 就是有一个分界点，分界点左边都是状态x，分界点右边都是状态y。通过二分就可以找到红色区域的右边界值或者绿色区域的左边界值 当想找不满足性质的边界…
2022/8/7 1:22:56 人评论 次浏览 -
CF464E The Classic Problem
下面的讨论默认 \(n,m,x_i\) 同阶。 这个问题与常规 \(\tt dij\)，仅仅差在高精度。而 \(\tt dij\) 所需的高精度如下：\(dis_u+w(u,v)\) 中的加法，应该有 \(m\) 次。 \(dis_u+w(u,v)\) 与 \(dis_v\) 的比较，应该有 \(m\log\) 次。考虑数据结构维护 \(dis\) 的二进制分解…
2022/8/6 23:27:15 人评论 次浏览 -
"蔚来杯"2022牛客暑期多校训练营5补题 B, C, F, G, H, K
G KFC Crazy Thursday 马拉车算法 题意： 给定一个字符串，问有多少个以K或者F或者C结尾的回文子串。 思路： 马拉车算法，求出len。 利用区间加法获得总和即可。 也就是（直接看代码更容易理解）对于新串在i处“+1”，在i+len[i]+1处“-1”。因为这个区间内的字符都有某个…
2022/8/3 23:25:28 人评论 次浏览 -
Java二分查找：给定一个?n?个元素有序的（升序）整型数组?nums 和一个目标值?target ?，写一个函数搜索?nums?中的 target，如果目标值存在返回下标，否则返回 -1
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。 示例 1: 输入: nums = [-1,0,3,5,9,12], target = 9 输出: 4 解释: 9 出现在 nums 中并且下标为 4利用二分查找思想 clas…
2022/8/3 1:23:39 人评论 次浏览 -
数据结构与算法--斐波那契查找
斐波那契数列 斐波那契数列，又称黄金分割数列，因数学家莱昂纳多斐波那契以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、…… 在数学上，斐波那契数列以如下被以递推的方法定义：F(1)=1，F(2)=1, F(n)=F(n - 1)+F(n…
2022/7/31 1:23:11 人评论 次浏览
