思路：拓扑排序。这题算是拓扑排序扩展的标准例题，没学过的同学可以好好学学。具体来说就是从外向内进行食物链条数的传递，传递到最内层，也就是出度为0的节点，他们的食物链条数之和就是答案 注意：本题有个踩坑点，那就是孤立点，孤立点是没有食物链的，不能计入答案中。因此，我们就可以在答案初始化的时候，排除入度和出度都为0的点，只初始化入度为0，出度为非0的点 代码： import sys from collections import deque input = lambda: sys.stdin.readline().strip() import math inf = 10 ** 18 def I()...

思路：hash表 + 模拟。直接根据题意进行模拟即可，当对手加入牌的时候，就把和加入到hash表中，注意需要判断下牌的范围是否在到之间；同理，当对手拿走牌的时候，就分别把和从hash表中减去一次，也是需要判断下牌的范围是否在到之间，如果牌减完了就直接从hash表中删掉。最终，hash表的长度就是每一次操作后的答案，添加到out数组中，然后整体输出即可 代码： import sys from collections import defaultdict input = lambda: sys.stdin.readline().strip() import math inf = 10 ** 18 ...

思路：网格图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 LI(): return input().split() def LII(): return list(map(i...

思路：贪心 + 区间合并。首先看数据量，用dp肯定过不了，那就考虑贪心；接下来把x和h进行排序，也就是用(x, h)进行自定义排序；然后进行区间合并操作，具体来说就是用栈进行模拟，模拟完后得到合并的多段区间。最终，按照区间长度进行降序排列，选择前m个长度最大的区间，加起来就是答案了 代码： 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...

思路：思维题。首先特判0，如果有0存在直接返回False即可；然后计数判断元素种类，如果元素种类不为2，此时必然满足条件，返回True；如果元素种类确实只有两种，那再额外判断一下他们的和是否为0，如果是的话必然无法满足条件，反之满足条件 代码： import sys from collections import Counter input = lambda: sys.stdin.readline().strip() import math inf = 10 ** 18 def I(): return input() def II(): return int(input()) def MII(...

思路：Floyd算法。把输入的a, b边建邻接矩阵，然后跑一遍Floyd算法，之后再算出每个数位有几种变化情况。最终，遍历输入x的每一个数位，把每个数位可能的变化情况进行累乘并取mod即可。为什么？因为每一个数位独立，那就可以用乘法原理把各自的可能性给乘起来，就可以得到最终答案了 代码： 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 ...

思路：模拟题。每次&运算取最后一位加到答案中，然后不断右移即可 代码： 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 LI(): return input().split() def LII(): return list(map(int, input().split(...

思路：思维题，脑筋急转弯。由于题目说了x元素是之前所有元素的异或和，因此根据异或的性质可知：整个长为n的数组a异或和为0。所以说数组a中的任意一个元素充当x，此时其他元素的异或和必然也是x，因为整体的异或和要为0，这恰恰满足条件。所以说输出任何一个元素即可，我这里输出第一个元素 代码： 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 m...

思路：非常经典的打表找规律题目，其背后的本质是：1.裴蜀定理：对于整数a和b，方程ax + by = n有整数解，当且仅当 gcd(a,b)∣n，也就是gcd能够去整除n。2.弗罗贝尼乌斯硬币结论：对于互质的正整数a和b，最大的不能表示为ax + by（x,y ≥ 0）的数是：ab − a − b。 因此，我们打个表可以发现如下规律：1.索引0~16，也就是前17个数没有规律性，直接收集到ans数组中回答即可；2.从索引17开始，每8个为一组，形成了的规律，那我们就在奇数的时候输出-1，偶数的时候就先用当前数n - 前17个舍去的数，再// 8 + 起始值3，就能得到表示的答案了 代码： im...

思路：斐波那契数列变种，矩阵快速幂优化。观察题目的数据量可知，这题我们需要用到矩阵快速幂进行优化。首先写两个函数：1.矩阵乘法函数mat_mul、2.矩阵快速幂函数mat_pow。由于本题的斐波那契数列递推比一般的斐波那契数列递推用到的数要更前一位，所以说就需要用到3维的递推矩阵 接着对3维递推矩阵进行矩阵快速幂操作，其幂次为。为什么？因为从索引0开始算起，那就有，有这三个基本数据，就可以推出后面的。因此，最大的基本数据索引为，那我们要推到，就只需要走步即可。此时的答案就是数组第一行向量，也就是，然后把答案添加到out数组中，最终整体输出即可 代码： import sys input = la...

思路：经典递推板子题，中间再加个取mod操作即可 代码： 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 LI(): return input().split() def LII(): return list(map(int, input().split())) def LFI...

思路：多源bfs。首先我们要弄清楚Sekai点是什么？其实就是度数为1的叶子节点，我们要找与Sekai点相距最近的最大距离Miku点，就只需要把所有Sekai点收集起来，做一个多源bfs，就可以得到Sekai点到其他Miku点的最短距离。然后统计其中的最大值及其出现次数，并且根据要求输出答案即可 代码： import sys from collections import deque input = lambda: sys.stdin.readline().strip() import math inf = 10 ** 18 def I(): return input() def II(): ...

思路：不定长滑动窗口，越长越合法。模板题，建议没学过不定长滑动窗口，越长越合法的同学好好练习一下 代码： 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 LI(): return input().split() def LII(): return list(map(int, i...

思路：模拟题。根据题意进行模拟即可，可以写一次遍历，我这里写的是两次遍历，看着比较简单 代码： 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 LI(): return input().split() def LII(): return list(map(int, input(...