29.3.18 考试小记

发布于 2018-03-29  2.45k 次阅读


T1

水DP。正解的思路非常好想,直接DP+组合数就好了,但是因为我秒了这道题,DP方程连写都没写,转移的时候没仔细考虑就选择了刷表法,以至于优化方式只有任意模数FFT一种,然后就不能拿到满分了。但是,如果写出来DP的方程,就变成了前缀和优化,然后这道题就变成了普及组DP= =另外,一定要特判n=m,否则会被前两个点卡掉。考场上因为这道题挂了好多分,就是因为上面两个细节,看来无论题目有多水都得认真思考啊。

 

T2

如果你直接从集合的角度想会不可做,直接从维护连通性会变成LCT,但是如果直接想答案的边的话就能AC了。因为n只有100,最多只有99条边,所以可以暴力线段树维护区间的边,查询直接暴力弄出O(nlogm)条边出来再跑MST就做完了。

 

T3

考虑把原图搞成序列。先把原图拉成序列,再把含有船的矩阵(与原图等宽)也拉成序列,那么某次移动合法的条件之一就是第二个序列为1的位置在第一个序列中也为1。这样我们就可以把第二个串反过来用NTT来优化匹配的过程。之后,我们可以BFS求出合法的移动方式,同时用相似的思路再记录可行位置,最后用第二个串的正串卷一下,就可以求出来每个位置的经过次数,然后就做完了。另外,有个细节可以减少一次DFT,详见代码。

 


Narcissus | HZOIer | zhuohaoyu1228@gmail.com | QQ 943382974