第二届新生程序设计竞赛解题报告.pptVIP

第二届新生程序设计竞赛解题报告 A: 进制转换II 题目的意思很明确，输入一个1000位以内的二进制数，将其转换为十六进制并输出。 我们都知道，要把二进制转换为十六进制只需要将二进制数四位四位的转换就行了。例如： 1010 0100 把这个二进制数分成两部分，前面四位一部分，后面四位一部分。前面四位转换为十六进制是A，后面四位转换为十六进制是4，所以输出A4就行了。 其中注意一些特殊的数据（位数不是4的倍数的时候）。如输入101100，结果是2C；因为输入的数据可以看成0010 1100，根据前面的方法四位四位的分开转换成十六进制就行了。 C:两圆外公切线之交 给定两圆的坐标和半径，求两圆的两条外公切线之交点。 数学知识：相似比 (x-x1)/(x-x2)=r1/r2 x=(x1*r2-r1*x2)/(r2-r1); (y-y1)/(y-y2)=r1/r2 y=(y1*r2-r1*y2)/(r2-r1);  D:精明的采购员John 动态规划 dp[i][j]=dp[i-1][w]+w*(node[i].x-node[i-1].x)+(j-w)*node[i].c; i:哪个摊位 J:到该摊位收集的蔬菜重量 Dp[i][j]表示费用 贪心： 根据什么来贪心 （1）和： (e-node[i].x)*node[i].f+node[i].c*node[i].f （2）比率： ((e-node[i].x)*node[i].f+node[i].c*node[i].f)/node[i].f E: Monky and Banana II 题目的意思是有一个懒猴子在树林里摘香蕉，告诉你香蕉的串数n及香蕉的高度a[i]，还有猴子站在地上能够够到的最大高度小于h,以及一个高度为b的箱子，求猴子最多能够摘到多少串香蕉。（有多组数据） 设初值k=0,利用循环,如果(h+a>a[i]) 则k++. F：单词串串烧 G 水题GCD 设计一个计算器，能够计算分数的加、减、乘、除，并将结果简化到最简的分数形式，比如100/8要进一步简化为25/2，而20/2要进一步简化为10/1，0/100要简化为0/1。 H : {A}∩{B} I：取数问题 J: Email地址 * * BY ACM集训队 2010-06-06 B:同花顺 简单题. 3<4<5<6<7<8<9<10<J<Q<K<A<2。但“小2”不能用于同花顺。 看清规则就OK了。 题目大意：给定一个4*4的方格，求能否在这个方格中找到所给的单词，其中每个方格不能重复走。 这是一道搜索题，其中在每个位置是它都可能有8个方向可走，即上、下、左、右，左上、左下、右上、右下 ，设当前位置为m,n;向每个方向走即加上（-1，0），（1，0），（0，-1），（0，1），（-1，-1），（-1，1），（1，-1），（1，1）；不能重复走只要在每次走过一格后标记一下。用一个参数记录走过的步数，当走过的步数和单词的长度相等且当前位置的字母等于单词的最后一个字母时就表示找到了这个单词。 挺水的，需要处理的也就是数据的溢出和gcd的编码问题。 题目要求的数据规模不大 -2000000000<=x,y<=2000000000 ， 在oj上用int类型可是可以的，但是两个这样的数相乘就会溢出，所以请选择用64位，并注意gcd的编码，也就是求最大公约数的问题分数的加减乘除就不用多说了吧，大家都是成年人 Gcd函数的代码，请注意返回值参数和形参用64位 __int64 gcd(__int64 a, __int64 b) { if(b==0) { return a; } return gcd(b, a%b); } 输入T组数据，第一组数据的个数n和n个数，第二组数据的个数m和m个数， 找两组数据中相同数据的个数。（注意每组数据都是递减的） 这道题主要的难点是数据太大，每个数都比较的话就会超时的，具体循环： p=q=0; for(i=p;i<n;i++) { for(j=q;j<m;j++) { if(a[i]>b[j]) {p++;break;} if(a[i]==b[j]) k++; if(a[i]<b[j]) q++; } } 这样写就会省去不少时间，就不会超时了。 动态规划的题目。 动态转移方程： If W_m+S(m+1) >= F(m+1), then F(m)=S(m+1)+W_m and S(m)=F(m+1) If W_m+S(m+1) < F(m+1), then