数据范围很小，我们可以枚举每一个点作为根节点，然后通过遍历，即可计算当前根节点到其他所有节点的二进制值即可。 对于根节点到孩子节点的值大小,可以通过实现更新，其中是节点的权值。  注意点： 对于无向图形式的树遍历，需要记录转移来源，也就是父亲节点是谁，这样子节点才不会走回头路。  import sys input = sys.stdin.readline if __name__ == '__main__': n,l,r = map(int,input().split()) w = list(map(int,list(input().strip()))) g = [[] for _ in ran...

本题可以直接利用贡献法求解。一个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次。 其余的就是z，贡献为4次。  题目要求最大的取值，那么我们不妨贪心的让x最小，y次之，z最大，这样就被分解为了3个等差数列，求解即可。 import sys from math import inf # 输入加速 input = sys.stdin.readline """ n = 2 1 2 3 4 n = 3 1 5 2 6 9 8...

这里讲解一种general的方法，如果我们给定了一个数组arr,然后在可以相邻的可以进行交换的情况下，变成另一个给定的数组，最小操作次数是多少。 对于本题就是 我们可以按照的元素值对应的顺序，给数组换成对应的索引值，问题就会转变为求逆序对的数量。逆序对可以分治或者树状数组求解，树状数组写比较简单，这里采用树状数组写法。 这里举两个例子： 对于样例1： arr = 11100 target = 10101 target元素对应的索引 0:[1,3] 1:[0,2,4] 处理出arr对应的索引 [0,2,4,1,3] ，逆序对就为3，可以自己手算一下。 对于样例2： arr = 01011 tar...

关于这种比较小的模数计数，一般可以给dp多加一个状态，也就是当前的数模特定值之后为多少。 对于本题，我们可以定义定义代表了从前位中选出的数模后值为，那么有如下状态转移方程：  情况1，不选当前数:  情况2，选当前数: ，其中是第位数的值。  其中basecase为，其他.  需要特别注意的是，空数组的值也为0，最后需要扣掉。  import sys if __name__ == '__main__': s = input().strip() n = len(s) MOD = 10 ** 9 + 7 f = [[0] * 9 for _ in range(n + 1)] f[0][0] = 1...

原始为求这么一个式子： 的数值增长是非常快的，在的范围下，其个数非常有限，那么我们不妨预处理出阶乘表，阶乘到刚好大于的位数就可以了。 由于的个数非常有限，我们可以直接枚举，然后一个二维问题就变为了：。 求最小，其实也就是绝对值在0附近，那么不妨直接假设,那么式子变为:。 由于可能有偏移，可以试一下和是否满足满足要求。 import sys from math import inf if __name__ == '__main__': n = int(input()) fac = [1] for i in range(1,31): if fac[-1] * i > 10 ** 9: fac...

数据范围是，直接算的因数肯定是不行的，那么可以拆开分别算，的因数，注意到输入一个数是，那么他拥有个因数，那么分别计算和的因数，以及乘起来的因数，总的就是我们的结果。 因数分解的时间复杂度是，枚举因数最大是,可以通过本题。 import sys from math import isqrt input = sys.stdin.readline if __name__ == '__main__': a, b = map(int, input().split()) lst1 = [] for i in range(1, isqrt(a) + 1): if a % i == 0: lst1.appen...

枚举即可，可以算出选第一种方案的最大个数,那么枚举选他的次数即可，剩下的物品个数再看能组成多少种第二种方案。 最后选出最大的即可。 import sys from collections import Counter # 输入加速 input = sys.stdin.readline if __name__ == '__main__': n,m,a,b = map(int,input().split()) cnt1 = min(n // 2,m) res = min(n,m // 2) * b #从a种逐渐扣 for i in range(cnt1 + 1): r1 = n - i * 2 r...

数据范围很小，极端情况下全是不同的字母，那么有种情况，直接dfs搜索所有可能即可。 import sys from collections import Counter # 输入加速 input = sys.stdin.readline if __name__ == '__main__': s = input().strip() res = 0 n = len(s) path = ['*'] * (n + 1) cnt = Counter(s) def dfs(i: int): if i == n + 1: global res res += 1 return for k,v in cnt.i...

很明显的树形dp问题，定义代表了当前节点选或者不选。  如果不选，那么：  如果选，在满足权值和条件的情况下，。其中d为选了其中一个孩子后的最大取值，不明白的话可以见代码。  import sys from bisect import bisect_left from math import inf, isqrt # 输入加速 input = sys.stdin.readline """ 树形dp，当前点选或者不选 f[i][0/1] """ if __name__ == '__main__': n = int(input()) weight = [0] + list(map(int, inp...

这种题一看就有很强的规律性，不如打个表，python打表很方便，代码如下 if __name__ == "__main__": n = 6 res = [] diff = inf for p in permutations(range(1, n + 1)): mx = -inf mn = inf for a,b in pairwise(p): mx = max(mx, a + b) mn = min(mn, a + b) if mx - mn < diff: res = p diff = mx - mn print(res)  可以看看结果如下  (1, 3, 2) (1, 4, 2, ...

首先说一种错误的做法，直接将所有元素放到堆里面，然后每次让最大的两个元素和出堆，然后放入和，这样会导致非常大，不能够这样做，并且由于需要比大小，所以中间过程不能够取模。 正解的话可以举例子看一下：  6 = 1 * 6 = 2 * 3 20 = 1 * 20 = 2 * 10 = 4 * 5  可以发现总是 和这样形式的和最大，详细证明题解区已经有了，可以去看看。 那么我们就可以给他排序，对于次操作，其实就是最大的个数的乘积，加上。 最后再加上剩余的元素即可。 #include <bits/stdc++.h> using namespace std; #define int lon...

对于连续子数组，考虑状态定义代表了以结尾的数组的异或和。由于代表了，他是一定包括了，所以。 然后对于新出现的,可以通过例子，不妨用题目给出的例子。 对于以索引3结尾(从0开始),有如下3个连续子数组： [1,2],[3,1,2],[2,3,1,2]。 我们可以发现索引2位置异或了3次，索引1位置异或了2次，索引0位置异或了1次。  通过上面的例子我们可以发现，其实异或的次数是固定的。但是异或并不满足结合律，不能够拆，那么我们不妨对每一个数拆位，这样就变为了一个01序列，由于是异或运算，可以直接通过前缀中1或者0的个数求解。 #include <bits/stdc++.h> usin...

经典题目：最长递增子序列的变种。 我们先将满足所有小于和的放到一个数组中，然后按照第一维度降序排序，如果相等，那么升序排序。然后找出第二维的最长递减子序列就是我们的答案。  为什么需要相等的时候升序排序呢？ 因为题目要求了相等的不能够杀死，那么我们给他升序，那么找最长递减的时候就不可能选到。  这道题题目范围数据给的很小，只有,可以暴力dp,定义代表了数组的的最长递增子序列长度，转移方程如下:  这样转移时间复杂度为,然后还有二分或者使用树状数组优化达到，这里给出二分写法。 import sys sys.setrecursionlimit(100010) read = sys.stdin.re...

这是最小生成树的变种，我们可以首先将的连接上，然后给剩余的边排序。需要注意排序后，索引信息回发生改变，需要保存好。然后依次检测联通性，如果不联通我们才连接。 连通性可以使用并查集来实现。 import sys sys.setrecursionlimit(100010) read = sys.stdin.readline if __name__ == "__main__": import sys sys.setrecursionlimit(100010) read = sys.stdin.readline if __name__ == "__main__": n,m = map(int,read...