HBlade

题解

/ 注册

全部文章 / 题解（共19篇）

【题解】Protecting the Flowers

题面：有n只牛，把牛都放到郊外吃花，每次带回一头牛，来回时长是2*ti,每头牛吃花的速度是di，问怎么带才能吃最少的花。思路：像这种题一般都往贪心去想，贪心有一个这样的理解就是，两个对比来贪。假如有两头牛，一个是a，一个是b，假如把a带回去，花费是，把b带回去就是因为排序可以通过比较函数排，我们...

2020-05-28

0 642

【题解】牛客算法周周练A-E

A 小A买彩票前言：开始以为这是一道可以通过计算算出来的题，后来想想不对，看到n这么小，应该就是概率dp了，在这道题上也可以看作暴力。思路：dp[i][j]表示前i张彩票，中奖总金额为j的概率的次数。转移方程：，其中k是1~4的数。为什么是这样？我们可以理解为，之后能抽到的总奖金j，是从之...

2020-05-27

0 783

【题解】货币系统

前言：这个题就是完全背包的裸题，只要把题目完全读懂就好了，难度不高。思路：首先我们知道，题目的意思是说能不能用更少种类的钱来表示这个货币系统，换言之就是，有的钱它可能可以通过小面额的钱来组成，那这种钱就不需要存在这个货币系统了，比如：2 5 9这个9就可以通过2+2+5来组成，所以9这个面额就...

2020-05-26

0 672

【题解】牛客算法周周练7 A、C、D、E

前言：快期末了时间越来越少了，补题也不能做那么多了，这次B题只过了40个大概就不写了吧，只写了比较简单的剩余4个题（其实C、D没见过这种题还真的不是那么简单） A 收集纸片这是小白月赛里面的题，我打过那场小白月赛，我当时用的方法是旅行商问题的DP，也就是先处理好两点间的距离dis[i][j]...

2020-05-26

1 654

【题解】建筑抢修

感想：这个题跟很早以前入门贪心的题看电影很类似，但是那个题是给定了开始时间和结束时间，所以按照结束时间贪心就好了，这个题给出的是持续时间和结束时间，但是依然是一个贪心。思路：如果按照工作时间排序，尽量做时间短的不一定就是最优解，因为可能时间短的都截止的晚，导致你截止时间早的就完不成了。所以首先肯定...

2020-05-25

0 603

【题解】小AA的数列

感想：真的不会做这种题，虽然已经想到了异或和这种题要按位求贡献，但是偶数还有区间这个问题想不出来怎么解决。后来看了别人的题解，想了好久才终于想明白怎么一回事了。思路：首先，一般异或和这种题都是按位求贡献这个方向是没错的。此时要算一个区间内的异或和的这一位是否有贡献（也就是区间异或和的这一位是否为1...

2020-05-23

2 1110

【题解】中位数图

每日一题终于来了一个简单的题了！！！思路：首先这是一个排列，也就是说每个数只出现一次。我们把要找到的数的位置记为pos，对于pos右边，从pos+1到n扫一遍，同时用map存下来一个值：从pos+1到i这段区间里面比b大和比b小的差值的个数（比如2 3 4这里面差值是-3，2 5 6的差值是1，也...

2020-05-21

0 671

【题解】图的遍历

感想：看到这个题目一开始没什么想法，因为不知道怎么才能每个点都走得到。后来发现本来是只能走图上的奇数位置点，如果你走一个奇环，就能改变奇偶了，从而可以走偶数个点了。思路：根据上面说的，如果一个图里存在一个奇环，就能够走完所有的点。但是这个图不一定是连通的，可能有很多个连通分量，所以这些连通分量之间...

2020-05-20

0 665

【题解】加分二叉树

我横竖睡不着，仔细看了半夜，才从字缝里看出字来，满本都写着四个字是‘区间DP’！为什么是区间DP呢？因为是中序遍历啊！中序遍历有一个很大的特点就是，根在中间，二叉树的左右子树节点在根的左右对应。那么我们只需要枚举根就好了，枚举根是不是就很像区间DP。对于一个区间，我们枚举分割点就相当于枚举根，然...

2020-05-20

0 646

【题解】简单瞎搞题

这是我第一次接触bitset的题，说实话我一开始真的不会做，后面发现是bitset优化dp才知道原来可以这样做。首先，这个题目是一个状压DP，dp[i]这个i表示前1到i个数的累加和能出现的状态有多少，这个我们可以用状压去记录，比如0号位是1表示0可以出现，1号位是1表示1可以出现。所以每个数需...

2020-05-19

0 668