2015省信息学奥赛培训在teacher上-竞赛指导

成功

+睿智的思想

+不懈的努力为什么要参加编程比赛，能力的提高学到很多书本上和大学里面学不到的知识和技能有机会云游四海，可以和众多武林高手同场交到很多志同道合的朋友$$,出国的机会对未来极其有利保研大公司不仅关注、同时自己举办各类编程竞赛、非常重视选手的编程比赛经历和成绩编程竞赛非常有趣！各种有趣的编程比赛报名时间：4月7日至5月8日http

/codejam程序设计大赛http/htt/nanti/报名时间：3月29日至5月23日http:

/tchtt/nanti/楼教主千秋万载，一统江湖楼教主君临斯德哥尔摩ACM

经典ACRush:切题就是升级,比赛就是PKPetrMitrichev两次ACM世界总决赛亚军TCOChampionTCCCChampionGCJChampion有朝一日，我可能像这些人一样牛吗？初学者如何进行What’s

needed

in

Contest精通算法稳定快速实现算法的能力数学水平心理素质两个ht

/usacogate(USACO)基本功训练基本算法讲解、训练每个题做出后有讲解、代码闯关模式初学者

Chapter1-4,Chapter5-6

性较强http:

/tcAlgorithm

Competition

-

Single

Round

Match(SRM)一个月3次左右，有rating分两个版(Div

I,

DivII)参加人数众多每次比赛后有详细的解题报告、代码比赛结束后有Practice

Room可以继续做可以查看每一个人的代码Forum很热闹，外国人非常有时候有$哦TopcoderTopcoderTopcoderTopcoderTopcoderTopcoder

RatingHandle

:exod40国内题库http:/

http

http

自己的OJ杭州电子科技大学http:

/vjudge华

大虚拟OJhttp

浙江大学国外题库数学题较多，OI选手必做国外最大题库，人很多，Forum也很热闹题较难PKU

Online

Judge可能收到的反馈信息包括：Compile

ErrorRuntime

ErrorTime

Limit

ExceededWrong

AnswerPresentation

ErrorAccepted搜索贪心递归分治动态规划程序=算法+数据结构计博弈一：有若干个

，两人轮流取，可以取一或二或三个辗，转取相得除最法后一个的人失败If(a==0)retuElse

return

g二：有若干堆，每堆若干汉个诺，塔两问人题轮流取，可以从任m意ov一e(堆t1,中t2取,t3任,n)意{多个（至少一个）m，ov取e(得t1,最t3后,t2一,n-1)个的人失败print(“Move

t1->t2”)move(t3,t1,t2.n-1)}化搜索一道经典例题给你一个数字三角形,形式如下:12

33

1

17

2

4

1找出从底层到顶层的一条路,使得所经过的权值之和最小算法：f(i,

j)=a[i,

j]

+

min{f(i+1,

j)，f(i+1,

j

+

1)}时间复杂度：N*N动态规划串、栈、队列树堆并查集哈希表程序=算法+数据结构树的术语：根结点叶子结点结点的度

父亲结点

儿子结点

兄弟结点

祖先结点

结点的层次树的高度ADCBFEGJIHLKM堆父亲节点权值小于儿子节点堆除了最底层，为满二叉树完全二叉树有两个儿子节点二叉树节点和边树同余模堆的应用堆排序：将N个数一次插入堆中，然后做N次删除堆顶元素操作，就可以获得顺序的排列。时间复杂度：O(n*log(n))树二叉树线段树伸展树AVL树树并查字典树生成树122多叉树250300110200991052302161、数论2、组合数学3、图论数学和常用模型1.素数与整除问题2.进制位3.同余模运算数论秦九韶算法：二进制数(10110)=1*16+1*4+1*2=((((1*2)*2)+1)*2+1)*2中国剩余定理：已知X

mod

M[i]=A[i]，求X筛法2，3，4，5，6，7，8，9，10……2，3，5，7，9，11，13，15……2，3，5，7，11，13，17，19……伪素数费马小定理随机判断a^(p-1) mod

p=1Miller-Rabbin测试素数的判定图的定义1、点V2、边3、边权E=(u,v,w)图论1E=(u,v

2435661655563421.图的遍历（连通性）2.生成树问题4.网络流问题5.匹配问题图论最大流费用流最小割最大二分图匹配最小生成树最小度限制生成树最优比例生成树3.最短路问题深度优先遍历强连通块桥、割点广度优先遍历带权匹配最小路径覆盖1、Bellman-Ford2、Dijkstra3、Floyd最短路算法计算几何一个简单的问题判断两条线段是否相交（不包含端点）？程，求出交点，判断交解析几何写出两条点的位交点的情点，唯一交点求出交点是不是太多余？只是判断线段各种浮点计算误差需要更简单的做法——计算几何！！一个简单的问题AB和CD相交，那么线的异侧，问题的转化如何判断点在直线的哪C、D也位于AB所在一侧？一个简单的问题有向线段规定直线具有一个正方向，直线将平面划分成两个区域：直线的左侧和右侧叉积现在的问题：是否存在一种运算，能判断向量a位于向量b的哪一侧？第一象限的情况：通过斜率来比较Yb/Xb-Ya/Xa>0?无法推广，除法代价高、误差大对其通分，得到：Xa*Yb-Xb*Ya经过实践检验，当a，b成右手系时，上式的结果总为正；当a，b成左手系时，上式的结果总为负；当a，b共线时，上式结果总为零。叉积叉 的面积两个向量的叉积：a×b=Xa*Yb-Xb*Ya有向面积力学中的四边形法则有向面积一个很当o

有价值的概念！

面积，左手系是为

积叉积的几何形式a×b=|a|*|b|*sinθ用叉积判断线段是否相交struct

Point{double

x,y;};double

xmult(Point

p1,Point

p2,Point

p0){return

(p1.x-p0.x)*(p2.y-p0.y)-(p1.y-p0.y)*(p2.x-p0.x);}//叉积，计算(p1-p0)×(p2-p0)bool

cross(Point

a,Point

b,Point

c,Point

d){return

xmult(a,b,c)*xmult(a,b,d)<0&&xmult(c,d,a)*xmult(c,d,b)<0}//判断线段ab和cd是否相交，不包括端点用叉积判断线段是否相交精度问题epsdouble

eps=1e-8；int

dblcmp(double

x){if(fabs(x)<eps)

return

0;return

x>0?1:-1;}从今天开始练习poj3299,poj2159,poj2739,poj1083,poj2262,poj1503,poj3006,poj2255,poj3094简单题用来练手熟悉OJ从今天开始练习基本算法:(1)枚举.(poj1753,poj2965)(2)贪心(poj1328,poj2109,poj2586)(3)递归和分治法.(4)递推.(5)构造法.(poj3295)从今天开始练习图算法:(1)图的深度优先遍历和广度优先遍历.(2)最短路径算法poj1860,poj3259,poj1062,poj2253,poj1125,poj2240(3)最小生成树算法poj1789,poj2485,poj1258,poj3026(4)拓扑排序poj1094从今天开始练习数据结构(1)串(poj1035,poj3080,poj1936)(2)排序(poj2388,poj2299)(3)简单并查集的应用.(4)哈夫曼树(poj3253)(5)堆从今天开始练习简单搜索(1)深度优先搜索(poj2488,poj3083,poj3009,poj1321,poj2251)(2)广度优先搜索(poj3278,poj1426,poj3126,poj3087.poj3414)从今天开始练习数学(1)组合数学:1.加法原理和乘法原理.2.排列组合.3.递推关系.(POJ3252,poj1850,poj1019,poj1942)从今天开始练习数学(2)数论.1.素数与整除问题2.进制位.3.同余模运算.

(poj2635,poj3292,poj1845,poj2115)建议初学时做一定量的题目打基础针对特定的经典算法，做相应的题目练习参加各种

编程比赛和训练赛，练习写代码的准确性和速度，积累比赛经验。（比赛预报：http:/

/

/re

hp?tid=125）过题数并不重要，做题数的

也不重要。参考书算法导论英文版入门级读物初读时，前面的数学部分建立基本概念即可，无需深究算法的正确性证明、复杂度分析一定要扎实掌握(Master

Theorem要会用，摊还分析了解)数据结构部分理解是关键，一些过于复杂的数据结构对于初学者并不一定要求实现(

树、二项堆、Fibbonacci堆），但基本的数据结构一定要熟练掌握，要能熟练实现图论经典算法要熟练掌握动态规划要熟练掌握高级部分只用选学一些参考书算法竞赛入门经典程序设计导引及刘汝佳实践

POJ首页书籍很基础，适合入门的同学算法艺术与信息学竞赛（黑书）较难适合有一定基础的同学对于初学者仍然

第一章和第三章刘汝佳、黄亮武功秘籍武功秘籍各种的资料很多非常好的一、

OJ的

资源共享