当前位置：文档之家 › ACM竞赛讲座之一

ACM竞赛讲座之一

  • 格式：ppt
  • 大小：1.44 MB
  • 文档页数：44

下载文档原格式

  / 44

合集下载

ACM程序设计算法讲解

ACM程序设计算法讲解

目录1.河内之塔 (3)2.Algorithm Gossip：费式数列 (4)3.巴斯卡三角形 (5)4。

Algorithm Gossip: 三色棋 (6)5.Algorithm Gossip：老鼠走迷官(一） (8)6.Algorithm Gossip: 老鼠走迷官(二） (10)7。

Algorithm Gossip: 骑士走棋盘 (11)8.Algorithm Gossip：八皇后 (14)9.Algorithm Gossip: 八枚银币 (16)10.Algorithm Gossip: 生命游戏 (18)11.Algorithm Gossip: 字串核对 (21)12。

Algorithm Gossip: 双色、三色河内塔 (23)13。

Algorithm Gossip: 背包问题（Knapsack Problem） (28)14。

Algorithm Gossip：蒙地卡罗法求PI (32)15.Algorithm Gossip: Eratosthenes筛选求质数 (34)16。

Algorithm Gossip: 超长整数运算（大数运算） (35)17.Algorithm Gossip: 长PI (37)18。

Algorithm Gossip: 最大公因数、最小公倍数、因式分解 (40)19。

Algorithm Gossip：完美数 (44)20.Algorithm Gossip: 阿姆斯壮数 (47)21。

Algorithm Gossip：最大访客数 (48)22。

Algorithm Gossip: 中序式转后序式（前序式） (50)23。

Algorithm Gossip：后序式的运算 (53)24.Algorithm Gossip：洗扑克牌（乱数排列） (55)25。

Algorithm Gossip：Craps赌博游戏 (57)26.Algorithm Gossip：约瑟夫问题（Josephus Problem） (59)27。

第六讲-IEL-INSPEC-ACM-lNCS

第六讲-IEL-INSPEC-ACM-lNCS

图表说明
:直接在INSPEC查找文献; :查找JCT(Journal, Classification & Thesaurus); :回到选择直接进入INSPEC或JCT的页面; :查看本次登陆执行的检索命令,用户 LOGOFF后检索历史将清除,点击现在查询将重新查 看检索结果; :查看在线帮助; :退出系统
6.高级检索(Advanced) .高级检索(Advanced)
1) 在输入框内输入检索式 检索式构成: 检索词1 逻辑算符……检索词n <in> 字段名1,……字段名n 2) 选择限制条件*; 3) 点击"Start Search"按钮,开始检索; 4) 系统列出符合检索条件的文献,点击每篇文献 下方的[Abstract]或[PDF Full-Text]可浏览文摘 或原文; 注:(1) 逻辑算符:and(与),or(或),not (非) (2) 常用字段名:ab:文摘 au:作者 ct: 会议名称 is:期刊卷期号 jn:期刊名 cy: 会议日期 ti:文献标题 de:主题词
(3) 截词 *:表示任意个字符,如:electro* 可检索出 含electron,electrons,electronic,electronics, electromagnetic,electromechanical及electrolyte的文献. ?:表示一个字符,如:cable? 可检索出cables或 cabled的文献,但不包括cable(?必须是一个字符). *限制条件: 1) 文献类型:文献类型有三种,期刊,会议,标准,打 钩为选中,默认状态为全选. 2) 检索年限:根据需要选择起始,终止年限,默认状态 为1988年-present. 3) 检索结果排序:检索结果可按时间(Year),文献标题 (By Publication Title),相关度(Score)进行升降序排列. 4) 每页显示的文献数量可选择:15,25,50. 当查出的文献数量超过已定义的每页显示的文献数时, 可通过画面下方的数字及[Prev],[Next]按钮翻页.

吉林大学ACM国际大学生程序设计竞赛简介

吉林大学ACM国际大学生程序设计竞赛简介

吉林大学ACM国际大学生程序设计竞赛简介竞赛宗旨ACM国际大学生程序设计竞赛是由位于美国的计算机协会组织的年度性竞赛，是全球大学生计算机程序能力竞赛活动中最有影响的一项赛事，它已成为国内外各高校展示实力、加强交流、相互促进、共同发展的广阔舞台。

ACM/ICPC作为具有国际权威性和影响力的国际大学生程序设计竞赛，已成为衡量大学生程序设计能力和学校计算机学科水平的重要标准之一。

我校于2002、2003、2004、2005年参加亚洲预赛，分别在这八个赛区中取得学校排名第16、第17、第12、第9，第7、第18，第21，第17，共获得银奖2块、铜奖6块，竞赛成绩在不断稳步提高。

竞赛支持网站：(校外)(校内)竞赛联系地点：前卫南校区萃文楼501竞赛交流平台：吉林大学BBS 牡丹园－电脑技术－算法版/cgi-bin/bbsdoc?board=Algorithm参赛对象1、凡吉林大学在校本专科生均可报名参加。

年级、专业不限。

鼓励低年级同学参加。

2、比赛学生以个人身份参加，每人独立参赛。

3、参赛同学应在竞赛网站上注册参加热身赛，在报名时提供个人资料。

4、参赛同学应保证自己身份等资料的真实性。

5、以往学校代表队同学成绩不影响其他同学排名及奖励。

竞赛细则1、选手在参赛时携带个人证件。

2、竞赛以上机为比赛方式。

3、竞赛中至少命题6题，至多命题10题，上机比赛时间为5个小时，中间不休息。

4、参赛选手可以携带诸如书籍、字典、手册、程序清单等文字性参考资料。

5、参赛选手不能携带任何可用计算机处理的软件或数据(不允许任何私人携带的磁盘或计算器)。

6、参赛选手不能携带任何类型的通讯工具，包括无线电接收器、移动电话等。

7、选手未解决全部题目不得提前离场8、竞赛的预定时间为5小时，但当竞赛进行一定时间后，竞赛裁判可以因为出现不可预见的事件而调整比赛时间长度，一旦比赛时间长度发生改变，将会以及时并且统一的方式通告所有参赛选手。

9、当参赛选手出现妨碍比赛正常进行的行为时，诸如擅自移动赛场中的设备，未经授权修改比赛软硬件，干扰他人比赛等，都将会被竞赛裁判取消参赛资格。

ACM程序员协会课程简介

ACM程序员协会课程简介

ACM程序员协会课程简介
ACM程序员协会于2008年11月16日，在计算机科学学院的支持下成立。

ACM程序员协会负责的第二课堂——《ACM程序设计》课程，与专业知识紧密结合，是理论性和实践性的有机统一，通过多种多种教学方法、教学环节与现代化教学手段相结合。

其中包括课堂上的多种教学方法，课外多种实践环节，以及多媒体课件和影像文献片，丰富课堂知识。

以教学带科研，科研促教学。

同时还有指导老师的悉心教导，让你的专业技能节节升高。

协会课程成员都需参加每年的挑战杯、“ACM程序设计”、“电子设计”等专业竞赛，我们将推荐10%左右的优秀学生参加初、中、高级程序员的认证，推荐4%左右的学生参加省级ACM程序设计大赛，争取获得参加国家乃至全球的ACM程序设计大赛资格。

在这里，你可以找到程序高手，让他们给你答疑解惑；在这里，你可以学到许多课堂上没有的东西，奇妙的逻辑运算，奇特的数字组合，当它们在你的程序中诞生时，你将体会到非同一般的成功的快乐。

在进行课堂学习的同时，我们还将通过开展一系列丰富多彩的活动来丰富教学，丰富课余生活，让同学们在活动的同时也能学到知识。

专业义工活动，不但能让你亲手实践，维护计算机系统，将理论运用于实践，还能让你了解许多不知道的知识。

计算机的硬件，计算机的巧妙应用，计算机的桌面美化等等。

满脑子的知识不是我们最终的目标，让这些活现在生活中才是我们的真正目的。

让知识动起来，让我们的手指在键盘上飞舞，让一个个活灵活现的字符在屏幕上跳跃，造就一个个丰富多彩的程序。

加入《ACM程序设计》，让你的知识跳起属于你自己的舞蹈。

——ACM程序员协会
——会长：江龙
——2009年9月15日。

浙江大学 acm程序设计竞赛 动态规划讲义

浙江大学 acm程序设计竞赛 动态规划讲义

Tom

的 烦 恼
Tom的烦恼 按结束时间排序，枚举结束时间作为 当前状态,以前状态就是该结束时间 对应的起始时间，这是已经确定的.
Tom

文 字 游 戏
文字游戏(fairfox邀请赛1) 给你一份单词表，和一个句子。求出该句 子能有多少中不同的划分方法.例如: 单词是ab cd a b c d 句子是abcd 他共有4种完全划分方案: ab/cd a/b/c/d a/b/cd ab/c/d; 当前状态就是单词在句子中向后靠的位置, 以前状态就是确定这个单词位置以后,除 掉这个单词长度后的一个位置.状态转移 方程是:F[i]:=F[i]+F[ilength(word[j])] IOI中有一题《前缀》也是类似的题目.
拦 截 导 弹

拦 截 导 弹


状态的表示－f[i]，表示当第i个导 弹必须选择时，前i个导弹最多能拦 截多少。 每个导弹有一定的高度，当前状态 就是以第i个导弹为最后一个打的导 弹。以前状态就是在这个导弹以前 打的那个导弹。 显然这是十分能够体现状态间的联 系的题目。
最 长 公 共 子 串

给定起点站和终点站还有 L1,L2,L3,C1,C2,C3，求出要从 起点到终点最少要花多少钱.
买 车 票
怎 么 办
当前所在的某个车站
买 车 票
这一题的以前状态其实只有3种.即 满足3种距离(收费)情况的3个车站. 要知道这3个车站可以先做一个预 处理.显然这3个车站在满足距离限 制的条件下应该越远越好.

可以看出动态规划的实质就是
动 态 规 划 的 实 质

这也就是为什么我们常说动态 规划必须满足重叠子问题的原 因.记忆化,正符合了这个要求.

ACM竞赛讲座

ACM竞赛讲座

• 3、第一行输入一个整数N(N<1000),接下来的2至N+1行，
每行输入一个英文字母。输入有多组数据，以N等于0为 结束。 • 输出：对N个字母按ANSI码排序后，把它们输出在一行， 并且相邻字母之间有个空格。
• Input Sample
•
• • • • • • • • •
7
Z z a b B c D 0 Output Sample BDZabcz
• 四、团队配合
通过以上的介绍大家也可以看出， 信息学竞赛对于知识面覆盖的非常广， 想凭一己之力全部消化这些东西实在 是相当困难的，这就要求我们尽可能 地发挥团队协作的精神。同组成员之 间的熟练配合和默契的形成需要时间， 具体的情况因成员的组成不同而不同。
五、练习、练习、再练习
•
知识的积累固然重要，但是信息学终究 不是看出来的，而是练出来的。只有通过 具体题目的分析和实践，才能真正掌握数 学的使用和算法的应用，并在不断的练习 中增加编程经验和技巧，加强团队的配合。 总之，在这里光有纸上谈兵是绝对不行的， 必须要通过实战来锻炼自己。 大家平时可以在我们的OJ,ZOJ或者POJ 多多做些题目。
• 一、控制程序的结束 • 1、输入要求是多组测试数据，并以“0”作为结束，例
如： 杭电OJ的1235 (还可以测试Runtime Error) 2、输入有多组测试数据，以文件末尾作为结束，例如： 2 杭电OJ的1089(还可以测试格式错误) 3、输入的测试数据组数已被给定，例如： 杭电OJ的1090 • 4、输入要求是多组测试数据，并以“0，0”作为结束， 例 如： 杭电OJ 1091 • 5、在相邻的输出结果之间打印一空行，例如： • 杭电OJ的1096 •
算法
1、算法中最基本和常用的是搜索。这里 要说的是，有些初学者在学习这些搜索基 本算法是不太注意剪枝，这是十分不可取 的，因为所有搜索的题目给你的测试用例 都不会有很大的规模，你往往察觉不出程 序运行的时间问题，但是真正的测试数据 一定能过滤出那些没有剪枝的算法。 2、常用算法中的另一类是以“相似或 相同子问题”为核心的，包括递推、递归、 贪心法和动态规划。

ACM入门讲座-LX

ACM入门讲座-LX
11
关于 ACM题目的输入输出 ACM题目的输入输出
由于ACM竞赛题目的输入数据和输出数据一 由于ACM竞赛题目的输入数据和输出数据一 般有多组（不定），并且格式多种多样， 所以，如何处理题目的输入输出是对大家 的一项最基本的要求。这也是困扰初学者 的一大问题。
12
先看一个非常简单的题目
13
A+B Problem
The input will consist of a series of pairs of integers a and b, separated by a space, one pair of integers per line. For each pair of input integers a and b you should output the sum of a and b in one line, and with one line of output for each line in input. Sample input: 1 5 Sample output: 6
5
ACM-ICPC竞赛内容 ACM-ICPC竞赛内容
竞赛涵盖的范围很广，大致划分如下： Direct（简单题），Computational Direct（简单题），Computational Geometry（计算几何），Number Geometry（计算几何），Number Theory （数论），Combinatorics（组合数学）， （数论），Combinatorics（组合数学）， Search Techniques（搜索技术）， Techniques（搜索技术）， Dynamic Programming（动态规划）， Programming（动态规划）， Graph Theory（图论），Other（其他） Theory（图论），Other（其他）

ACM竞赛简介和入门

ACM竞赛简介和入门

ACM竞赛简介：ACM国际大学生程序设计竞赛是由国际计算机界历史悠久、颇具权威性的组织ACM学会（美国计算机协会）主办，是世界上公认的规模最大、水平最高的国际大学生程序设计竞赛，其目的旨在使大学生运用计算机来充分展示自已分析问题和解决问题的能力。

(网上有更详细的介绍，这里只做个简介)ACM竞赛特点：竞赛中一般有10道题，比赛时间为5个小时，每支参赛队伍由3名选手组成，可以携带诸如书、手册、程序清单等参考资料，对每一道题编完代码后，将代码提交裁判，每一次提交会被判为正确或者错误，判决结果会及时通知参赛队伍。

在规定时间内提交并通过题目数越多排名越靠前。

（时间5小时，题目8~12题，同题目数按所用时间多少排名）ACM题目限制：时间限制（即程序运行所用的时间）空间限制（即程序运行时所开内存的多少）ACM基本要求⏹英语⏹分析理解能力⏹算法⏹编码⏹合作ACM竞赛意义学习编程，并不是为了参加竞赛，ACM竞赛对于我们的意义更多的还是专业能力的提高。

在备战过程中，无论是对自己的编程能力，还是团队合作解决问题的能力，都是一种很好的锻炼机会。

一般而言，每个在做ACM竞赛的学生，他们的编程能力会比较出色。

与数学建模相比，由于ACM竞赛针对的是我们学计算机的同学，所以没有数学建模的比赛规模，但是依旧是国际上最有影响力的大学生竞赛之一。

ACM竞赛入门现在有很多大学有专门为ACM竞赛开设自己的测评网站，上面有很多贴近竞赛的题目。

比如说北大poj，浙大zoj等等。

所以选择一个自己专门练习的网站，我们都用北大的poj，然后开始自己在上面做题，和同学交流经验。

等到回到本部，要是有了一定的实力和基础，张震老师就会对我们进行选拔和组队，最后参加省赛和亚洲的区域赛。

⏹在poj上做20左右道简单的题目，熟悉ACM题目的基本特点。

（这里列出几道相对较简单的题目的题号：1000，1003，1004，1046，1207，1226，1504，1552）⏹熟悉了poj之后，按照poj的题目分类，买一本或借一本算法的书（暨大ACM校队的基本都用机械工程出版社的《算法导论》）开始学习，然后做算法的专题，一般每个专题做10~30道。

IEEE和ACM简介

IEEE和ACM简介

一、IEEE简介IEEE的英文全称为Institute of Electrical and Electronics Engineers——美国电气和电子工程师协会，它是一个国际性的电子技术与信息科学工程师的协会，是世界上最大的专业技术组织之一（成员人数），拥有来自175个国家的36万会员(到2005年)。

1963年1月1日由美国无线电工程师协会(IRE, 创立于1912年)和美国电气工程师协会(AIEE,创建于1884年)合并而成，它有一个区域和技术互为补充的组织结构，以地理位置或者技术中心作为组织单位(例如IEEE 费城分会和IEEE计算机协会]])。

它管理着推荐规则和执行计划的分散组织(例如IEEE-USA 明确服务于美国的成员，专业人士和公众）。

总部在美国纽约市。

IEEE在150多个国家中它拥有300多个地方分会。

透过多元化的会员，该组织在太空、计算机、电信、生物医学、电力及消费性电子产品等领域中都是主要的权威。

专业上它有35个专业学会和两个联合会。

IEEE发表多种杂志，学报，书籍和每年组织300多次专业会议。

IEEE定义的标准在工业界有极大的影响。

IEEE (读做eye-triple-e，I-3E)。

学会成立的目的在于为电气电子方面的科学家、工程师、制造商提供国际联络交流的场合，为他们交流信息。

并提供专业教育和提高专业能力的服务。

学会的主要活动是召开会议、出版期刊杂志、制定标准、继续教育、颁发奖项、认证（Accreditation）等。

IEEE每年要举办300多个学术会议，有35万人参加。

IEEE的许多学术会议在世界上很有影响，有的规模很大，达到4－5万人。

IEEE定位在科学和教育,并直接面向电子电气工程通讯,计算机工程,计算机科学理论和原理研究的组织, 以及相关工程分支的艺术和科学。

为了实现这一目标，IEEE承担者多个科学期刊和会议组织者的角色。

它也是一个广泛的工业标准开发者,主要领域包括电能,能源,生物技术和保健,信息技术, 信息安全,通讯, 消费电子,运输,航天技术和纳米技术. 在教育领域IEEE积极发展和参与，例如在高等院校推行电子工程课程的学校授权体制。

校赛PPT-艾庆兴

校赛PPT-艾庆兴

西电ACM校赛
• 西电ACM校赛举办至今已11届，是我校选拔ACM校队队员 的主要方式，在校赛中成绩优异的选手将进入为期20天的 暑期集训，最终确定代表学校参加全国比赛的人选。 • 西电ACM校赛在每年的5月中旬举办，形式为现场赛的形 式，比赛时长共3小时，形式为参赛者在规定时间内解答6 道比赛题目，按解题数目和时间排名，排名实时更新，比 赛结束之时便可以看到最终比赛结果。 • 这一届ACM校赛的不同之处是，所有的参赛名额都从网络 预选赛中产生，网络预选赛前540名获得参加校赛的资格。
• 参考书籍：《算法竞赛入门经典》《算法导论》《挑战程序设 计竞赛》 • 练习网站：
– /land (西电ACM online judge） – （杭州电子科技大学online judge） – （北京大学online judge）
代码3:
int a,b,n,arr[10],num; while (n--) { printf("请输入a和b\n"); scanf("%d%d",&a,&b); int ans=0; for (int i=a;i<=b;i++) { split(i); int sum=0; for (int j=1;j<=num;j++) sum+=pow(arr[j],num); if (sum==i) ans++; } printf("一共有%d个水仙花数\n",ans); }
5月11日全天
ACM大赛简介&参赛流程 校赛全方位了解 网络预选赛辅导
ACM大赛考察什么？
编程能力 C\C++\JAVA
算法设计、数学知识 动态规划、搜索、博弈……

ACM讲义,ACM课件

ACM讲义,ACM课件
ACM程序设计大赛
9
最常见题型
Dynamic Programming(动态规划) Greedy(贪心) Complete Search(穷举) Flood Fill (种子填充) Shortest Path (最短路径) Recursive Search Techniques (回溯） Minimum Spanning Tree （最小生成树） Knapsack（背包） Computational Geometry(计算几何) Network Flow(网络流) Eulerian Path (欧拉回路) Two-Dimensional Convex Hull (二维凸包) BigNums (大数) Heuristic Search(启发式搜索) Approximate Search (近似搜索) Ad Hoc Problems(杂题)
ACM程序设计大赛
10
ACM程序设计大赛
11
离散数学第1讲 命题逻辑基础
数理逻辑将能够判断真假的陈述句称作命题。 命题通常使用大写字母A，B，…，Z或带下标的大写字母或数字 表示，如Ai，R等，例如： A1：我是一名大学生。 联结词： 合取联结词： 析取联结词： 否定联结词： 蕴涵联结词： 等价联结词： 逻辑真值： 0，1
16
命题的翻译： 例：假如上午不下雨，我去看电影，否则就在家里读书或看报。 解：设P：上午下雨；Q：我去看电影；R：我在家里读书；S： 我在家里看报。 本例可表示为： （PQ）∧（P（R∨S））。
ACM程序设计大赛
17
命题公式的解释：
定义 设P1，P2，…，Pn是出现在命题公式G中的全部命题变 元，指定P1，P2，…，Pn的一组真值，称这组真值为G的 一个解释或赋值，记作I，公式G在I下的真值记作TI （G）。 例如，G=（P∧Q）R，则I： P Q R 1 1 0 是G的一个解释，在这个解释下G的真值为1，即TI（G）=1。

4ACM简介及学习入门

4ACM简介及学习入门

信息技术学院程序设计班信息技术学院程序设计班ACM群号：685608810年11月第一章新手入门1.ACM国际大学生程序设计竞赛简介1) 背景与历史1970年在美国TexasA&M大学举办了首次区域竞赛，从而拉开了国际大学生程序设计竞赛的序幕。

1977年，该项竞赛被分为两个级别：区域赛和总决赛，这便是现代ACM竞赛的开始。

在亚洲、美国、欧洲、太平洋地区均设有区域赛点。

1995至1996年，来自世界各地的一千多支s代表队参加了ACM区域竞赛。

ACM大学生程序设计竞赛由美国计算机协会（ACM）举办，旨在向全世界的大学生提供一个展示和锻炼其解决问题和运用计算机能力的机会，现已成为全世界范围内历史最悠久、规模最大的大学生程序设计竞赛。

2) 竞赛组织竞赛在由各高等院校派出的3人一组的队伍间进行，分两个级别。

参赛队应首先参加每年9月至11月在世界各地举行的“区域竞赛(Regional Contest)”。

各区域竞赛得分最高的队伍自动进入第二年3月在美国举行的“总决赛(Final Contest)”，其它的高分队伍也有可能被邀请参加决赛。

每个学校有一名教师主管队伍，称为“领队”(faculty advisor)，他负责选手的资格认定并指定或自己担任该队的教练(coach)。

每支队伍最多由三名选手(contestant)组成，每个选手必须是正在主管学校攻读学位的学生。

每支队伍最多允许有一名选手具有学士学位，已经参加两次决赛的选手不得再参加区域竞赛。

3) 竞赛形式与评分办法竞赛进行5个小时，一般有6~8道试题，由同队的三名选手使用同一台计算机协作完成。

当解决了一道试题之后，将其提交给评委，由评委判断其是否正确。

若提交的程序运行不正确，则该程序将被退回给参赛队，参赛队可以进行修改后再一次提交该问题。

程序运行不正确是指出现以下4种情况之一：(1)运行出错(run-time error)；(2)运行超时〔time-limit exceeded〕；(3)运行结果错误(wrong answer)；(4)运行结果输出格式错误(presentation error)。

2010北大ACM暑期讲义数学题

2010北大ACM暑期讲义数学题

常见置换的循环数
计算置换的循环数,是这一算法的瓶颈.如果能 够快速计算出各置换的循环数,就可以大大提 高程序的运行效率 旋转:n个点顺时针(或逆时针)旋转i个位置的置 换,循环数为gcd(n,i) 翻转:
n为偶数时,
对称轴不过顶点:循环数为n/2 对称轴过顶点:循环数为n/2+1
置换群
以置换为元素的群 置换群G={a1,a2,...,a|G|} 例子中G内共有6个置换 123456 123456 123456 123456 612345 561234 123456 123456 123456 456123 345612 234561
循环
在一个置换下,x1->x2,x2->x3,...,xn->x1,这 样x1,x2,...,xn就构成了一个循环 定义ck为在置换ak下的循环总数 例子中: c1=6,c2=1,c3=2,c4=3,c5=2,c6=1
Polya定理
设G={a1,a2,...,a|G|}是N={1,2,...,N}上的置 换群,现用m种颜色对这N个点染色,则不 同的染色方案数为 S=(mc1+mc2+...+mc|G|)/|G| 证明比较复杂,略
利用Polya定理 解决组合计数问题的步骤
写出置换群 123456 123456 123456 123456 612345 561234 123456 123456 123456 456123 345612 234561 求出每个置换的循环数 c1=6,c2=1,c3=2,c4=3,c5=2,c6=1 计算染色方案 S=(26+21+22+23+22+21)/6=14
解二元模线性方程
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。


详细内容...
/
如何入门呢?
ACM题目特点:
由于ACM竞赛题目的输入数据和输 出数据一般有多组（不定），并且格 式多种多样，所以，如何处理题目的 输入输出是对大家的一项最基本的要 求。这也是困扰初学者的一大问题。 下面，分类介绍：
先看一个超级简单的题目：
开课目的
– 为瓯江ACM代表队培养后备人才 – 提高分析问题和应用计算机编程解决 问题的能力 – 培养必要的自学能力 – 培养学生的协调和沟通能力 – 体会学习的快乐
练习环境
浙江大学ACM网站现提供一千余道练习题 目以及在线自动判题系统 可在该网站注册后进行练习 例如 题号1001 A + B Problem

竞赛规则


竞赛中至少命题6题，至多命题10题 比赛时间为5个小时 参赛队员可以携带诸如书、手册、程序清单等 参考资料 试题的解答提交裁判称为运行，每一次运行会 被判为正确或者错误，判决结果会及时通知参 赛队伍 使用的语言包括C/C++，每支队伍使用一台计 算机
竞赛环境


不可行的方法：
– int f[100000000] – for(i=0;i<100000000;i++)
强化训练计划

短期的突击
基础回顾和环境入门 强化训练与培训 技巧方法
5月？日
4月 1日 15日 16日 30日 5月1日 15日
详细计划
4月1-15日： C语言知识复习、浙大ACM的自动判卷环境、数据结构 4月16-30日：自己的强化训练（至少30题提交成功）、讲座 5月19-24日：经验总结（程序格式、编程方法）、选拔参赛
Switch (exp ) { case 值1： 语句1； break; case 值2： 语句1； break; … default: 语句n+1; }
exp
语句1 语句2 语句n+1
基本控制语句_循环
while( P ) { A; }
P
A
基本控制语句_循环
do {
A P
A; }while( P );

瓯江学院学科竞赛颁奖
常见问题：
1、需要什么基础？( C/C++ ) 2、英语不好怎么办？(问题不大) 3 、如何加入集训队? 4 、可以退课吗? ( Of course! )
课后任务：
1、熟悉 2、完成在线练习：
——基本输入输出练习
3、学有余力，可以尝试下面题目: 1016-1018、1013、1061 1170、2000-2043

2人银牌 1铜 1银 2银1铜（省内排名？） ？？？
2008省赛排名情况
金奖＋银奖＝11＋30＝41 浙江大学：4＋8＝12 杭州电子：2＋6＝8（另：4铜） 浙江工大：2＋4＝6（另：2铜） 宁波理工：2＋2＝4（另：2铜） 宁波大学：1＋1＝2 浙江师大：0＋4＝4 杭电信息：0＋2＝2 温州大学：0＋1＝1 浙江理工：0＋1＝1 工大之江：0＋1＝1
ACM/ICPC是参赛选手展示计算机才华的广阔 舞台，是著名大学计算机教育成果的直接体现， 是信息企业与世界顶尖计算机人才对话的最好 机会。 在过去十几年中，世界著名信息企业APPLE、 AT&T、MICROSOFT和IBM分别担任了竞赛的 赞助商。 中国大陆高校从1996年开始参加ACM/ICPC亚 洲预赛 浙江省较早参与高校有浙江大学、浙江工业大 学
比赛形式
1支队伍1台机器（提供打印服务） 上机编程解决问题（可带纸质资料） 实时测试，动态排名 试题

– 8-10题 – 全英文（可以带字典）

时间：持续5个小时
ACM .vs. 校程序设计竞赛

ACM竞赛
– 团队合作精神 – 即时提交，通过所有数据才能得分 – 全英文题目，题目考察范围广
ACM竞赛的培训（之一）
李 洪 薛德东 温州大学瓯江学院 2009-4-1
ACM的介绍

ACM/ICPC（国际大学生程序设计竞赛） 是由ACM(Association for Computing Machinery，美国计算机协会)组织的年 度性竞赛，始于1970年，是全球大学生 计算机程序能力竞赛活动中最有影响的 一项赛事。
竞赛与自我发展
学习编程并不是为了参加竞赛，竞赛对于多数 选手的意义还是在于参与，以及在备战过程中 对自己的锻炼和提高。 ACM竞赛和其它一系列竞赛是一样的，只是它 的影响力和规模大些罢了，所以希望对编程有 兴趣的同学都能够关注竞赛，即使不参加，通 过了解竞赛中涉及的编程知识达到课内很难达 到的高度，这对每个人都是有益无害的。
基本控制语句_循环
for( B; P; C) { A; }
B P A C
数据结构
线性表 队列、堆栈 排序、查找（至少掌握1种）

详细内容...
算法的复杂性

在Number Sequence中
– 1<=A,B<=1000,1<=n<=100,000,000) – f(1) = 1, f(2) = 1; – f(n) =(A*f(n-1)+B*f(n-2)) mod 7.
涉及什么知识？

直接相关：C程序设计、离散数学、数据结 构、算法分析；

重要基础：英语、高等数学（数学分析）、 线性代数、操作系统、编译原理、人工智能；
C程序设计
输入输出格式 程序结构

运算符和表达式
基本控制语句
A
P
P
B
A
B
A
顺序
选择
循环
基本控制语句
复ch语句 while语句 实现循环结构的语句 do-while语句 函数调用语句
ACM in wzu

2003年9月，第一次参加此类比赛 （浙大邀请赛） 2004～2008，每年5月—— 2008年4月，瓯江首届邀请赛

浙江省第1～5届大学生程序设计竞赛

2008浙江省第五届大学生程序设计竞赛 （回顾）
全省72所本专科院校 300支队伍参赛 最强的阵容 历届规模最大、水平最高的程序设计竞赛

· 竞赛时间：2009年5月？日 12:00—17:00。 · 开幕式、熟悉场地时间：2009年5月？日8:00。 · 闭幕式时间：2009年5月？日19:00。 · 竞赛地点：浙江大学紫金港校区计算中心机房。 · 竞赛语言包括C++ 和 C。 · 每支队伍使用一台计算机，所有队伍使用计算 机的规格配置完全相同。

详细内容...
/
浙江省第五届大学生程序设计竞 赛本科组三等奖

胡盛迭、洪智妍、张慧同学
预期赛事（今后每年）

3-4月，举行校内大赛（暨选拔赛） 5月，参加浙江省大学生程序设计大赛 另外，每学期适当的练习赛
如何比赛?

3人组队
可以携带诸如书、手册、 程序清单等参考资料； 不能携带任何可用计算机处理的软件或数据、不 能携带任何类型的通讯工具； 可能收到的反馈信息包括：
– – – – – – Compile Error ; Run Time Error; Time Limit Exceeded; Wrong Answer ; Presentation Error Accepted

如何排名？
首先根据解题数目进行排名。 如果多支队伍解题数量相同，则根据总用时加上惩 罚时间进行排名。 总用时和惩罚时间由每道解答正确的试题的用时加 上惩罚时间而成。 每道试题用时将从竞赛开始到试题解答被判定为正 确为止，其间每一次错误的运行将被加罚20分钟时 间，未正确解答的试题不记时。

/showproblem.php?pid=10 89 Sample input: 1 5 10 20 Sample output: 6 30

初学者很常见的一种写法：
#include<stdio.h> void main() { int a,b; scanf(“%d %d”,&a,&b); Printf(“%d”,a+b); }

ACM/ICPC in China


中国大陆高校从1996年开始参加ACM/ICPC—— 前六届中国赛区设在上海，由上海大学承办； 2002年由清华大学和西安交通大学承办； 2003年由清华大学和中山大学承办。 2004年由北京大学和上海交通大学承办。 2005年由四川大学、北大和浙大承办。 2006年由上海大学、清华和西电承办。 2007年：北航、南航、吉大、西华 2008年：哈工程、北交、合肥、杭电、西南民大
实现选择结构的语句
for语句
基本控制语句_选择
if( P ) {
A;
} else { B; }
A
P
B
基本控制语句_选择
if( P ) {
A;
P
}
A
基本控制语句_选择
if( P1 ) { A; } else if ( P2 ) { B; } else { C }
P1 A P2 B C
基本控制语句_选择

校程序设计竞赛
– 个人编程能力的比拼 – 中文或英文（以后全英文），考察编 程基本功
ACM队队员的基本原则

基本要求
– 人品好 – 愿意花时间在这项赛事上 – 有团队合作精神

能力要求
– 程序设计 – 英语科技文献阅读
– 数学
杭电信息工程学院ACM
参赛历史 2005 2人 2006 2队 2007 2队 2008 6队 2009 ？