monkeycpp
monkeycpp
全部文章
分类
每日一题(20)
归档
标签
去牛客网
登录
/
注册
monkeycpp的博客
全部文章
(共20篇)
[每日一题] [NC19158] 失衡天平
题目大意:将一组物品分成两组,每个物品都可以不出现在任何一组。希望两组的重量差异不超过M,最大化总重量。 https://ac.nowcoder.com/acm/problem/19158 基本就是一个背包问题的变体,对于前i个物品,差异为gap时的最大总重量进行dp即可。转移为(i, gap) -...
2020-06-10
0
456
[每日一题] [NC20242] 最大子矩阵
题目大意:一个最多两列最多100行的数字矩阵,从中选出K个不重叠的矩形,他们的数字之和最大是多少? https://ac.nowcoder.com/acm/problem/20242 看到最多有两列,可以想到关于每一行的状态进行状态压缩DP,可能状态是:空,左边被占用,右边被占用,左右被不同矩形占用...
2020-06-05
0
697
[每日一题] [NC23486] 小A与小B
题目大意:一个迷宫里面有src和dst,src每次可以八个方向走一步,dst每次可以走两次,每次只能四个方向,不能走障碍物上。问最少多少次可以相遇。注意可以原地不动。 https://ac.nowcoder.com/acm/problem/23486 这题比较标准的双向BFS,注意可以原地不动。比如...
2020-06-04
0
548
[每日一题] [NC19916] 扑克牌
题目大意:有n种扑克牌,每种有ci个。还有m张百搭牌。一个套牌是1,2,...,n或者用百搭牌代替其中任一张。最多可以造出几个套牌。 https://ac.nowcoder.com/acm/problem/19916 也许有纯数学的做法,但是能造出k个套牌显然也能造出k-1个套牌,所以feasibi...
2020-06-03
0
665
[每日一题] [NC15034] 德玛西亚万岁
题目大意:有一些人可以站在mxn的格子里面,有一些格子不能站人,不能站在相邻格子,有几种站法。 https://ac.nowcoder.com/acm/problem/15034 这题就是一道很基本的状态压缩DP,时间复杂度是O(m2^n2^n)对于m=n=12刚好不会TLE。一开始没注意审题,注意...
2020-06-03
0
478
[每日一题] [NC15748] 旅游
https://ac.nowcoder.com/acm/problem/15748 题目大意:给定一个树,每天选择一个点访问,每次访问的时候标记其邻居。要求每天不能访问标记过的点。最多可以访问多少天。 题意就是选择一个maximum independent set,对于树来说就比较简单用tree d...
2020-06-01
0
578
[每日一题] [NC25043] Protecting the Flower
题目大意:有一些奶牛,每个奶牛有两个属性,一个是Ti,一个是Di。需要选择一个所有奶牛的排列,使得以下的值最小:每个奶牛被选中时,加上Ti和所有尚未被选中的Di的总和。例如T1=D1=D2=2,T2=3时,如果先选择1,该总和为T1D2=4,如果先选择2,该总和为T2D1=6,则12顺序优于21顺序...
2020-05-27
0
565
[每日一题] [NC21228] 货币系统
题目大意:给定n个数字[A1,...,An],用他们的非负倍数线性组合能生成的集合S[A1,...,An]最少可以由多少个数字生成。比如S[2, 4] = S[2],只需要一个数字。S[3,5]至少需要两个数字。 https://ac.nowcoder.com/acm/problem/21228 首...
2020-05-26
0
498
[每日一题] [NC14414] 小AA的数列
题目大意:给定一个int数组,求所有长度为偶数的连续区间,且长度在[L,R]区间内,xor的总和。 https://ac.nowcoder.com/acm/problem/14414 很明显,可以不妨只对一个数位进行计算。如果我们知道倒数第五位,xor在这一位为1的符合要求的区间个数为10,那么我们...
2020-05-22
0
608
[每日一题] NC19913 [CQOI2009]中位数图
题目大意:给定1,2,...,n的排列,和一个pivot number,求多少个长度为奇数的连续自序列的中位数恰好为这个pivot number。 https://ac.nowcoder.com/acm/problem/19913 因为没给数据范围,首先测了一下OJ,发现O(n^3) TLE,O(n...
2020-05-21
0
539
首页
上一页
1
2
下一页
末页