AC仅仅是一个开始(浙江省宁波万里国际学校何民春).docVIP

AC仅仅是一个开始 单位：浙江宁波万里国际学校 姓名：何民春 邮编：315040 邮件：helenhmc@163.com NOIP2009已经过去，可以看到，NOIP一直在发展。除05年外，其他年份都注重基础代码的运用和建模的能力。而今年在此基础上增加了算法优化的考察，可以说难度上有一定的提升。这是很多人在备考的时候没有预料到的。我希望在这里向大家介绍一些关于平常训练时应注意培养的思维方式，希望读者看后能够有所收获。因为篇幅有限，这里着重介绍题目的扩展和组合。 OI有一个非常大的特点，那就是数据的范围。同样是一个描述，如果数据范围不同，那么就不能说这是一个题目了。而且限制条件的设置也使得题目变化很大。下面我用一个简单的实例来说明这个问题。 a+b问题 每个OJ的第一题基本上都是这样的一个题目，数据范围只是[0，100]，学OI第一天就可以将这个题目AC。 现在我们对其中的条件进行逐步的改变： 1、数据范围进行改变，假设我们变成[0，10^100]，那么这个题目就要使用高精度了，难度上就有了一个质的提高。 2、数据范围再次进行改变，[0，10^100000000000000000000000000000000]这个时候就要进行压缩了，在高精度的基础上要进行压位，难度再次提高。 3、数据的符号进行改变，从全是正整数变成可能有负号，这样的话，就需要添加字符串的处理进行正负的判断，而且还需要再另写一个压位的高精度减法，而且还有可能最后的答案是一个负数，从而难度继续提高。 4、数据从整数变成浮点，而且浮点的精确度也可以很高，这样对读入时的判断有复杂了很多，难度依然在提高。 5、最后我们可以想到这个题目并没有脱离10进制，所以我们可以把题目的条件设置为8进制，或者16甚至32进制等，从而难度达到了最高。 现在我总结一下其中的条件。a+b这个题目最原始的条件是给出两个10进制正整数，并且是整数，范围在[0，100]，这5个条件的改变就是对其中的限制性条件进行改变，或者是替换（除了1到2的改变则是一种高精度算法的优化）。经过这5次的变化，这个题目变成了一个极其复杂的题目，如果说原始的题目可以在半分钟内一次AC的话，最后改变的题目则在一个小时内都不一定能写出代码，而且极有可能WA掉。 平常在训练的时候容易犯的错误就是只知道去做题，把AC作为最终的目标，其实AC只是一个开始。每次都进行这样的题目扩展性训练，对于思维的发散，知识的整合有非常好的效果。长期训练后，对于利用关键字的建模能力会有很好的提升效果。 这样的思维方法和过程可以形象的总结为 下面我再介绍一下题目的合成，同样使用大家最熟悉的知识进行讲解。 网格路问题 这个题目我相信大家都很熟悉，也知道如果用数学算的话，直接就是m+n，而用递推式，或者说是DP的方法列出方程就是f[i，j]=min{f[i-1，j]，f[i，j-1]}+1，复杂度为O(nm)。我想这些大家都很熟悉，所以不再赘述。下面我们来进行一下扩展。 1设置坏点，也就是说使某些点(i，j)不能走。这样的话，方程就需要另外加一个判断。 2设置其他的转移方法。比如传送门，即如果走到（i，j）可以直接传送到（i±x,j±y）这样一个点 3设置特殊路径，这个有现成的题目，以下为引用部分 ural1119 城市为正方形格子，每个格子的边长为100米。地铁站在其中一个十字路口。Nikanor从家里步行到地铁站。他沿着街道走，也可以穿越某一些格子的对角线，这样会近一些。 求Nikanor从西南角的家到东北角地铁站的最短路径。输入首行为N,M (0 N,M = 1000),东西、南北的格子数。Nikanor从格子（1，1）的西南角的家出发，地铁站位于格子（N，M）的东北角。第二行为K(0 = K = 100),表示有k个格子允许对角线穿越。以下K行为允许对角线穿越的格子，分别用一对数表示，空格隔开。求Nikanor的家到地铁站的最短路径，四舍五入到整数，单位：米。Sample Input 3 2 3 1 1 3 2 1 2 Sample Output 383 以最标准的思想列出方程 f[i,j]表示在map[i,j]到map[1,1]的最小值 则：f[i,j]=min{f[i-1,j],f[i,j-1]}+1 如果存在特殊边需要再这样处理一下 f[i,j]=min{f[i,j],f[i-1,j-1]+sqrt(2)} ans=round(f[n,m])即可 加了这样的一个条件，就使得方程需要特殊的判断，下面我们看看这个题目的加强版本 飞翔 背景 鹰最骄傲的就是翱翔，但是鹰们互相都很嫉妒别的鹰比自己飞的快，更嫉妒其他的鹰比自己飞行的有技巧。于是，他们决定举办一场比赛，比赛的地方将在一个