我出题比较喜欢安一个有趣冗长的背景,考查思维的题目。

所以可能很多小盆友都自闭了。

下面奉上题解,请食用。求轻喷。

【2019】【NEUQ-ACM SUMMER CAMP】第九次课程作业解题报告

兔子与快乐水

读题使人快乐。

题目大意可以理解为三堆可乐,两个人轮流挑一堆,最后一堆随意分配。求最后分到最少可乐的那个人最多能分得多少可乐。

乍一看是道博弈论的题目,实际是简单的脑筋急转弯。

我们可以这样思考,求最大值,那么浪费一定是最少的。那么,我们可以先取三堆可乐中较少的两堆,分别记为x1,x2,剩下来的最大堆的可乐数目(x3)一定不小于前两堆可乐的差值,即x3>=abs(x1-x2)。

那么我们模拟这个过程。第三堆先用来补前两堆的差值,剩余部分平分,加起来就是正确答案。

然鹅~

不需要这么麻烦。上文说过,求最大值,那么浪费一定是最少的。我们尽力做到不浪费的方法就是尽可能平分这三堆可乐。所以实际上最后就是一个求⌊总和/2⌋的过程。这种做法的正确性证明其实就是上一种做法。

记得定义变量需要long long

此题over XD

兔子的加班表

一维数组应用。

很多同学疑惑怎样才能求出连续的1。

其实很简单。可以设置一个maxn表示1的最大连续数量,ans表示当前连续1的数量。通过循环判断当前若是1,则ans+1;当前若是0,则把之前ans与maxn比较,更新maxn大小,并把ans重新置0。

至于如何实现首尾相接呢?

提供两种思路。

  • 开两倍的数组。把两份相同加班表依次存入数组,这样子自然就是上一份的尾巴接在了下一份的头上。而且题目保证一定存在0,所以无需担心如果全是1则需减半的情况。

  • 可以记录从数组第一个元素开始(如果有)和以最后一个元素为尾(如果有)的1的数量,最后加在一起。

兔子与玫瑰花园

一维数组应用。

此题三种解法,层层优化。但是由于最后一种解法树状数组和线段树知识点过分难,在此不做赘述。只讲基础的两种。

一,最简单暴力写法。

初始化数组point[n]为0。可以在每输入一个区间[l,r]的同时,通过一重for循环把point[l]到point[r]置为1。最后只需要i从0到n循环判断point[i]大小,若为0则ans++,最后输出ans大小即可。

二,优化写法。(较难,看不懂的同学可以跳过)

读入m组区间两端点left[i]和right[left[i]],第二个数组存在的意义是使直接通过左端点的值,就可以得知右端点的值。然后依据left[i]的值对数组进行排序。

对排序好的point数组遍历,扩展重叠区间的左右,即right[left[i]]<=left[i+1],则把区间右端点从right[left[i]]扩展为right[left[i+1]]。直至right[left[i]]>left[i+1],则把上个区间内point赋值为1。

接下去的做法同一。

这种做法节约了对重叠区间重复赋值的时间,但是比较难以理解。希望学有余力的同学可以好好思索,而且第二种做法数组也可用结构体代替。

祝大家下一次作业都AK!

× 请我吃糖~
打赏二维码