思路：很经典的s, t子序列匹配板子题，如果说题目要求判断s的子序列中有没有t，就可以直接用双指针，不过本题是要求算具体的数量，就该用子序列dp来做了。然后加了一个多输入，对于python来说要用try-except语句来实现。最终，输出答案即可 代码： import sys input = lambda: sys.stdin.readline().strip() import math inf = 10 ** 18 def I(): return input() def II(): return int(input()) def MII(): return map(int, input()....

参考：https://blog.nowcoder.net/n/0fd8dbf5108c4ebda0ae48f8b43f3ba6 思路：组合数学，推式子。这种组合数学比较常用的就是fac预处理以及乘法逆元inv和comb的函数了，要写熟。然后就是数学过程的推式子了，令表示中有多少个位置是3的倍数，同时也表示排列中有多少个数是3的倍数；再令表示我们最终需要的3的倍数位置个数。 n其实可以分成两组数据，一组为3的倍数，一组为不是3的倍数。那么答案就是先表示需要从cnt个3的倍数中选出除去3的倍数位置外，额外需要的3的倍数，他们的方案数，要把他们放到外面（不是3的倍数位置）；然后再表示从不是3的倍数中...

思路：超绝模拟题，写了一坨。题目大意就是只有第三位进行四舍五入，第二位和第一位只能进位 代码： import sys input = lambda: sys.stdin.readline().strip() import math inf = 10 ** 18 def I(): return input() def II(): return int(input()) def MII(): return map(int, input().split()) def GMI(): return map(lambda x: int(x) - 1, input().split()) def LI(): ...

思路：思维题。题目说了我们可以进行任意次操作，那么直接算整个数组a的gcd即可，为什么？因为越多数去算gcd，其结果不会变大，而会不变或者变小，这恰好满足元素和越小越好的要求；并且我们能够进行任意次操作，那就可以把所有的元素都变成整个数组a的gcd。所以我们先算出整个数组a的gcd再 * n就得到最终结果，然后输出即可 代码： import sys input = lambda: sys.stdin.readline().strip() import math inf = 10 ** 18 def I(): return input() def II(): return int(input()...

参考：https://blog.nowcoder.net/n/524adc66d6b04d149d89b0ce79b93c0b 思路：组合数学结论。本题主要就是这个结论，如果你不知道的话，基本上写不出来了。这个结论其实是隔板法的推论：对于m个数中可重复的选取n个数，方案数有comb(m + n - 1, n)个。因此，我们就去记录一下连续0的[l, r]，那么此时的m就是a[l - 1] - a[r + 1] + 1，此时的n就是r - l + 1，这些区间相互独立，用乘法原理不断累乘方案数并取模，最终输出结果即可 当然，我们这里还可以用一些方法来优化下代码。第一个就是预处理出取模的阶乘数组；...

思路：思维。首先我们要知道1到其他点的最短路径是什么？由于题目说了是无向完全图，即每个点都能直达另一个点，所以说直达可能是最短路径。假设直达不是最短路径，说明真正的最短路径之间会经过一些点，那么经过这些点的权重就是(a ^ b) + (b ^ c) + (c ^ d)....根据异或的性质，直达最短路径的权重，即起点值^终点值能够写成(a ^ b) ^ (b ^ c) ^ (c ^ d)...由于同形式的异或和不会大于算术和，因此直达的权重更小，它就是最短路径 并且题目要求把1到其他所有点的最短路径异或值给异或起来，其实就是(1 ^ 1) ^ (1 ^ 2) ^ (1 ^ 3) ^ (1 ^ ...

思路：题目说了n的范围较小，所以说可以用回溯来找到所有可能的路径并进行统计。首先我们可以做一个剪枝，如果当前的值已经>r了，就直接结束。然后还需要注意题目说了路径长度不能为1，因此要用一个depth变量来记录下长度 接下来就可以正常写回溯了，不过在统计答案的时候需要注意下，当前值处于l和r之间就可以进行答案统计，但是统计完了之后不要直接返回，因为有可能l和r的范围比较大，能够有多个满足条件的答案，这个和一般的回溯输出路径有所不同。 那写回溯就是三件套了：构建现场，递归，恢复现场。这里我用的是位运算来写的，这样会更快一些。然后再以每个节点作为开头，进行一次dfs，最终输出结果即可 代码： ...

思路：首先最简单的想法就是构建出查询数组，但他的时间复杂的是，也就是，不管是时间还是空间上都不行，因此我们不能直接去构建查询数组 那本题其实更像是一种不均匀的分组问题，然后查当前音符是属于哪个组的，如果是均匀分组的话，我们其实就可以用类似于位图的处理方法，用divmod计算除数和余数，确定分组，那对于这种不均匀的分组，我们其实可以用前缀和 + 二分查找来做 怎么想到的？注意到题目给出的查询t数组，其实就是一种前缀和，因此我们首先要处理出一个前缀和数组，并且由于前缀和数组天生具有的单调递增特性，我们就可以用二分查找。 这里我直接用bisect_right库函数，就是二分查找>当前数的第一个...

思路：两次dijkstra求和。题目强调了是单向边，并且是单源最短路径问题，所以说很容易能够想到用一次dijkstra，求得邮局到其他点的最短路径。但是题目还说了，每次送完信还要回到邮局，并且由于是单向边，所以说就不能再走第一次dijkstra的路，回到邮局就是我们要算其他位置到邮局的最短路径。 这其实是一个多到一的问题，我们只需要额外建一个反向图，这样问题就能转化成标准的一到多dijkstra问题，然后就和第一次dijkstra的代码是一样的。所以说，我们就可以把dijkstra写成函数封装起来，然后分别去处理原图和反图，最终相加得到答案即可 代码： import sys from coll...

思路：模拟。根据题意，把m和n异或起来，然后统计异或结果中二进制的1数目即可 注意：本题采用的是字符串处理，用python3会比pypy3快 代码： import sys input = lambda: sys.stdin.readline().strip() import math inf = 10 ** 18 def I(): return input() def II(): return int(input()) def MII(): return map(int, input().split()) def GMI(): return map(lambda x: int(x) - 1, ...

思路：hash表，模拟即可。还是那个问题，对于多次输出，要用一个out数组来记录输出结果，最终一个print全部输出。为什么？因为print很亏时间，如果每次查询都print输出的话，必然会超时 注意：句子中会有重复的单词存在，因此我们应该用defaultdict(set)进行去重 代码： import sys from collections import defaultdict input = lambda: sys.stdin.readline().strip() import math inf = 10 ** 18 def I(): return input() def II(): r...

参考及具体证明：https://blog.nowcoder.net/n/b5b3c86f177943bf9173333de3c027eb 思路：贪心，猜结论。我们要让损失的花朵最少，那么很容易想到贪心策略：越早运输损失大的牛越好，那该如何衡量损失大？应该用进行衡量，如果比值越大，那么我们要优先运输这个牛，以减少损失。所以说，我们就用自定义排序，按照比值进行递减排序，然后遍历一遍算结果，最终输出即可 代码： import sys input = lambda: sys.stdin.readline().strip() import math inf = 10 ** 18 def I(): ret...

参考：https://blog.nowcoder.net/n/7cc0194417e741dab76023f4596046a7 思路：这题主要是要想到奇数的二进制位最后一个数是1，那么或操作要为奇数，只需要区间中有一个奇数即可，还有就是要考虑怎么做不会重复区间。因此，我们记录一个last_odd为上一个奇数位置 在遍历时，如果当前数为奇数，那么索引从1开始，[1, i]为左端点的区间都满足条件，直接ans += i即可；如果当前数为偶数，那么从索引1开始，[1, last_odd]为左端点的区间都满足条件，直接ans += last_odd即可，并且不会重复。最终，输出累加后的答案即可 代码：...

思路：如题，非常经典的拓扑排序模板题。建议没学过的同学好好学习一下，主要是引入了pre数组，然后这里采用bfs实现 代码： import sys from collections import deque input = lambda: sys.stdin.readline().strip() import math inf = 10 ** 18 def I(): return input() def II(): return int(input()) def MII(): return map(int, input().split()) def GMI(): return map(lambd...