北京工业大学程序设计竞赛集训队一群有梦想的年轻人希望能在萌新的带领下走向人生巅峰

地址

OpenJudge – BJUT ACM(已结束)

体会

这是我自高一OI退役以后所参加的第一场算法竞赛。题目总共八道,送分的水题占了一半,考验选手能力的题目只有 C(单向链表的去重函数补写)、D(最大子段和)、E(平衡游戏,欧拉回路问题,HDU5882)、G(邻接表问题)。不过相较于 NOIP 复赛和省选而言,这几道题目的难度是远远没有达到的,不仅没有对多种算法、数据结构与数论的要求,也没有削弱题目结构的特点以模糊解题方向。

很惭愧,告别算法竞赛这么久,几乎完全忘记了之前所学的内容,以至于只完成了水题和平衡游戏。在 C 题的算法实现过程中,由于没有充分考虑到连续的重复元素输入,导致了去重不充分的情况出现。同时由于在 for 循环中大量使用break;以致于破坏了内存结构,并且没有在删除节点后进行 free 操作,导致了内存分配不合理。在 D 题的算法实现过程中,没有仔细读题而误解了命题人的用意,错误的将区间由硬币输入序理解为硬币价格序。对于 G 题,没有彻悟题意并简化模型,而是采用的暴力的方式,最终收获了 TLE、CE。

赛后经过与 licw 的讨论,终于明白了此题的神秘。根据题面,“定义:如果一个队伍里面,可以找到三个人,这三个人任意两两相互认识,或者任意两两相互不认识,那么这个队伍是缺乏创新力的;否则,这个队伍是富于创新力的。”假设我们现在有用户{a,b,c,...},那么对于用户a来说,剩下的人可以被分成“与A相识”和“与A不识”两个部分。由于鸽巢定理,我们易知,当n >= 6时,人群中至少存在三人且三个人任意两两相互认识或者任意两两相互不识。即对于任意n >= 6的情况,都是
Uncreative 的。所以我们只需要对n <= 6的情况进行判断即可。

CC BY-SA 4.0 北京工业大学程序设计竞赛集训队一群有梦想的年轻人希望能在萌新的带领下走向人生巅峰 by 小小泥娃 is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

发表评论

This site uses Akismet to reduce spam. Learn how your comment data is processed.