温柔GGboy

题解

/ 注册

全部文章 / 题解（共7篇）

题解 | #T6-小红统计区间（hard）#

提议描述非常清楚，就是求有多少个区间满足区间的和 >= k 依旧是从暴力入手： for i in range(n): s = 0 for j in range(i, n): s += a[j] if s >= k: cnt += 1 其中，a指的是输入数组，...

pypy3 Python3 树状数组离散化

2024-01-17

3 384

题解 | #极客杯-快乐假期-GGboy分饺子#

极客杯-快乐假期-GGboy分饺子先看问题是什么：每个孩子分到的饺子数目的最大值的最小值，有点绕其实就是说，分配的方案有很多种，每一种方案都有一个孩子分到的饺子数目是最多的，这个值我们设为。现在的目标是求这个的最小值。状态定义：状态转移：考虑给第给孩子分配的饺子集合为，设集合对应的饺子...

2024-01-09

0 272

题解 | #极客杯-快乐假期-GGboy的圣诞袜#

GGboy的圣诞袜目标：使得配对的袜子能量值最小首先我们先证明，如果第i双袜子没有丢，我们让那双袜子自己配对的操作是最优的。证明：如果有四只袜子 +=|A_i-A_j|=|A_i-A_j|&preview=true">+ 所以我们不用考虑成双的袜子，只需要考虑丢失了颜色的袜子即可。 ...

2024-01-09

0 244

题解 | #极客杯-快乐假期-GGboy的真命天女#

GGboy的真命天女这道题难点在于k是有正有负的，同学们需要进行大量的判断。不过我们可以换一种思路，如果从target倒推到k呢？如果target是k转移来的。那么target-1一定是2的倍数或者3的倍数，否则直接返回false 因为2k + 1 = target，或者3k + 1 = ta...

2024-01-09

0 235

题解 | #极客杯-快乐假期-GGboy的数组游戏#

极客杯-快乐假期-GGboy的数组游戏目标：最少需要几次操作使得数组不有趣换句话说，就是破坏所有的有趣三元组如果只有一个三元组，我可以破坏三元组的第一个，第二个，第三个元素都可以。一种贪心的思路是每次破坏三元组中间的那个元素，如果破坏第三个元素，我们只能让第三个元素变小，而变小之后，它可能跟...

2024-01-09

0 210

题解 | #极客杯-快乐假期-GGboy的魔术表演#

极客杯-快乐假期-GGboy的魔术表演目标：最少需要花多少钱得到1到n个不同的魔法药剂一共有n个不同的红色药剂，以及n个不同的蓝色药剂。比较第i种红色药剂和第i种蓝色药剂，谁更便宜就买谁。暂时先更新py的代码 def I(): return input() def II(): return ...

2024-01-09

0 227

题解 | #寻找小竹，python版本#

一、解题思路如果x,yx,yx,y路口是连通的，并且他们的优雅值存在至少两个共同的质因子，则共同优雅。而题意是要我们求出最大的优雅连通块，因此很容易想到并查集。另外，求共同质因子，数据范围是5×1065\times 10^65×106，因此考虑线性筛+分解质因子因此，考点并查集，分解质因子，线...

Python3 并查集线性筛分解质因数

2022-11-29

0 358