IEEE极限编程, 从周六早上八点(UTC 0点)一直到周日早上八点结束, 每小时都会放出新题目. 第一次打这种比赛, 属实难顶.
Day 0
星期五上午体育课体测跑一千米, 一年没锻炼的我居然只比去年慢了十秒钟, 不过四分四十秒还是没及格, 而且跑完之后跟死了一样, 课上第一批跑的等到下课半个小时才从网球场的椅子上站起来一步一步挪回宿舍, 下午还发烧了. 晚上又累又困十一点多就睡了.
Day 1
早上六点五十起床, 收拾收拾磨蹭磨蹭吃点饭正好八点零一到lyf老师的电工实验室. 队友还没来, 我先开了电脑看了下题, 发现前五分钟只有个神必环境测试题, 让我随便输出一个东西, 输出啥都是0分.
五分钟结束后放了个三道题. 一个傻逼签到题, 随便打打交了就过了. 然后一个计算几何和一个大模拟. 队友们来了, 我给他们解释一下计算几何的题意, 就去写大模拟了. 傻逼计算几何用的支持向量机当的背景, 要我们做一个线性分类: 给我们平面上两种点, 问能不能用一条经过原点的直线给他们分开. zirrtu没看到要经过原点, 直接上python交机器学习, 折腾了半天没过一个点. 我大模拟打了一小部分, 测了一下样例发现我连有效单词数都没统计对, 应该是题目读错了, 但是没找到问题在哪, 就直接去支援计算几何了.
机器学习失败被迫想正统做法, 但是没人学过计算几何的我们很容易就会想到一些很高深的计算几何算法. 三个人往凸包上搞了半天, 交了几发都是0分. 比赛开始两小时, 第四题放出来了, 一个图论题, 但是我们没去看. 我继续钻研计算几何, 发现根本不用什么凸包, 直接把每个点极角搞出来然后瞎搞搞就可以了. 给他们讲了一下, 他们也觉得毫无破绽, 然后我们准备去吃饭了. 临走之前看了一下第四题, 就是给一个无向图, 每次查询两个点之间路径必须经过的点.
出去吃饭的时候我们开始嘴第四题的算法, 我们想两点之间任意一条路径上不在环上的点都是必须经过的点. 然后好像是先做一个生成树, 然后枚举每个非树边, 这样就能找到所有的环, 用树剖可以标记这个环上的所有点, 然后查询两个点之间不在环上的点就行了. 后来忘了为什么弃用了这个算法, 找到了一个无向图缩环的模板. 吃完饭hx去打这题, 我开始打我嘴的计算几何. hx打着打着发现不对劲, 因为如果一个点在环内, 根据他在环内的位置, 会有不同个数的环和外界的联通点是必须经过的点, 而如果缩了环, 就无法得知这个点在环中的位置. 这题就这样放弃了.
然后我就开始了我长达几小时的计算几何自闭时间. 吃饭的时候放了一个水题, 他俩直接给过了. 我嘴的计算几何方法实现很麻烦, 而且一点点小的精度误差都会导致答案错误.
打了几小时,最多的也只是过了20%的点. 开始去看4小时放的一个构造题. 看了五分钟直接嘴了一个构造, 跟队友讲了一下也觉得天衣无缝. 交上去0分.
然后队友过来看, 找到了问题. 接着我又想了一个构造, 打了出来, 样例都过不去.
又自闭了. 回去继续计算几何. 自闭了一下午,毫无输出. 有人搬了一箱红牛和一堆水果进来了.
干啥啥不行,吃饭第一名. 五六点我就带着队友们买东西, 买了点面包,糖,咖啡和一包蒟蒻果冻. 然后就回去继续肝了. 过了一会hx发现我的第一个构造会只会在大于N/2列出事, 他把前N/2列的构造方法镜像到后N/2列, 然后又构造了一个方法填上了中间两列的空隙, 给我们讲了一下觉得毫无问题. 敲了一遍交了果然过了. 这时候发现又多了个水题, zirrtu已经给过了. 还打了几个暴力.
到了晚上, 我完全失去了战斗力. 出了一个奇怪的感觉是解方程的问题, 我用了个奇怪的线性规划, 打了个假到不能再假的暴力, 居然过了75分, 赛后发现这题75分还是高分, 只能说运气好.
出了一个更奇怪的题目, 给了一段Brain Fuck代码, 什么也没说, 有种CTF的感觉. 其实刚看到这个题目名字我就觉得不太对劲, 题目名字Furin Back, 正好是Brain Fuck的一个排列, 一打开果然就是一段Brain Fuck的代码, 还有一个奇怪的看起来像蛋白质结构的图. 题面只有一个代码, 我甚至怀疑是不是图片隐写, 这个图片里是不是藏了什么东西, 下下来binwalk了一下没找到什么, 就放弃了. 最后找了个BF解释器, 随随便便优化了一下, 就拿了个暴力分跑路了.
Day2
zirrtu跑路了, 后半夜我也完全没输出. 从十点到第二天四五点我都是划水状态, 也没怎么睡, 就读读题, 拍拍创佬黑照, 出去看看西电的夜景顺便发个说说, 附和一下hx的想法说没问题. 后半夜全靠hx, 一个人感觉做了有四五题, 太强了.
zirrtu还不起, 给他打了几个电话也没用. 六点多他起了, 让他继续去改改计算几何. 我做了个傻逼题. 计算几何最后也没有改对太多, 不过差不多就行了, 那题属实恶心.
最后一小时, 是个字符串题, 我想到了一个很对的算法, 但是交上去总是T一半. 结束后发现创佬跟我一样的做法, 他就A了. 然后发现string的有个地方用的不对, 导致复杂度不对了, 以后还是自己写哈希吧.
八点结束了, 去做分光计物理实验. 这是这期实验的最后一次实验, 所以一个教室只有八个人. 那个老师让我们不用调实验仪器, 直接大概做一下就行了, 然后当场把报告交了. 我头有点发热, 但是很精神, 可能是回光返照. 但是这样我还是做不出来实验现象, 无奈最后只能编数据. 事后才知道这个实验不调仪器根本不可能做出来实验现象.
做完实验中午吃个饭, 下午睡了一下午, 没事了, 结束了奇妙的极限编程+物理实验之旅.