提议描述非常清楚，就是求有多少个区间满足区间的和 >= k 依旧是从暴力入手： for i in range(n): s = 0 for j in range(i, n): s += a[j] if s >= k: cnt += 1 其中，a指的是输入数组，s指的是区间和，cnt指答案。 但是数据范围是10^5，因此暴力是无法通过的。 换个角度，区间和=k&preview=true"> 如果均大于0，那么可以用滑动窗口，一旦发现一个区间大于等于k，那么右边还剩多少元素，则有多少区间也满足大于等于k的要求，具备单调性。 可是现在存在负数，因此单调...

极客杯-快乐假期-GGboy分饺子 先看问题是什么： 每个孩子分到的饺子数目的最大值的最小值，有点绕 其实就是说，分配的方案有很多种，每一种方案都有一个孩子分到的饺子数目是最多的，这个值我们设为。现在的目标是求这个的最小值。 状态定义： 状态转移： 考虑给第给孩子分配的饺子集合为，设集合对应的饺子数目为 分类讨论： 如果cnt[s]>f(i-1, j^s), 说明第i个孩子分的饺子数目比之前的多，那么就要变为cnt[s]，因为第i个孩子分到的饺子数目比之前的孩子都多。那第i个孩子分到的饺子数目就是最多的，因此更新 否则，不变 枚举 j 的所有子集 s，则有 代码实现时，我们可以用一...

GGboy的圣诞袜 目标：使得配对的袜子能量值最小 首先我们先证明，如果第i双袜子没有丢，我们让那双袜子自己配对的操作是最优的。 证明： 如果有四只袜子 +=|A_i-A_j|=|A_i-A_j|&preview=true">+ 所以我们不用考虑成双的袜子，只需要考虑丢失了颜色的袜子即可。 因此我们的问题转换为，配对只袜子，使得能量值最小 现在我们来分情况讨论 如果K是偶数，似乎排序，然后每两个袜子进行配对即可。为什么呢？这里设排完序的袜子是A1到AK 用归纳法证明，在最优解中，总是和进行配对 假设和2)&preview=true">进行配对，和进行配对，且 就有+&...

GGboy的真命天女 这道题难点在于k是有正有负的，同学们需要进行大量的判断。 不过我们可以换一种思路，如果从target倒推到k呢？ 如果target是k转移来的。那么target-1一定是2的倍数或者3的倍数，否则直接返回false 因为2k + 1 = target，或者3k + 1 = target 具体我们看代码会更容易理解 def I(): return input() def II(): return int(input()) def MI(): return map(int, input().split()) def LI(): return list(input().spli...

极客杯-快乐假期-GGboy的数组游戏 目标：最少需要几次操作使得数组不有趣 换句话说，就是破坏所有的有趣三元组 如果只有一个三元组，我可以破坏三元组的第一个，第二个，第三个元素都可以。 一种贪心的思路是每次破坏三元组中间的那个元素，如果破坏第三个元素，我们只能让第三个元素变小，而变小之后，它可能跟其他的元素组成新的三元组。如果破坏第一个元素，我们只能让第一个元素变大，而变大之后的元素可能跟先前的元素组成新的三元组。因此贪心的认为破坏第二个元素是最好的。 怎么破坏，直接让第二个元素的值为无穷大。 具体代码如下： def I(): return input() def II(): return ...

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

如题

前言：以前一直用的另一个oj来记录自己的求职，结果它说我涉嫌广告，把我删了。。。9.16六点过就出发去酒店了，9点钟到了第一个面试。由于有部分同学还在面试，我就大概说下流程一面：自我介绍简单语言基础，大概几分钟问完场景题（主要基于你八股的回答，引申场景。这部分蛮赞的，学到很多）手撕算法（面试官会假装不懂，然后让你给他解释清楚。做完之后，他会基于这道题让你完成其他的功能）反问二面：面试官比较儒雅，是cpp的。跟我方向不太符合，自我介绍根据项目，一点一点的细问。（会引出一些你项目没有实现的需求，主要是看你的思考）根据我的回答，我说我优势是算法，他就让我讲了讲堆排序和归并。和一面面试官类似，就是装作不太明白，然后你给他讲明白。三面：自我介绍希望在哪里上班，期望薪资多少等等总的来说，没有八股文我觉得很赞。希望能够开奖，以前从来不刷牛客，都是刷另一个。最近每天起床第一件事情就是看看大家的面试情况。哎，秋招确实不容易，加上我体验过暑期实习的煎熬，所以如果能够开奖，我一定会坚定的选择你！如果有深信服hr看到，欢迎私信我，让我们彼此坚定的选择吧

一、解题思路 如果x,yx,yx,y路口是连通的，并且他们的优雅值存在至少两个共同的质因子，则共同优雅。 而题意是要我们求出最大的优雅连通块，因此很容易想到并查集。另外，求共同质因子，数据范围是5×1065\times 10^65×106，因此考虑线性筛+分解质因子 因此，考点并查集，分解质因子，线性筛 思路清晰了，代码实现也就比较简单了。 流程如下： 1.首先通过线性筛，把5∗1065*10^65∗106内的质数先筛选出来 2.然后把相邻的路口，并且共同优雅的路口，用并查集连通起来 3.输出最大的连通块即可 二、完整代码 import sys import os from io import...