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

第二届新生程序设计竞赛解题报告BYACM集训队2010-06-06A:进制转换II题目的意思很明确，输入一个1000位以内的二进制数，将其转换为十六进制并输出。我们都知道，要把二进制转换为十六进制只需要将二进制数四位四位的转换就行了。例如：10100100把这个二进制数分成两部分，前面四位一部分，后面四位一部分。前面四位转换为十六进制是A，后面四位转换为十六进制是4，所以输出A4就行了。其中注意一些特殊的数据（位数不是4的倍数的时候）。如输入101100，结果是2C；因为输入的数据可以看成00101100，根据前面的方法四位四位的分开转换成十六进制就行了。B:同花顺简单题.345678910JQKA2。但“小2”不能用于同花顺。看清规则就OK了。C:两圆外公切线之交给定两圆的坐标和半径，求两圆的两条外公切线之交点。数学知识：相似比(x-x1)/(x-x2)=r1/r2x=(x1*r2-r1*x2)/(r2-r1);(y-y1)/(y-y2)=r1/r2y=(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].fE:MonkyandBananaII题目的意思是有一个懒猴子在树林里摘香蕉，告诉你香蕉的串数n及香蕉的高度a[i]，还有猴子站在地上能够够到的最大高度小于h,以及一个高度为b的箱子，求猴子最多能够摘到多少串香蕉。（有多组数据）设初值k=0,利用循环,如果(h+aa[i])则k++.F：单词串串烧题目大意：给定一个4*4的方格，求能否在这个方格中找到所给的单词，其中每个方格不能重复走。这是一道搜索题，其中在每个位置是它都可能有8个方向可走，即上、下、左、右，左上、左下、右上、右下，设当前位置为m,n;向每个方向走即加上（-1，0），（1，0），（0，-1），（0，1），（-1，-1），（-1，1），（1，-1），（1，1）；不能重复走只要在每次走过一格后标记一下。用一个参数记录走过的步数，当走过的步数和单词的长度相等且当前位置的字母等于单词的最后一个字母时就表示找到了这个单词。G水题GCD设计一个计算器，能够计算分数的加、减、乘、除，并将结果简化到最简的分数形式，比如100/8要进一步简化为25/2，而20/2要进一步简化为10/1，0/100要简化为0/1。挺水的，需要处理的也就是数据的溢出和gcd的编码问题。题目要求的数据规模不大-2000000000=x,y=2000000000，在oj上用int类型可是可以的，但是两个这样的数相乘就会溢出，所以请选择用64位，并注意gcd的编码，也就是求最大公约数的问题分数的加减乘除就不用多说了吧，大家都是成年人Gcd函数的代码，请注意返回值参数和形参用64位__int64gcd(__int64a,__int64b){if(b==0){returna;}returngcd(b,a%b);}H:{A}∩{B}输入T组数据，第一组数据的个数n和n个数，第二组数据的个数m和m个数，找两组数据中相同数据的个数。（注意每组数据都是递减的）这道题主要的难点是数据太大，每个数都比较的话就会超时的，具体循环：p=q=0;for(i=p;in;i++){for(j=q;jm;j++){if(a[i]b[j]){p++;break;}if(a[i]==b[j])k++;if(a[i]b[j])q++;}}这样写就会省去不少时间，就不会超时了。I：取数问题动态规划的题目。动态转移方程：IfW_m+S(m+1)=F(m+1),thenF(m)=S(m+1)+W_mandS(m)=F(m+1)IfW_m+S(m+1)F(m+1),thenF(m)=F(m+1)andS(m)=S(m+1)当前W_m表示第m个数，S（m+1）表示乙取到m+1个数的时候的最大和。F（m+1）表示甲取到m+1个数的时候的最大和。J:Email地址看清楚题目的限制条件，自己考虑全面一点就很容易就做出来了。条件1：email里面必须要有@，用户名和域名至少要有1个字符条件2：用户名和域名只能合法字符构成，合法字符是大小写字母，数字，下划线和点。条件3：点的前后都必须要有合法字符，其中@不算合法字符.只要满足这三个条件的输入就输出Yes，否者输出No。在判断点的前后是否有合法字符时，可以加入一个标志数组，用来标记字符对应位置是否合法。请看下面例子：charemail[101];intflag[100];其中email是用来存储输入字符串的flag则是用于标记字符串中对应字符是否合法。[e-mail]11111100111101110111判断点的前后是否有合法字符只需要看flag数组前面和后面是否为1就行了。当然也可以用其他方法。