sunsetcolors

题解

/ 注册

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

树上子链

树上子链题目地址： https://ac.nowcoder.com/acm/problem/202475 基本思路：基本上类似树的直径的求法,我们每次找子树中的次长链和最长链相连取最大就是了,注意由于有负数的情况,可能取了次长链反而更不优,所以要再对只取最长链的情况多取一个，其余地方就和...

2020-08-13

2 644

没有上司的舞会

没有上司的舞会题目地址： https://ac.nowcoder.com/acm/problem/51178 基本思路：我们在每个节点用两个状态,设表示不选择节点,子树快乐指数的最大值, 表示选择节点,子树快乐指数的最大值。那么我们容易得到如下的转移方程：然后我们对和取就是答案了...

2020-08-13

0 583

小G有一个大树

小G有一个大树题目地址： https://ac.nowcoder.com/acm/problem/15033 基本思路：树的重心模板题，我们顺便来复习一下重心的性质：树的重心的定义就是题意：找到一个点,其所有的子树中最大的子树节点数最少。我们再来看下百度百科里树的重心的性质：树中...

2020-08-13

1 681

NC19833 地斗主

地斗主题目地址： https://ac.nowcoder.com/acm/problem/19833 基本思路：我们看到对于的数据,所以很明显这题应该能推出公式,因此,我们手推或者打表出前几项，然后我们用我们睿智的头脑,和锐利眼光去观察(使用oeis),就能得到如下递推式： . 然后我们...

2020-08-12

0 994

NC110793 Mr. Kitayuta, the Treasure Hunter

Mr. Kitayuta, the Treasure Hunter 题目地址： https://ac.nowcoder.com/acm/problem/110793 基本思路：比较明显的一个线性,关键点是我们要计算出增长与减少的范围。我们用表示在第个位置，上一次是跳的距离为时的最大宝石数...

2020-08-11

3 699

NC200190 矩阵消除游戏

矩阵消除游戏题目地址： https://ac.nowcoder.com/acm/problem/200190 基本思路：我们看到题目的范围非常小,因此我们考虑二进制枚举,我们枚举每一行,然后我们在选择行确定的情况下去贪心的选择列就好了,代码量可能比较多，但是没什么思维难度,具体可以看代码...

2020-08-10

0 681

NC16618 排座椅

排座椅题目地址： https://ac.nowcoder.com/acm/problem/16618 基本思路：我们贪心的进行隔断就好了,记录每个行,每个列,进行隔断能减少的交头接耳人数,然后将能减少的人数从大到小排个序,那么排序后的前行，和前列一定就是那些最优的选择.然后因为答案要从小...

2020-08-07

0 611

NC14700 追债之旅

追债之旅题目地址： https://ac.nowcoder.com/acm/problem/14700 基本思路：比较容易看出是一个最短路,我们把每个点,根据个到达时间拆成个点,然后我们一样跑,只是在的过程中多记录一下耗时就行了。最后我们在里取最小值就是答案了,如果都不能到达那就输出-1...

2020-08-05

0 660

NC20811 蓝魔法师

蓝魔法师题目地址： https://ac.nowcoder.com/acm/problem/20811 基本思路：考虑树形,我们用表示在以为根的子树中,包含且连通块大小为的方案数,考虑在以每一个节点为根的情况,我们对于它的每一棵子树进行转移,我们假设已经对之前的几个子树做完了处理,那么在...

2020-08-04

2 973

NC14526 购物

购物题目地址： https://ac.nowcoder.com/acm/problem/14526 基本思路：考虑,设表示处理到第天,买了个糖果的最小花费;首先我们在每一天里,肯定是优先买价格更低的糖果,因此我们先对每一天排序,并且求一个前缀和;然后我们考虑如何转移,首先我们第天的合法糖...

2020-08-03

2 834