前言：预祝大家新年快乐！希望大家能够在新的一年中，继续努力，实现自己的目标，成为更好的自己！ 思路：经典博弈论结论题。扩展巴什博弈：一堆有n个石子，每次可以取l~r个石子，少于l个石子不能再取，取走最后一个石子的人获胜。问先手和后手谁会赢？结论就是：当时，先手必败；其他情况下，先手必胜。然后我们就根据这个结论来进行答案的收集，最终输出结果即可 你套用一般巴什博弈的前提，取1~m个石子，用扩展巴什博弈的结论可以得到先手必败为，也就是一般巴什博弈的结论：时，先手必败 扩展： 尼姆博弈（多堆取石子问题）：假设有堆石子，每堆石子有个，如果每堆石子数的异或和为0，则先手必输；否则先手必胜。 1.小A取石...

思路：思维题。首先直接算最大的lcm比较困难，我们用另一个转换式子：，这个写法是防溢出的。因此我们要让最大，就需要让最大，最小 对于最大这个要求来说，我们根据题目说的条件，以及高中学过的基本不等式，即的前提下，有，转化式子得到，当且仅当时取得的最大值 对于最小来说，他只可能是1，因此我们可以写个gcd函数来方便后面的验证，当然python也可以直接调用math.gcd，这里我习惯自己手写 所以说有了上面两个分析之后，我们就可以先把一分为二，然后再判断与的是否为1。如果两者的为1，不用操作；如果不为1，那就不断a--和b++（这样能保证两者的和始终为n），直到两者的gcd为1时停止。最终，输出结...

思路：贪心。题目强调了最小化最大值这个要求，不知道有没有同学用二分答案呢？但你仔细分析一下可以发现，这题不具备单调性，比如钱越多，越怎么样？没有单调性是用不了二分的。考虑暴力，直接全排列n个大臣，然后再一个一个算，那么时间复杂度就来到了惊人的，那肯定过不了。 所以，正确的解法是贪心。首先第一直觉来说：越小，越大，我们倾向于放在后面，那感觉贪心和排序有关。然后我就开始猜了，试了下用直接、、、、、来进行排序贪心，最后发现贪心是对的。接着用前缀乘积算一遍结果，其中的最大值就是答案 代码： import sys input = lambda: sys.stdin.readline().strip() ...

思路：没想到吧，又考组合数学了。首先分析题意，题目说了给定的输入为2进制数组，要在只有0和1的数中找中位数，那只需要统计1的数量即可，如果1的数量，说明长为k的子序列中，有一半以上为1，中位数就是1；否则中位数就是0 然后，我们把三个经典的东西写上：1.取mod的阶乘数组fac；2.逆元函数inv；3.组合数学函数comb。接下来就可以枚举1的数量了，为了保证中位数是1，那我们至少要个1，这是下限；然后上限为也就是整个数组的长度和最大的1个数取更小的一方 接下来，我们不断累加当前枚举数量1时的结果，即，并且不断取mod，最终输出答案即可 往期每日一题考过的组合数学题： 1.计数 https:/...

思路：思维题。开始写了个纯暴力跑了一下（打表），然后观察找规律，感觉可能是矩形覆盖的所有整数点。答案确实就是这个，直接输出结果即可 代码： 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...

思路：思维题。开始我题没读明白，以为是用线性基来做，而这题其实是利用&运算的性质来做。一般的，越多数字进行&操作，其结果只会不变，或者越来越小 因此要得到最大&值，我们有两种情况可以讨论：1.先用异或把所有数字给异或起来，最终得到只有一个数字，他可能是最大了；2.用异或把前半段变成一个数字，再把剩下的后半段变成一个数字，此时就是两个数字进行&操作，他们可能得到最大值。再接下来的3，4，5，6....个数字进行&操作，只会得到不变，或者更小的结果，就不再需要考虑了 那如何快速处理多个连续数字的异或和？当然是使用前后缀和来解决。从实现上来说，我们先算整个数组...

思路：推式子。首先是两个特判：1.当n为1时，无法形成长为2的路径，直接输出0；2.当n为2时，无法每个点都形成'^'字形的长为2路径，输出1。 对于n >= 3来说，我们长为2的路径由两部分组成：1.当前节点向下延伸，此时长为2的路径有条，我们累加起来并不断取mod；2.形成'^'字形路径，此时长为2的路径数量和节点数量一致为条。最终，我们在1的结果上再加上2的结果，然后取mod输出即可 代码： import sys input = lambda: sys.stdin.readline().strip() import math inf = 10 ** 18 def I(): retu...

思路：思维题。由于每个数可能出现多次，所以说先用hash表统计一下，然后排序贪心地算可以免费删除的最大次数，具体流程如下：先定义一个变量表示上一个元素是多少，初始化为-1，因为题目说了输入数据，这样初始化能保证他不会和第一个数连续 再定义一个变量表示上一个元素出现的次数，然后遍历hash表判断是否连续。如果连续的话，免费的删除次数就是，累加到中。然后更新和，这里需要注意一下，由于我们可以形成的连续链长度>= 2，所以说应该更新为当前元素的出现次数c，他不仅可以被上一个元素作用，也可以作用于接下来的元素。如果碰到不连续的了，那么直接令表示不会产生免费删除次数 最后清空整个数组的最小操作代价...

思路：模拟题。根据题意进行模拟，最终输出结果即可 代码： 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(): return input().spli...

思路：定长滑动窗口+贪心。我们要让每个滑动窗口的值都并且操作数最少，那就主要操作窗口中靠近右侧的元素。为什么？因为越靠近右侧的元素，在我们向右滑动窗口时，更容易被保留下来，也就会产生更大的贡献。 因此，我们就滑动窗口，当发现窗口中的和时，就累加操作数，然后从窗口右端开始往左端，对元素进行减操作，修改元素值。这里我理解错了题意，题目说的是输入数据，我就下意识以为操作后的每个盒子，其糖果数也必须，这里调了挺久，其实是可以变成0的。 最后，输出累加后的操作数即可，他的时间复杂度应该是，但能过就很神秘 代码： import sys input = lambda: sys.stdin.readline(...

思路：经典博弈论结论题。巴什博弈：一堆有n个石子，每次可以取1~m个石子，取走最后一个石子的人获胜。问先手和后手谁会赢？结论就是：当时，先手必败；当时，先手必胜。然后我们就根据这个结论来进行答案的收集，最终输出结果即可 补充：尼姆博弈：有堆石子，每堆石子有个，如果每堆石子数的异或和为0，则先手必输；否则先手必胜。 代码： import sys input = lambda: sys.stdin.readline().strip() import math inf = 10 ** 18 def I(): return input() def II(): return int(input()) d...

思路：模拟题。直接用一个cnt变量，表示模拟栈括号匹配时的深度，然后每次成功匹配一个')'时，更新答案，最终输出结果即可 代码： 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().sp...

思路：数学题，主要是精度和特判。第一个特判就是，此时令得到结果为0，这就是最小了；第二个特判就不好想了，当时，我们直接输出1即可，为什么？因为当时，对于来说，会超过题目的，并且差距会越来越大，所以说为了得到最小的结果，m只能取1 然后就可以直接算根了，为什么？因为题目给的是先减后增的，我们也可以在desmos里画图看一下。算出根之后，为了保证精度，我们取为半径，得到和，然后算邻域范围内，能够取到最小函数值的自变量x，那就是答案了。 最后还是那个道理，对于多测来说要用一个out数组来记录所有答案，然后再一次print输出，会更快，因为python的print很花时间 代码： import sys...

参考：https://blog.nowcoder.net/n/9a329387829c45cab18f6e0e409afec0 思路：思维题。base case比较容易想到：1.操作必须同时+1和-1，所以说整个数组和不变；2.要求最大化众数的个数，由于可以进行任意次操作，所以说令，那么当时，我们可以把数组a中的所有数都变成平均数，他也是众数。那么plus(+1)和sub(-1)操作操作相同，只需要算一个就行。 除去base case以外就不太容易想了，由于，所以说会产生余数，导致数组a中的元素无法都变成平均数，那此时的最大众数有多少个？答案是n - 1个，我们可以选出一个数字来通过和他操作，...