以诚丶

分类

题解(26)

/ 注册

全部文章（共24篇）

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

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

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

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

Python3 pypy3 数学

2025-07-15

1 17

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

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

pypy3 Python3 枚举

2025-07-15

1 25

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

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

pypy3 深度优先搜索

2025-07-15

1 17

题解 | #小美的树上染色#

很明显的树形dp问题，定义代表了当前节点选或者不选。如果不选，那么：如果选，在满足权值和条件的情况下，。其中d为选了其中一个孩子后的最大取值，不明白的话可以见代码。 import sys from bisect import bisect_left from math import inf...

pypy3 Python3 树形dp

2025-07-14

1 28

题解 | #小美的排列构造#

这种题一看就有很强的规律性，不如打个表，python打表很方便，代码如下 if __name__ == "__main__": n = 6 res = [] diff = inf for p in permutations(range(1, n + 1)): ...

C++ 数学

2025-06-15

1 47