首页
题库
公司真题
专项练习
面试题库
在线编程
面试
面试经验
AI 模拟面试
简历
求职
学习
课程
专栏·文章
竞赛
搜索
我要招人
发布职位
发布职位、邀约牛人
更多企业解决方案
在线笔面试、雇主品牌宣传
登录
/
注册
hnust_zhouzisheng
获赞
38
粉丝
2
关注
0
看过 TA
1
男
湖南科技大学
2023
C++
IP属地:山东
暂未填写个人简介
私信
关注
拉黑
举报
举报
确定要拉黑hnust_zhouzisheng吗?
发布(30)
刷题
hnust_zhouzisheng
2020-06-16 21:40
C++
【题解】 分特产
题意:有m种物品,每个物品有ar[i]个,将其分予n人使得每人至少有一个,求分配方法种数。 容斥原理。运用容斥原理关键在于求得至多或至少然后去重。题目中有一个“至少”,不过显然不是我们要找的。不妨这样理解:每人至少有一个,也就是有0人没有被分到。那么我们可以找至少有x人没被分到,容斥一下便是0人没被分到的结果。考虑至少有x人没有被分到:C(n,x)选出x人,插板法将每种物品分给剩下的n-x人,每个人被分到的可以为零,乘法原理相乘即可:f(x)=C(n,x)* C(ar[i]+n-i-1,n-i-1)。所以答案即为f(0)-f(1)+f(2)-...+ * f(m-1)。 代码: #inclu...
0
点赞
评论
收藏
转发
hnust_zhouzisheng
2020-06-17 07:46
已编辑
C++
【每日一题】 Paint Box
数论——容斥原理。 从m种颜色中选出k种颜色给n个盒子上色,要求k种颜色都要用到且相邻盒子不能同色,求方法数。 首先,计算C(m,k)为选出k种颜色的方法数。 其次,k种颜色都要用到,换一句话说就是恰好用到k种颜色,显而易见应该转化为至少或者至多再考虑用容斥原理去重。记f(i)表示至多用i种颜色上色的方案数,容易得到f(i)=i* 。考虑对f(k)去重:最终方案数=至多用k种颜色方案数-至多用k-1种颜色方案数+至多用k-2种颜色方案数-至多用k-3种颜色方案数+...+(-)至多用1种颜色方案数。注意,其中用i种颜色的方案数,并不仅仅是f(i),应该是C(k,i)*f(i),因为要考虑至多...
0
点赞
评论
收藏
转发
hnust_zhouzisheng
2020-06-15 16:56
C++
【每日一题】 字符串
尺取法。 1.从第一个字符开始,向右移动右界至子串合法,用vis数组记录每个字母出现的次数,cnt表示vis记录次数为零的字母数。 2.当cnt=0时,此时每个字母都至少出现了一次,也就是说此时的长度就是一个合法子串的长度。更新ans。同时向右移动左界至子串不合法,移动过程中不断更新ans。返回第一步直至右界超过字符串长度。 3.输出ans。 代码: #include <iostream> #include <queue> #include <set> #include <map> #include <vector> #include...
0
点赞
评论
收藏
转发
hnust_zhouzisheng
2020-06-14 17:02
C++
【算法】 排列组合——插板法
插板条件:1.每个元素相同2.分成的组不为空 原始问题:将10个相同的球放到3个不同的篮子里,每个篮子至少有一个球,有多少种方法?用0代表球、-代表板子,则有:0-0-0-0-0-0-0-0-0-0,相邻两球之间插个板,共有9个板,我们只要从中选出两个板即可分成3个部分,也就是三个篮子。即C(9,2)。若将n个相同的球放到m个不同的篮子里,篮子不为空,则有C(n-1,m-1)种不同的方法。 变形1:将10个相同的球放到3个不同的篮子里,篮子可以为空,有多少种方法?因为篮子可以为空,所以不符合第二个条件。可以考虑加入三个球,按照原始问题的方法分成三个篮子后,每个篮子拿掉一个球,这样就考虑到了空篮...
0
点赞
评论
收藏
转发
hnust_zhouzisheng
2020-06-11 17:40
C++
【算法】 主席树
解决问题:m次询问,每次给定一段区间,求静态区间kth。 考虑对每个点i建一棵权值线段树,维护1-i区间里的数出现的次数。例如给定6个数:1 3 2 3 6 1,第4棵树如下:n棵权值线段树形状一样,考虑对两棵树相减:第i棵树维护1-i区间里的数出现的次数,第j棵树维护1-j区间里的数出现的次数(i>j),第i棵减第j棵则得到一棵新的权值线段树,维护j+1-i区间里的数出现的次数。这就是主席树的一个核心思想:前缀和思想。 现在看主席树的另一个核心思想:空间优化。建立n棵线段树需要的空间太大了,需要进行优化。观察每次添加新节点时树的变化,发现只有从某个叶子节点到根节点路径上的点的权值发生了...
0
点赞
评论
收藏
转发
hnust_zhouzisheng
2020-06-10 23:51
C++
【每日一题】 粉刷匠
动态规划。 原问题:n个木板粉刷t次的最多粉刷个数子问题:前i个木板刷j次的最多粉刷个数描述:记dp1[i][j]表示前i个木板刷j次的最多粉刷个数推出dp1[i][j]=max{dp1[i-1][j-k]+第i个板粉刷k次的最多粉刷个数},k<=j 这又产生了新问题,如何求某个板粉刷某次的最多个数呢?用第二层动态规划:原问题:某板整体粉刷k次的最多粉刷个数子问题:某板前j块刷k次得最多粉刷个数描述:记dp2[j][k]表示某板前j块刷k次得最多粉刷个数因为每次粉刷连续一段,所以考虑第j块时可以考虑从第j块前面的第l块一直刷到第j块,刷的颜色取决于这一段红蓝两色应刷的个数;预处理sum[...
0
点赞
评论
收藏
转发
hnust_zhouzisheng
2020-06-10 00:04
C++
【每日一题】 失衡天平
动态规划。 首先,题目说不限操作次数,但其实只要操作一次即可,因为每次操作得到的两堆重量差值均<=m,只要将每次得到的两堆按大小互补的方式与前一次的两堆合并到一起即可,最后相当于得到一次操作的结果。 其次,动态规划。原问题:从n个物品中选出两堆重量差不超过m时最大重量和。子问题:从前i个物品选出两堆重量差不超过j时最大重量和。描述:记dp[i][j]表示从前i个物品选出两堆重量差不超过j时最大重量和。分析状态之间的关系,对于第i个物品,有如下几种可能的情况:不选取,dp[i][j]=dp[i-1][j];加在大堆,dp[i][j]=dp[i-1][j-ar[i]]+ar[i];加在小堆,...
0
点赞
评论
收藏
转发
hnust_zhouzisheng
2020-06-06 10:20
C++
【每日一题】 德玛西亚万岁
状态压缩动态规划,即状压dp,是利用二进制表示状态的一种dp。根据题意,标记为1的土地只有有人(1)和无人(0)两种状态,所以状压显而易见。 记dp[i][j]表示第i行状态为j的方案数,初始化dp[0][0]=1;同时采用二进制数ar[i]记录第i行的土地状态。首先,对于每一行i,状态j必须是合法的,得到((j|ar[i])==ar[i])&&(j&(j>>1)==0),因为方案不能与土地冲突,同时同一行相邻的两个不能同时为1。其次,考虑第i-1行状态k转移到第i行状态j,得到(j&k)==0,因为同一列相邻两个不能同时为1,求得转移方程:dp[i...
0
点赞
评论
收藏
转发
hnust_zhouzisheng
2020-06-01 16:28
C++
【题解】 点对最大值
树上dp。记low1[u]为从u向下搜索到的最大路径值加起点值,low2[u]为从u向下搜索到的次大路径值加起点值。考虑非叶子节点u及以其为根的子树:若u为端点,则ans=max(ans,low1[u]+weight[u]);若u不为端点,则ans=max(ans,low1[u]+low2[u])。 对于dfs遍历到的每个非叶子节点都以此更新ans的值;对于叶子节点则令low1[u]=weight[u],low2[u]=-inf,因为同一段路径不能经过两次。 代码: #include <iostream> #include <queue> #include <se...
0
点赞
评论
收藏
转发
hnust_zhouzisheng
2020-05-30 12:39
已编辑
C++
【算法】 前向星存图
前向星是一种特殊的边集数组。不同于邻接表和邻接矩阵对顶点的处理,前向星存图处理的是边与边的关系。 int cnt; //记录边的编号 int head[maxn]; //head[u]表示上一个以u为起点的边的编号,初始化-1 struct st //储存边的信息 { int to; //边的终点 int w; //边的权值 int next; //下一个同起点边的编号 } edge[maxn];这里再解释一下head数组和edge数组: edge[i]并不是表示第i个顶点,...
0
点赞
评论
收藏
转发
hnust_zhouzisheng
2020-05-18 22:17
C++
【每日一题】 Rinne Loves Edges
题意:给定一棵带权树和它的根,要求删除一些边使得叶子节点无法到达根节点,求删除边的权值之和的最小值。思路:树型dp,其本质为搜索,即遍历树并在返回时维护相关的值。将原树拆分成以其孩子为根的多个子树,对于一棵子树有两种情况:1.删除子树的根与其双亲相连的边。2.删除子树的边。只要对这两种情况取最小值再回代即可。代码: #include <iostream> #include <queue> #include <set> #include <map> #include <vector> #include <stack> #in...
0
点赞
评论
收藏
转发
hnust_zhouzisheng
2020-05-16 11:38
C++
【每日一题】 合并回文子串
题意:给定两个字符串a和b,从a和b中选取若干元素,不改变其在原字符串中的顺序,求能够形成的回文串的最大长度。思路:区间dp。用dp[i][j][k][l]表示从a串选取第i个到第j个元素,从b串选取第k个到第l个元素,这些元素能否形成回文串。可以这样考虑回文串的形成:一个回文串在两边加上相同的字符形成一个新的回文串。因为要求不改变字符在原串的顺序,所以两边加上的字符有以下几种可能: a[i]-a[j] a[i]-b[l] b[k]-a[j] b[k]-b[l];得到以下状态转移方程:dp[i][j][k][l]|=(a[i]==a[j])&&dp...
0
点赞
评论
收藏
转发
hnust_zhouzisheng
2020-05-15 22:57
C++
【每日一题】 滑动窗口
题意:给定一个长度为n的序列和长度为k的窗口,求每次窗口滑动时窗口内元素的最大值和最小值。思路:经典的单调队列题目,这里采用双端队列处理,维护单调非递增(/减)队列考虑求最小值:若ar[i]小于等于队尾元素,则不断弹出队尾元素,因为ar[i]比它们有更大的发展空间;将ar[i]入队,因为当队首元素不断弹出时,其有可能成为最小值;若队首元素离开窗口则弹出;输出队首元素。最大值情况同理。代码: #include <iostream> #include <queue> #include <set> #include <map> #include <...
0
点赞
评论
收藏
转发
hnust_zhouzisheng
2020-06-15 16:43
已编辑
C++
【每日一题】 数学考试
题意:给定一个长度为n的序列,选取两个不相交且长度为k的区间,求两个区间的元素之和的最大值。思路:记sum_right[i]为以i为右界且长度为k的区间内元素和,记left_max[i]为左界大于等于i的所有区间元素和的最大值。一趟遍历可求出sum_right,再利用其求出left_max,最后求得ans=max{sum_right[i]+left_max[i+1]};代码: #include <iostream> #include <queue> #include <set> #include <map> #include <vector...
0
点赞
评论
收藏
转发
hnust_zhouzisheng
2020-05-15 15:41
已编辑
C++
【每日一题】tokitsukaze and Soldier
题意:有n个士兵,每个士兵 i 有武力值v[i]和限制人数s[i],即:若选择了第 i 个士兵则选择的总人数不能超过s[i]。求v[i]总和的最大值。 思路:贪心,优先队列。按s[i]从大到小的顺序进行排序并遍历,对于每项v[i]直接入队。若size<=s[i]直接更新ans;若size>s[i]则最小项出队后更新ans。此方案确保将v[i]足够大的留在队列中,同时也考虑到了v[i]大而s[i]小的情况。 代码: #include <iostream> #include <queue> #include <set> #include <ma...
0
点赞
评论
收藏
转发
1
2
工具箱
TA的圈子
暂未加入圈子
TA的圈子
TA的笔记
暂无笔记
TA的笔记
登录
0
天
已登录
0
天
连续登录
0
人
今日访客
牛客网
牛客企业服务