lifehappy

分类

未归档(1) 每日一题(2) 题解(78)

/ 注册

全部文章（共81篇）

装货物

装货物思路显然对每个物品我们有两种操作，与已经放好了的放在一起，或者新开一个盒子来放，由于数据比较小，我们可以直接稍加剪纸的爆搜即可。第一个优化，当的时候立即返回。第二个优化，给定的序列从大到小排个序，这样我们就能保证后面的决策会较少的重复利用前面已经放号的盒子，减少回溯成本。代码 /* ...

2020-08-18

1 0

NC14250 MMSet2

MMSet2 思路这道题目显然能够通过的复杂度来暴力，这显然不能达到题目要求的复杂度，因此我们可以对题目要求我们计算的东西进行转换。某个点到所有点集的最大距离最小，这就有点像是重心的求法了，但是这题又有所不同，如果这是在一颗树上，显然我们可以很快的得到答案，，所以这题我们也可以转换思想，每次求解...

2020-08-17

1 824

[SCOI2009]生日礼物

[SCOI2009]生日礼物思路如果没有记错的话，这题跟某次多校的题几乎一模一样。区间问题的最小值，有一个最简单的办法就是尺取法了，只要通过两个指针的扫描就可以以线性的复杂度简单的实现，这里我们按照每个物品属于的种类作为我们num数组记录的值，然后再通过一次扫描就可以得到答案了。代码 /* ...

2020-08-15

1 654

[SCOI2010]游戏

[SCOI2010]游戏思路很容易看出这是一个二分图匹配问题，对于每一种属性，我们必须找到一个与之可以相应匹配的物品，所以我们建立的两条边，然后从开始匹配，当遇到第一个无法匹配的属性时我们即可输出答案，因为题目要求所有的攻击必选是连续递增的属性。代码 /* Author : lifehap...

2020-08-13

0 884

地斗主

地斗主思路看到这非常大，感觉一定是个结论公式题，但是感觉又不像是排列组合，于是可以考虑矩阵快速幂了，所以关键就是得得到递推公式了。我们将棋盘分成两部分我们假定显然对分别有种分法，对应到原来一整块的部分上也就是,并且后面的变化是由不断循环下去的，所以我们只要将即可得到递推式接下来就是这么一个简...

2020-08-12

2 1284

Mr. Kitayuta, the Treasure Hunter

Mr. Kitayuta, the Treasure Hunter 思路一眼看过去感没跑了，但是这个的数组着实开不下，但是我们不难发现有用的状态并不是太多，所以想想有没有什么方法来进行一下空间的优化，最多500个上下移动的步数我就不证明了。我们定义，表示我们从某个位置走了步到这里，所以我们有状态...

2020-08-11

0 772

矩阵消除游戏

矩阵消除游戏思路直接进行二进制枚举我们要选定的行，然后再贪心地选了，列，这样我们即可以保证我们都选择是最优的，然后取这些选择值里面的最优值就🆗了，具体看代码注释吗。代码 #include <bits/stdc++.h> using namespace std; #define...

2020-08-10

3 1036

没有上司的舞会

没有上司的舞会思路树形dp入门经典题里面的关系是一个树状的无环图，每个节点我们显然有两种取法，参加派对，不参加派对，所以状态转移方程就出来了参加派对，上司参加了舞会，其直系下属不能参加舞会不参加派对，上司没有参加舞会，其直系下属可以参加，也可以不参加。代码 /* Author...

2020-08-09

2 732

二叉苹果树

二叉苹果树思路一般的树都是对节点进行统计或者计算，但是这题是对边进行统计计算，所以要稍加特殊处理，貌似我这种方法处理的比较微妙。我们按照传统定义表示节点连接了条边的果子数量最大值，所以我们显然可以对当前节点进行统计枚举： for(int i) for(int j) 两重循环，表示的是该...

2020-08-09

1 0

小G有一个大树

小G有一个大树思路树的重心，经典的问题了，我们只要用一个数组来统计当前节点的儿子个数即可，然后按照题目更新答案。代码 /* Author : lifehappy */ #pragma GCC optimize(2) #pragma GCC optimize(3) #include <...

2020-08-09

1 750