Peterliang

题解

PAT挑战日记(15) 《算法竞赛进阶指南》系列题解(4) 心路历程(1) 未归档(5) 模板(2)

/ 注册

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

NC576 题解 | #牛牛锻炼#

题意分析一共有个项目，每个项目的得分上线为。现在已经每个项目已经得到的分数了。每个项目对应的得分为。给定一个,我们想要总的得分得到最少还需要多少时间。思路分析贪心。我们很容易可以想到，如果想花费的时间最少，肯定实现做训练时间短的项目。所以，我们计算每个项目还可以得到的分数和这个项目...

Go 牛客题霸

2021-09-14

0 578

NC575 题解 | #牛牛算数#

题意分析给你一个序列，需要将这个序列进行两两合并，最后合并成一个数字。每次合并的花费就是这两个数字的和乘上一个c，问合并成一个数字的最小的花费是多少？思路分析学过数据结构的同学应该都知道，这一题是一个很经典的类似于哈夫曼树的题目。解题的方法就是每次找到当前最小的两个数字，然后将这两个数字...

牛客题霸

2021-09-14

0 640

NC568 题解 | #牛牛的导弹系统#

题意分析需要在每一天至少发射M枚炮弹。在进行交接的时候必须至少有一个系统可以正常发射。每个系统发射的时间为A天，冷却的时间为B天。问至少需要部署多少个导弹系统可以保证符合上述要求。思路分析首先，我们发现可以把A+B看作是一个周期，因为这个周期过后之前冷却的有可以继续使用了，相当于进入了...

牛客题霸

2021-09-14

0 549

NC574 题解 | #牛牛的魔法值#

题意分析给出一个序列，这个序列的数字都是不一样的，我们需要找出所有的子序列里面的最大值和次大值的异或的结果中的最大值。思路分析题目的意思已经很明显了。我们需要找到最大值和次大值。但是我们发现数据范围太大，直接暴力会被TLE。所以，我们要相办法进行优化。我们发现，在我们直接暴力枚举的时候，...

牛客题霸

2021-09-14

0 690

NC572 题解 | #连通块#

题意分析给你一棵树，需要我们将这棵树划分为k个联通块，同时每个联通块的节点的权值的和都要大于等于给定的值，问是否可以达到目的。思路分析我们观察得到，为了确保是联通块，而且达到贪心的目的，我们应该从树的叶子节点往上面进行扩展。如果某一个节点和他的子树可以构成一个满足题目条件的联通块。那么我...

牛客题霸

2021-09-11

0 905

NC571 题解 | #寻找牛妹#

题意分析给出一个以1为根的树，然后是m个询问，对于每个询问，需要我们计算从结点1到这个被询问的结点的最大的花费是多少？（题目中说的是至少要带多少金币才可以保证任何情况下都可以找到牛妹，所以应该是一个最大的花费。）思路分析首先，我们观察题目，我们发现这个题目是一个多组询问，所以应该是需要先...

牛客题霸

2021-09-10

0 599

NC567 题解 | #异次元空间#

题意分析给我们一个数组，这个数组的每个数都有一个每天都会进行一个增长，假如增长了x天，那么x天后的值为。但是这个数会对一个进行取模运算。同时，我们可以决定在什么时候让这个数字停止增长和继续增长。问至少要多少天可以使得这个数组里面的数字至少有个数字都为。思路分析首先，我们根据题目的意思进行...

牛客题霸

2021-09-10

0 789

NC569 题解 | #分组#

题意分析给你一个长度为n的序列，需要我们将这个序列分为连续的k部分，要求分的所有的情况里面，对于每个部分的数字的和，要求所有的部分数字的和的最小的最大化。样例解释有3种分法[1],[2,1,5]，数字和分别为1，8，最小值为1[1,2][1,5]，数字和分别为3，6，最小值为3[1,2,1],...

牛客题霸

2021-09-08

1 747

NC566 题解 | #连续段的中数#

题意分析给我们一个序列，要我们找出一个长度大于等于k的序列，然后这个序列里面的中数要尽可能大。“中数”的定义就是这个序列里面大于等于这个数字的个数要大于等于这个序列的长度的一半。所以在保证这个序列是升序排列的情况下，下图所示的就是中数。思路分析解法一暴力枚举+优先队列维护这个思路...

牛客题霸

2021-08-18

0 708

NC43 题解 | #没有重复项数字的所有排列#

题意分析给你一个序列，需要先将这个序列的相同的元素去掉，也就是先去重。然后按照原来的序列进行一个全排列，需要对每个排列进行字典序排列。前置知识我们按照顺序来。首先，你需要知道怎么去重，在C++里面，对数组的去重两种方法，一种是自己实现，先对整个数组进行排序，然后两两相邻的进行比较。一旦...

牛客题霸

2021-08-16

0 812