来水一下比赛总结吧!
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吧~