- 1、本文档共48页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
- 5、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
- 6、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们。
- 7、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
- 8、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
查看更多
USACO(Train)部分
Chapter1
Section 1.1
Your Ride Is Here (ride)
这大概是一个容易的问题,一个ad hoc”问题,不需要特殊的算法和技巧。这道题的难度相当于联赛第一题。用数组incomoutcom记录每个人的收入和支出,记录每个人的名字,对于送礼人i,找到他要送给的人j,inc(incom[j]outcom[i] div n),其中n是要送的人数,最后inc(incom[i]outcom[i] mod n),最后输出incom[i]-outcom[i]即可。(复杂度O(n^3用Hash表可以进行优化,降复杂度为O(n^2)按月为单位计算,模拟运算,1900年1月13日是星期六(代号1),下个月的13日就是代号(1+31-1) mod 7+1的星期。因为数据小,所以不会超时。当数据比较大时,可以以年为单位计算,每年为365天,mod 7的余数是1,就是说每过一年所有的日和星期错一天,闰年第1、2月错1天,3月以后错2天。这样,只要先求出第一年的解,错位添加到以后的年即可。详细分析:因为1900.1.1是星期一,所以1900.1.13就等于(13-1) mod7+1=星期六。这样讲可能不太清楚。那么,我来解释一下:每过7天是一个星期。n天后是星期几怎么算呢?现在假设n是7的倍数,如果n为14,那么刚好就过了两个星期,所以14天后仍然是星期一。但如果是过了15天,那么推算就得到是星期二。这样,我们就可以推导出一个公式来计算。(n天 mod 7(一个星期的天数)+ 现在日期的代号) mod 7 就等于现在日期的代号。当括号内的值为7的倍数时,其代号就为0,那么,此时就应该是星期日这样,我们可以得出题目的算法:int a[13]={0,31,28,31,30,31,30,31,31,30,31,30,31}int b[8]={0}
a数组保存一年12个月的天数(因为C语言中数组起始下标为0,所以这里定义为13)。b数组保存星期一到星期日出现的天数。用date记录目前是星期几的代号,然后用两个循环,依次加上所经过的月份的天数,就出那个月是星期几,当然,要注意判断闰年!知道了这个方法,实现起来就很容易了。注意考虑闰月的情况。最后注意要换行,否则会错误。O(n)。
把两个同样的项链放在一块,从头开始用两个变量(变量)a,ba+b之最大值,遇颜色变换时再将b指定给a即可,代码十分简洁。
思路二:每次将串s的首位移动至末位,每次均能从两头开始有哪些信誉好的足球投注网站,无需考虑环的问题。
思路三:无需考虑w的。进行分类讨论,只有rb和br两种情况。
Section 1.2
Milking Cows (milk2)
有三种思想。
离散化(其实就是进行了优化的有哪些信誉好的足球投注网站而已)
按照开始时间升序排序,然后从左到右扫一遍,复杂度是O(nlogn+n)的(排序+扫一遍,用堆、合并、快排都可以)。
所谓从左到右扫一遍,就是记录一个当前区间,[tmp_begin,tmp_end]。
如果下一组数据的begin比tmp_end的小(或相等),则是连接起来的,检查这组数据的end,取max{end,tmp_end}。
如果下一组数据的begin比tmp_end的大,则是相互断开的,整理本区间,ans1取max{tmp_end - tmp_begin,ans1}。ans2取max{begin - tmp_end,ans2}。
看不懂?去看看PASCAL或C的范例程序就明白了。
线段树
本题的规模是1e6,简单的模拟是O(nm)(n是奶牛个数,m是最大范围)的,会超时。(但是本题数据远没有描述的那么恐怖,直接模拟也是很快的)。
用线段树统计区间,复杂度降为O(nlogm+m),可以接受。
标记数组(哈希)
1e6的范围,开一个布尔数组完全可以,有人为TRUE,无人为FALSE,注意边界即可。最后线性扫描即可。
时间复杂度,应该是O(n),n为最后结束的时间。缺点就是……比较慢。叫什么好呢?并查集加速直接模拟。
记录一个fa[i]表示i之后第一个没覆盖的点。下次遇到这里的时候就可以直接跳过了。复杂度大概算o(n)吧。
Transformations (transform)
设a是原始状态,b是改变后的状态。
水平翻转:b[i,n-j+1]:=a[i,j] b[j,n-i+1]:=a[i,j] 这道题唯一的知识点就是数制的转换。 f[i,j]=f[i-1,k-1]+d[k,j] (i=k=j)
另一种解法:
1.初始化答案为0。S=T+#+Reverse(T)+$,得到串S(O(n))。
2.求出后缀数组SA、名次数组Rank (倍增法:O(nlogn) Dc3算法:O(n))
3.计算height数组并进行标准RMQ方法预处理(O(n))
文档评论(0)