TG2011总结

· · 个人记录

TG2011真题

T1 铺地毯

我们只关心最后一张覆盖所求点矩形的编号，倒序查找，符合条件直接输出就好

T2 计算系数

很EZ，杨辉三角，之前周测写过 0912限时测试

T3 选择客栈

之前周测也写过 0912限时测试

前缀和维护前i个点中有几个 最低消费不超过 p 元的咖啡店 ，即 p > b<sub>i</sub>

然后O(n<sup>2</sup>) 求 两个颜色相同的点之间有 满足p>b的点 的方案数 ， 80分 ，O2优化 100分

T4 聪明的质监员

30分做法：

我们可以暴力的枚举W , 然后对于每个W , O(nm)求 最小的 \sum_{j=1}^{m}y_i

可以考虑对30分做法进行优化

枚举 ---> 二分 70分

观察式子，可以发现，当W增大，满足要求的矿石减少，导致 y<sub>i</sub> 减少，反之同理。

所以我们可以二分 W , 取最小的 \sum_{j=1}^{m}y_i

前缀和 100分

对于每个W , 用前缀和先处理出 \sum_{j=l_i}^{r^{i}}[w_j{\geq}W] 和 , \sum_{j=l_i}^{r^{i}}[w_j {\geq} W]v_j 就不用逐个枚举浪费时间

T5 观光公交

考虑部分分

对于10% 的数据，k=0

记录汽车 到达每个景点的时间S[i] 和 离开每个景点的时间F[i]

S[i] = F[i-1] + d[i]

F[i] = max(F[i-1]-d[i],F[i])

对于20%的数据，k=1

枚举每一个d[i]，使其减一，每次跑一遍10分的做法

100+100+80+30+30=340>270