市选总结

刚参加完今年的信息学市队选拔(GZOI2012), 对成绩还算满意. 很可惜, 没进市队(高中前4), 参加省赛要给500块…

Day 1 5道题,  phonebook(30)+typeprint(50)+english(30)+guess(50)+snow(40)=200

第一题是电话本查找, 要用数字匹配姓名拼音/拼音首字母/电话号码, 输出所有符合的人. 人数30个, 不用什么复杂的匹配算法, 故属于水题.

第二题是老题”密码键盘”(“聪明的打字员”), 不过我以前没做过. 先写了BFS, 但发现队列会很快被挤满. 后来改成DFS+深度剪枝+优化, 速度还可以接受. 据同学看数据, 我都是0.02s或者0.03s过的, 比BFS快. 很可惜算法的优化其实有错误, 现场评测能AC是因为一个点的答案恰好也错了, 而那个点竟然值11分. 第二天同学交申请要求改答案重测, 我被打回原形…

第三题是把十位以内的整数翻译成英文, 试卷上给了详细的方法, 直接模拟. AC.

第四题”大话骰子”, n个人时猜, 要计算剩下5*(n-1)个骰子里有至少k个等于x的可能. 当然, 规则有些特别, x=1时概率取1/6, 其他要取1/3. 我没浪费时间想公式, 直接用递推式: p(t,k)=1/6*p(t-1,k-1)+5/6*p(t-1,k), 加上边界(k=0返回1.0, t<k返回0.0), 然后直接输出p(5*(n-1),k). AC. 不过这题还可以加个记忆化优化, 会更快.

第五题也是老题”滑雪”, 方格图最大50*50, 求最长路径. 一看到是做过的题, 我就忍不住搬出了自己摸索出来的算法”LPFA”(把SPFA反过来写), 对所有点入队一次(假设每个点都可能为出发点), 最后直接输出最长的距离. 很可惜, 算法的效率本来很ok的, 却被一个点卡了, 估计是个沿对角线单调倾斜的图(退化为标准的网状图, SPFA会被卡). 于是一个点超时了. 出来后被同学纷纷鄙视, 因为用最差的穷举效率也只有50^4, 绝对超不了…

第一天现场评测的结果是190分, 全场第一, 也让我飘飘然的. 后来被扣了11分变成179, 排第二.

Day 2 4道题, (?)(25)+sequence(25)+map(30)+gps(40)=120

第一题忘了…

第二题要对四个整数进行四则运算(除法只能整除), 得到所有结果后找到最长连续序列. 我用链表存某两个或多个整数运算后的所有结果(无序/未去重), 连成长链, 最后放进数组进行排序+去重+寻找序列. 反正就四个数, 内存再怎么样也不会耗太多. 不过最后不知出了啥问题, 有几个点出错. 应该不是因为数组开200000没开够.

第三题规则很像扫雷, 地图15*15. 我没想到好方法, 所以用的搜索加剪枝. 5*6的样例秒过, 6*9的也很快. 不过最后当然一大堆超时. 出来后同学说可以用贪心一个一个放雷, 他虽然没AC但只错了很少的点.

第四题要求在指定经过若干条边后使GPS搜索的最短路线等于给定路线, 要求输出最少指定的边数目. 我先用了Floyd, 然后记忆化搜索从a点到b点的最短路径, 但其实有严重漏洞: a->i, i->i+1, i+1->b各自都是最短路径的情况下, a->i->i+1>b也不一定会被选中. 不过最后还是过了一些数据点.

具体每题得分都不太记得了, 只知道没有题目全对, 也没有题目全错. 最后总分拿了67, 一般般.

 

 

最后算分公式很有趣, 个人得分=(NOIP2011成绩/当年广州最高分成绩=580)*30+(Day1成绩/当天最高分=188)*35+(Day2成绩/当天最高分=101)*35=73.35, 排在第6. 谁叫我NOIP成绩那么渣呢.
接下来是4月28日的省赛. 虽然没什么精力准备, 还是要努力考好的.

2012 年 04 月 04 日

OI, 竞赛

叽叽歪歪