[LOJ10013]曲线

三分法适合求解凸性函数的极值问题

\(设当前求解的区间为[l, r],令lmid = l+\frac{r-l}{3},rmid = r-\frac{r-l}{3},计算f(lmid), f(rmid)\)

将其中函数值更优的点叫做好点,函数值较差的点叫做坏点

最优点与好点会与坏点同侧,据此缩小区间

\(因为a≥0,所以S是开口向上的二次函数,F(x)=\max \{S_{i}(x)\} 也满足单调性,可用三分法求其区间最小值\)

 

[LOJ10012]Best Cow Fences

\(二分答案,判断是否存在长度不小于L的字段,平均数不小于二分的值\)

\(如果把数列中每个数都减去二分的值,就转化为判定是否存在一个长度不小于L的子段,子序列和非负\)

\(用前缀和维护数列,就可用O(1)的时间查询平均数\)

\(这题由于精度问题,需要先将读入的数乘上1000再整数二分……乘完之后还要开long long\)

 

[LOJ10011]愤怒的牛

求最小距离尽可能大,采用二分答案的方法

\(对二分的最小距离d进行校对,若不满足条件则减小,满足条件则增大\)

 

[LOJ10010]糖果传递

\(设x_{i}为第i个同学从第i-1个同学获得的糖果数,若x_{i} < 0,则第i-1个同学从第i个同学获得-x_{i}个糖果\)

\(特别地,x_{1}为第1个同学从第n个同学获得的糖果数\)

\(均分后,每个同学拥有的糖果为avg = \frac{\sum_{i = 1}^{n}a_{i}}{n},则\)

$$avg = a_{1}+x_{1}-x_{2} \\ avg = a_{2}+x_{2}-x_{3} \\ … \\ avg = a_{n}+x_{n}-x_{1}$$

\(改写一下,有\)[……]

继续阅读

[LOJ10009]钓鱼

\(枚举每一个湖k作为终止点,期间的钓鱼次数则为\frac{60H+5\sum_{i=1}^{k-1} T_{i}}{5}\)

\(要使钓到数量最多,则需要保证每一次钓到的鱼最多,用优先队列维护\)

\(要注意\frac{60H+5\sum_{i=1}^{k-1} T_{i}}{5}>0才能将湖k作为终止湖\)

\(当优先队列最大值为0时直接跳出循环,这一步剪枝很重要!\)

 

[LOJ10008]家庭作业

[LOJ10004]智力大冲浪一样的思路

\(但注意的LOJ10004中复杂度为O(Nt),肯定会TLE,所以要考虑优化\)

\(注意到每次查找空闲时间的时候都是从t_{i}往前找,复杂度为O(t)\)

\(可以用并查集维护每段连续的被占用的时间,达到O(1)的复杂度,这样总复杂度就可以缩减到O(n)了\)

 

[LOJ10007]线段

[LOJ10000]活动安排一样的思路

 

[LOJ10006]数列分段

这道算贪心吗……可以说是模拟了

从前往后扫就行了

 

[LOJ10005]数列极差

\(根据贪心的策略,取max的时候尽量保证数列中两个最小的数相乘,取min反之\)

\(用优先队列维护数列,复杂度O(nlogn)\)

 

[LOJ10004]智力大冲浪

\(根据贪心的原则,罚款尽可能小,也就是说罚款大的要尽可能保证能不罚,所以将w从大到小排序\)

\(对于w_{i},从t_{i}往前安排,这样t_{i}前的任务也能充分完成,时间复杂度O(n^{2})\)