NOIP 问题解答专题.ppt

问题解答专题 基础题 2003p-1 2004p-1 2004p-2 2009t-2 2009p-2 2001p-1 2004t-2 2005p-2 1998p-2 1995p-5 1995t-2 1998p-3 排 序 2005p-1 排列组合 2008p-1 2009p-1 2002p-2 2001p-2 2001t-２ 归纳 1999p-2 1995p-4 2002t-2 1999t 2006t-2　 递　推 2000p-2 2000t-2 2007p-2:最短路线 2009p-1 1998p-1 递　归 2007p-1:子集划分 2002t-1 分　治 1996p-9 2006p-1 数据结构 2003p-2 1999p-1 1997p-8 一笔画 1998t-3 2008p-2 2000p-1 1998t-2 2001t-1 1996t-7 1997p-9 标识符树 2002p-2 1997p-4 其　他 2006t-1 2006p-2:取石子游戏 2005t-2：取火柴游戏 传球问题 出栈序列统计 求路径数 整数分划问题 var a:array[1..20,1..20] of integer; v:array[1..20] of boolean; i,j,max,n,p:integer; flag:boolean; begin readln(n); for i:=1 to n do for j:=1 to n do read(a[i,j]); fillchar(v,sizeof(v),false); v[1]:=true;{源点} for j:=2 to n do {n-1次贪心} begin max:=maxint; for i:=1 to n do{寻找源点到其它顶点的最短权值} if not v[i]and(a[1,i]0)and(a[1,i]max) then begin max:=a[1,i];{打擂台} p:=i; end; v[p]:=true;{已求出标志} for i:=1 to n do {更新权值} if (a[1,p]0)and(a[p,i]0) then if (a[1,i]a[1,p]+a[p,i])or (a[1,i]=0) then a[1,i]:=a[1,p]+a[p,i]; end; for i:=2 to n do write(a[1,i], ); end. 原来是无路的 1 2 3 5 4 4 29 4 4 6 3 6 5 0 4 29 4 0 2 0 0 0 3 0 6 0 0 4 0 0 0 0 6 0 0 4 0 0 4 11 4 7 样例 有6个城市，任何两个城市之间有一条道路连接，6个城市之间两两之间的距离如下表表示，则城市1到城市6的最短距离为____________。 ? 城市1 城市2 城市3 城市4 城市5 城市6 城市1 0 2 3 1 12 15 城市2 2 0 2 5 3 12 城市3 3 2 0 3 6 5 城市4 1 5 3 0 7 9 城市5 12 3 6 7 0 2 城市6 15 12 5 9 2 0 0 2 3 0 8 10 0 0 3 0 5 10 0 0 0 0 5 8 0 0 0 0 0 7 已知，按中序遍历二叉树的结果为：abc 问：有多少种不同形态的二叉树可以得到这一遍历结果，并画出这些二叉树。 给出一棵二叉树的中序遍历：DBG