NOIP集训-10.13总结

农夫过河:SuperOjP923
SB DP..
 
------------------------------------------------------------------------------------
 
掘金:SuperOjP924
首先可以把输入转换成一个图论模型,并删去距离大于m的边
对于第一问,只需求出最大的联通块的大小
对于第二问,考虑状态压缩DP:
f(i,s),其中s是一个二进制数
表示到了第i个节点,s表示哪些节点已经走过了,距离的最小值
最后答案就是f(n,(not 0)) (这里的not指位取反,并且只对低n位操作)
 
------------------------------------------------------------------------------------
 
动物园:SuperOjP925
首先可以知道一个点的num就是从一个点i向前跳(每次令p = next[p],这样),
跳到i/2以内的时候开始计数(每跳一步计一次),跳到0所需步数。
首先可以求出k(i) = 从i开始跳到0所需步数
假设m(i) = 从i开始跳,第一次进入i/2以内的时候的点
于是现在就是怎么求m了
 
我写的70分做法:
倍增,可以求出每个点向前跳2^j次到的点,这样就可以求出离i/2最近的点,再跳一次就可以了
(据说这个nlogn做法是可以卡过去的,然而并不能...)
 
100分做法:
把[1,i]的子串拿来和整个串匹配
第一次匹配的位置一定是可以从i跳到的,然后如果超过了i/2,再往前跳。
下一次匹配的位置一定不会小于这一次匹配的位置
因此有均摊每个点O(1)的复杂度
------------------------------------------------------------------------------------