好吧,我还是回来了,竞赛结束后也没怎么碰那个unnamed.space了,现在早就已经过期了。同样的几个月没有碰OI了,手明显生疏很多,毕业了重新搞搞OI吧,想必落下了很多。
高考考得很渣,不过很荣幸自主招生进了电子科技大学某郫县男子技校,于是去他们的OJ上围观了一下,随便做几题玩玩。
嘛,嘛,不提了,我来讲讲CDOJ 3的大致做法,很明显的追及问题,因为数据很小,(O(n))暴力可过,然而推公式的话,也是有(O(1))的做法的。
这里我没有用暴力(我是做完后对拍才到网上搜到的暴力做法……),一开始就推导公式了。
因为题目说是kennethsnow看的时间,而且看样例数据可以得出来,一开始的T是不计入最后结果的,一开始没注意到被坑了。
首先考虑简单的情况,在(X<Y)和(TY>S)的时候结果是显而易见的,直接输出(frac{S}{X})就是答案。
我们知道一开始的T时间加载了(TY)的数据——至此我称其为第0阶段。
第1次播放完将耗时(TY imesfrac{1}{X-Y}),这个时候又会加载完毕(TY imesfrac{X}{X-Y})的数据——我称之为第1阶段
第2次播放完将耗时(TY imesfrac{X}{(X-Y)^2}),这个时候又会加载完毕(TY imesfrac{X^2}{(X-Y)^2})的数据——我称之为第2阶段
……同理,看得出播放耗时和已加载视频都是等比数列
第n次播放完将耗时[TY imesfrac{X^{n-1}}{(X-Y)^n}],如果这个时间(>S/X),意味着这第n次已经加载完了整个视频,则第n段的耗时就是(S/X)
又上面的不等式得[TY imesfrac{X^{n-1}}{(X-Y)^n}>frac{S}{X}]
解得[n=leftlceillog_{X/(X-Y)}frac{S}{TY} ight ceil]
根据等比数列求和公式,总用时[egin{align*}sum&=frac{TY}{X-Y} imesfrac{left(frac{X}{X-Y} ight)^{n-1}-1}{frac{X}{X-Y}-1}+frac{S}{X}\&\&=frac{TY}{X-Y} imesfrac{left(frac{X}{X-Y} ight)^{n-1}-1}{frac{Y}{X-Y}}+frac{S}{X}\&\&=Tleft[left(frac{X}{X-Y} ight)^{n-1}-1 ight]+frac{S}{X}end{align*}]
……博客园的数学公式真难看
这个时候答案已经得出来了,最后只需要把它变成代码即可(咦,我怎么记得我已经在博客园上传了SyntaxHighlighter来着,怎么文件都不见了)。建议呢还是自己打一遍,因为解题的所有思路都在上面了嘛。
1 #include <cstdio> 2 #include <cmath> 3 using namespace std; 4 5 int T; 6 double x, y, t, s; 7 double time; 8 int n; 9 10 int main() { 11 scanf("%d", &T); 12 for (int kase = 1; kase <= T; ++kase) { 13 printf("Case #%d: ", kase); 14 scanf("%lf%lf%lf%lf", &x, &y, &t, &s); 15 if (x > y && t * y < s) { 16 n = ceil(log(s / (y * t)) / log(x / (x - y))); 17 time = t * (pow(x / (x - y), n - 1) - 1) + s / x; 18 printf("%.3lf ", time); 19 } else printf("%.3lf ", s / x); 20 } 21 return 0; 22 }