思路：首先看到子数组，多次查询，首先要想到前缀和。不过要注意两点：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...

思路：非常经典的最大化最小值问题，用二分解决。不过题目没明确说明是最大化最小值，需要分析一下。如果没有学过这种二分题型的同学可以学习一下 代码： 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, in...

思路：ACM赛制下就需要手搓一棵符合题目要求的二叉树了，没有接触过的同学可以练习一下，具体流程如下：1.写一个节点类；2.分别对各编号建立节点；3.读入边然后建二叉树，顺便存储一下边；4.通过入度为0，找到根节点编号，并取出根；5.用经典的递归来写三种遍历方式，输出结果即可，当然你也可以扩展一下，用非递归的栈来写 代码； import sys input = lambda: sys.stdin.readline().strip() import math inf = 10 ** 18 def I(): return input() def II(): return int(input()) d...

思路：思维题，我们考虑一下不同次数操作，有什么影响。一次操作时可以把相邻的两个元素翻转，也就是距离为1的元素进行翻转，比如"11"变成"00"；两次操作时，可以把距离为2的元素进行翻转，比如"101"变成"000"；三次操作时，可以把距离为3的元素进行翻转，比如说"1001"变成"0000"，等等 一般来说，我们可以把任意距离的两个元素进行翻转，当然在字符串长度的约束下，这里的任意距离长度是length - 1，也就是在有限次操作中可以做完。那我们就只需要判断一下s中的&qu...