赛事传送门
T1、新年快乐 - 题解
题面大意
有nnn堆糖果,每次你可以将任意一堆复制到另一堆上。每堆糖果的数量不能超过fff
题意分析
求最多能复制几次。
解题思路
每次我们把较小的一堆复制到较大的一堆,那么考虑找出最小的一堆,由它来当被复制的,复制到其他堆上。这样每堆能操作的次数才会最多。
时间复杂度解析
找出最小的那堆糖果,扫描所有糖果堆,计算最小糖果堆能复制到其它糖果堆的操作次数,复杂度为O(n)O(n)O(n)
代码演示
T2、新年大扫除 - 题解
题面大意
给你nnn个字符,只由大写字母NNN和OOO组成,每次可以选择kkk个连续的字符,将选中的各个字符变成NNN。
题意分析
找到最小的操作数,将所有的OOO变成NNN
解题思路
每次选择kkk个字符,如果从iii开始选,则可变的范围就是[i,i+k−1][i,i+k-1][i,i+k−1],考虑只有OOO需要变成NNN,我们可以找到第一个为OOO的字符,从这个字符开始选择kkk个字符变成NNN,然后继续找到下一个OOO。
那么实际上每次我们只需要维护一个值rrr,它表示≤r\leq r≤r的字符都能变成NNN
时间复杂度解析
我们只需要遍历一次字符即可,复杂度为O(n)O(n)O(n)
代码演示
T3、新年魔法 - 题解
题面大意
给你两个数字,a,ba,ba,b
每次用较大的数去减去较小的数,如果 a>ba > ba>b 那么$ a = a - b $, bbb不变。
如果两个数字相等,例a−ba-ba−b或b−ab-ab−a皆符合,直到有一个数字小于等于0,就停止运算。
题意分析
问多少次后会停止运算
解题思路
这个操作过程与辗转相减是一样的
如果每次用减法去模拟,当两个数值相差很大时,就要运算很久,我们可以直接用除法去代替减法。
嗯,如果变成除法的话,这与辗转相除法相同。
时间复杂度解析
复杂度与辗转相除法的复杂度等同,O(log max(a,b))O(log \ max(a,b))O(log max(a,b))
代码演示
T4、新年排列 - 题解
题面大意
给你一个长度为nnn的全排列ppp,和一个整数kkk,每次可以任意选择kkk个元素,以升序移动到ppp的末尾,直到ppp为升序。
题意分析
求最小操作次数,使得ppp变为升序
解题思路
找到以1开头的最长上升序子序列qqq,那么不属于qqq部分的则都要移动,将非qqq部分的元素移动到ppp的尾部就好。
时间复杂度解析
我们只需要遍历一次ppp序列,就能找到子序列qqq,复杂度为O(n)O(n)O(n)。
代码演示
T5、新年游戏 - 题解
题面大意
你有nnn个正整数,每次可以选择一对数,pip_ipi 与pjp_jpj (i≠j,pi>pji \neq j,p_i > p_ji=j,pi >pj ),然后使pip_ipi = pip_ipi - pjp_jpj
最终会得到一个新的序列
题意分析
要求最终序列的和最小
解题思路
每次我们用一个大的数pip_ipi 减去一个小的数pjp_jpj ,操作后,pjp_jpj 会变成那个较大的数,pip_ipi 会变成那个较小的数字,继续重复这个操作。我们发现与辗转相减的操作是一样的,那么实际上就是求最大公约数。
时间复杂度解析
代码演示
T6、新年均馔 - 题解
题面大意
有nnn盒饼干,每盒的饼干数量可能不同,只能从盒子里拿出饼干,问最少拿多少饼干可以使得每盒饼干数量相同。
题意分析
求拿出饼干的最少数量,使得每盒饼干数量相同
解题思路
因为饼干只能拿出,不能放入,如果使得每盒饼干数量相同,根据木桶原理,那么最终每盒饼干的数量一定等于饼干数量最少的那盒。
时间复杂度解析
我们只需要遍历所有饼干,算这盒饼干与数量最少的那盒饼干的差值就行,复杂度为O(n)O(n)O(n)。
代码演示
T7、新年花坛守护战 - 题解
题面大意
现在有nnn个花坛,每个花坛上有aia_iai 个小年兽,你需要驱赶所有的小年兽。
有两种驱赶的方案
幸运福花:消费 1个1个1个 金币可以驱赶一个小年兽
烟花炮:消费 kkk个 金币,可以驱赶任意一个花坛上的所有小年兽
题意分析
请问最少花费多少个金币,就可以将小年兽全部驱赶呢?
解题思路
每个花坛只要选择一种方案就行了,然后我们要看是选择幸运福花还是烟花炮,如果某一个花坛上的小年兽数量是小于烟花炮需要的金币数量,那么就选择幸运福花驱赶这个花坛上所有的小年兽,反之选择烟花炮。
时间复杂度解析
遍历所有花坛,进行分析即可,复杂度为O(n)O(n)O(n)。
代码演示
T8、新年红包 - 题解
题面大意
有nnn个数字,只有一个数字出现了一次,其他数字都出现了两次。
题意分析
求出现一次的那个数字
解题思路
用异或去消除两两出现的数字,剩下那个就是出现一次的数字
时间复杂度解析
遍历所有数字,复杂度为O(n)O(n)O(n)
代码演示
T9、新年糖果 - 题解
题面大意
给你一个数hhh,可以被分成n+1n+1n+1个数相加,数的取值为pi(0≤pi<n,pi=n×2)p_i(0\leq p_i < n, p_i = n \times 2)pi (0≤pi <n,pi =n×2)
题意分析
问hhh最多能被分成几个$ n \times 2 $
解题思路
因为题面告诉我们hhh这个数,最多只能被分成n+1n+1n+1个,所以答案的最大值为n+1n+1n+1。
再看一下hhh里面有多少个$ n \times 2 $就可以
时间复杂度解析
求得hhh能被分成几个$ n \times 2 $,用除法就行。复杂度为: O(1)O(1)O(1)
代码演示
T10、新年消消乐 - 题解
题面大意
给你 n×2n \times 2n×2 个数,两个数字相加如果是奇数则消除,且一个数只能被使用一次
题意分析
是否所有数都能被消除。
解题思路
一个偶数加上一个偶数还是一个偶数,一个奇数加上一个奇数会变成偶数,一个奇数加上一个偶数才会是奇数。
所以,统计奇数与偶数的数量是否相等即可。
时间复杂度解析
遍历所有数统计数量即可,复杂度为O(n×2)O(n \times 2)O(n×2)。
代码演示