牛客练习赛58总结

来水一下比赛总结吧！
t1 送分题，直接贪心即可
t2 感觉有一个显然的贪心策略直接写
5min 写完前两题
t3 一眼没想到什么状压，感觉可以通过某些瞎搞写一写，然后因为忘了return迷之tle
血亏三发提交，罚时爆炸...，30min左右通过！
然后看t4，最初感觉是个最短路，像是一个分层图记录一个方向之类的，感觉是懵猜的结论，没有敢写！
然后看t5，发现s = t肯定是最优的，那么好像是一个分解质因数，然后区间判断一个数是否出现，这个可以用vector搞定，可是要注意lower_bound要判断一下边界情况，end等等，1h过4题，感觉还可以！
然后看t6感觉不难就是一个数据结构，维护链上前缀和，然后用树剖线段树合并一下？推了一下，感觉没有道理，不大对！
时间只剩1h了，不太想肝数据结构了，于是回来看t4，细想类比推出了点结论，只能向右和下走，然后知道了这个我们可以DP，记录dp[i][j]为走到i,j需要改变状态的贡献，然后向两个单方向dp一下，注意点边界，完事！
再回来看t6，发现刚刚自己降智了qwq，只要维护可能产生贡献的点即可，就是check一下奇偶性，然后用树链剖分维护即可，但是来不及写了QwQ!
今天题不太难，回来补一补t6吧~