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

kzl 2019-08-05 13:07:41 2019-08-10 13:32:13

A:a+b(送答案题)

·不解释·

B:精灵的比武(送分题)

该题考查素数判定以及求一个数的约数。

解法1:对于每一个数,遍历其所有约数.,然后对于每一个约数,判断该数是否为质数。 对于一个数A而言,可以求得A的约数中最大的质数是a,然后比较各个数字的最大质数,求出最大值,然后输出对应数字。

解法2: 素数筛,暴力筛选出20000内的质数,然后第一轮循环从大到小遍历所有质数,第二轮循环遍历所有数字A,第一个可以整除质数的A即为所求。

C:精灵的薪水(送M题)

显而易见,这是一道区间操作的题目

按照惯例我们先来 口胡 思考一下暴力的解法

1.先把数据读进来

2.进行m次操作

  • 操作一:暴力循环,将[L,R]所有的数加上C
  • 操作二:仍暴力循环,将[L,R]所有的数乘以-1
  • 操作三:还是暴力循环,将[L,R]所有的数计算个累加和
  • 操作四:依旧是暴力循环,查找[L,R]中的众数(别问我众数是什么)

3.最后别忘了 输出一下最小值

看起来除了众数的操作要想一想之外,其他的操作只是循环数组小练习

那就先细想一下众数怎么找:

  1. 先排个序,就可以把相同的数扔到一起了(只sort区间[l,r]的数)
  2. 然后进行一个循环数组小练习,伪代码大致如下
while(l<=r){
	   if(当前元素a[l]和下一个元素a[l+1]相同)  //统计当前元素的个数
			    当前众数个数sum++
		else{                                           //当前元素的个数统计完毕
				if(sum>max)
					   更新max和ans
		}
}

输出ans

暴力的解法get了,惯例算一下复杂度:

  1. 先把数据读进来 O(N)
  2. 进行m次操作 O(M)
  • 操作一:暴力循环,将[L,R]所有的数加上C O(R-L)
  • 操作二:仍暴力循环,将[L,R]所有的数乘以-1 O(R-L)
  • 操作三:还是暴力循环,将[L,R]所有的数计算个累加和 O(R-L)
  • 操作四:依旧是暴力循环,查找[L,R]中的众数(别问我众数是什么)O((R-L)log(R-L)+R-L)

3.输出最小值 O(N)

根据题目中给定的数据范围

对于100%的数据:N<=10000,M<=10000 ,-108 <= C <=108,保证操作4中的[L,R]区间长度不超过103

R-L的极限范围是N,操作4中的R-L是103

综上所述,时间复杂度为10^8,刚好可以。暴力可以AC。平时做题时千万要计算复杂度,加强练习啊。

补充一个不是正解的众数方法:类似选择排序形式的二重循环,如果M个操作都是极限的在[L,R]求众数,那么这样的时间复杂度会是O(MN2)。但是因为数据没有刻意的加强,会导致超时的求众数操作没那么多、范围没那么大,所以这种写法也不会超时。

C作为一个普通的输入数字,题目中莫名其妙的告诉了数据范围且范围在int之内,务必要想想为什么突然告诉你这条没用的信息!!转自众多Oier在NOIP2018普及组赛后的感慨:十年OI一场空,不开LL见祖宗

本题与NOIP2018 PJ T4 给分思路一致“敢写暴力我就敢给分”,不过我的数据范围相对严谨一点。

此外,为写线段树的TZ默哀三分钟==!

D:精灵的游戏(动态规划)

考察区间动态规划的基本思想: 令dp[i][j]表示在拿走i-j的牌能够取得的最小分数。

那么状态转移方程为:dp[i][j] = min(dp[i][j],dp[i][k]+dp[k][j]+a[i]*a[k]*a[j])

表示在[i,j]的区间内,最后抽取第k张牌,所能得到的最小分数是多少,然后枚举第k张牌的位置,得到dp[i][j]的最小值。注意由于是最后抽取的第K张牌,所以最后[i,j]的区间内还剩下三张牌a[i],a[k],a[j]所以抽取第K张牌的花费为a[i]*a[k]*a[j]

E:精灵的魔法值(单调栈)

考察单调栈的基本知识:

由题目意思可知:要求选出一个区间,使得区间中的最小值与区间和的乘积最小。我们可以利用前缀和的思想O(N)求出任意区间的和。但是如何求的区间最小值呢?一个朴素的思路是采用RMQ O(NlogN)预处理出每一个区间的最小值。然后平方枚举区间,对于每一个区间找到其最小值与区间和的乘积最大。这样的算法是平方级别的,数据范围告诉我们,这是肯定会超时的。

其实我们没有必要枚举每一个区间。因为大多数区间的最小值是相同的。对于每一个值,我们只需要找到以它为最小值的区间最长长度是多少就ok了,那么问题就被归纳到了一个这样的模型:枚举每一个数,需要找这一个数列中前面第一个比它小的数的位置,需要找到这一个数列中后面第一个比它小的数的位置。然后用这位置之间的区间和乘上当前这个数然后取最大值就可以算得一个答案。这就是一个单调栈的模型。

关于单调栈是什么——> https://blog.csdn.net/zuzhiang/article/details/78134247

Hint 注意数据全部是0的情况

Input: 10 0 0 0 0 0 0 0 0 0 0

output:

0

1 1

96分的TZ大概就在这一组上没过

请以下同学提供收货地址

  1. gzq123
  2. Zhou
  3. ldn
  4. _automaticlyTLE_
  5. jcf927
  6. gyh
  7. LiBoyi

麻烦五日内回复邮箱中收到的邮件,提供收货地址

经费有限,意思意思

共 6 条回复

TooY0ung

%%%%%%%%%%%%

liuzhen_

kzl AK IOI

babyec

C题简直毒瘤

cww970329

啪!

cww970329

啪!

zC2409190

还是爱洛谷

AMAZE UI
Hello world!