温柔GGboy
温柔GGboy
全部文章
题解
归档
标签
去牛客网
登录
/
注册
温柔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
371
题解 | #极客杯-快乐假期-GGboy分饺子#
极客杯-快乐假期-GGboy分饺子 先看问题是什么: 每个孩子分到的饺子数目的最大值的最小值,有点绕 其实就是说,分配的方案有很多种,每一种方案都有一个孩子分到的饺子数目是最多的,这个值我们设为。现在的目标是求这个的最小值。 状态定义: 状态转移: 考虑给第给孩子分配的饺子集合为,设集合对应的饺子...
2024-01-09
0
266
题解 | #极客杯-快乐假期-GGboy的圣诞袜#
GGboy的圣诞袜 目标:使得配对的袜子能量值最小 首先我们先证明,如果第i双袜子没有丢,我们让那双袜子自己配对的操作是最优的。 证明: 如果有四只袜子 +=|A_i-A_j|=|A_i-A_j|&preview=true">+ 所以我们不用考虑成双的袜子,只需要考虑丢失了颜色的袜子即可。 ...
2024-01-09
0
238
题解 | #极客杯-快乐假期-GGboy的真命天女#
GGboy的真命天女 这道题难点在于k是有正有负的,同学们需要进行大量的判断。 不过我们可以换一种思路,如果从target倒推到k呢? 如果target是k转移来的。那么target-1一定是2的倍数或者3的倍数,否则直接返回false 因为2k + 1 = target,或者3k + 1 = ta...
2024-01-09
0
233
题解 | #极客杯-快乐假期-GGboy的数组游戏#
极客杯-快乐假期-GGboy的数组游戏 目标:最少需要几次操作使得数组不有趣 换句话说,就是破坏所有的有趣三元组 如果只有一个三元组,我可以破坏三元组的第一个,第二个,第三个元素都可以。 一种贪心的思路是每次破坏三元组中间的那个元素,如果破坏第三个元素,我们只能让第三个元素变小,而变小之后,它可能跟...
2024-01-09
0
204
题解 | #极客杯-快乐假期-GGboy的魔术表演#
极客杯-快乐假期-GGboy的魔术表演 目标:最少需要花多少钱得到1到n个不同的魔法药剂 一共有n个不同的红色药剂,以及n个不同的蓝色药剂。 比较第i种红色药剂和第i种蓝色药剂,谁更便宜就买谁。 暂时先更新py的代码 def I(): return input() def II(): return ...
2024-01-09
0
226
题解 | #寻找小竹,python版本#
一、解题思路 如果x,yx,yx,y路口是连通的,并且他们的优雅值存在至少两个共同的质因子,则共同优雅。 而题意是要我们求出最大的优雅连通块,因此很容易想到并查集。另外,求共同质因子,数据范围是5×1065\times 10^65×106,因此考虑线性筛+分解质因子 因此,考点并查集,分解质因子,线...
Python3
并查集
线性筛
分解质因数
2022-11-29
0
356