以诚丶

分类

题解(31)

/ 注册

全部文章（共29篇）

题解 | #游游出游#

大思路是二分+dijkstra。需要注意到车的重量越小，我们可以走的路越多，越能够到达终点，具有二段性，可以二分。我们可以二分车可以达到的最大重量，假设为,然后对题目给出的图跑dijkstra,注意图的边有效的条件是他的可承受重量小于车的重量。时间复杂度,cpp能跑过，python过不了。 ...

C++ 二分最短路

2025-07-24

1 64

题解 | #游游的整数操作#

本题好像只要用支持区间加，区间重置的线段树也能过，但是不能够在过程中取模？大思路就是，我们给原数组排序，因为每次加减都是在所有数的上面操作，然后加法不会改变顺序，而减法可能会导致从某个位置开始往左全是0，具有二段性，我们可以二分找到这个位置，然后将左边的全部置为0，右边的正常减就行了。由于涉及到...

C++ 线段树

2025-07-22

1 51

题解 | #游游开车出游#

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

Python3 数学

2025-07-22

1 43

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

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

pypy3 分治数学

2025-07-21

1 62

题解 | #游游的正整数#

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

Python3 数学

2025-07-21

1 57

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

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

Python3 深度优先搜索

2025-07-18

1 44

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

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

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

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

Python3 树状数组

2025-07-18

1 68

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

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

Python3 动态规划

2025-07-17

1 48

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

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

Python3 数学

2025-07-17

1 44