R·ex / Zeng


音游狗、安全狗、攻城狮、业余设计师、段子手、苦学日语的少年。 MUGer, hacker, developer, amateur UI designer, punster, Japanese learner.

培训第五天

注意:本文发布于 3840 天前,文章中的一些内容可能已经过时。

昨天的日志居然断开了!算了,从今天开始写吧。

其实过了五天之后,感觉每天过的都很有规律——早上6:30起床,吃完早饭后考试,中午吃完饭后休息,然后下午早早地去报告厅占位置,然后听神牛们讲一下午课,晚饭后去物理实验室充电,然后洗澡睡觉。所以生活已经没什么可写的了,那就写写今天的四道题吧!

第一题

这道题就是求一个连续的子段和,使得这个和小于总和,并且尽量的大。考试时我用了两重循环+强力剪枝,但最后还是只过了6个点。真正的算法是弄一个前缀和,然后枚举左端节点,二分查找右端节点,于是就被O(nlogn)秒过了,不过改过之后第3、4两点始终过不了,这也算是一个杯具吧。

第二题

题目意思是统计长度为4的上升子序列的个数,乍看像排列组合问题,鉴于组合数学我没学过所以直接用了4个for循环暴力枚举完事。后来ToJaRa和Jack想出了个很表被动的递推算法,于是他们一给我讲我就明白了,然后几分钟代码就出来了……还有要注意的是,统计的变量及数组都要开成int64级别,否则会215错误。

第三题

此题一看数据范围我就放心了,n≤15,m≤25,怎么搞也不会超时啊,于是用了个暴力DFS无压力秒过。据说集训班的人看到这套题,都在讨论前两题的算法,但一到第三题就说,这是什么大水题啊!

第四题

此题我不会做,于是TLE了,但是据说Skq去年模拟赛上有这道题,于是我要好好把那一堆套题看一下。


下午是QQ神牛讲课,果然比前几任神牛讲得好,现场气氛也很活跃,不愧是神牛啊。

Orz Zyh神牛!初中的学生居然在有一道题没提交的情况下得了300分!我提交了4道结果200分,改完后也才280分。这就是差距啊,还好我们不是一级的,否则太恐怖了。

明天还是QQ神牛讲课,争取全部听懂!

版权声明:除文章开头有特殊声明的情况外,所有文章均可在遵从 CC BY 4.0 协议的情况下转载。
上一篇: 培训第三天
下一篇: 培训第六天

这是我们共同度过的

第 2253 天