ABC327 总结

发布时间 2023-11-04 22:32:43作者: shinzanmono

A

傻逼题,降智吃了一发罚时。

B

依旧是傻逼题,std::pow 炸精度又吃了一发罚时。

C

傻逼题,切了

D

发现就是个判断二分图,切了。

E

一眼丁真,感觉最后一个一定是最大的,然后就是求以最大的结尾的 LIS。

交上去,喜提 WA29。

转变思路,考虑 dp。

\(f_{i,j}\) 表示当前选了 \(i\) 个(从后往前),第 \(i\) 个是 \(j\)

\(f_{i,j}=\max_{k=j+1}^{n} f_{i-1,k}+0.9^ia_j\)

后缀 \(\max\) 优化 dp 即可。

F

发现原题等价于选定一个矩形 \([L,L+W-1][R,R+D-1]\),使得里面的点最多。

考虑枚举一维,\(\log\) 一维。

发现加入一个果子等价于只要箩筐终止于了 \([T,T+D-1]\) 这一段。于是我们统计加入一个果子就给 \([T,T+D-1]+1\),否则就给 \([T,T+D-1]-1\),然后统计全局 \(\max\) 即可。时间复杂度 \(O(V\log V)\)

G

傻逼数数题,鸽了。