在刷题的单身狗很开心

题解

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

/ 注册

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

题解 | #数字组合#

首先最容易想到的是暴力的四层遍历，时间复杂度为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

题解 | #牛可乐和魔法封印#

一个二分查找的基本题，不同的是需要寻找范围。那么就是要找第一个符合的最小的数，最后一个符合的最大的数。这样可以通过返回下标直接相减加一得到数量。在寻找最大的数的最大下标的时候需要mid = (l+r+1）/2。因为如果相等会让l = mid。但(l+r)/2会偏向于l处。在相邻的时候会出现不变的情况...

C++ 二分

2023-09-04

3 569

题解|#[NOIP2013]表达式求值#

本题字符串中符号最大达到100000，那么只用递归的方式去求解表达式的话就需要100000层的递归（会超时）。那么可以回到后缀表达式的思路。使用op栈保存符号，num栈保存数字。在计算过程中遇到*就进行计算后把计算的结果压栈。重复这个过程就可以了。要注意：题目要求当答案长度大于4位时...

C++ 栈

2023-09-03

2 409

题解 | #华华教月月做数学#

本题考察快速幂算法和快速乘算法，快速幂算法可以正着进行也可以反着进行，在这里采用正着进行倍增的思路。以2^10为例，其中指数10可以变成二进制1010，也就可以变成2^(2^3)+2^(2^1)。2的出现也就意味着可以使用倍增的思路去求解。也就是将指数变成二进制进行挨个计算，在计算过...

C++ 递归快速乘快速幂倍增

2023-09-03

1 389

大吉大利，今晚吃鸡

本题与经典汉罗塔很像，但由于只能相邻移动的特点有导致移动方法有些不同。假设只有两个盘子：由于只能相邻移动所以不能先从A到B，再A到C，因为A到B之后中间那根柱子由于最上面的盘子挡着呢，所以过不去。那么就只能通过B柱子一次性移动到C才可以将下面的盘子从A到B。然后还需要将C上面的盘子借...

C++ 汉罗塔递归

2023-09-02

6 470

兔子的逆序对

题目链接：1008-兔子的逆序对_2021秋季算法入门班第二章习题：递归、分治 (nowcoder.com) 本题求逆序对的思路还是按照归并排序的过程去求解，但不同之处在于本题需要不断的变换区间里面数的排列。首先考虑在每一次变换之后都去求解逆序对的数量肯定是会超时的。然后可以联想到如果...

C++ 递归思维

2023-09-02

1 427