在刷题的单身狗很开心

分类

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

/ 注册

全部文章（共201篇）

题解 | #位数差#

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

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

2023-09-06

1 399

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

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

C++ 二分查找前缀和

2023-09-06

2 350

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

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

C++ 二分查找

2023-09-06

1 280

题解 | #完全平方数#

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

C++ 二分查找

2023-09-05

1 403

题解 | #K-th Number#

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

C++ 二分查找双指针

2023-09-05

0 577

题解 | #[NOIP2012]借教室#

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

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

2023-09-05

2 376

题解 | #[CQOI2010]扑克牌#

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

C++ 二分查找

2023-09-05

1 370

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

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

C++ 二分查找

2023-09-05

1 400

题解 | #数字组合#

首先最容易想到的是暴力的四层遍历，时间复杂度为O(n^4)。对最后一层的遍历可以改成二分查找，时间复杂度为O(n^3logn)。但上两种方式都会超时。有四个数字序列，可以联想到先使用二重循环将前两个和后两个序列的所有结果求出来。然后在根据前一个求出来的序列去二分寻找后一个序列中符合要求的有多...

C++ 二分查找

2023-09-05

7 344

题解 | #晾衣服#

采用二分验证的方式，验证：先假设没有烘***，那么t分钟过后每件衣服就消耗了t个水分。这时候在使用烘***的话就水每分钟消耗n-1个水分，那么每一件衣服还需要使用多少次烘***就可以计算出来。然后一共可以使用t次烘***，进行比较即可得到。要注意在计算过程中次数可能超出int的范围，需...

C++ 二分查找

2023-09-04

1 368