首先是其实是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 长乐集训