在刷题的单身狗很开心 - 个人主页动态 - 牛客网

发布(192) 评论刷题收藏

2023-09-16 11:12

中原工学院 Java

题目链接：D-数树_牛客小白月赛78 (nowcoder.com)   本题要求构造出来的有根二叉树的所有导出子图是一颗满二叉树的数目最多是多少？那么显而易见必须是一个完全二叉树。   那么问题就回到了给你一个完全二叉树有多少个节点，求完全二叉树里面有多少个导出子图是满二叉树的数目。   首先介绍官方题解的思路：   官方题解将问题进行拆分，首先完全二叉树除了最后一层上面的一定是一个满二叉树。那么就上面这个满二叉树而言，每一个的大小就是i*(n-i+1) （i是层数，n是慢二叉树的高度）。   那么剩下的就是对于最后一层的处理，对于最后一层，最后一层的个数为2的倍数的时候，那么他可以增加的满二...

0 点赞评论收藏

分享

2023-09-16 10:54

已编辑

中原工学院 Java

C-第K小表示数

题目链接：C-第K小表示数_牛客小白月赛78 (nowcoder.com)   看了题解真的感觉还挺简单的，但考试的时候没有注意到所有的数都是由a*x+b*y构成的。而且题也没有读明白，以为一开始不止两个数呢。   本质上是一道数学题吧，感觉不算什么算法硬要说的话算贪心吧。   可以看到所有的数都是由a和b的倍数和相加得到，那么我们想得到最小的第k个数，就需要每一步得到一个最小的值。而如何去计算出最小的值呢，那么可以掏出当前的最小的值（也就是set容器的第一个，因为set容器内部默认从大到小排序）。那么这个最小值要么加上a要么加上b可以得到最小的，可能你会想要是b超级大那么加b得到的不就不是小...

0 点赞评论收藏

分享

2023-09-15 17:21

中原工学院 Java

题解 | #DongDong认亲戚#

//并查集的模板题，写个并查集完事 #include <bits/stdc++.h> using namespace std; map<string , string> mp; string find(string s) {     return mp[s]==s? s:mp[s] = find(mp[s]); } void merge(string s1, string&...

0 点赞评论收藏

分享

2023-09-15 17:00

中原工学院 Java

题解 | #牛可乐与NCPC#

这题好难。。。，题目上要求不存在一个队伍j使得链接：aj≤ai,bj<bi 或者 aj<ai,bj≤bia_j< a_i,b_j\leq b_iaj<ai,bj≤bi 那么就可以加入观察里面。单纯从数据上看两个变量都需要满足，有点麻烦。   但如果放到坐标系上可以看出其实是要求i所形成的矩形里面不能有别的点（包括边框）（这是难想的第一步，将问题进行转换）。那么现在要解决的问题就是如何快速的知道某个矩形里面有没有不符合要求的点。按照题目来说就是每增加一个判断里面是否有点，如果没有就加入观察队列里面，还需要将受这个点影响而导致变成不符合的点排除。   那么如何用代码实现呢，...

0 点赞评论收藏

分享

2023-09-15 16:05

中原工学院 Java

题解 | #任务#

本题是一个贪心问题，如果进行任务和机器的匹配是我们要考虑的问题。首先如果按照任务的要求去找机器的话，那么任务可以先定时间，去机器里面找时间上符合要求的机器，然后肯定是要选择满足难度级别的最小的那一个，这样可以为后面的任务腾出最大的空间。但题目要求数量和利润都达到最大，但从利润的计算公式上看，时间的占比是难度级别赶不上的。所以直接按照难度级别尽量的去做任务就可以了。本题在寻找满足难度级别的难度级别最小的机器的时候要使用二分查找，或者使用现成的lower_bound，否则双重循环会超时。   #include <bits/stdc++.h> typedef long...

0 点赞评论收藏

分享

2023-09-15 14:02

中原工学院 Java

题解 | #Let'sPlayCurling#

算是一道考验思维的题吧，关键在于看出来如果要距离红球比篮球近的话那必然不能跨越篮球。那么就需要红球扎堆，也就是说红球扎堆的越多就有更多的胜利。   那么就到了统计红球的个数了。可以使用前缀和来求解。   #include <bits/stdc++.h> using namespace std; const int maxn = 5e5+10; //1代表红色，0代表蓝色 map<int, int, greater<int>> mp; map<int,&n...

0 点赞评论收藏

分享

2023-09-14 21:11

中原工学院 Java

题解 | #星球大战#

本题的数据范围有点大，所以得使用map去进行离散化。由于map的key不能重，而一行里面又有多个y坐标，所以要用map里面套set的方式去求解。   在消除某一行的时候自然需要把这一行里面列相关的给消除掉，毕竟题上说了死人不能再死一次。让我奇怪的是得要用multiset？难道有可能在一个坐标处建立两个基地吗？   #include <bits/stdc++.h> using namespace std; int N, M; map<int, multiset<int> > mpx...

0 点赞评论收藏

分享

2023-09-14 17:31

中原工学院 Java

题解 | #[JSOI2007]建筑抢修#

先按照最晚修理时间进行排序，从最早的开始进行遍历。进来后如果可以达到最晚修理时间那么直接加入即可，如果达不到的话，与我已有的建筑的修理时间进行比较如果修理时间比原有的小的话那么就需要对原来的建筑进行一个调整，如果大的话不变就行，总之是一个一换一的过程，但同时也为后面腾出了更多的修理时间，所以贪心成立。因为要比较最大的那一个所以维护一个大根堆比较方便。   #include <bits/stdc++.h> typedef long long ll; using namespace std; int N; const...

0 点赞评论收藏

分享

2023-09-14 16:54

中原工学院 Java

题解 | #tokitsukaze and Soldier#

本题是一个可后悔的贪心，首先从简单来看，如果单纯根据战力选择可能会因为人数现在而没有达到最优，如果根据人数限制选择，可能会出现极端战力导致错误。   但如果两个条件其中之一我们已知的话求解起来就比较简单了，如果我们已知人数限制，那么只需要在所有人数限制超过这个的人里面选最好的几个就行了。这看起来很像二分答案的思路，   但因为战力总和相对于人数并不单调，无法采用二分的方式。在这里采用从人数大到小枚举的方式，因为人数在从大到小，所以原来人数限制大的哪些士兵是不需要退出的，因为他们本来人数限制就可以容忍。但因为会有新的士兵进来，所以可能会将战力底的老士兵给挤掉，所以在这里建立一个小根堆来维护最小的...

0 点赞评论收藏

分享

2023-09-14 14:58

中原工学院 Java

题解 | #[JSOI2010]缓存交换#

本题是一个贪心问题，关键在于贪心策略如何选择。   想要缺失的可能性尽可能少，首先可能就想到丢掉后面出现次数少的，但比起出现次数顺序更加重要。最后得到贪心策略为：去掉最近的。   在本题中算法如何实现也不容器，应当保存下标才方便，否则如果相同的时候会有不必要的麻烦。   #include <bits/stdc++.h> using namespace std; const int maxn = 100000+10; map<int, int> mp; int nexti[...

0 点赞评论收藏

分享

2023-09-13 21:46

中原工学院 Java

题解 | #Running Median#

使用对顶堆可解，左边的堆维护中位数前半部分，右边的堆维护中位数后半部分。在新的数进来的时候判断应该插左边还是右边，然后对左右如果差值超过1进行调整。   这样要么左堆的顶端是中位数，要么当左右相同大小的时候就是两个堆顶的数取平均数。   //对顶堆，以左边为承载多出来的那个中间数的堆 #include <bits/stdc++.h> using namespace std; int p; int main() {          cin&gt...

0 点赞评论收藏

分享

2023-09-13 20:22

中原工学院 Java

题解 | #第k小#

//建立两个堆，一个大根堆，一个小根堆。从K处劈开 #include <bits/stdc++.h> using namespace std; int n, m, k; const int maxn = 2e5+10; int a[maxn]; int main() {     priority_queue<int, vector<int>, less<int>&n...

0 点赞评论收藏

分享

2023-09-12 15:48

中原工学院 Java

题解 | #Largest Rectangle in a Histogram#

限制大小的关键在于某一个矩形向左可以到什么地方，向右可以到什么地方。 如果可以得知这个长度，再乘以该矩形的高度就是我们所需要的该矩形的最大面积。  然后枚举求出所有矩形的最大面积，求最大的那一个就可以了。   那么如何去向左和向右寻找最远的地方呢？我们可以将问题转换成找最近的阻挡点，那么就可以使用一个单调栈来维护这个最近的阻挡点。如果当前是最小的那一个，那么就不存在什么阻挡点所以直接将他的下标填到极限的地方，否则就去栈里面不断将大于等于该矩形高度的不断出栈，最后剩下的就是最近的阻挡点。右边的过程同样如此。   //限制大小的关键在于某一个矩形向左可以到什么地方，向右可以到什么地方。 //如果可...

0 点赞评论收藏

分享

2023-09-12 13:59

中原工学院 Java

题解 | #Look Up#

类似于滑动窗口，但比滑动窗口要简单。在本题中因为是向坐看（其实是向高下标的方向看）。所以从后向前去遍历，如果栈为空那么直接加入即可，如果当前的数比栈顶的数要大，那么栈顶里面的数不可能成为那个被仰望的了，所以弹出，又因为可能不止一个，所以用循环。如果比栈顶数要小证明还有可能称为那个背仰望的，接着加入栈中就可以了。   #include <bits/stdc++.h> using namespace std; const int maxn = 100000+10; stack<int> st; ...

0 点赞评论收藏

分享

2023-09-12 10:57

中原工学院 Java

题解 | #Sliding Window#

本题是一个滑动窗口问题，在移动过程中改变的是第一个数被丢掉和下一个数加进来。那么可以建立一个队列，如果当前进来的这个数比前面的某些数要大的话就需要出队，因为由于这个更大的数的存在前面的数就不可能变成最大的数。那么就需要直接从队列里面删除。如果第一个在窗口移动的时候被丢掉了同样也要删除。如果新加进来的比队列里面的数要小，那么他就还有称为最大值的潜力，将他放在队尾保留。求最小值同样也是这样。   要注意：由于在窗口移动过程中丢掉的不能直接使用数值是否相等来判断，因为可能有一样的数字造成错误的删除。保存下标才是明智之举。   #include <bits/stdc++.h> u...

0 点赞评论收藏

分享

创作者周榜

更多

关注他的用户也关注了：

牛客网
牛客网在线编程
牛客网题解
牛客企业服务