以诚丶

分类

题解(26)

/ 注册

全部文章（共15篇）

题解 | #Fibonacci 前 n 项和#

由题意可知，。也就可以可以通过的后面一项和的后面两项推出来。那么可以得到如下矩阵形式：这个形式就可以通过矩阵快速幂求出。 import sys from collections import Counter from heapq import heappop, heappush from ma...

Python3 快速幂动态规划矩阵

2025-07-28

1 18

题解 | #倍集#

这道题看了其他大佬的题解才看出来，首先就是需要让每一个独立的区间内部没有倍数，这可以通过收缩左边界实现。然后假设全要，这个时候需要的就是找出和没有倍数关系的有几个。我们从开始枚举，我们要满足，也就是乘一个倍数过后，仍然小于d。那么可以反解出k。然后我们又需要让,那么最大的一个数就是,个数就是...

Python3 数学

2025-07-24

1 22

题解 | #游游的k-好数组#

根据间隔分组，也就是和是一组的，然后对于每一个组内元素，由于操作只能够加，不能减，所以所有元素一定会变为最大值。设每一个组的最大值为,个数为,总和为,那么代价为。那么求出所有组的总需求量，如果不够，那么直接返回。然后将扣除后剩下的贪心的全部分给一组，那么就只要枚举组，记录哪一个最大即可。 im...

Python3

2025-07-24

1 19

题解 | #游游开车出游#

实际上就是求一个这个函数所能够达到的最小值，这个是一个关于的函数，我们可以对他进行求导，让，可以得出如下式子：。 import sys from math import sqrt # 输入加速 input = sys.stdin.readline if __name__ == '__main_...

Python3 数学

2025-07-22

1 14

题解 | #游游的正整数#

分类讨论最多和最少的情况即可。对于最多的情况，我们先贪心的给他分配最小的，设,整除后，同时。如果为0，那么可以整除，最大就是，否则，我们可以将多出来的部分，分配到已经分配好的d个集合中，他们现在全为，那么还能够分配进去的个数最多为。只要m不超过这个数，就能够分配好。对于最少的情况类似，请读者...

Python3 数学

2025-07-21

1 19

题解 | #游游的二进制树#

数据范围很小，我们可以枚举每一个点作为根节点，然后通过遍历，即可计算当前根节点到其他所有节点的二进制值即可。对于根节点到孩子节点的值大小,可以通过实现更新，其中是节点的权值。注意点：对于无向图形式的树遍历，需要记录转移来源，也就是父亲节点是谁，这样子节点才不会走回头路。 import sy...

Python3 深度优先搜索

2025-07-18

1 19

题解 | #游游的矩阵权值#

本题可以直接利用贡献法求解。一个n * n的矩阵可以分解为3个部分，以如下 4 * 4的矩阵为例： x y y x y z z y y z z y x y y x x代表了四个角，每一个x的贡献为2次。 y是除了四个角的最外面元素，每一个y的贡献为3次。其余的就...

Python3 数学贪心

2025-07-18

1 23

题解 | #游游的交换字符#

这里讲解一种general的方法，如果我们给定了一个数组arr,然后在可以相邻的可以进行交换的情况下，变成另一个给定的数组，最小操作次数是多少。对于本题就是我们可以按照的元素值对应的顺序，给数组换成对应的索引值，问题就会转变为求逆序对的数量。逆序对可以分治或者树状数组求解，树状数组写比较简单，这...

Python3 树状数组

2025-07-18

1 21

题解 | #游游的9的倍数#

关于这种比较小的模数计数，一般可以给dp多加一个状态，也就是当前的数模特定值之后为多少。对于本题，我们可以定义定义代表了从前位中选出的数模后值为，那么有如下状态转移方程：情况1，不选当前数: 情况2，选当前数: ，其中是第位数的值。其中basecase为，其他. 需要特别注意的是，空...

Python3 动态规划

2025-07-17

1 20

题解 | #游游的数值距离#

原始为求这么一个式子：的数值增长是非常快的，在的范围下，其个数非常有限，那么我们不妨预处理出阶乘表，阶乘到刚好大于的位数就可以了。由于的个数非常有限，我们可以直接枚举，然后一个二维问题就变为了：。求最小，其实也就是绝对值在0附近，那么不妨直接假设,那么式子变为:。由于可能有偏移，可以试一下和...

Python3 数学

2025-07-17

1 21