预览加载中,请您耐心等待几秒...
1/2
2/2
在线预览结束,喜欢就下载吧,查找使用更方便
如果您无法下载资料,请参考说明:
1、部分资料下载需要金币,请确保您的账户上有足够的金币
2、已购买过的文档,再次下载不重复扣费
3、资料包下载后请先用软件解压,在使用对应软件打开
备战NOIp2011Noname001OnlineJudgeSystem模拟试题Noname001OnlineJudgeSystem-NOIp2011复赛模拟赛五–解题报告Copyright©2011ABCDEFGHI,Allrightsreserved.第页共NUMPAGES2页Noname001OnlineJudgeSystemNOIp2011模拟试题(一)解题报告过河问题这道题初看之下不好DP,但是容易想到贪心策略,每次让最快的人将每个人送过河,但这样会有反例(样例就是)。幸运的是,反例也只是一种情形,即最快的人回来,最慢的两人一起过去,第二快的回来,再一起回去。这样可能节省时间。可以证明,不存在第三种策略比这两个策略更优。因为策略已经固定,对于第i个人,这两个策略最多只与第i-1人有关系,所以我们按时间大小考虑每个人,Fi表示前i个人到对岸所花最小时间。根据两种策略,不难得出状态转移方程为:F1=T1;F2=T2;F1=min{Fi-1+T1+Ti;Fi-2+T1+Ti+T2*2}其中Ti表示第i人的渡河时间,这样我们就成功使用贪心来作为DP方程的转移来解决了这道题。总时间复杂度O(N*logn+n)。超级筷子加工厂排序+DP。按木棍重量从小到大排个序(注意,这道题在按木棍重量排序时,还应该考虑木棍的长度,也就是说不是单一的按重量关键字排序,而是重量和长度的多关键字的排序,排序时,在木棍重量相等的情况下,长度大的排在后面)。排完序后,剩下来的问题就和NOIp1999中导弹拦截的第二问一样了。最长公共子串【算法一】DP:由于是要求连续的,那么设f[i][j]为串a到i位置时、串b到j位置时能得到的最长子串长度。于是1<=i<=len(a),1<=j<=len(b),a[i]==b[j]时f[i][j]=f[i-1][j-1]+1。最后找f[i][j]里最大的输出。时间复杂度为O(lenA+lenB),可以通过40分。【算法二】我们可以借用RK算法的思想(用哈希判断两串是否相等来进行匹配)得到期望时间复杂度为O(nlogn)的方法。使用二分答案的方法。设left=0,right=min(la,lb),mid=(left+right)/2,易知最长公共子串的长度肯定在left~right之间。我们可以考察a与b是否有长度为mid的公共子串,如果有,则left=mid+1,否则right=mid-1,直到left>right(应该输出right的值)。用哈希来判断来自a与b的两个子串是否相等:依次计算出b[1]~b[mid],b[2]~b[mid+1],……b[lb-mid+1]~b[lb]的哈希值,存在哈希数组h[i]中,再算出a[1]~a[mid],a[2]~a[mid+1],……a[lb-mid+1]~a[la]的哈希值,若有冲突(哈希值相等),则很有可能匹配。但是,这只是有可能匹配,为了保证匹配,必须多开几个哈希数组,每个哈希使用不同的mod值。字符串的哈希值是什么?就是这个哈希值可以表示出这个字符串且不会有两个字符串共用一个哈希值。由于此题中的字符都是小写字母,设字符串的长度为m,可以采用(s[1]-97)*26^0+(s[2]-97)*26^1+...+(s[m]-97)*26^(m-1)的方法构造哈希值。但是,这只是有可能匹配,为了保证匹配,必须多开几个哈希数组,每个哈希使用不同的mod值。翻转游戏思路分析:这道题主要是考查广度优先搜索和位运算。下面以题目中给出的例子来介绍如何利用位运算来处理这道题。bwbwwwwwbbwbbwwb按输入顺序(从0到15),我们把这个状态转换为15141312111098765432101001101100000101bwwbbwbbwwwwwbwb输入第4行输入第3行输入第2行输入第1行数组num[i]的值为,对于输入过程中的每一个“b”,我们通过按位或运算,可以把上面的二进制表示的状态,转换成10进制状态39685。对每一个状态,我们可依次选择第0到第15个位置进行翻转尝试。对位置i可以通过i/4取得它在棋盘中所在的行号,可以通过i%4取得它在棋盘中所在的列号。然后再通过循环改变它相邻位置物件,此处通过异或运算求出选择在该位置翻转时得到的状态,判断这个状态是不是出现过,没出现过就入队,做相应的标记。直到出现目标状态即可退出搜索,或者队列为空时无解。可以看到,在此题中用到了按位或运算(|)、按位异或运算(^)及左移运算(<<)。