首先最任务进行排序，首先按截止时间进行排序然后按z的值从大到小进行排序。按截止时间进行排序是因为如果过了截止时间那就相当于没完成，所以比较优先，那之后为什么按照z的值进行排序呢？因为z的值大能耗费更小的钱去买。在做任务的过程中如果前面任务的时间相加超过当前任务的截止时间了，就得需要向前面的任务以及他自身要时间，这时候自然要选取运行时间不为0且z值最大的那一个。那么可以使用一个优先队列来维护z值的大根堆，如果因为花钱导致运行时间为0了就从堆里面剔除就好了。   #include <bits/stdc++.h> using namespace std; /...

题目链接：D-数组_牛客练习赛116 (nowcoder.com)   本题的思路感觉没有那么难，但是最麻烦的是理解题目中的数学公式。在题目中r所需要满足的两个要求其实是A从i开始的累加和直到到达r的位置使小于等于k*c，到r+1的位置大于k*c。   那么我们可以计算A的前缀和，然后在使用upper_bound的时候将查找的值加上a[i-1]，这样就实现了在i到最后的位置的前缀和的查找。   然后考虑题目中说的链接每次操作可以选择一个下标 让c对应下标的值加一。让c的值加一的话可能会使在这个下标下的r值增大，但绝对不会减小。所以我们想要max-min最小就需要去改变min的值。在这里使用一个...

题目链接：C-排序_牛客练习赛116 (nowcoder.com)   本题需要出题目的描述中得到许多有效的结论，其一最重要的结论就是某个数x是否能变得更小取决于后面有没有x-1，当然就算有还需要知道能否移动到这个位置上来，这时候就需要判断在x-1到x的位置移动路径上有没有数字的阻挡，也就是路径上有没有除x-2和x之外的数字的存在。那么如果按照这个思路暴力的话一定会超时，这时候只需要用10个队列去保存每个数的各个下标（小的放前面）。如果在x-2和x之外的数字出现在路径上就不能移动直接保存。 当然还需要用一个哈希数组来记录某些下标下的数是否已经被使用过了，如果使用过了自然也是不能用的。在判断某个...

题目链接：1010-网络优化_2021秋季算法入门班第五章习题：优先队列、并查集 (nowcoder.com)   一开始想到了放炸弹烧草那道题，以为可以先对l进行排序使其尽量能走多少人就走多少人的贪心策略。但我忽略了走的并不一定是一个连续的区间。有可能因为走多了而导致浪费了一些。   那么从人上开始如果，对于每一个人选取一个服务线，那么如何选择服务线又成了一个贪心问题。选择服务线一定是选择r偏小的那一个，因为r小的话如果再不发挥作用就没机会了。如果r相同的话就选v小的那一个。因为有可能v比较小但r比较大，这时候可以将其放到后面发挥作用，如果放前面的话会浪费。   #include ...

将区间x~y中1个数是偶数还是奇数转变成1~x-1和1~y两个区间里面的奇偶性相反的问题。然后通过扩展域并查集求解。   #include <bits/stdc++.h> using namespace std; unordered_map<int, int> mp; int find(int x) {     return x==mp[x]? x : mp[x]=find(mp[x]); } void&nbsp...

扩展域并查集解决了有多种相互关系的问题。这题如果单纯的去判断是不是同类就是用普通的并查集就可以了。但由于有想吃的关系，所以得使用扩展域并查集，有三种动物，将并查集的数组扩大三倍。对于某x,y两个动物是同类的情况这两个动物可能是A,B,C任意一种。那么将x,y合并。x+n,y+n合并。y+2*n,x+2*n合并。来代表他们是同一种动物。如果x吃y的话，那么假设x为A，y+n是B。所以将x和y+n合并表示x吃y的关系。同样如果x是B或C也要进行合并。   这样我们要进行判断的时候，一个是判断数据是否合理，   如果D==1的话判断x,y有没有之前已经记录的吃的关系。   如果D==2的话判断x,y...

做这道题的时候一开始想到了对顶堆但发现如果根据输入逐步使用对顶堆的话，不好实现最优的选择。   看了题解才知道这不是一道对顶堆的题目，可以使用对物品的价值进行排序，然后某个物品能否作为中位数可以通过向左取(m-1)/2个物品，向右取(m-1)/2个物品。取左右物品的最小重量总和然后加上中位数可以判断这个物品能不能作为中位数。如果可以那么取可以作为中位数中的最大值。   当然如果是偶数的话，我们还需要进行一些处理。因为偶数是两个数的平均数作为中位数，所以我们需要去左右两个数。直接暴力寻找会超时的，所以我们选择遍历一个数，二分去寻找另一个数。然后取他们和的最小值。   如何快速验证某个数能不能作为...

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

这题的标签是倍增。。。这真的算倍增的吗。   由于题中所给是父亲节点，那么可以想办法将儿子节点带来的贡献转化成x作为父亲节点时儿子所带来的贡献。这样通过记录每一个点作为自身、父亲、爷爷。所接受的影响。   三个关键数组：   tag[x]：x节点改变对自身的改变。   ftag[x]：x节点作为父亲时收到儿子的影响改变   gtag[x]：x节点作为爷爷收到孙子节点的影响改变。   in[x]：记录x节点的所有临界点的个数。   为什么只持续到爷爷。因为一个数改变对于父亲节点有加一的影响，而父亲节点加一会让爷爷节点计算的结果也加一。所以影响持续到了爷爷节点。   计算下方的贡献：   当儿子作...

本题使用倍增的思路去做，如果不考虑区间问题要想分成最少个连续段使每段的和都<=k，那么就需要从第一位开始贪心的跳跃到最远的那个下标处。   那么我们按照这个思路对每一位数都可以得到一个可跳跃的最远下标。那么结合倍增，如果可以的话我们甚至可以直接跳跃1段，两段，四段。。。。那么在某一段里面到底能跳多少段其实是拿可以跳的最大的段，然后逐步缩小。最后就可以得到到底最少可以跳跃几段。倍增的递推式为：dp[i][j] = dp[dp[i][j-1]][j-1];。要注意跳跃会超过n所以要对n+1地方进行处理。还有就是需要从大向小遍历数，因为前面的数需要后面数跳跃距离的结论。   #include&...

首先读懂题目，题目要求的是所有连续子数组的权值和。二权值和为数组中人选出连个数的异或之和。由于是异或运算所以对于某个数上某位二进制数为0与之前的连续区间里面能凑成多少个1取决于前面有多少少个1，还要注意的是从第一个数到这个数之间的区间也可以分成子区间，那就是说假如前一位的是1的话，那么回和前面的位异或上前面为的编号次，也就是i+1次。如果我们自己某一位二进制可以和前面凑成多少个1，那么在这一位直接按这一位的二进制值乘上个数即可。   如何维护个数：对于2,3,1这个序列来说，从1来看的话他构成的子数组为[2,3,1]和[3,1]，所以前面的3里面的数其实是被异或相加了两次。有了这个规律开一个二...

一个需要维护附加信息的并查集。需要维护的信息为某编号为 x 的积木下方有多少块积木。直接维护需要更新一棵树的所有节点，这显然是不方便的。   在这里我们选择让根节点保存某个编号下的箱子总数，然后下面被连接的根节点保存其下方有多少箱子。这样查询某个编号的箱子下面的箱子个数只需要向上将除了根节点之外的数量全部加起来即可。        #include <bits/stdc++.h> using namespace std; struct node {     int&nbsp...

题目链接：F-神奇编码_牛客小白月赛78 (nowcoder.com)   第一种简单但会超时的方式：   #include <bits/stdc++.h> typedef long long ll; using namespace std; priority_queue<vector<ll>, vector<vector<ll> >, greater<vector<ll>> > pq; int&nbs...

题目链接：E-自动计算机_牛客小白月赛78 (nowcoder.com)   这是一道思维题。要想将结果变成0那么就需要经过x轮y次操作。首先从轮来看每次加的都是一样的，如果遍历轮的次数达到了n次，那么n+1次一定会发生循环（因为取余的存在）。   所以我们就确定的应该遍历的最大的轮数。如果超过n次还没有得到正确答案，那么循环成立之后就永远不可能得到正确答案了。所以在每一次轮数遍历的时候再去寻找有没有等于mod-x的前缀和数。如果有那么经过y次就可以得到结果。   #include <bits/stdc++.h> typedef long long&n...