分析1

并不想思考前三部分分着怎么打啊?

很直观的就可以想到,在可以达到的doge之间连有向边,代价为方向上的走向所需要的步数

直接跑一遍裸的dijkstra就有36分了咯…..

为了代码文章看起来好一点,就把头文件去掉了


分析2

思考bfs

用数组\(f[i][j]\)表示\({doge}_{i}\)到建筑\(j\)的最少步数

初始\(f[0][B_0]=0\),每次用\(f[i][j]\)去尝试拓展\(f[i][j\pm P_i]\)和位置\(j\pm P_i\)其他doge

一旦拓展到\({doge}_{1}\),直接输出答案即可,时间复杂度\(O(NM)\),期望得分57

代码同样,暂时去掉了头文件


分析3

一口毒奶……这题好毒啊……

考虑分块来做

\(P_i>\sqrt n\)时,可以直接暴力来做,因为最多只会有\(n\sqrt n\)条边

\(P_i\le \sqrt n\)时,我们可以发现有大量的边重合,考虑把他们合并起来

具体的合并方法:

不妨对每个点建\(\sqrt n\)个额外点,设第\(i\)个点的第\(j\)个额外点为\(P_{i,j}\)。我们在\(P_{i,j}\)\(P_{i+j,j}\)连长度为\(1\)的双向边(因为每一次跳跃的花费为\(1\))

再由所有\(P_{i,j}\)\(i\)连长度为\(0\)的边。对于\(vi≤C\)doge,我们就由\(xi\)\(P_{xi,vi}\)连长度为\(0\)的边即可,很容易理解

然后剩下的,就是跑一下最短路了……我直接写了一发SPFA…

内存很坑爹啊…RE了无数次总算是把官方数据跑过了…hack的数据实在是无能为了了

在调试的时候,发现不应该取\(\sqrt n\),实际表明,取\(\sqrt {\frac {n}{logn}}\)附近的时候比较优

为了更达到减小内存的目的,稍微增大时间,我手动的把\(\sqrt {\frac {n}{logn}}\)减小一个常数,多次提交…..

 


发表评论

电子邮件地址不会被公开。 必填项已用*标注