2017长乐集训day2

首先是其实是A+组的B组

T1      今天唯一的得分项也是这几天第一次A的题,题目要求区间[0...1000]一些二次函数的最大值中的最小值,注意区间可取的数可为实数(刚开始被这个卡样例),因为二次函数的a总是大于零,即开口向上,可知F[x]在区间内定有最小值,画图可知。于是便可用三分查找的方法不断逼近最小值(要注意精度)。

 

T2        字符串分块,动态规划,不是很清楚

 

T3        非常强势的暴力,同样需要非常强势的预处理。。用线段树什么的

--------------------------------------下面是萌萌的分割线----------------------------------

A组

T1    求两个极大的数的最大公约数,可以将他们的因数直接暴力gcd求解✓

也可以用质因数分解,二者有异曲同工之妙。

 

T2

暴力  40分

AC

蛋疼的一笔的题,我是用类似模拟的方法做的,预处理出每一行每一列各有的观察点的个数,用w、s、a、d来表示机器人上下左右的观察点数,先预处理出第一次的情况,因为哈夫曼距离只和竖直水平有关,所以把答案分成竖直水平的两部分来处理,每次操作通过预处理的数据即可在O(M)的时间处理完后续的询问。

(因为把x打成y卡了好久。。代码太长的坏处,气得我直接把300+的代码缩成100+)

 

T3

密文和明码。。只要用第一个字母往后找再判断即可,无论是暴力或者是KMP算法都可AC。

 

T4

暴力40分

AC  容斥加一堆的数学方法。。头痛

 

 

The world has kissed my soul with its pain, asking for its return in songs。

Y.W.        2017/7/17     长乐集训

发表评论

邮箱地址不会被公开。 必填项已用*标注