SRM #512 div1

VictorWonder posted @ 2015年5月27日 10:42 in TopCoder with tags 日常向 二分答案 二分查找 解题报告 , 1117 阅读
最近打算刷几套SRM提高智商,就选了这套,512这个数字特别顺眼,万万没想到竟然出现了一件非常有趣的事情。

我们先来看一张图:
可能有人发现了,我的Score好像有点奇怪啊,还有Challenge Succeeded是不是有点多?
具体的过程是这样的,我不会做T2,好不容易才登上了TC的官网找到了题解,发现题解似乎有点问题(实际上是因为我自己题目没看仔细),有一个要求是最后的两个序列合并起来之后,元素都是单调递增的,但是我没有看到,题解中说第一个序列的最后一个元素必然比第二个序列的第一个元素小,我感觉很有问题啊,随便构造了一个数据{"1","2","3","4","5","8"},自己觉得答案是6,于是就随便找了一个人,Challenge了一下,竟然Challenge Succeeded了,接着又找了一个人,竟然又Challenge Succeed了,一连叉了十多个人,总算遇到一个过了的人,可是一看输出,竟然是5,我再仔细地观察了一下题面,终于发现了自己的错误,然而,既然都已经开始叉人了,在Claris的怂恿下,我就多叉了一会儿,几乎把所有人的程序都叉了一遍(可能会有漏网之鱼)。
最后大致统计了一下,几乎90%的C++程序都是有问题的,会显示段错误,其次是Java,好吧,主要是Java的基数比较大,也找到了好几个有错的程序,但大多数情况下的Java程序都是没有问题的,紧接着是C#,总共也没几个人用C#,所以只有1~2个人的程序是有问题的,最强的是python,没有人的程序是有问题的,主要原因是没有一个人打了python。
然而,现在这张图已经看不到了(还好我截图截的早),将Medium这题提交并测试之后,我的分数瞬间就掉了下来,真是难过。
 
Easy-256pts
题目大意:一共n天,每天有m种菜可以买,第i天买第j种菜的价格是p[i][j],第i天买了第j种菜,那么第i+7天也得买第j种菜,有一天不买菜,那么接下来都不能买了,给出拥有的钱数,问最多可以买几天的菜。
因为有一天如果没有买了,接下来就不能继续去买了,所以,我们二分最终的天数,然后统计一下每天买哪种菜,最终的总花费最少,就可以得出最后的答案了。
 
Medium-512pts
题目大意:定义类斐波那契数列为f[i]=f[i-1]+f[i-2](i>1)的数列(f[0]和f[1]任意定义),给出50个数,先后两次从中挑出一些数,每次挑出来的数都是某个类斐波那契数列的子序列,要求将两次挑出来的数合并在一起,数字从小到大递增。
因为开始没有看到将两次挑出的数合并在一起的条件,以为是网络流或者是DP什么的,然而,有这个条件的话,我们先将给出的数列从小到大排序,那么两次挑出的序列,一次是在前i个数中挑出来的,一次是在后n-i个数中挑出来的,那怎么从中挑出数呢?具体请看题解,我们首先枚举类斐波那契数列的头尾两个数,然后再判断有哪些数是在这个类斐波那契数列中就可以了。(至于为什么会出现段错误,我也不清楚)
 
Hard-1024pts
还在做

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter