在刷题的单身狗很开心

题解

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

/ 注册

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

题解|#网络优化#

题目链接：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

题解 | #叠积木#

一个需要维护附加信息的并查集。需要维护的信息为某编号为 x 的积木下方有多少块积木。直接维护需要更新一棵树的所有节点，这显然是不方便的。在这里我们选择让根节点保存某个编号下的箱子总数，然后下面被连接的根节点保存其下方有多少箱子。这样查询某个编号的箱子下面的箱子个数只需要向...

C++ 并查集维护附加信息的并查集

2023-09-17

1 452

题解 | #DongDong认亲戚#

//并查集的模板题，写个并查集完事 #include <bits/stdc++.h> using namespace std; map<string , string> mp; string fin...

C 并查集

2023-09-15

2 277