竞赛讨论区 > “夜莺杯”武汉理工大学新生赛题解

“夜莺杯”武汉理工大学新生赛题解

头像
Zechariah_2001
发布于 2021-11-22 15:10:42 APP内打开
赞 4 | 收藏 0 | 回复2 | 浏览722

Problem A. 分糖果

类型

思维 + 贪心

题意

已知一组有规律的数,{} (n 为偶数)

现在需要将其分为相等的两个集合,使两个集合的所有数的和之间的差值最小,求最小差值大小

题解

运用到一个特别简单的数学公式 = -2

对于前n-1个数,由上式可知,它们的总和是定小于的,为了使差值尽可能的小,那么所在的集合的数应该尽可能的小,即和前个数放在一起

进一步推导方程可以得到解的形式为的形式

Problem B. 拯救美少女

类型

模拟,BFS,剪枝

题意

见题面

题解

  • 通过观察可以发现,存在一些固定区域魔球无法到达(安全区域),所以先模拟魔球的扩散处理出这些区域。
  • 当勇者不在安全区域中时,相邻的两圈魔球到马也怪(圆心)的半径之差为(即有格没有魔球)。
    • 若勇者朝着靠近马也怪方向移动,则勇者与魔球相向而行,勇 者最多可以走 回合。
    • 若勇者朝着远离马也怪方向移动,则勇者与魔球同向而行,勇者可以走无限多回合。
  • 在具体实现时,还应记录每个位置下勇者当前最多的剩余回合数,若勇者 当前剩余回合数 该位置下最多的剩余回合数,则此时的移动不是最优,无需接着移动。如果不使用剪枝会导致

时间复杂度

  • 时,最坏时间复杂度为
  • 但实际上大多数的情况会被剪掉且,一般情况下时间复杂度可视为

Problem C. 简单的数学题

类型

数学题,或者找规律(

题意

如题,就是求该式子的值

题解

如果用dfs的话,大概在30层就可以得到误差<1的结果,相信大家都会找规律(

这里给出证明

由平方差公式可得

因此有

得到题目形式

其实就是拉马努金恒等式

Problem D. 三分钟学会 Treap

类型

模拟构造题。

题意

给定数组满足满足,要求构建出这棵树并查询一些节点的父节点标号。

题解

可以由以下方法构造出满足性质的:

个点按 从小到大排序得到的编号的序列就是这个树的先序遍历。每次找到最大的x的作为根,然后

排序之后x两边的数进行分治,根据先序遍历的性质两边数中的根就是x的左右儿子。

所以这样的只有确定的一种形态。

用以上方法构造之后记录父亲处理询问即可。

因为树高期望深度为所以分治期望进行层。期望复杂度

Problem E. HearthStone!

类型

排序、贪心

题意

​场上有一个怪物,场上有种怪物,求场上所有怪物攻击一次后,场上怪物的剩余血量可能数

题解

首先,可以证明,怪物剩余的可能血量是连续的(详细证明在下方),也就是说,可能血量的数量 最大剩余血量 最小剩余血量 ​。

先看的怪物攻击力是否为,如果为​,那么就没有亡语会触发了,答案显然为

攻击力不为时:

考虑求最大剩余血量,也就是要怪物出手的次数尽量少,可以发现场上原有的怪物都会有一次出手,那么贪心地先把有亡语的怪物全部去攻击一遍,这样就可以把亡语召唤出来的怪物数量最小化,也就能最小化怪物的出手次数。

考虑求最小剩余血量,也就是要怪物出手的次数尽量多,那么我们只需要让亡语召唤尽可能多即可。当场上有​个怪物时,我们先考虑让场上​最小的怪物去攻击,然后再把亡语召唤的怪物攻击掉,腾出位置,这样就可以尽可能的减少亡语召唤的浪费,从而达到让亡语召唤尽可能多的目的。贪心策略已经很显然了,但是​的规模太大了,不可能去一次一次地去模拟怪物的攻击。可以发现,怪物总是一种一种地攻击,也就是较小的种类的怪物先攻击,按照排序一下,然后处理一种怪物去攻击对血量的贡献即可。

复杂度

证明

设最大剩余血量为,最小剩余血量为

求最大剩余血量的时候,只要每次让​​​的怪物去攻击即可,跟顺序没有关系,那么按照求最小剩余血量的顺序去让怪物攻击。如果某个怪物攻击之后会使得亡语有溢出,那么我们先清掉一个的怪物,然后再让的怪物去攻击,可以发现,这就是得到血量的决策,那么以此类推,在将要溢出时,清掉两个的怪物,即可得到血量.......推到最后,就是把能提前清掉的​的怪物全部清掉,然后再让最小的怪物去攻击,这就变成求的贪心思路了,所以所有可能的血量是连续的。

Problem F. Awa 玩游戏

考点:思考题

题意:

如题面 说的很清楚了

思路:

很容易观察到第一轮只有手牌为m(或1)的人才能判断出自己是最大(最小)的,也就是所有人(没有人)比自己小,所以只有手牌为1或m的人会退出。
那么在第二轮中,因为排除了1和m,最小可能变为2,最大可能变为m-1,所以手牌为2或m-1的人也可以判断出结果并退出。
以此类推
第k轮手牌为k或m-k+1的人将退出(结论1

那么还有什么情况下可以判断呢?
容易想到当场上只剩一个人的时候他当然知道没人比自己小(结论2)
或者场上的人数与剩余可能范围内的数相同时所有人都能判断(结论3)(重要)
举个栗子
n取3 m取5
三个人的手牌分别为2 3 4
第一轮显然没人能判断
但第二轮时,剩余可能的手牌只有2/3/4了,那么对于手牌为3的人来说,另外两个人一定是2/4,所以他也可以判断出结果。

解法:

先以所有人手牌大小为关键字进行排序(记得保存Awa的手牌编号),每次观察当前最大和最小的两个人,判断谁会退出(或者一起退出)(结论1),当发现只剩一个人(结论2)或者剩余人数与可能的值域内数的个数相同(结论3)时所有人全部退出。

Problem G. 生蚝接柿子

前言

这题差点把原题搬上来了......感谢lygg验题

类型

数据结构优化dp

题意

n个柿子,y坐标两两不同,x坐标范围在,同时开始以1/s的速度落下,最底下有个人,最初能接到柿子的范围是,人的移动速度是v/s,问最终人最多能接到多少个柿子。

题解

由于所有柿子的y两两不同,且下落速度相同,所以接柿子的顺序一定是将所有柿子按y从小到大排序后的一个子序列(不一定连续)。

考虑dp,设dp[i][j]表示考虑前i个柿子,生蚝的左手在j位置时接到的最大柿子数,设状态转移非常简单,分成两种
$$
那么这个转移很显然可以用线段树进行优化,线段树支持区间更新最大值、单点查询。

需要注意的是,如果开个线段树,空间会超限,考虑将dp的第一维滚掉。

时间复杂度

当然这是比较无脑的做法,实际上就是维护滑动窗口的最大值,直接单调队列即可。

时间复杂度

Problem H. 和生蚝一起做乘法吧

前言

题意是学长ljw给的。

类型

贪心,二进制

题意

现在有的正整数共个,现在每次可以将其中两个数的一个二进制位互换,操作可进行任意次,问最终所有数的最小非零乘积是多少。

题解

先说做法:对于每个二进制位统计该位为1的数的个数,对于除了位以外的位找到1的最大个数,先分出,剩下的个数是按照尽量取最大一个个组成的。随手画一下大概就是这样。

image.png

黑色的矩形表示这一位1的个数,红色矩形表示最终数组中的数。

然后来证明:(1)这种做法一定可行;(2)这种做法得到的乘积最小。

(1)可行性

其实就是要证明一定可以分出r-l+1-k个1,也就是说位为0的数字个数一定小于等于k。

考虑对位分类讨论,首先中当位是1时,从顺着来看位和位的变化情况。

  • 位是1时,下一位情况是,接下来是这就完成了一个循环,可以发现顺着看的话位的1的个数始终大于等于位0的个数。
  • 位是0时,下一位情况是,接下来是,同样,这个循环也是满足位1的个数始终大于等于位的0的个数。

然后再考虑位是0的时候,由于都是正整数,所以必然能找到一个最小的使得位是1,那么的数都满足位是1,而这一部分位0的个数是,接下来的数都满足位是0,而这一部分位0的个数也是,继续下去又会重复上述过程。

这样就说明了一定可以分出r-l+1-k个1,可行性成立。

(2)正确性

首先有:如果最多能分出k个1,那么最终的最优状态一定会有一个状态是含k个1。可以反证说明,假设最终有t个1(t<k),且最小乘积小于含k个1的情况,那么我可以找到k-t个大于1的奇数,将他们与其他大于1的数进行操作,将除了位的以外的位全都换成0,那么这相当于什么呢?先看一个最简单的情况,原来的变成了,显然,推广一下,就可以得到我们操作之后乘积会比原来要小,假设不成立,所以最终状态一定是含k个1。

那么对于剩下r-l+1-k个数,我们要证明上面的贪心策略是正确的。考虑将每个数的每个二进制位分开看,即,这样的话最后乘起来将所有乘法分配后得到的式子每一项都是在每个数的二进制位中选一位得到的,考虑我们的贪心策略,当我们顺着去选的时候,每一个数由于都尽量取了最大,也就是把能取的二进制位全都取了,所以会使得后面能选的二进制位最少,于是就能得到按照这样的贪心策略得出来的式子的所有项的多重集是其他任意一个可能的式子的所有项的多重集的子集,因此这样得到的答案是最小的。

实现

很大,这里不能直接把所有数求出来,考虑枚举位直接算出这一位1的个数,最后的答案计算考虑按照1的个数从大到小枚举二进制位来算贡献。具体来说,把所有位按照1的个数cnt从大到小排序,依次枚举,当cnt改变时就说明最后会有cnt[i]-cnt[i-1]个相同的数,直接用快速幂乘进答案里。

复杂度

Problem I. 突破模式

前言

玩游戏之后结合做过的一些题想的简单题

知识点

dfs遍历

题意

给定几棵树,树上的一个节点到达其父节点需要增加一定数量的士兵,且在向上遍历过程中能将经过节点的士兵数量累积起来,求如果每棵树上仅在一个节点增派士兵(可以为根节点)并满足根节点的需求,一共需要增派多少士兵。

题解

因为每棵树仅从一个节点增兵,且每个节点处需要士兵的数量(能最终到达根节点并满足需求)跟它到根节点的道路上的所有节点都有关系,考虑从根节点向下遍历,并向下传递自己的信息。

令f[i]代表在i号节点增兵并能到达根节点所需的数量,fa[i]代表i的父亲节点,当b[i]>=f[fa[i]](即在i增兵并突破i节点后,可以满足fa[i]的需求,直接继续向上走),则f[i]=b[i]-a[i]+0;若f[fa[i]]>b[i],则说明如果i点刚刚增兵到b[i]的数量,可以突破i,但满足不了fa[i]的需求,则f[i]=b[i]-a[i]+f[fa[i]]-b[i]。

每棵树遍历一遍,求出每个节点的答案并取最小值,加起来即可。

Problem J. Awa 不会打音游

考点:状压dp+滚动数组

题意:

如题面,讲的很清楚了

思路:

注意到长条按住之后只有到最后才能松手,中间全是垃圾时间没有意义(只有按住和松开的过程影响转移)
那么一个很显然的想法,把一个长条拆分成两个点,记录为在第几条轨道-什么时间-出现(消失)以时间为第一关键字,出现/消失为第二关键字排序,先出现的在前面,先消失后出现(因为从松手到换轨道按住不需要时间)

重要信息——手指直接不能互相跨越

那么对于5条轨道来说,最左边的手指只能打1/2道,第二根只能2/3道,第三根只能3/4道,最右边的只能4/5道。

状态压缩,用一个四位二进制数保存状态,对应当前的手指被占用(1)和未被占用(0)(比如我只使用了手指1和手指3,则记录为1010,使用手指2和手指4记录为0101)

再观察轨道,容易发现最左和最右的轨道一定由手指1和手指4来打,轨道2和轨道4一定由手指1/2和手指3/4来打,中间的3一定由手指2/3来打

那么转移就很显然了,状压dp吧!

注意到n可能很大,拆分之后如果直接dp,2*n*2^4个int可能爆空间,所以用滚动数组进行优化

dp[i][j]表示当前为第i个点时当前手指的状态为j,用k表示准备使用的手指
对于按住,

dp[i][j]|=dp[i^1][j-(1<<k)]

对于松开,

dp[i][j]|=dp[i^1][j+(1<<k)]

(具体实现见std)


有的人可能疑惑:你怎么知道松开的手指是不是你按下去的时候用的手指?
举个栗子,假如现在我的手指分别按在1/2/3/4道上,现在我松开3道上的手指,如果dp中错误的松开了2上的手指,那么后续松开2的时候就只能松开手指1,当松开1时就会发现并没有手指按住1,出现矛盾,没有前置可转移过来的状态,那么在这里这个错误的状态就会被否决掉啦(也就是说,只有正确的匹配才会导向可行的最终结果)

Problem K. 新生训练

前言

胡乱出的签到题,主要在读题上设置障碍。

类型

暴力枚举,gcd

题意

对于分子在,分母在的所有分数,找出所有,对于其最简约分式,满足a的数位是x的数位的子序列,b的数位是y的数位的子序列,且a相对于x删去的数位上的数字的多重集和b相对于y删去的数位上的数字的多重集相同。

题解

数据范围比较小,直接枚举分子分母判断,把答案存下来排序输出即可。

关键在于根据题意判断,首先我们求出约分后的答案,如果约分后的分子分母依然有相同的数字,那么此时还要继续删,也就不可能满足条件。否则的话先分别判分子分母是否可以通过删除一些数位(即保留其他数位)得到,如果可以的话再判分子分母删掉的数字多重集是否完全相同。

可能出现的误区:纠结于数位完全删完以后怎么算,实际上删完以后怎么都不可能得到正确答案,也就不可能计入答案中。

Problem L. 美少女的预言

类型

dp,前缀和优化

题意

从一组序列(记作A序列,长度为)中依次选出元素组成给定的另一组序列(记作B序列,长度为),问有多少种选取方法。

题解

  • 表示A序列中元素下标,表示B序列中元素下标,表示当前A,B序列中分别选取元素有多少种合法选取方法,则,最终答案为。以上方法的时间复杂度为,在本题的数据范围下会导致超时。
  • 注意到在运算中反复的求,那么可以通过数组将其记录下来递推,此时时间复杂度为

Problem M. zech的神秘题库

前言

希望大家都能做出这题。

类型

贪心,签到

题意

题解

如果所有题目的难度总和小于总难度数m,那么显然无解,否则一定有解。

可行解证明:

我们按难度从小到大选择题目。记当前的题目难度为,剩余可选择的难度总和为

时,我们直接选择

时,如果,那么我们已达到要求。否则我们只需要选择,并放弃之前选择的一道难度为的题目即可。由于,根据题目给出的条件一定可行。

最优解证明:

易得要求难度总和小于等于时,按难度从小到大选择得到的题数一定是最优题数。

要求难度总和恰好等于的最优解题数一定满足

可以发现上述操作所的到的题数一定等于,因此为最优解。

2条回帖

回帖
加载中...
话题 回帖

近期热帖

等你来战

查看全部

热门推荐