主题:60次编程比赛结果
FancyMouse [专家分:13680] 发布于 2007-08-25 20:32:00
评测规则:这次的数据,n<=5000有3个,全部在0.5s内解出的进入下一等级。5000<n<=50000的有2个,全部0.1s内解出的进入下一等级。最后的大数据有5个。这些数据每个10分,总分100分。若有编译上的错误,经过我的修改的,-5分。如果有无关的输出、或者64位整形输出不对,我手动修改,不扣分
若干位朋友在规定时间以内提交了有效代码,以下是总的得分排名。具体评测结果见后
1. crossbow 100
2. flushtime 50
eagle37 50
4. ddszolo 40
5. jacob007 15
6. plant 0
yjy2410578007 0
isjk 0
merry05
crossbow为冠军,享有下次命题权,若放弃,则接下来名次的行使命题权
-----------------------------------------------
评测详情:
crossbow
Compile Successful!
Test case 0: Accepted, 0 ms
Test case 1: Accepted, 0 ms
Test case 2: Accepted, 0 ms
Test case 3: Accepted, 0 ms
Test case 4: Accepted, 0 ms
Test case 5: Accepted, 0 ms
Test case 6: Accepted, 0 ms
Test case 7: Accepted, 0 ms
Test case 8: Accepted, 0 ms
Test case 9: Accepted, 0 ms
总分:100
---------------------------
plant
Compile Error
添加#include<stdio.h>以后(-5)
Test case 0: Time Limit Exceeded
Test case 1: Time Limit Exceeded
Test case 2: Time Limit Exceeded
总分:0
----------------------------------
ddszolo
Compile Successful!
Test case 0: Wrong Answer
Test case 1: Accepted, 0 ms
Test case 2: Accepted, 0 ms
Test case 3: Accepted, 0 ms
Test case 4: Accepted, 0 ms
Test case 5: Wrong Answer
Test case 6: Wrong Answer
Test case 7: Wrong Answer
Test case 8: Wrong Answer
Test case 9: Wrong Answer
总分:40
---------------------------
merry05弃权
---------------------------
yjy2410578007
Compile Error
F:\Temp\ACM\code.cpp: In function `int main()':
F:\Temp\ACM\code.cpp:16: error: `ultoa' undeclared (first use this function)
ultoa这个错误无法修正,因此保持Compile Error
总分:0
---------------------------
jacob007
修改void main()(-5)
Compile Successful!
Test case 0: Accepted, 0 ms
Test case 1: Accepted, 109 ms
Test case 2: Time Limit Exceeded
Test case 3: Time Limit Exceeded
Test case 4: Time Limit Exceeded
总分:15
--------------------------------
isjk
修改cin至std::cin(-5)
Compile Successful!
Test case 0: Wrong Answer
Test case 1: Wrong Answer
Test case 2: Wrong Answer
Test case 3: Wrong Answer
Test case 4: Wrong Answer
Test case 5: Wrong Answer
Test case 6: Wrong Answer
Test case 7: Wrong Answer
Test case 8: Wrong Answer
Test case 9: Wrong Answer
总分:0
-------------------------
flushtime
Compile Successful!
Test case 0: Accepted, 31 ms
Test case 1: Accepted, 0 ms
Test case 2: Accepted, 15 ms
Test case 3: Accepted, 93 ms
Test case 4: Accepted, 78 ms
Test case 5: Time Limit Exceeded
Test case 6: Time Limit Exceeded
Test case 7: Time Limit Exceeded
Test case 8: Time Limit Exceeded
Test case 9: Time Limit Exceeded
总分:50
--------------------------------
eagle37
Compile Successful!
Test case 0: Accepted, 0 ms
Test case 1: Wrong Answer
Test case 2: Wrong Answer
Test case 3: Accepted, 0 ms
Test case 4: Wrong Answer
Test case 5: Accepted, 15 ms
Test case 6: Accepted, 0 ms
Test case 7: Wrong Answer
Test case 8: Accepted, 0 ms
Test case 9: Wrong Answer
总分:50
回复列表 (共19个回复)
沙发
FancyMouse [专家分:13680] 发布于 2007-08-25 20:33:00
总结一下算法方面。新手们以为这个是1+2+...+n,但是事实上最后一步合并就需要这么多的体力,所以显然不是这个答案
正确的模型是Huffman Tree,用O(n^2)的算法可以过n<=5000的数据,O(n*log(n))可以过n<=50000,有朋友想到了这点
当然,n<=500000000,即使是线性算法也无能为力。此时需要分析在合并苹果时,苹果堆的苹果数的规律。总而言之,能够做到O(sqrt(n))或者O(log(n))的均能ac
板凳
crossbow [专家分:150] 发布于 2007-08-25 21:14:00
问你的分析方法……我是列了前20个数作了3阶差分之后找的规律……
3 楼
FancyMouse [专家分:13680] 发布于 2007-08-25 21:18:00
找规律咯。我的做法是1,2,3...n -> 一个公差为3的等差数列 + 一个不和谐项 -> 一个公差为9的等差数列 + 一个不和谐项。。。
每一步大概都是数列长度是上一步1/3,算"->"导致的体力可以在O(1)内算出,于是ok
注意到第二步开始总是保持一个前面的数成等差数列,最后一个数不和谐的话,写代码会方便许多
4 楼
crossbow [专家分:150] 发布于 2007-08-25 23:45:00
[quote]找规律咯。我的做法是1,2,3...n -> 一个公差为3的等差数列 + 一个不和谐项 -> 一个公差为9的等差数列 + 一个不和谐项。。。
每一步大概都是数列长度是上一步1/3,算"->"导致的体力可以在O(1)内算出,于是ok
注意到第二步开始总是保持一个前面的数成等差数列,最后一个数不和谐的话,写代码会方便许多[/quote]
你的本质上应该和我是一样的了,三阶差分之后序列就变成了
3,4,4,4,5,5,5,5,5,5,12个6,24个7,...
但是理论上来说这个不算什么正确的做法……或者叫做没证明算法是对的……如果能直接推导出来...
5 楼
FancyMouse [专家分:13680] 发布于 2007-08-25 23:52:00
我证明过的,第一个箭头成立,然后后面必定是:挑两个小的,加起来以后得到的一个数比最大的大,也就是说就像个队列一样出两个进一个。嘛,归纳法还是挺好证的
6 楼
FancyMouse [专家分:13680] 发布于 2007-08-26 00:14:00
(eastcowboy)
没有找到O(n)的算法。
基本思想是:越是数目大的堆,就越应该尽量减少操作的次数。因此在不考虑效率的情况下可创建huffman树来解决:把1到n这n个数组成huffman树,每个叶子结点到根的长度乘以叶子本身的数值,最后相加即可。这样做的时间复杂度为O(n*log(n))。
因为是n个连续的数,所以具有某些特殊的特性。当取n为合适的数值时可发现以下规律:最底层的总是连续的两个数3k-2, 3k-1,组合后得到6k-3,这个6k-3会与另一个6k-3组合得到12k-6,然后得到24k-12,然后48k-24,...。直到这个表达式超过n,才不再有这个规律。
利用下面的方法可找出所有不满足规律的结点:
如果某数为6k-3,(如果6k-3小于等于n,则应该不断的乘以2,直到大于n为止),这个值就是例外。如此可知大约1/6的数据是例外,对例外的结点建立huffman树,并计算每一结点所在的层数。
利用找到的规律和已经产生的huffman树,可以想象出整个huffman树的全貌(但不必建立之),只要求出每一个叶子结点到根结点的距离就可以了。
求距离的思路:如果值为k的叶子结点到根的距离为x,k+1的叶子结点到根的距离为y,则根据huffman树的性质有x>=y。也就是说,“叶子结点到根结点的距离”这个函数是阶梯状的,只要找到每级阶梯的起止位置,即可计算所求值。
看起来太复杂,程序写了较长时间也没成功。不知道如何才是简单高效的方法呢?
--------------------------------------------------------------------------
你的意思是打乱原来的贪心算法确立的计算顺序?
7 楼
eagle37 [专家分:40] 发布于 2007-08-26 08:27:00
我认为还有更简单的计算方法:
只要找到满足以下条件的一个数m:
1.m〈n
2.如果m=1(mod3)时2m+1〉n/2
如果m=2(mod3)时淘汰。
如果m=0(mod3)时2m>n/2
3.在合并m堆时,剩下的堆数为2^t堆
则消耗的总体力为Am+(n+1)n/2*t;其中Am表示在合并到第m堆时消耗的体力
时间复杂度:
找到m实际上不需要太多时间:log(n)
根据前面几楼的规律计算Am其实很简单:O(1)
所以总体时间:log(n)
能否劳驾楼主将我的程序中没通过的数说一下,我检查一下程序的漏洞。先谢了
8 楼
eastcowboy [专家分:25370] 发布于 2007-08-26 08:39:00
上面那个方法不管怎么说还是O(n*log(n))的啦,只是系数会小点。要过500000000的规模的话是不可能的。还需要找更多的规律啊。
P.S. 我运行了一下crossbow的那个程序,发现输入0的时候输出-3。看来还得稍稍改改。
9 楼
FancyMouse [专家分:13680] 发布于 2007-08-26 09:43:00
@eagle37
你可以用朴素算法来为1~1000000内的数据进行检验
@eastcowboy
题目中说了输入的是正整数,所以不考虑输入0的情况
10 楼
zhangc511 [专家分:310] 发布于 2007-08-26 09:46:00
[em20]希望每届冠军,能够辛苦点,把自己的算法思想写出来,最好再把程序注释下,让我们后辈能够多学点。
我来回复