解药,解题报告(共4篇)

《解药,解题报告(共4篇)》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、为了适应公司新战略的发展，保障停车场安保新项目的正常、顺利开展，特制定安保从业人员的业务技能及个人素质的培训计划解药,解题报告(共4篇)　　Doubly-sortedGrid　　GCJ09FinalProblemC　　【简要描述】　　给出一个N*M的方格纸，在方格内可以任意填写字母a到z，但是必须保证，任意一行从左到右字母的字典序必须保证不降，同时任意一列也必须保证字典序不降。　　现在一些格子已经填上了一些字母，现在要求将剩余没有填写的空格子填满，同时要使得整个方格纸上满足双调不降的要求。问总的方案数取模10007的值。　　Smalldat

2、aset　　N,M≤4　　Largedataset　　N,M≤10　　【分析与算法设计】　　看到这个问题当然最简单的想法就是搜索了。　　不过，注意到每一个格子可以填26种不同的字母，所以简单考虑就可以发现，对于即使单独1*M的方格纸，可能填写的数目也将达到O(26M)的规模——所以简单的搜索是绝不可行的。目的-通过该培训员工可对保安行业有初步了解，并感受到安保行业的发展的巨大潜力，可提升其的专业水平，并确保其在这个行业的安全感。为了适应公司新战略的发展，保障停车场安保新项目的正常、顺利开展，特制定安保从业人员的业务技能及个人素质的培训计划　

3、　但是，同时我们也可以注意到，其实我们在进行搜索的时候进行了很多的重复搜索，所以我们需要尝试确立一些搜索的状态来进行记忆化搜索，或者进行递推。　　算法1：　　注意到在Small中，虽然总的方案数很多，但是注意到行数和列数都不是很大，因此我们可以尝试进行状态压缩的动态规划。　　沿用状态压缩动态规划的一般方法，我们记录扫描线上的状态进行转移。　　如有图所示，其实我们需要记录的状态仅仅是紫色格子　　中的字母填写情况，蓝色格子中的已经填写过的字母情况我们其实就不用知道了——通过紫色格子已经可以反映出蓝色　　格子的字母状况了。　　然后我们只要枚举橘红

4、色格子填写什么字母然后进行状态的转移即可。　　那么考虑紫色扫描线上的点只有O(M)，相应的，状态数　　即为O(26M)，这在Small中，是完全可以接受的。　　至于一些格子已经填写了一些字母，我们只需要在转移　　到具体的格子然后再进行判断即可，算法并没有什么关键的转变。　　时间复杂度：O(NM26M　　)目的-通过该培训员工可对保安行业有初步了解，并感受到安保行业的发展的巨大潜力，可提升其的专业水平，并确保其在这个行业的安全感。为了适应公司新战略的发展，保障停车场安保新项目的正常、顺利开展，特制定安保从业人员的业务技能及个人素质的培训计划　

5、　空间复杂度：O(NM+26M)　　期望得分：Small通过　　观察到在Large中，虽然N和M仍然不大，仅仅10而已，但是，考虑到26个字母的可能填写方案，显然的，仍和关于字母具体信息的扫描线记录方式都是完全行不通的。我们知道，记录一个位置到底是什么字母，就需要花费26的记录代价，这是导致我们无法记录信息的关键问题。　　那么，我们能不能分离这一问题，并不去记录某一个位置是什么字母，而去记录每一种字母到底占了哪些位置呢？　　显然的！　　算法2：　　这里我们就需要利用到双调有序这一重要性质了。　　如果在格子(x1,y1)内的字母比(x2,y2

6、)内的字母字典序小，那么则必然有这样的限制条件：x1≤x2，y1≤y2。　　所以，对于字母c1，以及恰好比其大一个字典序位置的字母c2，其分界线一定是一个从左下角到右上角的连续折线，并且任意一点只会向上，或者向右：　　如右图所示，我们这里标出了字母a，b，c下方的分界　　线，注意这里字母c所在的格子并不是连通的，所以，字母c的分界线是存在一部分与b的分界线是重合的。而其实字母d的分界线是完全和字母c重合的。　　字母e的分界线就是整个方格的下拐折线。目的-通过该培训员工可对保安行业有初步了解，并感受到安保行业的发展的巨大潜力，可提升其的专业水

7、平，并确保其在这个行业的安全感。为了适应公司新战略的发展，保障停车场安保新项目的正常、顺利开展，特制定安保从业人员的业务技能及个人素质的培训计划　　并且任意字典序大于e的字母的分界线都是与字母e重合的。我们不妨称这样的一条从左下角到右上角的折线为一　　条路径。　　对于两条路径P1和P2，如果满足两条路径不严格相交，并且路径P1存在一部分严格的处在在P2的上方，则我们称P1=jtheninc(x,1shl(i-1));　　fork:=x+1tox+(1shl(i-1))dod[i,j]:=d[i,j]+d[i-1,k]*p[j,k]/100;

8、　　d[i,j]:=d[i-1,j]*d[i,j];　　end;　　ans:=1;　　fori:=2to1shlndo　　ifd[n,i]>d[n,ans]thenans:=i;