思路：看到题目中提到了传递性，并且和点、边有关，首先要想到并查集。但直接用常规的连续并查集，对于1e9的点数量来说，会爆内存，因此我们需要在创建、使用并查集之前，对数据进行离散化操作 之后就是创建并查集，然后判断c为0的情况下，a和b是否已经合并过了。如果有的话，说明存在矛盾，输出"NO"；否则就合并a, b，最终合并完成都没有矛盾，直接输出"YES"即可 代码： import sys from bisect import bisect_left input = lambda: sys.stdin.readline().strip() import ma...

思路：题目问的是在一个连续的区间[l, r]中恰好存在k个"01"子序列，这其实是一个恰好不定长滑动窗口问题。一般来说，如果要计算满足条件的连续区间个数，我们需要用两次不定长滑窗解决，也就是用<= k - <= k - 1 = k，即用两个至多逻辑得到恰好逻辑（用至少逻辑也行） 不过本题只需要求出这样一个区间就行，并没有要求计算其个数，那么就只需要一次<= k滑窗，然后判断结果是否为k，如果有的话就输出结果即可；否则继续滑窗，最终没有恰好等于k的连续区间的话，输出-1 代码： import sys input = lambda: sys.stdin.rea...

思路：分类讨论，首先注意到操作1并不会改变x, y的值，所以说我们要使得x, y的值改变，得看操作2。因此，令操作2中的，得到，那当且仅当为0的时候成立。 由于我们操作1可以进行x, y的交换，所以说我们只需要考虑怎么得到0即可，有三种情况：1.原本里面就有0，那就不管，具体是x还是y，这个讨论一下即可；2.x == y，此时通过得到0，但此时x都和y相等了，那结果其实直接为0；3.x和y互为相反数，此时通过得到0，模拟一下可以发现，这种情况的操作数为3。最后，其他情况都不满足，输出-1即可 代码： import sys input = lambda: sys.stdin.readline()...

思路：首先要想到一个特判，那就是当节点n的个数为奇数时，必然不满足条件中的全偶数划分。然后就是贪心进行划分，什么意思？打个比方来说，我在4的时候进行划分，不如在2的时候就进行划分，这样就可以多一次划分，更优 所以说，我们可以统计子树大小，一旦遇到偶数就进行划分，这可以用递归dfs来做。具体来说，当我们执行自底向上的归部分时，一旦遇到偶数就进行划分，但不用真的去把子树划分，也不需要改变size的大小，为什么？ 因为偶数 + 偶数，依旧是偶数，我们自底向上的过程中，是size的不断累加，我们只需要在size为偶数的时候划分就可以了 注意：首先需要用python3 + 栈扩展提交，这是题目说的。其次...

思路：模拟，贪心。我们读入数据的时候，先判断当前的圆是否包含了原点。如果包含有原点，那就计算出它的移动代价，并且存放到一个临时数组中。之后就判断一下这个数组的长度是否<=k，如果是直接输出0即可；否则，我们要先把代价从小到大排序，然后取前length - k个元素。 代码： 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(...

思路：用dp打表找规律，可以发现在x > 14时，结果都为True；在x <= 14时，结果不都为True。那么我们就在x <= 14的时候用dp表判断一下，否则直接输出Yes即可 代码： 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(): retu...

回想去年的这个时候，已经是大二上的期末了，那时候我还是挺迷茫的，不知道自己闲下来之后该干嘛。但在偶然间听说了算法竞赛这方面的事情，这激起了我的兴趣，其实在初中的时候，我在翻看家里的书籍，里面有一本书我的印象特别深，就是《Python编程：从入门到实践》。有一段时间我就照着书上的语法去学习，可惜限于当时自己太小了，不懂得该如何去学习，也没有大人发现我这方面的学习意向，于是很长一段时间，算法这个词，对我来说显得十分陌生。回想起了往日种种，我开始学习算法，并且选择用Python来作为主要编程语言，也算是对曾经自己的回敬。到现在，一年的时间里。我已经在力扣，牛客，洛谷，CF，Atcoder平台中，总共积累了2000+的题目量。由于是自学，没有人指导，所以说在学习的过程中难免会踩很多坑。但我还是挺享受这个过程的，从分析问题到解决问题，带给我思维上的愉悦感。从去年第一次参加学校的蓝桥杯校赛Python组，获得的3等奖；到今年再次参加获得学校的蓝桥杯校赛Python组，获得的1等奖，并且是其中的第1名，我能实实在在的感受到自己的进步。但我想说的是，这一切都只是杯水车薪，算法的世界远比我想象中的复杂、深邃。我所做的事就如同乌鸦汲水，不断收集一颗颗算法石子，放入到我的知识库中，等待着某一天，甘泉的流出。

思路：非常裸的状态机dp板子题，挺典型的，建议没有接触过状态机dp的朋友们好好学习 代码： 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(): re...

思路：我们首先要知道&的性质，简单说来就是&操作过后，结果不会变得更大。那么根据题目中的式子，我们可以大胆推测：对于每个将被的式子，比如：来说，其结果应该就是。那么其他将被的式子结果就应该是，因此最终结果就应该是所有元素的异或和 代码： import sys from functools import reduce from operator import xor input = lambda: sys.stdin.readline().strip() import math inf = 10 ** 18 def I(): return input() def II(): re...

思路：按照题意，用双指针进行模拟即可 代码： 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().split() de...

思路：贪心的想：对于左右排列来说，如果他们落在相同的y上越多，我们越倾向于划分；对于上下排列来说，如果他们落在相同的x上越多，我们越倾向于划分。那就用两个hash表来模拟这个贪心过程即可 代码： import sys from collections import defaultdict 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, in...

思路：分类讨论 代码： 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().split() def LII(): re...

思路：我们每次要选择最小的不舒适度，那就可以把数组a建小根堆，然后不断模拟即可 代码： import sys from heapq import heapify, heappop, heappush 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...

思路：我们知道要构成长为x的"0101..."串，首先得计算对应的"0"和"1"够不够，那就可以分别用a, b减去x // 2得到剩余的"0"和"1"，记作c, d。接下来先判断c, d是否有负数，如果有的话就无法构成；然后判断c, d是否有奇数，如果有奇数，那么会剩下某个字符无法消去，也就无法构成长为x的01串；否则就可以构成"010100...11..."这样的串，最终消去之后满足长为x的01串 tips：Python3对于字符串的处理要快于PyPy3，因此本题用Pyth...