在刷题的单身狗很开心

题解

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

/ 注册

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

题解 | #Tree Decoration#

利用题目中的数据构造出来一个向下的树。然后如果是在叶子节点的话毫无疑问就得叶子节点独自承受所需要的灯笼，如果不是叶子节点的话就得是递归回去的时候带来子树挂上了多少灯笼以及最小时间花费的节点是多少。这样如果叶子节点不够挂的时候就直接去挂那个最小的时间花费即可。 #include <...

C++ 思维递归

2023-10-02

1 349

题解 | #Lake Counting#

可用DFS,BFS,并查集。在这里使用DFS，将所以为W的点记录下来，然后遍历这些点，在遍历某一个点的时候使用深度优先遍历将其相邻的所以池塘全部标记下来，这样在遍历W的时候可以将其跳过。 #include <bits/stdc++.h> using names...

C++ 广度优先搜索深度优先搜索并查集递归

2023-09-26

1 370

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

本题考察快速幂算法和快速乘算法，快速幂算法可以正着进行也可以反着进行，在这里采用正着进行倍增的思路。以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

求逆序数

题目链接：1007-逆序数_2021秋季算法入门班第二章习题：递归、分治 (nowcoder.com) 快速排序模板题，要注意结果会超过Int，要使用long long。 #include <bits/stdc++.h> typedef long ...

C++ 递归归并排序

2023-09-02

1 378

题解 | #[NOIP2004]FBI树#

题目中给的数据范围明确说明了长度是偶数，偶数的长度更容易分隔。题目中有要求后序遍历，那么可以从下向上进行是FBI的输出，又易知根是FBI的哪一种取决于子树的类型是否相同。这样只需要让子节点将类型返回就可以简单地得到当前节点是什么类型。 #include <bits/std...

C++ 二叉树递归

2023-09-01

1 436

题解 | #小q的数列#

链接：https://ac.nowcoder.com/acm/contest/21763/1002 来源：牛客网题目描述小q最近迷上了各种好玩的数列，这天，他发现了一个有趣的数列，其递推公式如下： f[0]=0 f[1]=1; f[i]=f[i/2]+f[i%...

C++ 递归

2023-09-01

4 469

题解 | #[NOIP2001]求先序排列#

以题目中给出得例子为例，通过后序遍历取最后一位可以得到当前子树的根节点为：A，然后到中序遍历里面取寻找这个根节点，从而可以通过中序遍历来将当前树分割成左子树和右子树。然后递归重复这个过程就可以得到先序遍历。要注意递归的条件要l1>r1，因为在边界处可以会出现l1>r1的情况这时候...

C++ 递归二叉树

2023-09-01

2 582

题解 | #第k小数#

在快速排序的过程中进行操作，快速排序定下的某个数排序结束之后可以得到当前数是第几个数，然后根据得到的第几个数可以进行向左还是向右的调整。可以省略掉一些不必要的操作。 #include <bits/stdc++.h> using namespace&nbs...

C++ 快排递归

2023-08-30

0 457