历年题目训练solution_第1页
历年题目训练solution_第2页
历年题目训练solution_第3页
全文预览已结束

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

1、solutionyycgame1、对于 20%的数据，, = 10。可以枚举取牌的所有可能。时间复杂度为( )。+2、对于 60%的数据，, = 2000。因为先手和后手取牌情况类似，所以只先手。可以设为取牌时考虑这一轮的情况：了张黑色牌，张白色牌时的获胜概率。取到黑色牌，直接获胜；取到白色牌，对手取到黑色牌，对手获胜；取到白色牌，对手也取到白色牌，pupil 取到白色牌，进入到下一轮；取到白色牌，对手也取到白色牌，pupil 取到黑色牌，进入到下一轮。可以推出：121 =+ 3 + 1 2 +则是要求的+1+2+1+2。时间复杂度和空间复杂度都为( )。3、对于 100%的数据，, = 10

2、000。可以发现 60 分算法中，真正对有贡献的状态只有1 个，于是只算这些状态3就可以了。还有个更加方便的，可以设表示进行了轮，nyx 和 Diaoyeye 全都取的白色牌，pupil 已经取走了张黑色牌的概率。这个转移方程也很好推，而且先手和后手获胜概率可以一起算。1数组开滚动就行了。时间复杂度为( )。3str1、对于 30%的数据， = 40。直接枚举两个子串，然后用 hash 判重。时间复杂度为(4)。如果你不会算第二问，就只能得 10 分了。2、另有 20%的数据，串由 1 个 a 和 1个 b。我没有写这个部分分，大概可以枚举一下 a 的个数和几个块中 b 的个数，然后算一算。2

3、、对于 100%的数据， = 2000。得到的串由 + ，考虑仅当串的长度最长时计算它。容易证明，被计算的方案满足 + ()不为的子串，其中()表示串的第一个字母。定义()为串中以字母开头的不同非空子串的个数，()为串中加上字母以后不为的子串的不同非空子串的个数。又因为, 均可为空，所以最终为 () () + 1)。u对于求()和()，可以将的所有子串下就行了。第二问纯属搞笑的。到一个中去重，然后直接判断一这些串中字典序最大的显然是由的字典序最大的子串的前缀加上这个子串，可以发现，这个前缀全由同一个字母组成，所以这一部分也可以通过计算。时间复杂度为(2 26)。3、数据范围可以开到105级别，

4、用后缀自处理字符串就可以了。test1、对于 20%的数据， = 50。 直接按题目里给出的式子算。时间复杂度为(4)。2、对于 40%的数据， = 0 = =1 =1 =1 =1即满足 + = ( + )的, , , 的个数不小于。那么可以算出所有 + 的值，求出每个值的出现次数，然后再乘一乘就可以了。时间复杂度为(2 log2 )。3、另有 30%的数据，全相等。要求一个最大的，满足 + + + =1 =1 =1 =1= = 4 可以注意到， = = 4 + 不会超过 1000，所以把每个值的个数算出来再求个后缀和就行了。4 + + + 的出现次数同样可以分两边算。时间复杂度为(2)。4、对于 100%的数据，1 = = 100000，1 = = 4。对于任意1 = = ，保证0 = =

人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论