以诚丶

分类

题解(28)

/ 注册

全部文章（共26篇）

题解 | #游游的选数乘积#

提供一种序列分治的思路。还算比较general。首先我们需要知道，0的个数取决于和的个数的最小值。启示我们预处理出每一个数字中5的个数和2的个数。根据的个数来进行排序，然后我们定义如下分治函数,会将区间分割为.那么答案就拆分为计算左右区间之间跨区间的个数，然后分治计算。关键是如何跨区间，由于我...

pypy3 分治数学

2025-07-21

1 36

题解 | #游游的正整数#

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

Python3 数学

2025-07-21

1 34

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

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

Python3 深度优先搜索

2025-07-18

1 31

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

本题可以直接利用贡献法求解。一个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 30

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

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

Python3 树状数组

2025-07-18

1 42

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

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

Python3 动态规划

2025-07-17

1 36

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

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

Python3 数学

2025-07-17

1 28

题解 | #游游的因子计算#

数据范围是，直接算的因数肯定是不行的，那么可以拆开分别算，的因数，注意到输入一个数是，那么他拥有个因数，那么分别计算和的因数，以及乘起来的因数，总的就是我们的结果。因数分解的时间复杂度是，枚举因数最大是,可以通过本题。 import sys from math import isqrt inpu...

Python3 pypy3 数学

2025-07-15

1 34

题解 | #游游的水果大礼包#

枚举即可，可以算出选第一种方案的最大个数,那么枚举选他的次数即可，剩下的物品个数再看能组成多少种第二种方案。最后选出最大的即可。 import sys from collections import Counter # 输入加速 input = sys.stdin.readline if __n...

pypy3 Python3 枚举

2025-07-15

1 44

题解 | #游游的字符重排#

数据范围很小，极端情况下全是不同的字母，那么有种情况，直接dfs搜索所有可能即可。 import sys from collections import Counter # 输入加速 input = sys.stdin.readline if __name__ == '__main__': ...

pypy3 深度优先搜索

2025-07-15

1 26