[NKU]sweet @ Google && TopCoder && CodeForces

  BlogJava :: 首页 :: 联系 :: 聚合  :: 管理
  33 Posts :: 1 Stories :: 15 Comments :: 0 Trackbacks
485做出一题,486作出两题但是被系统挂掉一道……

485 250:
给出一个正数等差序列(长度>=4,<=50),但序列某位如果是偶数,则把他一直除2直到是奇数
给你的是改造后的序列
求该序列,如果多解则输出字典序最小的
乍一看没想法,实际上可以这么分析,这个问题和奇偶性密切相关
我们分析:
首项为偶,公差为偶 -> 可以同除2,得到的答案一定不是字典序最小,可舍
首项为奇,公差为偶:奇奇奇奇……
首项偶,公差奇:偶奇偶奇……
都是奇:奇偶奇偶
总之,都有两个奇数项,是和原序列相同的,这样的话咱就枚举那两个,产生数列并且更新答案就行……

rank:1283->1338,小涨一点

486
1:给出一个数A,让你由若干步A+=A A-=A A*=A A/=A 得到B,如果多解要字典序最小
这个题目我实现时有点2B,A-=A实际是废的(1000000000>=A,B>=1),得到0就产生不了别的了;A/=A实际上只要一次(只是产生1,晚用不如早用),看某个小鬼子的代码,就是用+=和*=去DFS扩展A,或者用+=和*=去DFS扩展1,然后求字典序最小的解输出……我的BFS写的貌似正确,也没人敢Cha,实际上简单的1->2就把我挂了……学习、增加经验了……

2:这题背景是Qsort,给你了这么个定义:选定基准P之后,这次的代价分为2部分:(有多少个本该<P的东西在P后+有多少个本该>P的东西在P前)+(左右两部分递归求代价),给的数组范围是50,并且元素个数不相同
一时没有想到好的做法,后来看人知道可以DP……实际上我用MAP水了一下……因为数字的绝对大小无关紧要,我们可以把这些数离散成1~N的,然后枚举基准P,统计第一部分,并分出左右两部分,接下来离散左右两部分到1~left.size(),1~right.size(),并递归求解……
为啥离散到1~n而不直接搞呢……是为了记忆化搜索,因为对1~n的一个排列,这个值是固定的,所以我用了一个Map<string,double>,把状态塞进string里进行记忆化搜索,竟然过了……

rank:1338->1416,又小涨一点

总的来讲,近日在TC上表现不错……我要一点一点向上爬……
另:TC可以学习他人的代码,的确很有益
另:我有时感觉有的人代码的确有错,实际上系统测试下来真有错,但是没敢Cha,也没想好怎么构造让他挂的数据,Cha人能力也要提高,只指望写有时还是无力的……

posted on 2010-10-27 01:37 sweetsc 阅读(181) 评论(0)  编辑  收藏

只有注册用户登录后才能发表评论。


网站导航: