在刷题的单身狗很开心

题解

2023河南萌新联赛第（八）场(3) c++(1) 动态规划(5) 差分与前缀和(4) 洪水填法(1) 牛客小白月赛78(4) 牛客练习赛115(2) 牛客练习赛116(2) 算法(1) 算法刷题(2)

/ 注册

全部文章 / 题解（共18篇）

题解|#指纹锁#

用set保存，set有内部默认从小到大排序的特性还有自动去重的特性。在进行检测的时候使用set的lower_bound函数，这个函数对找到最近的插入位置，如果存在该数就返回第一个数的下标。如果不存在就返回第一个大于该数的下标，所以是否有符合要求的数只需要看返回的迭代器对应的数以及前一个数是否...

C++ 二分查找 set

2023-09-24

2 457

题解 | #Greedy Gift Takers#

首先可以看出是按照奶牛的编号进行二分去寻找第一个没有礼物的奶牛。但如何验证某个编号的奶牛前面有死循环存在呢。因为是从后面插空的所以会因为后面牛数量的改变而改变。但可以转化到插第几个位置，如果位置2上有两个及其以上的牛的目标都是它，那么就会造成死循环。同样如果3这个位置上有三个及其以上的牛目标...

C++ 二分查找

2023-09-08

1 308

题解 | #小咪买东西#

可以采用二分总价值的方式，已知总价值为x了，那么需要对分数进行价值和/花费和>=0进行变形得：总（价值-x*花费）>=0.势必要贪心的选取价值-x*花费最大的前k个东西。那么就可以得到是否满足。之后二分就行。值得注意的是本题的答案是在实数范围内的。所以采用足够的循环来界定要二分多...

C++ 二分查找 01分数规划

2023-09-07

1 555

题解 | #[SCOI2010]传送带#

对CD来说进早了可能因为路远，时间增大，进晚了因为没有省力所以时间增大，故区间是一个凹状的，可以使用三分去解决。对于何时进入CD也是一样的。故嵌套三分的做法。但因为本题针对实数的运算，所以要求精度。至于为什么要在计算距离时加上精度，我想是因为在求距离过程中小数位会有所丢失的原因吧。所以需要加...

C++ 二分查找

2023-09-07

0 452

题解 | #[HEOI2014]南园满地堆轻絮#

二分答案，验证方式为将当前的音符值降到尽量小，以便后来的付出小的代价就可以维持递增。比较坑的是取余运算，在这里面取余运算一定要加括号，因为取余运算和乘除运算同级。不加括号将不符合取余运算的规则。 #include <bits/stdc++.h> typedef&n...

C++ 二分查找

2023-09-06

0 308

题解 | #位数差#

做这题的时候因为没有看清题目走了好多弯路[栓Q]，题目中要去i<j，所以不会出现抽取相同下标的数。也是因为这个要求所以不能对数组直接进行排序，会将数组顺序打乱导致错误的。但要求数位差如果有序的话最好的办法是求得大于等于10-a,100-a,1000-a的个数，然后相加。但本题不能直接排...

C++ 二分查找 C++ 二分二分查找

2023-09-06

1 403

题解 | #[NOIP2011]聪明的质监员#

从题中描述可以看出w和检验结果之间有一定关系：w越大检验结果越小，w越小检验结果越大。从而得到w的结果具有一个单调的性质。然后根据这个性质可以考虑二分w的做法。在二分的过程中，如果Y>S那么w就得增大，如果Y<S那么w就得减小，如果Y==S那么直接退出就可以了。但我们最终的答案是...

C++ 二分查找前缀和

2023-09-06

2 346

题解|#华华给月月准备礼物#

//二分答案的方式，将答案二分然后验证。 #include <bits/stdc++.h> typedef long long ll; using namespace std; const int maxn...

C++ 二分查找

2023-09-06

1 278

题解 | #完全平方数#

关于lower_bound和upper_bound：、 lower_bound返回可插入的最小位置的迭代器，即返回第一个符合条件的元素位置。 upper_bound返回可插入的最大位置的迭代器，即返回最后一个符合条件的元素位置。 #include <bits/stdc...

C++ 二分查找

2023-09-05

1 394

题解 | #K-th Number#

首先可知答案的数字具有一定的单调性。考虑使用二分答案的方式。如何验证：已知这个数字，去区间里面找有多少个数比当前这个数字大，如果数量大于等于m的话证明该数小了，需要向右移动反之向左移动。在统计区间里面有多少个数比当前的数字大的时候，要注意使用双指针的方式，否则会超时。还有就是要用lo...

C++ 二分查找双指针

2023-09-05

0 516