思路：如题，非常经典的拓扑排序模板题。建议没学过的同学好好学习一下，主要是引入了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...

思路：经典博弈论结论题，尼姆博弈问题。简单说来，假设有堆石子，每堆石子有个，如果每堆石子数的异或和为0，则先手必输；否则先手必胜。因此，我们先把所有异或起来，判断不用-k操作时的初始状态，能否获胜。如果说能获胜就直接返回"YES"，否则我们就要使用-k操作了 使用-k操作时，就直接遍历一遍，当时才能进行操作。具体操作时，就利用异或的性质，即，先把当前元素x从异或和中异或去掉，然后再异或，判断能否获胜。如果可以的话，直接输出"YES"；最终都不行的话，输出"NO" 代码： import sys from functools import...

思路：整体来说就是构造出A、B数组，然后把B数组的元素异或起来。对于构造A数组来说，直接根据题意模拟即可；对于构建B数组来说，首先要注意d | i表示d去整除i，而不是i去整除d，这里我开始就弄错了，然后就可以用埃式筛来构建B数组了。简单来说，埃式筛就是两层for循环，外层i的步长为1，内层j的步长为i，主要是用于筛质数，这里是筛对应的倍数 代码： import sys input = lambda: sys.stdin.readline().strip() import math inf = 10 ** 18 def I(): return input() def II(): return ...

思路：首先看到子数组，多次查询，首先要想到前缀和。不过要注意两点：1.的值不包括0，因此不用担心后续除到0的情况；2.乘积之后的值可能会非常大，如果不提前取mod的话，肯定会超时。因此我们处理一个带mod的前缀和数组pre，后续查询就采用pre[r] // pre[l - 1]然后取mod得到最终结果 对于有除法的取模，我们需要用到小费马定理。具体来说，要求mod是质数，此时有。很常用的公式，记住即可。然后对于Python来说，pow内置函数的功能类似于快速幂，直接用即可；对于其他语言来说，要手搓一个qpow出来才行 代码： import sys input = lambda: sys.std...

思路：这题第一眼贪心，但具体怎么贪就需要仔细想想了。首先可以注意到一个特判，当数组a最大值>数组长度n时，这个最大值无法组乐队，直接输出-1。除此之外的其他情况都可以组乐队，比如最差情况下，所有人一起组一个乐队 然后就是怎么贪心了，这个不太好弄，我想了一个多小时，WA了11发才解决。具体流程如下：首先看一个样例1 1 1 4，如果直接从小到大贪心，会出问题。为什么？因为末尾的4我们其实应该组成1 1 1 4才行，从小到大贪心就会剩下单独的4，不知道该怎么放，所以说应该从大到小贪心。那再来看一个样例 1 1 1 4 4 4 4 4，如果说从大到小贪心，会出问题。为什么？因为从左往右的第一个...

思路：阅读理解，模拟。由于两者做题顺序一致，都是从左到右，因此我们就可以从左到右遍历每一题，然后判断两者会不会做这题即可。对于clccle来说，难度<他的预期并且花费时间足够才会做题；对于rqy来说，难度>=他的预期并且花费时间的2倍足够才会做题；难度<他的预期并且花费时间足够才会做题。最终遍历，模拟一遍，输出结果即可 代码： import sys input = lambda: sys.stdin.readline().strip() import math inf = 10 ** 18 def I(): return input() def II(): return in...

思路：整体思路比较容易想到：当两数间的差值时，用公差为的等差数列去从小到大的插入，结果就是，然后不断累加即可。但是有个特判不好注意到，整体思路可以处理差值中有k的情况，此时会正确输出0；但当所有差值都< k时，此时应该输出1，因为我们要额外构造一个数，使得差值为k。所以说再额外引入一个flag数组，作为特判的标记 代码： import sys input = lambda: sys.stdin.readline().strip() import math inf = 10 ** 18 def I(): return input() def II(): return int(input()...

思路：贪心，我们需要最少的操作次数，那就可以cnt出每个字符串对应位置的元素个数，并且要所有对应位置的字符都变成最大数量的那个字符，具体是什么字符我们不关心。那么剩下需要修改的字符数量就是n // k - mx，我们遍历一遍，然后累加即可得到ans 注意：具体实现的时候不需要把具体的n // k个字符串构造出来，直接用step遍历即可，步长为k 代码： import sys input = lambda: sys.stdin.readline().strip() import math inf = 10 ** 18 def I(): return input() def II(): retur...

思路：多次修改，多次查询的区间问题，要想到用线段树解决 注意：对于Python来说，print函数的时间代价很大，所以说像这种多次查询并输出的题目，我们需要用一个数组来记录每次要输出的答案，最终用一次print输出，来减少超时的风险 代码： 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()...

参考：https://blog.nowcoder.net/n/0a5f5968e0c94844917ada856a748cc5 思路：思维题，题目说了边界补零且无法被更改，所以说要让所有元素相同，那么最终结果应该都是0。因此对于中间是0来说，直接统计即可；对于中间是正数来说，他四周应该都<=0，才可能-1操作到0；同理对于中间是负数来说，他四周应该都>=0，才可能+1操作到0。最终统计出来后，判断一下没补0的n * n矩阵中，非零元素是否等于可操作元素即可，如果是的话输出"YES"，否则输出"NO"。 代码： import sys input...

参考：https://blog.nowcoder.net/n/9814e3fcac084972ad72b1c6ffe1357e 思路：对于这种需要明确连接关系的题目来说，适合用邻接矩阵来做。因此，我们先建邻接矩阵，之后用i, j, k枚举三个点，并且判断其在邻接矩阵中的边关系。然后输出真分数就用gcd分别去除两个数值，进行约分，最终输出结果即可 代码： import sys input = lambda: sys.stdin.readline().strip() import math inf = 10 ** 18 def I(): return input() def II(): retur...

思路：排序 + LIS。他的本质是算一个二维最长严格递增子序列，然后再用小红本身的H和A，去判断是否能够战胜最大的二维严格递增子序列结尾。如果可以的话，就更新ans = max(ans, dp[i])，最终输出ans即可 注意：这里排序是为了贪心的得到更长的二维最长严格递增子序列，而且题目只限制了h, a的值关系，位置可以改变 代码： import sys input = lambda: sys.stdin.readline().strip() import math inf = 10 ** 18 def I(): return input() def II(): return int(inp...

思路：思维题，首先有一个特判可以注意到：令k = n // 2，如果此时k是奇数，那么数组左边是奇数个偶数和，结果为偶数；数组右边是奇数个奇数和，结果为奇数。因此，左右两边的和不可能相等，直接输出"NO"即可 然后我们就可以往左边填偶数，从2开始填，形成一个等差数列，其求和公式为k * (1 + k)，结果令为s。右边就可以从1开始填奇数，然后s减去对应的奇数，这样做的好处就是每次填的奇数都比对应位置的偶数少1，那么我们只需要填k - 1位，最终第k位就填剩下的s即可，它必然为奇数。并且由于题目说了n的规模远小于ai的规模，所以说这样填不会超过ai的最大值，最终拼接起来，输...

参考：https://www.nowcoder.com/share/jump/5537992501767403764056 思路：这题可以用划分dp来做，我们定义表示到使得数组为空的最小划分数，并且记录一个数组，用来记录元素值的最小划分次数。这样后续在进行首尾元素相同，状态转移的时候，就可以找到结尾元素对应的最小划分次数，然后进行划分 + 1，完成状态转移。最终判断一下能否被划分即可，如果可以的话，输出最小划分值；否则输出-1。这个算法可以解决值更大的情况 代码： import sys input = lambda: sys.stdin.readline().strip() import ma...