AHOI'14 游记

被虐翻了呢>.<

Day 0

早上7点不到就起来了,来到一中发现所有学生都站在广场排成队,于是就跟周围的同学闲扯了一会儿……(貌似安徽搞OI的还不少?感动)然后大概上百人就浩浩荡荡地上楼去机房了……

然后比赛就开始了……题目大概是这样地:

  • Porblem 0 : 给定s个高度一样的黑白格子染色的矩形,求一个排列使排列出来的矩形最大白色子矩形最大。(s <= 总面积 <= 10^5)

  • Problem 1 : 给定n (n <= 200)种食物,每种食物有保质期和价格,每次买食物要给f的快递费,每次可以买任意多食物。求有m元钱的情况下,每天吃一种不过期的食物最多可以吃多少天。

  • Problem 2 : n (n <= 10^5) 种怪兽,每种怪兽完全打死要K HP,但是花S HP可以把它转化成其他一些怪兽……求打死一只怪兽1所需要的最小体力。

看到题目就傻了……全部都是最优化题目 >_<

(看来要回家养猪了呢…… >_<)

先搞了t0矩形数 <= 3的暴力分,中间单调栈还搞了一会……然后感觉考虑每个矩形左右的极大全白矩形然后用某种方法merge可以再骗一点分,但是还是没有敢再想下去……

然后看了一眼t2,感觉好像很傻逼?建一棵dfs树然后有后向边直接输出K不就OK了?Flag 0然后20min搞完了开始推t1……

只需要推出来一个 F(t),表示活t天至少需要多少money。如果只快递一次,我们可以搞出来一个F_0(t),然后如果邮购1次的是F_1(t),那么显然就可以用前者的图像“更新”后者的图像,然后这么搞下去然后二分。

一直画呀画画呀画,哎呀比赛要结束了妈蛋!但是由于我画的太失败(论绘画功底重要性)根本看不出来什么,只能大概发现有个循环节,然后就写了个暴力找循环节骗了点分 >_<

然后比赛就结束了……看到第五大爷不停地微笑,眉宇间隐隐透露出一股进队爷的气质,嘴角里淡淡彰显着蔑视凡人的霸气,然后就看傻了……lz大爷表示毫无压力,真是吓出那啥了。怎么你们都这么强?!

比赛结束就回教室拿了一下书本,在教室还遇到了若干同学,聊了一会……发现马上下午的课要开始了赶快拉着Alexa跑出了学校。跟Alexa又聊了好一会,和Alexa在一起真是感动不已,路上遇到几个美女。

中间跟Alexa讨论了t2,我自信满满地告诉了他我的solution,他表示质疑,但是没有反驳。下午跟lz大爷聊天,然后就知道自己t2没分了。

淡淡的忧伤……早知道写暴力了。以后能写暴力就写暴力。嗯。

Day 1

其实还是有一点紧张的。因为这场比赛就决定了我能不能退役了。

Written on April 20, 2014