一.题目描述 NC545扩散 给出n个结点，n-1条双向边使得结点之间双向连接，有每次操作，每次操作会使会使对应的点和其之间连接的点的点权加一，求m次操作过后每一个点的的点权是多少？ 二.算法一(模拟) 首先我们可以利用二维vector进行存边，对于每一次的m操作，我们可以先将指定结点点权加一，然后对所有和指定结点连接的结点的点权加一，进行m次操作后返回所有点的点权。 下面给出完整代码和注释： class Solution { public: vector<int> solve(int n, int m, vector<int>& u, vector...

一.题目描述 NC638简单的变换 给一个正整数n，如果n是奇数，将其减去3；如果n是偶数，将其变为n/2。如果可以进行若干次操作后使得n等于0，返回需要操作的次数，如果无法将n变为变为0，返回-1。 二.算法一(数学) 我们可以从0开始反过来推导，首先要使n的最后值是0那么必然是n−3=0n-3=0n−3=0，不可能是由n/3n/3n/3得到的。那么n−3=0n-3=0n−3=0的上一步n必然是3的倍数，所以我们可以发现，如果给出的n不是3的倍数，那么必然不能通过操作将n变为0，所以直接返回-1。如果给出的数是3的倍数，那么我们就要根据奇偶来分情况讨论了，要是奇数就直接减去3，要是偶数就直...

一.题目描述 NC637牛牛算数 给出n个元素的数组arr[i]，问这个数组的中位数大还是平均数大，如果中位数更大输出1，如果平均数更大输出-1，如果中位数和平均数相等输出0。 二.算法一(模拟) 对于比较最后中位数和平均数的大小，我们可以直接求出来整个数列的中位数和平均数，如果中位数更大返回1，如果平均数更大返回-1，如果 中位数和平均数相等返回0。下面是完整代码： class Solution { public: int Answerofjudge(vector<int>& arr) { double ave=0; int nu...

NC636牛牛爱奇数一.题目描述对于一个序列，每一次操作可以把相同的偶数除以2，求将整个序列全部变成奇数最少需要几次操作。解释：对所有的2进行一次操作数组变为[1,1,3]，那么满足整个序列全部变成奇数二.算法(模拟)首先理解题意我们知道对于相同的偶数而言，我们每一次的操作是相同的那么，那么对于每一个偶数我们来记录其是否被操作过，并且记录下经过几次操作后，偶数可以变成奇数。但是我们需要注意对于每一次处理前后的数都要进行标记，这样的话再遍历过程中遇到前面被操作过的数就直接跳过，下面是完整代码加注释： class Solution { public: int oddNumber(int n...

一.题目描述题目大意：有一个N个数的数列，每一个数可以删去右边连续递减且小于当前数的数列，返回需要进行几次操作可以使得数列保持稳定，其数量不会发生变化。二.算法(模拟+递归)理解题目的意思我们可以知道每次都会将一个数右边小于该数字的连续子序列删除，那么对于每次删除后的结果进行递归，记录最后数列趋于稳定所需要的次数，返回就可以得到最后的答案了，下面是完整代码和注释： class Solution { public: /* 不是吧 不是吧 不会有人还 不知道 这个题目的数据弱的只有一个数据点吧 22 */ int solve(int N, vector<int...

一.题目描述NC572连通块有一棵树有n个节点n-1条边，需要判断是否可以将这棵树划分为k个连通块并且每一个联通块的节点的总和是不是大于等于m。二.算法(暴力搜索)我们需要判断是否可以将这棵树划分成k个连通块并且每个连通块的总和是不是大于等于m，等价于是否可以把树划分成大于等于k个的连通块并且每一个连通块的节点总和大于等于m。那么我们就可以利用暴力对树形结构进行搜索，记录每一个连通块的节点总和，对于连通块的总和大于等于m对计数器进行加一操作，最后比较计数器的最后大小和m，要是计数器的大小大于m，最后的返回值就是true，否者返回值就是false。下面是完整代码: class Solution ...

一.题目描述NC571寻找牛妹n个结点之间有n-1条边，有一个目标数组X，其中有m个目标结点，从根结点走到每个目标结点Xi，每条边最多可以走两次，问从根结点走到每一个目标节点最多可以经过几条边?二.算法(暴力搜索)首先我们要理解题意，但对于n个节点之间有n-1条边我们可以认为其是一个树，由于其连通性我们可以做出如下分析： ，下面我们利用暴力搜索来解决，下面给出完整代码： class Solution { public: int num[200005];//记录孩子个数(并不是一层而是下方全部) int dis[200005];//记录距离 vector<int&...

一.题目描述NC574牛牛的魔法值求一个数组中每个连续子段中最大值和次最大值的异或值的最大值二.算法(模拟)我们可以枚举数组中每个元素，将其作为次大值，因为它所在的连续子段中只存在一个最大值，可以去寻找右边第一个比它大的元素和左边边第一个比它大的元素，分别进行将枚举的元素和左右边最大值异或运算，得到这个连续子段中最大值和次最大值的异或的最大值，维护这个最大值，最后返回这个最大值。下面是完整代码： class Solution { public: int solve(int n, vector<int>& a) { if(a.size()==1) re...

一.题目描述NC575牛牛算数计算x，y两个数的和，需要花费秒，并且每次只能计算一次，怎么合理安排计算的顺序，可以使得花费的时间最短，输出计算n个数字和的最小花费的时间。二.算法(优先队列)利用STL中的priority_queue来解决问题，用priority_queue来模拟小根堆，开始对所有花费时间插入堆中。每次弹出两个堆中元素对两个元素的和进行累加，然后将结果再放入堆中排序，直至堆中只有一个元素。最后的返回值是两个元素的和的累加值乘以c。下面是完整代码： class Solution { public: long long solve(int n, int c, vector&...

一.题目描述NC570扩散IIn个节点，n-1条边使之连通(两两之间是联通的)，每条边代表距离为1。一共m次污染，每次发生在数组元素x[i]，影响范围是与发生点距离不超过y[i]，影响范围所有节点污染指数增加z[i]，污染指数初始值全部为0，求m次污染发生后，每个节点的污染指数。二.算法(搜索)理解题目意思后我们可以利用搜索来解决，我们可以用邻接矩阵构建一个无向图，然后对每次发生污染的初始节点进行一次遍历，对其进行深度优先遍历，搜索的层次为y[i]，对每一个被搜索到的点进行节点污染指数增加z[i]，求出m次污染发生后每个节点的污染指数。 (图片来源牛客)所以整体搜索的思路也变的很清晰了，我们对...

一.题目描述NC567异次元空间数组a表示n个异次元空间的暗物质数量，每天每个异次元空间的暗物质数量会增加d数组中对应元素的值，可以选择冻结空间使之每天不再增加，也可以选择解除冻结，如果异次元空间的暗物质数量大于等于P，会对P取余，P一定为质数，最少可以在第几天的晚上有不少于m个异次元空间有刚好k个暗物质。二.算法(数学)上面是博主的推导过程(字丑勿怪)，下面是对其进行解释。首先对于每一个异空间可以进行两种选择就是冻结和解除冻结，所以对于每一个异空间刚好有k个暗物质物质是独立了，所以对于每一个异空间什么时候是刚好是k个暗物质是可以计算的(这块可以参考上面图片的推导，涉及到同余和拓展欧几里得求逆...

一.题目描述NC516牛妹的招聘每一个人都有一个聪明值Si(-1000<=Si<=1000)和勤奋值Fi(-1000<=Fi<=1000)。希望选入所有人的Si+Fi的总和最大，并且选中的所个人聪明值与勤奋值的和不能是负数，求出最大的总和。二.算法(单调栈)对于n个人每个人存在两个状态就是选择或者不选择，如果我们暴力进行那么就之间的复杂度，很显然是会直接爆炸的。不如我们换一种思路利用单调栈去维护最大值，可以对时间进行极大的优化。开始的时候我们用一个q记录所有可能达到的聪明值的和和与勤奋值的和，如果利用单调栈维护最大值，进行提前淘汰，就会减少很多无用搜索。我们开始要按聪明...

一.题目描述NC566连续段的中数一个长度为n的正整数序列a1,a2,a3......an，现在要从里面取出一段连续的长度大于等于k的序列。定义一个序列的“中数”为最大的整数x，使得序列中至少一半的数字大于等于x，求这个取出来的序列的中数最大可以是多少？二.算法(暴力)首先题目要求取出一段连续长度大于等于k的序列，我们可以遍历所有长度等于k的序列，然后找到每一个序列的中数，然后找到中数中的最大值。对于如何找到中数我们可以想到类似中位数的概念，在一段有序的序列中类似中位数是不是就满足这里的中数的条件呢？所以对于每段长度等于k的序列我们可以进行排序，后找出其中位数，就是其中数了，所以题目的思路就很...

一.题目描述NC565分石子有n堆石子堆，第i堆一共有ai个石子。对任意一堆石子数量大于1的石子堆进行分裂操作，分裂成两堆新的石子数量都大于等于1的石子堆。现在需要通过分裂得到m堆石子，求这m堆石子的最小值最大可以是多少？二.算法(暴力)可以采用暴力模拟的方法来解决，由于将石子不断进行分裂操作所以最大值一定小于等于初始石子堆的最小值，所以我们可以从开始的最小值不断递减去寻找，是否找到一个值可以使石子堆被分成m堆，然后返回这个值，那么这个值就是最小值的最大值，思路很简单，下面是完整代码： class Solution { public: int solve(int n, long lon...