- 1、本文档共14页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
第一个题目count
[题目转述]
????给定n个自然数,统计不同的自然数出现的个数,按照从小到大的顺序输出。其中自然数的范围为0..1.5e9,n=200000
**[解题思想1]
????显然,此题可以用排序的方法来解决,根据n的范围,可以看出,O(nlogn)的算法是可以接受的。
[解题思想2]
????维护一个二叉树,以数的大小作为节点的权值,以数的重复次数作为节点的附加信息。之后中序遍历即可。看起来,树内的节点个数应该不到n,所以可能表现不错,其算法复杂度依然为O(nlogn)
[实际数据规模]
????挺小的,全部数据都是送分的。
[分析]
??这个题目实在不能说是一道TG组的好题。实际上,个人认为题目最大的意义在于:提供了10个测试排序算法的不怎么特别好的数据。话说回来,此题是送分题,但是送分题送的这么水,考察的也就只有OIers的细心程度了。在考试的时候,要相信有简单的题目,要相信有直接的算法。在我的身边就有几个同学因为这个题目与一等失之交臂,这是最可惜的事情。
第二个题目expand
[题目转述]
????给定一个字符串,如果某个-左边同为数字或同为字母,并且右边的Ascii码严格大于左边的Ascii码,则在原串中删去-,并在该位置上插入左右字符之间的字符。其中插入字符有3个参数。
参数p1=1==字母为小写
????=2==字母为大写
????=3==字母、数字都用*代替
参数p2????==同一字母填充的个数
参数p3=1按ascii递增填充,
??????=2按ascii递减填充。
其中原串的长度不大于100。
[解题思想]
????直接模拟,按照题目的大意转述即可。代码复用率要尽量高一些。尽量直接读入之后输出。
[实际数据规模]
????数据规模不大,但是各种情况都考虑了一些。
[分析]
??该题目实在是为了提高总分而用的。测试数据没有保证第一位不是-
第三个题目game
[题目转述]
??给出一行m个有序的数,每次取数可以从左端或右端取,第i次取数的权值为2^i,每次取出的数的值乘上权值累加,使得总得分最大。游戏进行n次。n,m=80,操作的数=1000
[解题思想]
??其实看题目,读到这里,显然也要估计到这是一道DP的题目。稍微分析一下就可以知道,这是一个较为经典的DP题目,对于区间[i,j],由于区间长度是确定的,所以无论从左边取还是右边取,权值必然也是确定的。这时,可以写出方程f[i,j]=max{f[i+1,j]+w*a,f[i,j-1]+w*a[j]}按照j-i的大小进行DP即可,每一层循环之后,另w:=w+w。其中j-i的最大值是m-2,最小值是0。
最后,max{f[i,i]+w*a,i=1..m}就是所求。
在计算中,需要进行大约2N^2次高精加、2N^2次高精乘单精,写得不好就会TLE,所以我考试的时候采用了10000进制。
[解题思想2]
??每一层的w重复计算了好多好多次,考虑优化,只要把w算进f内。考虑到w每次*2,问题规模扩大后,本质没有变化。设g[l,r]表示从l到r的区间内进行游戏(只有r-l+1个数)的最大得分,那么g[l,r]=2*max{g[l+1,r]+a[l],g[l,r-1]+a[r]}
省去了高精乘的时间复杂度。总共只需要n^2次的高精加高精,2n^2次的高精加单精。本思路代码为game.cpp
[实际数据规模]
依然是不大,覆盖的范围也比较全。但是如果高精度写得不好也会TLE
[分析]
作为一道DP题,该题的模型还是可以认为是显而易见的。仅从我个人的观点来看,题目设计的比较有水平,但是DP模型还是暴漏的太明显,数据还是小了些。高精度算法如果写得不好也会TLE。这要求我们平常多攒RP,要用快速的高精度。
[小小的技巧]
其实,本题的最大答案理论上也不会超过2^100。所以可以直接采用recordx,y:int64;这种结构进行运算。
typebignum=recordx,y:int64;end;令max=10^20即可(不要直接:=)
这样,类似于复数相加,写procedure也方便了,即使人工inline也很方便进位也只有一种。可以大大的缩短行数。不过由于int64这么多事事,还是不推荐。代码为game2.cpp
第四个题目core
[题目转述]
给出一棵无根树,边上有权。称最长路径为直径,定义路径的偏心距为:点到路径的上的点的最小值的距离的最大值,给出一个s,找出直径上的某段长度不超过s的路径,使得偏心距最小。
[解题思想]
算法是严格立方的。中心理念是不要做重复的工作。算法比较笨拙。考虑到树的性质,对于
您可能关注的文档
最近下载
- 2023届高考数学一轮复习专题:三角函数有关w的值及w取值范围的求法题型总结.docx
- 2024新湘艺版音乐七年级上册第二单元 汉族民歌 课件.pptx
- 教师资格证小学科目二默写本《教育知识与能力》.pdf VIP
- 江苏省淮安市淮安区2022-2023学年统考八年级上学期期中数学试卷 .docx
- GB-T17167-1997企业能源计量器具配备和管理导则.pdf
- 【优质】某地区一级水电站建设项目可行性研究报告-优秀甲级资质可研报告180页.doc
- 灶具成品检测标准.pdf
- 腹股沟疝(共27张PPT).pptx
- 部编版小学语文五年级上册第四单元整体解读与教学建议.doc
- 幼儿园 中班数学《10以内的倒数》.ppt VIP
文档评论(0)