NOIP集训-10.13总结
_THIS_IS_START_OF_ARTICLE_
_THIS_IS_END_OF_ARTICLE_
农夫过河: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)的复杂度
------------------------------------------------------------------------------------
评论 (0)
