在刷题的单身狗很开心

题解

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

/ 注册

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

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

题解 | #数字组合#

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

C++ 二分查找

2023-09-05

6 366

题解 | #晾衣服#

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

C++ 二分查找

2023-09-04

1 354

题解 | #[USACO 2016 Jan S]Angry Cows#

寻找R的最小值，同样可以使用二分验证的方式去做，那么问题就落到了如果验证当前的R可以将草堆全部引爆。如何验证：从左向右去炸第一问即可，在其中维护一个当前爆炸的最大坐标从而来判断当前这个草堆是不是需要去炸的第一个就可以了。 //寻找R的最小值，同样可以使用二分验证的方式去做，那么问题就落到了...

C++ 二分查找

2023-09-04

1 576

题解 | #跳石头#

一个寻找最小的尽量大的题目，做这种题目首先要考虑是否可以使用二分验证的方式，因为这种题目的答案在一个单调区间里面寻找。所以可以通过二分答案加一验证的方式快速寻找的答案。那么要考虑的就是如何验证是否可行，在本题中使用双指针的策略。last保存上一个石头，如果长度符合那么就让last和i都增加，...

C++ 二分查找双指针

2023-09-04

1 404

题解 | #[USACO 2009 Dec S]Music Notes#

//使用前缀和记录在什么时候音符开始演奏，然后在通过二分查找值的范围即可。 #include <bits/stdc++.h> using namespace std; const int maxn = 50000+...

C++ 前缀和二分查找

2023-09-04

1 303