lifehappy

题解

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

/ 注册

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

[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

排座椅

排座椅思路直接贪心，看哪个位置隔开得人多就在这个地方开一条路，所以我们只要统计一下每条道路隔开得人数，然后按照这个作为关键字，从大到小排序，然后就可以得到我们得答案了。代码 /* Author : lifehappy */ #pragma GCC optimize(2) #pragma G...

2020-08-07

2 694

追债之旅

追债之旅思路最短路问题，考虑，用一个二维数组，表示第天到达号点的最小花费，数组的更新方式改为则更新数组，所以我们最后只要遍历天到达号节点，也就是数组，最后取其最小值就行。的关键就是一个有能够记录当前天数，这个状态的最小值，当前位置，这样的结构体，然后重载一下小于号运算符就可以跑个板子了。代码...

2020-08-05

4 939

蓝魔法师

蓝魔法师思路树上问题求方案数，考虑树形，我们设置表示，当节点联通块数量是时，以为根节点的树上的方案数量。显然我们可以做一个树上背包来枚举节点的连接情况，每次遍历一颗子树时枚举，要注意背包的枚举顺序均要从大到小开始枚举。最后再特判一个不与这颗子树相连的特殊情况，也就是。代码 /* Aut...

2020-08-04

10 806