2005noip
发布网友
发布时间：2022-05-30 05:50
共2个回答
热心网友
时间：2023-11-02 12:11
[问题分析]
此题初看是一个典型的搜索题。从河的一侧到河的另一侧，要找最少踩到的石头数。但从数据范围来看。1..109长度的桥。就算是O(n)的算法也不能在一秒内出解。
如果搜索石子，方法更困难。这要考虑到前面以及后面连续的石子。若换一种方法。用动态规划，以石子分阶段的一维动规，时间复杂度是O(n2)。最多也只有100×100的时间。但是这样分状态就十分复杂。因为石头的分布是没有任何规律，而且会有后效性。
这样只好有回到搜索。搜索石子会和动规一样没有规律。我们一桥的长度为对象进行搜索，然后再加上一个巧妙的剪枝就可以在很短的时间内出解。可以号称为O(m2)。[批注：号称一词已成为湖南OI本世纪流行词汇 ]
[题目实现]
先以时间为对象进行搜索。时间复杂度为O(L)。从桥的一侧到另一侧，中间最多只有100个石子。假设桥长为最大值(109)，石头数也为最大值(100)。这样中间一定会有很多“空长条” (两个石子中的空地)，处理时把这些跳过，就只会有M次运算。关键是找出每一个可以跳过的“空长条”。
我们可以先把青蛙可以跳出的所有可能求出，然后就可以求出可以忽略的“空长条”。
[特殊算法]
a[i]:前i个坐标中石子最小个数,初始为第i个坐标的石子个数
b[i]:第i个石子坐标
动规
a[0]=0;
对n>=t
a[n]=min{a[n]+a[n-s],a[n]+a[n-s-1], ...,a[n]+a[n-t]}
对s=<n<t
a[n]=max{a[n]+a[n-s],a[n]+a[n-s-1],...,a[n]+a[0]}
但由于n较大直接动规会超时。所以要将n压缩
查看坐标，可以发现，如果b[i]-b[i-1]>t，显然对于b[i-1]+t<n<b[i]，a[n]总是等于a[b[i-1]]..a[b[i-1]+t]中的数，因此可对其进行压缩。
注意，在计算过程中，由于其中有一些坐标是永远走不到的，因此需要用一个布尔型的数组c[n]进行判断。方法是，对于c[n],如果0<n<s,则c[n]为false，如果n>s,c[n-t],c[n-t+1],...,c[n-s]都为false,则c[n]也为false。
第三题 篝火晚会-fire
[问题评估]
此题或许大多数人会觉得很麻烦。或许有人会选择搜索来做，显然，50000的数据量不可能允许搜索不超时。或许有人会用贪心，但是却无从下手。
动态规划？怎么划阶段更是一个难题。然而，此题却不是考察选手的算法的，而是考察你从题目中找出基本核心的能力。
[题目实现]
题目给你的初始状态是一个回路，从第一个同学前断开，不难看出这是一个严格的上升序列。而输入的数据也可以将之构成一个包含所有同学的回路，否则就达不到没个人的愿望。
我们可以用两的数组来储存两个数组的状态，初始状态为st，目标状态为en。st[i]=i,
i<=n。而输入数据我门可以先用一个二维E数组储存，E[I，1]即表示第I 个人的第一个愿望。我们将目标状态数组en的第一个元素赋值为1，然后就可以把s[1]的第一个愿望加入数组为s[2]，依次我们可以逐个加入，加入没个元素的时候，还要判断一下每个元素是否在数组当中，如果在，那就取第2个愿望。如果第二个愿望也在数组当中，那么我们的目标状态的数组也就构造完成了。
如果每个人的愿望都能实现，显然，目标状态的数组的元素必定是N，而假如不是，那么就可以输出-1了。
此时，问题就显的简单些了，如何让一个数组从一中状态变成另一种状态，相信有很多方法，可还是个麻烦事。
从目标状态转换成初始状态的步数是等同于初始状态转换成目标状态，而此时再看看初始状态的数组，相信你已经看出些疑端了吧！
排序！！！
对，其实从目标状态转换成初始状态的过程就是一个排序的过程，而且还是一个最简单的冒泡排序的过程！
到了这了，问题已经明了了，题目所求就是每次进行连续交换的人数总和，这样，一个看似复杂的题目就变的异常的简单了！而题目2秒的时间*更是保证了冒泡排序经过一些优化以及剪枝后不会超时。
但是，千万不能用其他的排序法来解决。虽然能让你的程序变的更快，却同时你也得不正确的解！
就是这样
热心网友
时间：2023-11-02 12:11
