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

余林韵_Tasksauthor

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的限制,其实还是有些难度的 ? 数学分析很重要 ? 细节决定成败