TuringJudge monthly 图灵姬月赛 2019.9【解题报告】

yayoi 2019-09-06 8:37:34 2019-09-08 21:52:54

A.环形加密

众所周知,这是一道签到题,注意一下可能有空格(ASCII码是32),行读入以及取模的时候注意结果可能是负数(注意k的范围)就行了。

不做过多的解释

看了大量同学爆零后,我还是说一下要注意的点吧。

  1. 题意:题目给的是加密规则,询问的是解密,所以是减k不是加k。
  2. 字符串存在空格,所以不能直接cin或者scanf,要行读入,用gets或者getline。
  3. 循环位移k次实际上对于字母来说就是位移k%26次,对于数字来说就是位移k%10次。
  4. 因为是减k,所以可能会减成负数,而负数取模还是负数,所以记得取正。

B.白皇后

简单的模拟题

因8月月赛“精灵的薪水”荣获 得分率 最低的题目,这次 又白 决定一定要出一个真正的水题

数据规模很小n<=300,即使有O(n^2)做法,也要放O(n^3)的做法AC!只是卡了O(n^4)的做法

做过八皇后问题的学生应该都知道,这一类问题,我们是把行、列、对角线,分别用4个数组表示出来的。其中对角线分别以x-y,x+y作为特征值(注意下标不要为负数)。此题同理,用这4个数组分别表示出行、列、对角线中的最大值,然后枚举每一个皇后,注意皇后自身不算攻击范围内的点,相当于把连续的一段分割成了前后两段,所以我们需要在前面分别计算数组的前缀最大值和后缀最大值,这样就能分别求出两段的最大值,她能攻击的范围内的最大值就可以直接O(1)算出。

但是我们是一个水题,我们只需要枚举矩阵中每一个点O(n^2),然后在循环体中枚举当前行O(n)+当前列O(n)+两条斜线O(n),找出Max即可。

注意不要把自己算上,审好题!

只学完C语言就能写出的O(n^3)愚蠢~、代码,极其友好。

C.信号站

传播范围相当于半径,这也是这题要保留一位小数的原因,我们可以去求直径,这样就避免了浮点型的计算。

  • 对于10%的数据,k=1,直接输出数组最大值减去最小值。

  • 对于20%的数据,k<=2,枚举数组左右两部分,求出左右部分较大段的最小值。

  • 对于40%的数据,n<=10,直接深搜枚举数组分割成k份,求出最大段的最小值。

  • 对于60%的数据,n,k<=100,可以才用f[n][k]表示前n个数分成k段的情况中,最大段的最小值,那么f[n][k]=min(f[n][k],max(f[i][k-1],sum[n]-sum[i-1]))

  • 对于100%的数据,可以二分答案,将直径二分出来,直径越大需要的信号站就越少,然后通过贪心的方式,计算出最少所需的信号站是否超过k。 注意n为10^6的级别的时候,别用cin读入,会在读入浪费很多时间的,效率O(nlogn)

D.勇者的盾

首先要能看出来,这题加防御没有半点作用,是属于多余条件。

所以问题模型就变成了,盾硬度为0~n,在最坏并且勇者存活的情况下用最少的战斗次数知道勇者的盾硬度。

对于y=1的数据,因为勇者只能复活一次,所以要谨慎的从0开始测试n,所以战斗次数就是n

对于n<=10的数据,可以使用深搜枚举勇者每一次选择的怪物攻击力

对于100%的数据:

  • 可以用f[n][y]表示盾硬度在0~n之间,剩余复活次数为y次的情况下,要知道盾硬度的最少战斗次数。
  • 假设选择了攻击力为k的怪物,那么分两种情况:
  1. 勇者存活即盾硬度在k~n之间(等价于0~n-k),复活次数剩余y;
  2. 勇者死亡即盾硬度在0~n-1之间,复活次数剩余y-1,因为是最坏的情况,所以选择攻击力为k所需要的战斗次数是max(f[n-k][y],f[n-1][y-1])+1。
  • 然后勇者可以自行选择不同攻击力的怪,所以k可以是1~n,即f[n][y]=min(f[n][y],max(f[n-k][y],f[n-1][y-1])+1)。
  • 效率O(n^3)

Rank

恭喜以下同学:

麻烦一周内回复邮箱里的邮件提供收货地址

听说这次又实体奖牌

友情提醒:注册了不打会掉rating的,不提前注册直接来打没有rating

共 5 条回复

lu_ruo_kuan

前排资瓷

lu_ruo_kuan

@yayoi 请问什么积分还没有加上?

babyec

有加上吧

lu_ruo_kuan

哦,好像现在加上了

babyec

一般发布成绩之后就会算分了

AMAZE UI
Hello world!