Peterliang

题解

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

/ 注册

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

NC581 题解 | #牛牛排队#

题目意思给出每个编号的左右两边的差的绝对值，然后我们需要找出所有的满足题目条件的排列的情况数。思路分析我们发现，对于一个序列，只要位置是固定的，那么它的左右两边的差值也是固定的，与这个位置的是哪个数字其实是没有关系的。所以其实数组里面的数字的都是固定了的。我们只需要判断这个序列是否合法...

C++

2021-09-19

0 542

NC580 题解 | #枪打出头鸟#

题意分析给出一个序列，需要找到每个位置的数字前面的比他大的第一个数字的位置。将这个下标累加到最后的答案里面。思路分析思路一暴力查找既然是找每个位置的前面比它打的第一个数字，那么我们直接用暴力查找就行了。枚举每个位置，然后从这个位置的前面查找比这个位置的数字大的第一个位置。代码...

C++

2021-09-17

0 486

NC579 题解 | #牛牛的函数2#

题意分析定义函数，然后在给定a和b的情况下，求的值。思路分析这个题目就是NC578的加强版。这个题目就是一个公式的推导。这就是数学，一个很复杂的公式推导出了一个简洁的式子。另外，我们发现，这个式子的数据范围过大，可能存在爆long long的写法。所以这里我们使用int128...

C++

2021-09-16

0 915

NC578 题解 | #牛牛的函数#

题意分析定义函数，然后在给定a和b的情况下，求的值。简单明了。思路分析我们就按照题目的要求直接进行计算。但是我们发现这个题目我们在求幂次方的时候数字过大。而且很可能会爆。这里我们就要介绍快速幂的写法。快速幂就是让我们在对数的时间范围内快速计算幂次方的。这个思想有点类似于分治然后再进行...

C++

2021-09-15

0 575

题解 | #牛牛的超市#

题意分析给你一个序列，我们需要选取其中几个数字拼接成一个固定的数字，问不同的拼接方案？思路分析 DP 解法一首先，我们来分析一下，这个题目需要n种数字拼接成一个固定的数字x，假设我们当前已经知道了前i-1种数字的情况凭借成x的方案数，那么当我们枚举到第i种数字的时候，我们拼接的方案数就可...

C++

2021-09-14

1 580

NC576 题解 | #牛牛锻炼#

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

Go 牛客题霸

2021-09-14

0 578

NC575 题解 | #牛牛算数#

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

牛客题霸

2021-09-14

0 639

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