回 帖 发 新 帖 刷新版面

主题:第75次编程比赛结果

我感觉这次比赛出得很烂,人烂题目更烂,才导致参加的人这么少。
    我就先说下出这道题目的过程中的一些想法,明天在宣布由谁来主持下场比赛。
    题目最先的原型来自一道叫做dota651里面补刀的一道题目,就是根据一些数据,求出能补刀补上的时机,该题目我想到的解法是2分,但是代码写上之后提交,果然WA了。
    我就打算出个2分的题目,这道题的最先版本是没有周期和下限的。我一想,太简单了。于是把周期之类啥的能加的都加上,尽量让它看上去很牛逼,当时也没有细想,粗略的想了一下nlogn应该能出结果吧,所以最先的数据量是50万,汗。
    后来我又仔细的想了很久,但是终于我败了...想来想去只有暴力才是王道。
忽然发现某o(N)算法其实是错的。。。。期待版主把她的o(N)算法写出来。
    说到枚举,我想到一个比现在这个稍微好点的方法。。。就是不用每个时间点去试探,只是需要减少的时候才去减,时间复杂度可以降到O(T*log(n)),T = sum((Ai-Di)/Ci),如果Ci为1,而差平均为K,那么复杂度就是O(K*n*log(n))。



下次比赛就由mht@来主持吧,我再给你加了点,你分最多,我相信你。




回复列表 (共7个回复)

沙发

顶一下LZ. 

其实我倒是觉得题目挺有意思的. 可惜比赛时间是周一到周五. 一般比赛都会持续一周或以上,至少会把双休日包含进去.大概这是人少的原因之一吧.

潜水很久,但一直常来逛. 这里挺好玩的.

板凳

刚开始看到是 Ti 小于7 于是就来了个暴力破解,后来看看又改了

听到别人说可以有t(n)的,俺是苦思冥想也没想出来。

哎~~,算法基础差啊!

3 楼

neverPE大牛出现了~

根本没时间做,电子竞赛+校运会+没有双休~

题目看到女朋友三个字就软绵绵的了,呜呜呜呜~

4 楼

怎么才看到 就发现已经结束了啊 
应该双休日放里面的 时间会多一点……
我想知道那个“dota651里面补刀”的题目在哪 感兴趣…… 呵呵

5 楼

就是解线性方程,若非整数,就试验它最接近的两个整数
若越出当中某方程未知数的上界,那么把该方程直接设为其上界,然后重新解那个方程
最好情况下O(n),至于最坏有没有可能达到O(n^2),我就不清楚了

6 楼

dota补刀的题目最初是出在 电子科技大学的一次比赛里面,然后被复制到了acm.tju.edu.cn

7 楼

好吧!感觉还有点稀里糊涂呢。

  下个星期有考试,所以时间比较紧,初次参加也不知道出什么题

  就想着在其他地方挖点题吧

  我会尽快出题的

我来回复

您尚未登录,请登录后再回复。点此登录或注册