在刷题的单身狗很开心

分类

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

/ 注册

全部文章（共201篇）

题解|#数组#

题目链接：D-数组_牛客练习赛116 (nowcoder.com) 本题的思路感觉没有那么难，但是最麻烦的是理解题目中的数学公式。在题目中r所需要满足的两个要求其实是A从i开始的累加和直到到达r的位置使小于等于k*c，到r+1的位置大于k*c。那么我们可以计算A的前缀和，然后在使用up...

C++ 二分查找堆(优先队列)

2023-09-24

1 377

题解|#排序#

题目链接：C-排序_牛客练习赛116 (nowcoder.com) 本题需要出题目的描述中得到许多有效的结论，其一最重要的结论就是某个数x是否能变得更小取决于后面有没有x-1，当然就算有还需要知道能否移动到这个位置上来，这时候就需要判断在x-1到x的位置移动路径上有没有数字的阻挡，也就是路径上...

C++ stl 贪心

2023-09-24

1 398

题解|#网络优化#

题目链接：1010-网络优化_2021秋季算法入门班第五章习题：优先队列、并查集 (nowcoder.com) 一开始想到了放炸弹烧草那道题，以为可以先对l进行排序使其尽量能走多少人就走多少人的贪心策略。但我忽略了走的并不一定是一个连续的区间。有可能因为走多了而导致浪费了一些。那么从人...

C++ 贪心堆(优先队列)

2023-09-22

1 445

题解 | #Parity game#

将区间x~y中1个数是偶数还是奇数转变成1~x-1和1~y两个区间里面的奇偶性相反的问题。然后通过扩展域并查集求解。 #include <bits/stdc++.h> using namespace std; unordered_map<in...

C++ 并查集

2023-09-22

2 256

题解 | #食物链#

扩展域并查集解决了有多种相互关系的问题。这题如果单纯的去判断是不是同类就是用普通的并查集就可以了。但由于有想吃的关系，所以得使用扩展域并查集，有三种动物，将并查集的数组扩大三倍。对于某x,y两个动物是同类的情况这两个动物可能是A,B,C任意一种。那么将x,y合并。x+n,y+n合并。y+2*n,x+...

C++ 并查集

2023-09-21

1 349

题解 | #背包#

做这道题的时候一开始想到了对顶堆但发现如果根据输入逐步使用对顶堆的话，不好实现最优的选择。看了题解才知道这不是一道对顶堆的题目，可以使用对物品的价值进行排序，然后某个物品能否作为中位数可以通过向左取(m-1)/2个物品，向右取(m-1)/2个物品。取左右物品的最小重量总和然后加上中位数可以判...

C++ 堆(优先队列) 前缀和二分 C++ 贪心二分优先队列前缀和

2023-09-20

3 441

题解 | #N皇后问题#

深度优先遍历加剪枝的经典问题。在递归过程中按行去递归保证了不在同一行，然后使用结构体数组来保存前面行已选定的坐标，在每一行都循环的去选择是哪一列。然后判断和之前的是否在同一列或同一对角线。如果递归到N次了，那么就证明可以有一个方案了。如何判断在同一对角线：abs(y-y`)==abs(x-x...

C++ 深度优先搜索

2023-09-20

2 334

题解 | #点权和#

这题的标签是倍增。。。这真的算倍增的吗。由于题中所给是父亲节点，那么可以想办法将儿子节点带来的贡献转化成x作为父亲节点时儿子所带来的贡献。这样通过记录每一个点作为自身、父亲、爷爷。所接受的影响。三个关键数组： tag[x]：x节点改变对自身的改变。 ftag[x]：x节点...

C++ 树

2023-09-19

1 348

题解 | #区间的连续段#

本题使用倍增的思路去做，如果不考虑区间问题要想分成最少个连续段使每段的和都<=k，那么就需要从第一位开始贪心的跳跃到最远的那个下标处。那么我们按照这个思路对每一位数都可以得到一个可跳跃的最远下标。那么结合倍增，如果可以的话我们甚至可以直接跳跃1段，两段，四段。。。。那么在某一段里面到底...

C++ 倍增

2023-09-18

1 410

题解|#小美的区间异或和#

首先读懂题目，题目要求的是所有连续子数组的权值和。二权值和为数组中人选出连个数的异或之和。由于是异或运算所以对于某个数上某位二进制数为0与之前的连续区间里面能凑成多少个1取决于前面有多少少个1，还要注意的是从第一个数到这个数之间的区间也可以分成子区间，那就是说假如前一位的是1的话，那么回和前面的位异...

C++ 位运算

2023-09-18

2 1110