交大ACM队机试结束
题目很恶心,7水+2难.结果就是N多人都是7道题,7道题主流啊…qujun这种做了7道题结果因为全场最水的G题看错题而排名靠后的就悲剧了…
A题,给出C个字母,要求输出由这些字母所有满足下列条件的字符串:所有字母升序排列,每个字母只用一次,长度为L(L<=15),单词里至少有一个元音两个辅音.
这道题因为刚开始状态不太好卡了一会儿,不过最后还是比较顺利的搞出来了.
B题,给一个01矩阵,问有几个连通块(只有上下左右连通才算).
简单的BFS.
C题,给一个5*5的数字矩阵,从任意一点开始每一次向上下左右的任意一个方向走一步,可以走重复的格子,经过6个格子之后会得到一个六位数.问总共可能得到多少个不同的六位数.
纯搜索.
D题,题目描述比较恶心,反正就是给你一堆矩形叠在一起的影子,问最少多少个矩形能够叠出这样的影子.所有矩形都是放在地面上的.
用链表维护一下就行,题目稍微长一些,但是很简单.第一次写写错了,写的算法和想的算法不是一个…走神了啊.不过还好,后来改对了.
E题,有N头牛,每头牛都有一个强壮指数和重量.现在把它们按照某个顺序叠起来,每头牛计算一个上面所有牛的重量之和(不包括自己)减去它的强壮指数,问如何所有牛的这个值的最大值尽量小,输出这个最小的最大值.
刚开始还以为是二分答案,后来想到了贪心是把重量和强壮指数加起来,大的放在底下,但是没法证明,第一次submit还错了.后来发现第一头牛的这个值应该是负的自己的强壮指数,改了再交就过了.但是没完整地证明出来(只证明了三头牛是正确的).
F题,给定函数f(a),计算方法是:把a的最后一位挪到第一位前面,然后平方,再把结果的第一位挪到最后一位后面.问第N个满足条件f(a)=a^2的a是多少.
写个暴力找下规律,就可以发现是1,2,3,21,221,2221,22221…于是直接输出就可以了.
G题,全场最水的一道题.就是给定N个点,两个点之间有个某某概率为1/sqrt((x1-x2)^2+(y1-y2)^2+(z1-z2)^2+1),问最后一个点和前面所有点分别算这个概率,最大的一个概率是多少.
只需要把最后一个点和前面所有点的概率分别算出来然后找个最大的就行了…很可惜,因为是个人赛,所以没办法刚开始就看完所有题…基本上每个人都是最后才做出这道题的.还有很多看错题,求了所有点对之间的…那些人很悲剧…
然后是两道不可做题.
H题,要求求出一个序列{a_n},满足sigma(i=1~n)a_i=x,sigma(i=1~n)a_i^p=y,而且sigma(i=1~n)a_i^q尽量小.输出这个最小值.
数论题,我是直接放掉了…
G题,给一个有向无环图,给四个点abcd,四个点的编号都不同,从a到c和从b到d可以找到一对不相交路径(就是没有公共点),问这样的路径对有多少种.
这道题写了个暴力交上去,然后眼睁睁的看着前面的judge拿我的程序跑,大概在第三个点TLE了…然后给我return了一个TLE…于是就再也没想出来…
大概就是这样,题还是很水的了.最后排在所有人的第13名,比笔试退后了两名…不过据说这次又会有N多人晋级面试,唉…
就要是大学生了吗…
前几天终于到了交大, 乱七八糟地也算是过了一个礼拜. 总体感觉还是很爽的.
Z41到上海, 然后听从 HL 的话一号线转五号线, 大约一个多小时就到了 SJTU.
坐地铁的时候遇到了唯一一次服务态度极其差的情况… ft, 上海人还是很不错的, 并不想所说的那样对外地人很 bs…
然后拿书办卡, 还算挺顺利, 办卡的时候相片照的太难看了…
接下来是分宿舍, 和吴培峰, 傅一波还有强瑞鑫一起分到了 5L, 于是要把一堆大包小包的东西都搬上去… 累的也算够呛. 然后中午 12 点的时候屋里另外三个人也没有来, 只好先去吃饭.
吃 饭的时候叫上了 HL, 去二食堂二楼… 貌似是一个新疆馆, 所以也没吃出来饭和北方有啥太大的不同. 唯一不适应的就是米饭很硬, 而且一粒一粒的, 不过吃了几天也就好了. 还有, 这几天我才发现, 上海的饭真的有很多是甜口的, 不过很合我的胃口. 价格也不是太贵, 总体来说伙食很不错的.
宿舍里面各种东西也很齐全, 除了只能洗凉水澡, 别的基本完美了.
对了, 上海这里早晨的天气是很凉的, 但是到10点左右的时候就很热了, 而且要一直持续到半夜… 于是如果盖被子睡觉就会热到, 不盖就会冻到, 比较烦人的事情.
课上了五节, 周四第一节英语因为老师迟到所以在语音教室坐了一节课, 第二节英语扯了一节课… 然后周五的三节数学更是连扯三节课… 预习了 6 节完全没有派上用场啊…
同学们之间说话还是没什么大问题的, 不过 wpf 和 fyb 两个浙江人要是说起话来我可就听不懂了… 不过他们貌似还可以听懂大部分天津话的, at…
还有, 南方人打牌似乎都是两副牌… 我那天拿出一副牌说, “我这儿有一副牌, 咱们打牌吧”, 然后 wpf 和 fyb 疑惑地问我, “一副牌怎么打啊…” 嗯不过这几天过得很好玩哇.
自行车可以租, 但是没有租过… 校园其实也不是太大, 走着稍微累一些而已.
嗯别的事情也没什么了, 换了个手机, 号码是 (见校内), 原先的号码不用了…
能上网就方便了, 有啥事想起来再写好咯…
ACM/ICPC World Final 2009 结束
真的好久没有更新了呢, 快一个月了吧.
这篇 blog 只说刚刚结束的 WF 的事情, 不会很长, 别的我要是不困再写一篇.
知道今天有 WF 也是下午回家之后的事, 然后立刻开 ranking 观战. 这时有人发来一个视频直播的链接, 打开看了, 很卡加上半懂不懂的英语解说, 我获得的信息基本还是来自 ranking 的.
当时一直关注着 SJTU 的尴尬的 2 题, 然后就发现 tsinghua 在前面也停滞不前了. 接下来就是眼睁睁的看着 tsinghua 被一次次的赶超.
然后 tsinghua 貌似出了一题, 但是很快就发现 ZJU 赶了上来… 这时 TJU 都跑到了 SJTU 的前面, 真的很尴尬. 直到 FROZEN 的时候, ZJU 是 rank 5, TSU 是 rank 6, 而 TJU 和 SJTU 都是 3 题 (似乎快封板了才搞出一题?), 排在好几十名, TJU 貌似更靠前.
然后 FROZEN, 接下来就是一边看亚冠一边期待…
刚刚看完亚冠回来的时候, 群里对比赛结果有 N 种说法… 最后在饮水思源上看到了 JinBin 的发言, 基本确定了 tsinghua 最后是第二, 似乎是最后时刻爆发了, 做出了9题 (封板的时候第一名是8题, 第二名6题, tsinghua 是第6), 不过还是因为罚时只拿到了第二… ACRush 教主竟然拿了两个第二, 真的不知道说什么好… 听说楼教主当时哭了, 其实我也想哭了…
可能记得不是很清楚, 有不对的地方, 但大致的进程就是这样…
ICPC 真的很刺激… 终于又一次发现了它的魅力… 团队协作的比赛, 还是比 TC 那种单打独斗更加令人痴迷, 令人陶醉.
就是这样. 最终圣彼得堡的一个什么学院拿了第一, 清华第二, 圣彼得堡大学第三. 浙大拿到了第六, 赞一个. 而交大最后是并列第13, 很无奈.
Everything is New
友情提示: 本文没有任何实用价值, 请自行决定是否观看本文, 或者直接拉到最后 (不过估计我写不了几行).
虽然说就要进大学了, 但是还没有个新的面貌啊.
Blog 已经两周一次更新了, 足以体现现在我有多么懒. 整天玩游戏, 上校内, 切题, 过得毫无感觉.
Boss 那儿给了不到 20 道二分图匹配的题, 竟然前两道题都没有 1Y, 我真弱智.
嗯还是说正题吧. 开始为 ACM 做准备了. 虽然听说了 SJTU 的 ACM 队很难进, 不过还是有一些憧憬的. 毕竟大一的同学里只有这些 OIer 在竞争, 虽然个个都是高手, 不过自己也不能就这么放弃.
然后呢, 现在很无聊, 于是想为以后的 ACM 准备个用户名. 主要是在各个 OJ 上的 sqybi 的刷题记录没办法清除, 所以换个用户好知道自己哪道题还没做过… 毕竟以前做的题现在不一定还会了.
现在在用 sqybicpp, 看着就难看. 所以自己准备了一些用户名, 欢迎留言告诉我哪个好, 或者有更好的创意也请告诉我…
ssjqtyu – sSjQtYu
sqeezey – SQeezeY
saqcym – SaQcYm
crapixo – cRaPiXo -> RPX -> (R+1)(P+1)(X+1) -> SQY
sterizy – sTeRiZy -> TRZ -> (T-1)(R-1)(Z-1) -> SQY
后面是解释.. 基本就围绕着 sqy, sjtu 和 acm. 貌似 crapixo 还比较好看… ssjqtyu 那个就很难看…
另外, 最近做题要顺手整理代码了, zmc 给我的那份代码库简直太强大了… 不过还是自己整理的代码用着舒服.
武汉大学百度杯比赛惨败
为了方便搜索引擎, 列出全名:
百度杯 第四节华中北区程序设计邀请赛
The 4th Baidu Cup Central China Invitational Programming Contest
比赛也算是比较圆满的结束了 (如果不考虑比赛过程中不断的 HTTP 503 / 500 的话), 挂的也是够惨.
据说除了校内队伍取 40 支, 然后我们总排名第 54. 还有一丝希望晋级吧. 已经被淘汰了. 也好, 轻松了.
不想再发泄什么因为我晚到半小时导致比赛结束 10 min 才出 I 题的事情… 昨天发泄够了也在校内被 bs 够了. 当然当时没 bs 够的还可以接着来这篇文章底下留言 bs… 我现在心情至少比那时候好.
正式比赛里, gnocuil 牛领衔的 E.W.F. 队没有如愿拿到第一, 第一被 jby 神牛的 Gold Kylin 抢去了… 第三竟然是 cqf 神牛, 不知道做题的时候神牛有没有用到 SBT 呢… 第四不认识, 第五是 xt 神牛, 果然中学队伍比较强大.
然后强力的 wh 拿到了第 16, orz一个. 啊, 忘了说, 然牛貌似是第 12 啊. And, rank 13 是姜里羊神牛. 能认出来的貌似就这些.
比赛刚开始, 我就迟到了… 等我到的时候, 比赛已经开始了半小时, 貌似有很多队伍都出两三道题了. 而 zmc 也过掉了 G (似乎是水题, 我没看题).
到了之后我就鬼使神差地开始写 E (一个不是太恶心的枚举), 还鬼使神差的读错题了. 于是贡献了 4 个 WA 以后才 A 掉, 这也就导致我们在出 4 题 5 题的时候, 排名一直是最靠后的.
在我 submit E 的同时, zmc 也在做 J (据说是弱智DP). 然后我在 E 多次 submit 都 WA 的情况下, 最终开始搞 H (纯水题, 排序), 在使用了大量 STL 的情况下 (map, set, vector, pair, algorithm, 基本上 1/2 的程序行都有这些东西), 终于 2Y 掉. 而在 Y 掉 H 之前, zmc 和 Nxun 找到了 E 的问题, 就是读题读错了 (关于该黑棋还是白棋走的问题). 于是 E 题也过掉. 紧接着, zmc 也过掉了 J.
然后, Nxun 就开始折腾那道不太该折腾的题, F (根据化学式计算相对分子质量, 需要高精度). 这道题直到最后也没搞对, 最终确定是高精度写错了. 而我正好发现了 D 题 (Cipher 加密法) 是我曾经给 FNOI 的小朋友们出过的一道题 (瀑布汗! 我当时出的是解密, 这里要求加密), 于是赶快写, 1Y 掉. 这道题本该早写的, 但是当时看 AC 人数比较少所以都没看题…
接下来的时间就是每人一道题慢慢磨的时间了, zmc 是 C (恶心计算几何貌似?), Nxun 还是 F, 而我是 I (SCDP). 最终三道题一道也没出, 比赛结束 10min 后搞出了 I. 错的原因也在校内说过了, 数组开小了 1. Shoot.
这次败得够惨, 顺便膜拜搞出 A (双向宽搜) 的牛们.
顺便提一句, TCO Round 1 我就被淘汰了, 最近状态 ttm 差了…