Codeforces Round #621


A. Cow and Haybales

题意

每次可以将相邻两个位置的一堆干草进行挪动。最多允许  \(m\) 次挪动,问最后第一堆干草最多能有多少。

分析

每次贪心的从之后的最靠前的有干草的位置挪一堆干草过来即可。

时间复杂度 \(O(tnd)\) 。

B. Cow and Friend

题意

每次移动的距离只能是给定的 \(n\) 个数中的任意一个,要求用最少的移动次数从 \((0,0)\) 移动到 \((x,0)\) 。

分析

显然,我们可以用最大的步数,大步的走向终点,如果最后一步会超过终点,我们可以把最后一步分成两步来完成,即做一个等腰三角形的走法。

有一种特殊情况时,最大的步子一步就会跨过终点,这样的话,需要直接用等腰三角形的走法。

当然,如果其他的步子可以一步到达终点的,也需要特判。

C. Cow and Message

题意

求在字符串中出现次数最多的满足要求的子序列,要求是:

  • 在字符串中的出现的位置构成等差数列。

分析

显然,长度为 \(1\) 和 \(2\) 的子序列,无论如何都能满足要求。

考虑长度为 \(3\) 的,假设出现的子序列为 \(abc\) ,而显然 \(ab\) 包含在 \(abc\) 当中,那么 \(ab\) 的出现次数应该大于等于 \(abc\) 出现的次数,显然找长度为 \(3\) 的子序列是没有意义的。

更一般的,可以发现找所有长度 \(> 2\) 的子序列都是无意义的。

于是只需要找长度为 \(1\) 和 \(2\) 的子序列,直接暴力即可。

D. Cow and Fields

题意

给定一张图,图中有部分的点是特殊的。

现在要在特殊的任意一对点之间添加一条边,要求添加边以后使得从 \(1\) 到 \(n\) 的路径最长。

分析

首先,很容易发现的是,如果特殊点之间本来就有边的话,显然答案就是最短路径,因为边均为 \(1\) ,直接 bfs 即可。

之后考虑需要加边的情况,假设要在 \(x,y\) 之间加边

显然可以预处理出从 \(1\) 到 \(x\) 的最短路径为 \(f[x]\) ,从 \(x\) 到 \(n\) 的最短路径为 \(g[x]\) 。

于是添加了一条边以后的最短路径其实就变成了 \(min(f[x]+g[x],f[y]+g[y],f[x]+g[y]+1,f[y]+g[x]+1)\) 。

那么我们添加一条边,显然需要满足这条边的两边 \(min(f[x]+g[y],f[y]+g[x])\) 尽可能的大。

我们不妨假设 \(f[x]+g[y] < f[y]+g[x]\) 则有 \(f[x]-g[x] < f[y]-g[y]\) ,也就是说我们对于每一个点 \(x\) ,按照 \(f[x]-g[x]\) 排序以后,对于 \(i,j (i< j)\) 一定有 \(min(f[i]+g[j],f[j]+g[i])=f[i]+g[j]\) 。

这样要找最大的就方便了,对于每一个位置,找在他之前最大的 \(f[i]\) 与其配对即可。

You may also like

LEAVE A COMMENT

Statistics

  • 0
  • 61,990

Categories

Archive

Comments