TG2011总结
TG2011真题 T1 铺地毯 我们只关心最后一张覆盖所求点矩形的编号，倒序查找，符合条件直接输出就好 T2 计算系数 很EZ，杨辉三角，之前周测写过 0912限时测试 T3 选择客栈 之前周测也写过 0912限时测试 前缀和维护前i个点中有几个 最低消费不超过 p 元的咖啡店 ，即 p > bi 然后O(n2) 求 两个颜色相同的点之间有 满足p>b的点 的方案数 ， 80分 ，O2优化 100分 T4 聪明的质监员 30分做法： 我们可以暴力的枚举W , 然后对于每个W , O(nm)求 最小的 $\sum_{j=1}^{m}y_i$ 可以考虑对30分做法进行优化 枚举 ---> 二分 70分 观察式子，可以发现，当W增大，满足要求的矿石减少，导致 yi 减少，反之同理。 所以我们可以二分 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