《程序设计大赛指导.ppt》由会员分享，可在线阅读，更多相关《程序设计大赛指导.ppt（51页珍藏版）》请在三一办公上搜索。
1、ACM/ICPC与HNCPC竞赛,国际大学生程序设计竞赛,ACM International Collegiate Programming Contest(ACM/ICPC)Sponsored by IBM(AT&T,Microsoft,etc)Regional Contest每年10，11，12月World Finals次年3月底到4月初,Regional Contest,Asia RegionalBeijing,Bombay,Dhaka,Ehime,Kanpur-Kolkata,Manila,Seoul,Zhejiang,Sichuang,Taipei,Tehran国内赛区Beijing北
2、京大学Zhejiang浙江大学Sichuang四川大学（其它）,湖南省大学生程序设计大赛(简称)竞赛情况,湖南省大学生程序设计大赛竞赛情况首届,2005年，首届省“湘邮科技杯”大学生程序设计大赛在湘潭大学举行。参加本次大赛的有来自中南大学、湖南大学、湘潭大学等30余所高校的74支代表队，共200余人。我院选派两个代表队参赛，获一项三等奖，团体排名第五。,湖南省大学生程序设计大赛竞赛情况第二届,2006年，第二届省“软考杯”大学生程序设计大赛在湖南商学院举行。来自全省25所高校的81个代表队共250多名选手。其中国防科大Robust队、长沙理工大学ACIE队获得一等奖，湖大Zealor队、国防科
3、大Snails队、Puzzle队获得二等奖。我院选派四个代表队参赛，获两项优胜奖，团体排名第七。,湖南省大学生程序设计大赛竞赛情况第三届,2007年“铁道社杯”湖南省第三届大学生程序设计大赛在湖南农业大学举行。全省近所高校、多支队伍参赛。,Regional 竞赛内容(1),参赛资格ICPC：在读本科生，研一学生 HNCPC：在读本专科生专业不限鼓励女选手参加比赛一个选手至多参加4年预选赛人员组成3个人组成一个队如果一个队伍有2个以上的女生，则为女队（部分赛区要求3个都是女生）设“最佳女队”奖,Regional 竞赛内容(2),比赛形式1支队伍1台机器（提供打印服务?）上机编程解决问题（可带纸质
4、资料）实时测试，动态排名试题6-10题全英文（可以带字典和非电子资料）时间：持续5个小时,Sample Problem,Task:Calculate a+bInput:Read from sum.in a series of pairs of integers a and b,separated by a space,one pair of integers per line.Output:For each pair print the sum of a and b one per line to the screen.,Sample Solution,#include#include usi
5、ng namespace std;int main()int a,b;ifstream fin(“sum.in”);while(finab)couta+bendl;return 0;,评测方法,Time Limit,对程序的要求,程序执行所需要的时间要短(Time Complexity)程序执行所使用的内存要少(Space Complexity)结果(Output)要完全正确,ACM.vs.校程序设计竞赛,ACM竞赛团队合作精神即时提交，通过所有数据才能得分全英文题目，题目考察范围广校程序设计竞赛个人编程能力的比拼赛后提交，可得部分分数中英文题目，考察编程基本功,队选拔过程,院程序设计资格赛,
6、初选赛,日常训练,暑期集训,队选拔赛,队队员的基本原则,基本要求人品好愿意花时间在这项赛事上有团队合作精神能力要求程序设计英语科技文献阅读数学,一朝参赛，终身受益,相关的知识,数学知识离散、组合数论、图论计算几何算法&数据结构基本数据结构搜索、分治动态规划贪心,大学程序设计竞赛试题讲解,问题描述,给定一个N位的二进制串b1 b2 bN-1 bN将该串作旋转，即将b1移到bN后面，得到一个新的二进制串：b2 bN-1 bN b1 d对新的二进制串再做旋转，得二进制串b3 b4 bN-1 bN b1 b2重复旋转操作操作，可得N个二进制串，对这N个串排序，可得一个N*N的矩阵,问题描述,例如：1
7、0 0 0 1 0 0 0 1 11 1 0 0 00 0 1 1 00 1 1 0 0,问题描述,对它们进行排序，得矩阵0 0 0 1 10 0 1 1 0 0 1 1 0 01 0 0 0 1 1 1 0 0 0,问题描述,要求：给定这种矩阵的最后一列，求出矩阵的第一行。对于上面的例子，给出 1 0 0 1 0，要求你的程序输出 0 0 0 1 1。,0 0 0 1 10 0 1 1 0 0 1 1 0 01 0 0 0 11 1 0 0 0,问题描述,输入文件名：bincode.in第一行有一个整数 N，表示二进制串的长度第二行有N个整数，表示矩阵最后一列从上到下的数值。,问题描述,输出
8、文件名：bincode.out第一行包括N个整数，表示矩阵第一行从左到右的数值。,问题描述,输入样例bincode.in51 0 0 1 0,问题描述,输出样例bincode.out0 0 0 1 1,问题描述,限制1=N=1000,解法一 猜测法,计算输入列中包含 0 的个数 k生成输出行：前k个为0，后N-k个为1思路：因为矩阵按字母序排序，所以0应该在前面。该算法不能保证正确，但对样例正确,0 0 0 1 10 0 1 1 0 0 1 1 0 01 0 0 0 11 1 0 0 0,解法二 穷举法,生成一个长度为N的全0序列按规则将其旋转生成N*N矩阵如果最后一列与输入相同，则输出开始的
9、序列。按字母序生成下一个长度为N的二进制序列，goto 2.,解法二 穷举法,显然这一算法不是最优的，但是它是正确的，因为它穷举了全部可能。,解法三 迭代法,初始化一个N行，最开始是0列的工作矩阵.将输入列放在当前工作矩阵左边，对行排序.如果矩阵列数小于N,goto 2.输出第一行,解法三 迭代法,例子（输入10010）1 010 00 100 0000 000 00 000 0010 000 01 001 0111 111 10 110 1000 101 11 011 110,解法三 迭代法,例子（输入10010）1 0001000 0001 10001 0001100010001 0011
10、 00011 0011000110011 0110 00110 0110011001100 1000 11000 1000101100110 1100 01100 11000输出：00011,解法三 迭代法,分析该算法所需计算时间O(N3)N次迭代，每次要对一个N*N的矩阵排序,解法三 迭代法,证明该算法的本质是逐一构造矩阵的前 I 列对于I=1,重新排序后显然成立对于IN，如果前I列就是矩阵的前I列，那么把最后一列加到前面，从序列的顺序来说，是正确的，重新对这I+1列排序保证了行顺序的正确性。,解法三 迭代法,分析一个值得注意的现象是：每次排序总是把开头是0的行按原来的先后次序移到前面，而把
11、开头是1的行按原来的先后次序移到后面。,1 0 0 0 10 0 0 1 10 0 1 1 0 0 1 1 0 01 1 0 0 0,0 0 0 1 10 0 1 1 0 0 1 1 0 01 0 0 0 11 1 0 0 0,解法四 线性算法,算法描述：1.计算输入列中0和1的个数，并用它们形成第一列.,解法四 线性算法,2.生成一个Next数组，使得数组中的i个0指向最后一列第i个0的行数，数组中的第j个1指向最后一列第j个1的行数.,解法四 线性算法,3.从第1行开始，按照Next指引的顺序 从k到Nextk,每次把该行最后一列的数字取出生成第一行的相应数字。,解法四 线性算法,例如 输
12、入 10010有3个0，2个1，所以第1列一定是00011,解法四 线性算法,例如 输入 100102.生成Next数组 输入列 Next10122003300541115104,解法四 线性算法,例如 输入 1 0 0 1 0 Next 2 3 5 1 43.沿着Next，根据 输入列，生成第一行 0 0 0 1 1,解法四 线性算法,证明对于序列（1）b1 b2 bN-1 bN，左旋一位变成（2）b2 bN-1 bN b1，我们只要知道（1）左旋后得到的（2）在矩阵中是哪一行，就可以根据该行第一列的值得到 b2，依次类推得到b3，b4，,解法四 线性算法,证明假设矩阵中两行都以0开始，则它
13、们左旋后，前后次序不变，所以在矩阵中以0开始的第1行，它的左旋后的序列在最后一列的第一个0的行。对1开始的行有同样的性质。,解法四 线性算法,证明例如 1 0 0 0 1 1 第1，2，3行以0 20 0 1 1 0 开始，左旋后0 30 1 1 0 0 到最后1列，但 41 0 0 0 1 前后顺序不变，51 1 0 0 0 所以是2，3，5,解法四 线性算法,证明该算法就是利用了这一性质，根据第1列和最后1列，直接算出第1行。,测试数据,20 组100 位 全1100位 全0100位 01011000位 0011,5位，10位，15位的小数据长度为300-1000的随机序列 13个,解题的一般步骤,理解题意，建立数学模型设计模型在计算机中表示的方法（数据结构）设计解决该问题的算法分析算法的时空效率编程实现测试程序的正确性和效率提交,Question&Answer,
