在刷题的单身狗很开心

题解

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

/ 注册

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

题解 | #[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

题解 | #[NOIP2012]借教室#

订单的编号具有单调性，也就是说可以往二分答案的方向去思考。已知订单的编号，也就是说在此订单及其之前的订单都能满足。那么如何快速验证订单是否满足就是要解决的问题。按题中描述以某一天为下标每个订单都有连续几天的租借数量，对于连续区间的加减问题可以联想到差分与前缀和的解法可以将原来教室数量的列表...

C++ 二分查找前缀和差分

2023-09-05

2 385

题解 | #[CQOI2010]扑克牌#

通过二分答案的做法，在这里是二分套牌的数量。那么这就转换成了已知套牌的数量如何去验证能不能达到这么多套牌数。假设有ABC三种套牌：A：3，B：4，C：5。如果已知套牌数量为x那么对ABC来说数量上就得大于等于x，缺少的就需要用joker来补，那么到底需要多少joker就可以算出来。对...

C++ 二分查找

2023-09-05

1 366

题解 | #[USACO 2010 Feb S]Chocolate Eating#

求最小幸福值的最大值，本题中只需要以答案入手去二分答案即可。至于如何验证：从第一天开始遍历，如果幸福值小于给定的最小幸福值那么就吃巧克力就完了。看最后是巧克力被先吃完，还是能够满足贝西每天的幸福值需要。需要注意的是在记录记录每天吃巧克力的方案的时候前提是需要验证通过。因为最后结果有可...

C++ 二分查找

2023-09-05

1 397