当前位置:首页 >> 学科竞赛 >>

余林韵


APIO 2013 讲题大会 Tasksauthor
清华大学
余林韵

题目大意
? 给定两个问题的若干解法,要求选手出测试数据让这些解法部分超时
? 最短路径
? Modified Dijkstra

? Bellmanford
? Floyd

? 染色

问题
? Gamble

? Recursive Backtracking

得分情况(国内部分)
? 100分:唐翔昊 ? 99分:王康宁 ? 92分:郑宇凡

? 60-70:万诚等12人
? 50分及以上:共28人 ? 平均分:23.3分

选手讨论
? 如何思考这个问题 ? 对哪些测试点有特殊的想法

SSSP
? Floyd
? Counter=N^3 ? 101个点的图

? 空图即可
? F=1+101+1+2=105

SSSP
? Bellmanford
? Counter = Q*迭代次数(max=n-1)*m ? 迭代次数:最短路为一条逆序编号,长为n-1的链即需要迭代 n-1 次 ? Vs Floyd:
? 100个点,1050条边,10次询问 ? T=1+100+1050*2+1+20=2222 ? Counter=10*99*1050

? Vs dijkstra:
? 330个点,330条边,10次询问 ? T=1+330+330*2+1+20=1012 ? Counter=10*229*330

SSSP
? Modified dijkstra:
? Counter=节点值被更新次数 ? 当有负权边时有可能被更新多次!

8

4

2

16

-12 8

-6 4

-3

SSSP
? 更新次数
? 每一个三角形使得更新次数翻倍 ? 需要17个三角形,询问8次 = 2^17*8

? 35个点,51条边
? F=1+35+51*2+1+16=155 ? 第六个点会挂!!!

SSSP
? 更细一点的看
? 用F(i)表示i个三角形的迭代次数 ? F(0)=1

? F(i)=2F(i-1)+2
? G(i)=F(i)+2->G(i)=2G(i-1)=3*2^i ? F(n)=3*2^n-2 ? N=16,询问6次即可! ? 需要整数个数 1+33+48*2+13=143

染色问题
? 做法应该很多? 这里仅举一个例子 ? 超时:
? 完全图

? 不超时:
? 2部图

总结
? 看上去很简单,但是由于T的限制,其实还是有些难度的 ? 数学分析很重要 ? 细节决定成败


相关文章:
提纲_余林韵new
赛事介绍 1 2009 年全国青少年信息学奥林匹克竞赛冬令营讲课提纲 清华大学 余林韵一、 讲课目的:培养大家对信息学的兴趣 ·爱因斯坦有句名言: “兴趣是最好的老师。...
【历届IOI】国际信息学奥林匹克竞赛中国队金牌数
余林韵 福建福州一中 福建 银牌 第 21 届 IOI2009 保加利亚 漆子超 湖南雅礼中学 湖南 金牌 高逸涵 北京清华附中 北京 金牌 毛杰明 南京外国语学校 江苏 金牌 ...
2005年全国高中信息学联赛一等奖名单获奖名单
(43 名)姓名 胡伯涛 杨沐 余林韵 肖汉骏 石智黄群杨参 谢凌曦 金鑫林奔黄靖张弋蒋浩 蔡文挺 应涵 吴晓悦 林欣葳 王旭辉 杨龙琪 郑暾 梁塔锭 戴彦祺 学校...
2012年清华大学博士研究生拟录取名单公示(1)
余林韵、张峰、张国波、张圣林、张旭、章明星 公开招考 艾斯卡尔肉孜、曹乐乐、程舒晗、冯卓楠、郭华源、哈里旦木·阿布都克里木、 解辉、李立、李孟涵、李文全、...
2010-2011学年度清华大学优秀学生干部名单公示材料
余林韵 陈洪昕 乔白晖冰 周芬芳 石梦凯 黄渊华 徐可成 李延武 余韵寒 李腾麟 郭治鹏 柯锐 张权权 师陈东俊 白晨媛 孙皖楠 王哲夫 张博戎 胡贾李杨曌元 侯...
2010试题回顾与竞赛特点分析—王宏0116-2
LCA 模拟 时限 s/ 内存 M 1/512 2/512 2/512 1/512 10/512 命题或 解作者 胡伟栋 陈丹琦 俞华程 徐持衡 余林韵 唐文斌 周若凡 高逸涵 顾研 俞华程 ...
IOI主办情况和中国队获奖情况
(杭州二中) 余林韵(福州一中) 余林韵(福州一中) 陈丹琦(长沙雅礼中学) 陈丹琦(长沙雅礼中学) 金牌 金牌 金牌 金牌 金牌 金牌 金牌 金牌 金牌 金牌 金牌 金牌 ...
2004年全国高中数学联赛一等奖名单
(43 名)姓名 胡伯涛 杨沐 余林韵 肖汉骏 石智黄群杨参 谢凌曦 金鑫林奔黄靖张弋蒋浩 蔡文挺 应涵 吴晓悦 林欣葳 王旭辉 杨龙琪 郑暾 梁塔锭 戴彦祺 学校...
2006年全国青少年信息学分区联赛福州赛区获奖学生及指
余林韵 杨屹 宋立林 宋立林 陈颖 魏丽真 陈颖 肖汉骏 刘抒 黄丽华 宋立林 魏丽真 陈光 陈岩欢 陈骥远 郑暾 程传威 陈阜东 姓名 陈刘晟勤 所在学校 福州三中 ...
NOIP2003获奖名单
余林韵 等 肖汉骏 杨智杰 奖 林镌若 林(32 名) 斌 王则翰 陈颖 黄丽华 宋立林 黄海燕 陈理辉 王娟 洪绍辉 苏炜 陈延辉 廖斯达 张闻君 朱亦博 戴彦祺 ...
更多相关标签: