首页
题库
公司真题
专项练习
面试题库
在线编程
面试
面试经验
AI 模拟面试
简历
求职
学习
课程
专栏·文章
竞赛
搜索
我要招人
发布职位
发布职位、邀约牛人
更多企业解决方案
在线笔面试、雇主品牌宣传
登录
/
注册
hnust_zhouzisheng
获赞
38
粉丝
2
关注
0
看过 TA
1
男
湖南科技大学
2023
C++
IP属地:山东
暂未填写个人简介
私信
关注
拉黑
举报
举报
确定要拉黑hnust_zhouzisheng吗?
发布(30)
刷题
hnust_zhouzisheng
2020-08-07 19:15
C++
【每日一题】 Max Power
题意:一个技能树一共有n行,第i行有n-i+1个技能,要学习第i行第j列技能的前提是学习第i-1行第j列和j+1列的技能,每个技能会带来一定收益。问给定技能的最多学习次数,能够得到的最大收益是多少。 思路:dp。将技能的收益按如下格式列出:1 2 3 4 51 2 3 41 2 31 21因为一个技能能够被学习的前提是其正上方技能和右上方技能被学习,而递推之后可以发现实际上是一个上三角区域内的技能全部被学习,所以可以推出要学习一个技能至少要用多少个技能点。除此之外,不排除 第二列学习四个技能。第一列只学习了一个技能 的情况,所以不能仅...
0
点赞
评论
收藏
转发
hnust_zhouzisheng
2020-08-07 18:48
C++
【每日一题】 [CQOI2007]涂色PAINT
题意:对于一段空白的木板,每次可以选取连续的一段涂上任意中颜色,问将木板涂至给定颜色需要的最少次数。 思路:区间dp。原问题:将木板全部涂色完成需要的最少次数。子问题:将木板的连续某一段涂完需要的最少次数。记:dp[i][j]表示将木板的第i块至第j块涂成指定颜色需要的最少次数。 区间dp考虑先枚举长度;当块的长度为一时,只要涂一次,即dp[i][i]=1;当木板长度大于一时:若端点的两块颜色相同,可认为在涂一端时顺带涂了另一端,所以 dp[i][j]=min(dp[i][j-1],d[i+1][j]);若端点的两块颜色不相同,则可以在端点间枚举端点,即先涂第i块到第k块,再涂第k+1块到第j...
0
点赞
评论
收藏
转发
hnust_zhouzisheng
2020-07-24 22:24
C++
【每日一题】 乌龟棋
动态规划 一道很正的动态规划题,直接进行分析:原问题:选取所有卡片到最后一个格子是能够得到的最大分数;子问题:四种卡片分别选i,j,k,l张时能得到的最大分数;记dp[i][j][k][l]为四种卡片分别选出了i,j,k,l张时能够取得的最大分数。 有的人可能会按“前i个格子如何选取卡片”类似这样的套路分析,这里要注意的是,当每种卡片的个数确定了以后,走到的格子也是确定的,同时题目还确保了使用所有的卡片可以恰好到达最后一个格子,这就更没有必要讨论“前几个格子了”。 代码: #include <iostream> #include <queue> #include <...
0
点赞
评论
收藏
转发
hnust_zhouzisheng
2020-07-24 17:04
C++
【每日一题】 小A的柱状图
单调栈 本题要求找出最大矩形的面积。从基本概念入手,给定长(本题也可以说“高”)和宽便可以确定一个矩形的面积,所以我们的任务便是找到高和宽。 首先,要尝试所有的区间很显然是不可能的;可以发现对于每一段区间,矩形的宽都可以用a数组的前缀和求出来,所以我们的任务重心转移到了矩形的高上。 求高便是求一段区间内h的最小值,这里容易想到单调队列栈。很显然此处不能用单调队列处理,因为并没有指定矩形的宽占多少区间,所以采用单调栈处理。单调栈:求数组某个位置的值在哪个最大区间(相邻)是最值。此时只要找到每个位置的在哪个最大区间是最小值即可,因为一旦超过这个区间,要么是超过了边界,要么是存在一个h[i]小于该高...
0
点赞
评论
收藏
转发
hnust_zhouzisheng
2020-07-20 18:58
C++
【每日一题】 区间权值
前缀和 首先说明一下题目中的要求值的式子的意思:对于所有的区间[l,r](其中1<=l<=r<=n),求每个区间点对应的数的和(即a[i]的和),将其乘以区间的长度对应的权值(即w[r-l+1]),取和并输出。 理解了上述之后,毫无疑问此题需要用前缀和,解决此题有两种处理途径:枚举点和枚举区间长度。枚举点:通过计算每个点在不同长度的区间中的贡献,进而求得该点在所有长度的区间中的贡献,可求得所有点在其所有出现过的区间中的贡献。枚举区间长度:通过计算在给定长度下的一个区间中其中所有点的贡献,进而求得在给定长度下所有区间中所有点的贡献,可求得在所有长度的区间中所有点的贡献。由于两种...
0
点赞
评论
收藏
转发
hnust_zhouzisheng
2020-07-16 20:06
C++
【每日一题】 点权和
首先,考虑一下常规思路,每次将操作数和与操作数相连的点的权值都加一,然后计算值。显然这种思路的会TLE。不过我们可以发现,这种思路其实不止适用于树,还适用于图。如此我们便要思考,就本题而言,树与图有什么区别。树型结构为一对多的关系,不像图的多对多,这使得我们可以从树中找到节点的祖宗及后代,因此我们要从这里入手。 先前常规思路的超时,主要原因是在每次操作中,计算了所有与操作数相连的点,时间复杂度为O(n),我们需要在O(1)的时间复杂度内完成此操作。在树型结构中,一次操作要计算指定点、其父节点和其所有子节点,而一次对指定点的操作会影响到其父节点、子节点和其祖父节点、孙子节点(当计算与其相邻的点权...
0
点赞
评论
收藏
转发
hnust_zhouzisheng
2020-07-15 22:27
C++
【每日一题】 [SCOI2009]生日快乐
递归 数据范围较小,直接递归解决。考虑将当前蛋糕分成left块:当left==1时,返回长与宽的比值;当left>1时,若沿着当前蛋糕的某一条边切割总共有n/2种切割方法(考虑对称性),沿着长和宽总共有(n/2)*2种切割方法;对于当前蛋糕的每一种切割方法,递归考虑其切割后的两个蛋糕,得到二者切割后能够生成的小蛋糕中长宽比值最大者(从一种切割方法生成的n块蛋糕中找到长宽比值最大的一块);对于当前蛋糕的所有切割方法,从中选出每种比值最大的小蛋糕的最小比值,返回该比值。 值得注意的是,对于递归中生成的所有最小蛋糕,不能一味取其最大比值或最小比值;要分清楚递归过程中,哪些步骤是在选择切分方法(...
0
点赞
评论
收藏
转发
hnust_zhouzisheng
2020-07-12 11:10
C++
【题解】 [AHOI2007]密码箱
数论。 题意:给定一个正整数n,要求找到所有在[0,n)之间的整数x满足:%n=1。 思路:%n=1可以写作=nk+1,即:(x-1)(x+1)=nk。拆分x与k得到:(x-1)(x+1)=(n1k1)(n2k2),所以有:x-1=n1k1、x+1=n2k2。接下来当n1<=n2时,可以在时间内枚举n1,同时计算出n2并枚举k2,计算出x,判断是否存在整数k1。当n1>n2时同理枚举n2。此时要注意x<n的条件。 最后将两种情况的答案合并排序并去重后输出即可。 代码: #include <iostream> #include <queue> #incl...
0
点赞
评论
收藏
转发
hnust_zhouzisheng
2020-07-10 23:58
已编辑
C++
【每日一题】 kingdom
动态规划。 根据题意直接构造出树比较难,所以采用动态规划的方法。 记ans[i]表示当树有i个结点时所求花费的最大值。假设在考虑有i个结点时,我们已经知道了结点数小于i时的ans,则可以通过ans[i]=max(ans[i],ans[j]+???)得到答案,其中j为结点数为i时所有可能的重儿子,也就是题目中所说的“官员的心腹”。现在只需将“???”求出来。 理解“???”是什么意思,不妨先看看转移方程中缺什么。在选定了重儿子的同时其贡献也求了出来,即ans[j],现在需要安排轻儿子:求出轻儿子的贡献同时确保其小于重儿子。这就要求将除重儿子以外的结点分成若干组,每组结点数不能大于j。因此,我们再...
0
点赞
评论
收藏
转发
hnust_zhouzisheng
2020-07-10 21:25
C++
【每日一题】 矩阵取数游戏
区间dp。 首先,由题意,每行取数独立,因此可以分别分析每一行的情况。 其次,基础的区间dp。原问题:从序列第1个数到第m个数取出后的答案子问题:从序列第i个数到第j个数取出后的答案记dp[i][j]表示从序列中第i个数到第j个数取出后的答案,得到转移方程:dp[i][j]=max(dp[i+1][j]+ar[i]* ,dp[i][j-1]+ar[j]* ),其中len为区间的长度。简单说明一下为什么这里是而不是 。当区间长度为1时,意味着我们只取一个数,但是它是数列中最后取走的数,因为区间dp是从短到长考虑的,直接考虑完整的区间就不是dp了;当考虑区间长度为2时,新添加的数是倒数第二个被取走...
0
点赞
评论
收藏
转发
hnust_zhouzisheng
2020-07-09 12:33
C++
【每日一题】 平衡二叉树
递推 要求所有高度为n的平衡树中不平衡度的最大值,没必要考虑所有的树,只要想办法构造出一棵不平衡度最大的树即可。要想不平衡度最大,只要根节点的左右子树节点数差值最大即可。若不选取根节点,则高度上限会减少,得到的树不平衡度不是最大。而要使左右子树节点数差值最大,只要使左子树节点数最大、右子树节点数尽可能小即可。 左子树节点数最大即排满,为 -1。考虑右子树,即考虑在n和d的限制下节点数最少的平衡树,这里采用递推的方法。记f[n]为高度为n的节点数最少的平衡树,其左右子树高度差不超过d。要构造高度为n的树,可以进行如下操作:新建一个节点,其左子树为高度为n-1的平衡树,其右子树为高度为n-1-d的...
0
点赞
评论
收藏
转发
hnust_zhouzisheng
2020-07-04 12:05
C++
【题解】 Counting Cliques
dfs优化 题意:给定一个n个点、m条边的无向图,要找出图中大小为s的完全图的个数。 思路:先看一个常规思路,不过会TLE:从所有节点开始都进行一次dfs,将不在集合中并且能与集合中的点形成完全图的点加入集合,集合大小等于s时ans加一,逐层返回。为什么所有节点都要进行一次dfs?因为题目没说图一定是连通图。不过此算法要进行多次去重,例如当s=2时,1->2和2->1的两次dfs中得到的集合可能相同。所以鉴于上述考虑,我们只选择1->2这一次得到的集合而放弃2->1得到的集合,而如何实现已经暗示得很明显了,就是要从较小点走向较大点。将原来的无向图改为有向图,从较小的点指...
0
点赞
评论
收藏
转发
hnust_zhouzisheng
2020-07-11 18:36
已编辑
C++
【题解】 Recursive sequence
矩阵快速幂。 题意:一组数的递推公式如下:F(1)=a,F(2)=b,F(n)=F(n-1)+2* F(n-2)+ (n>2)。现要求出该序列中的第n个数。 思路:由于n的值太大,直接递推不行,这里采用构造系数矩阵的方法。本人目前的理解:当以递归得到数的效率太低时,可以研究递归过程,拆分或者合并公式中的数,研究两个过程的数之间的关系并建立一个矩阵,建立系数矩阵以系数矩阵的幂代替递归。诸如此类的还有求第n个斐波那契数。观察发现递推过程中的数有:F(n),F(n-1),,而下一个递推过程中的数有:F(n+1),F(n), ,我们要想办法通过第一个过程得到第二个过程。发现第二个过程需要 ,因此...
0
点赞
评论
收藏
转发
hnust_zhouzisheng
2020-07-02 16:50
C++
【每日一题】 毒瘤xor
数学+前缀和。 对于序列中的每一个数,采用二进制表示,以此判断X在每一位的值。 先考虑区间[1,n],假设这n个数有t个数的第j位为1,则有(n-t)个数的为0。接下来判断X在第j位应该是0还是1。已知异或的运算规则:相同为0,不同为1。如果要使求和得到的值尽可能大,那么X与每一个数的第j位异或运算后得到的1应该尽可能多。所以比较t与n-t的大小关系即可,若t>n-t,则1较多,X的第j位应该为0;反之则为1。有一点需要注意,题目要求在求和值尽可能大的同时,X的值要尽可能小,所以当0与1一样多时,X的第j位应为0。其它位以此规则可算出,最后累加即可。 当考虑区间[l,r]时,采用同样思路...
0
点赞
评论
收藏
转发
hnust_zhouzisheng
2020-07-02 10:09
C++
【每日一题】 珂朵莉的数列
离散化 + 树状数组 先看一下一般求逆序数的思路:设置vis数组,表示数字在前面遍历过程中出现的次数;遍历数组,vis[ar[i]]加一,然后求出大于ar[i]的数在前面出现的次数并加入到ans中。当序列数字过大是可以采用离散化处理,因为只需要知道大小关系即可,不必知道到底大了多少;对于求大于ar[i]的数出现的次数,可以采用树状数组求和:sum(vis[maxx]-vis[ar[i]])。 再回到本题,要求出所有区间的逆序数的总和,换一句话说就是求出所有逆序对所在区间数的总和。当(i,j)为逆序对时,其对ans的贡献为i* (n-j+1)(考虑到树状数组,下标从1开始)。当(i_1,j)(i...
0
点赞
评论
收藏
转发
1
2
工具箱
TA的圈子
暂未加入圈子
TA的圈子
TA的笔记
暂无笔记
TA的笔记
登录
0
天
已登录
0
天
连续登录
0
人
今日访客
牛客网
牛客企业服务