coj2019国庆欢乐赛

Source

commetoj 2019国庆欢乐赛

F 高速公路

请先思考后再展开

考虑求出每个点的真实上界mm,我们称$a_i=mm_i$为关键点,那么超速一定是在关键点;

考虑mm怎么求,注意到其实$mm_i=min(mm_{i-1},a_i,mm_{i+1})$,左往右再右往左扫即可求出

设第i个关键点的位置为$pos_i$,枚举在第i个关键点超速,那么其实变化的只有$(pos_{i-1},pos_{i+1})$,重新算即可,$O(n)$

H 二人桌游

请先思考后再展开

如果是个dag,显然从终止状态直接建边,拓扑倒推,存必胜必败情况,$O(n^2)$
接下来我们主要关心环、平局这两个玩意,其实他们是一个问题
先老实写出转移是怎么转的:
若当前点只能去必胜态,那么只能去必败态
若当前点能到达必败态,则必胜
注意从必败态转移,我们能直接判断当前点的状态,所以平局不可能可以到达必败态

注意怎样才会是平局:要么去的两个点都是平局,要么去的一个点是平局,一个点是必胜态,而没有人会愿意前往一个必胜态来让对手必胜,所以平局一定成环,所以没拓扑到的点一定是平局

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/c7da7568.html
转载请注明出处,谢谢!