蓝桥杯练习题库 2基础练习之VIP题

基础练习阶乘计算时间限制：1.0s内存限制：512.0MB查看参考代码锦囊1数组。锦囊2使用数组来保存一个整数，按手算的方法处理。问题描述输入一个正整数n，输出n!的值。其中n!=1*2*3*…*n。算法描述n!可能很大，而计算机能表示的整数范围有限，需要使用高精度计算的方法。使用一个数组A来表示一个大整数a，A[0]表示a的个位，A[1]表示a的十位，依次类推。将a乘以一个整数k变为将数组A的每一个元素都乘以k，请注意处理相应的进位。首先将a设为1，然后乘2，乘3，当乘到n时，即得到了n!的值。输入格式输入包含一个正整数n，n=1000。输出格式输出n!的准确值。样例输入10样例输出3628800本题的C参考代码如下：#includestdio.h#defineN10000intmain(){inta[N]={1};intk=0,l=1,n;inti,j;scanf(%d,&n);for(i=1;i=n;i++){for(j=0;jl;j++){a[j]=a[j]*i+k;k=a[j]/10000;a[j]=a[j]%10000;}if(k){a[j]=k;l++;k=0;}}printf(%d,a[l-1]);for(i=l-2;i=0;i--)printf(%04d,a[i]);printf(\n);return0;}基础练习高精度加法时间限制：1.0s内存限制：512.0MB查看参考代码锦囊1数组。锦囊2使用数组来保存一个整数，按手算的方法处理。问题描述输入两个整数a和b，输出这两个整数的和。a和b都不超过100位。算法描述由于a和b都比较大，所以不能直接使用语言中的标准数据类型来存储。对于这种问题，一般使用数组来处理。定义一个数组A，A[0]用于存储a的个位，A[1]用于存储a的十位，依此类推。同样可以用一个数组B来存储b。计算c=a+b的时候，首先将A[0]与B[0]相加，如果有进位产生，则把进位（即和的十位数）存入r，把和的个位数存入C[0]，即C[0]等于(A[0]+B[0])%10。然后计算A[1]与B[1]相加，这时还应将低位进上来的值r也加起来，即C[1]应该是A[1]、B[1]和r三个数的和．如果又有进位产生，则仍可将新的进位存入到r中，和的个位存到C[1]中。依此类推，即可求出C的所有位。最后将C输出即可。输入格式输入包括两行，第一行为一个非负整数a，第二行为一个非负整数b。两个整数都不超过100位，两数的最高位都不是0。输出格式输出一行，表示a+b的值。样例输入201001222010012212345678902010012220100122样例输出20100122203011233454668012#includestdio.h#includestring.h#includestdlib.hvoidf(chara[],charb[]){intw=200,i,j,la,lb;la=strlen(a);lb=strlen(b);charc[200];for(i=la;iw;i++)a[i]=48;for(i=lb;iw;i++)b[i]=48;a[w-1]=0;b[w-1]=0;for(i=0;ila;i++)c[i]=a[i];for(i=0;iw-1-la;i++)a[i]=48;j=0;for(i=w-1-la;iw-1;i++){a[i]=c[j];j++;}for(i=0;ilb;i++)c[i]=b[i];for(i=0;iw-1-lb;i++)b[i]=48;j=0;for(i=w-1-lb;iw-1;i++){b[i]=c[j];j++;}for(i=w;i=0;i--){j=a[i]+b[i]-96;if(j9)a[i-1]=a[i-1]+j/10;c[i]=j%10+48;}c[w-1]=0;for(i=0;iw;i++)if(c[i]!='0')break;for(;iw-1;i++)printf(%c,c[i]);printf(\n);}intmain(){chara[200],b[200];gets(a);gets(b);f(a,b);return0;}基础练习Huffuman树时间限制：1.0s内存限制：512.0MB查看参考代码锦囊1贪心算法。锦囊2按题目要求处理即可。问题描述Huffman树在编码中有着广泛的应用。在这里，我们只关心Huffman树的构造过程。给出一列数{pi}={p0,p1,…,pn-1}，用这列数构造Huffman树的过程如下：1.找到{pi}中最小的两个数，设为pa和pb，将pa和pb从{pi}中删除掉，然后将它们的和加入到{pi}中。这个过程的费用记为pa+pb。2.重复步骤1，直到{pi}中只剩下一个数。在上面的操作过程中，把所有的费用相加，就得到了构造Huffman树的总费用。本题任务：对于给定的一个数列，现在请你求出用该数列构造Huffman树的总费用。例如，对于数列{pi}={5,3,8,2,9}，Huffman树的构造过程如下：1.找到{5,3,8,2,9}中最小的两个数，分别是2和3，从{pi}中删除它们并将和5加入，得到{5,8,9,5}，费用为5。2.找到{5,8,9,5}中最小的两个数，分别是5和5，从{pi}中删除它们并将和10加入，得到{8,9,10}，费用为10。3.找到{8,9,10}中最小的两个数，分别是8和9，从{pi}中删除它们并将和17加入，得到{10,17}，费用为17。4.找到{10,17}中最小的两个数，分别是10和17，从{pi}中删除它们并将和27加入，得到{27}，费用为27。5.现在，数列中只剩下一个数27，构造过程结束，总费用为5+10+17+27=59。输入格式输入的第一行包含一个正整数n（n=100）。接下来是n个正整数，表示p0,p1,…,pn-1，每个数不超过1000。输出格式输出用这些数构造Huffman树的总费用。样例输入553829样例输出59#includestdio.htypedefstruct{inta[100];intlen;}huf;intsum=0;intdel(huf*in,intt){inti,j;for(i=0;iin-len&&in-a[i]!=t;i++);for(;iin-len-1;i++)in-a[i]=in-a[i+1];in-len--;return1;}intadd(huf*in,intt){in-a[in-len]=t;in-len++;}intfind_two_mins(huf*in){inti,j,t;intmina,minb;for(i=0;iin-len-1;i++)for(j=i+1;jin-len;j++)if(in-a[i]in-a[j]){t=in-a[i];in-a[i]=in-a[j];in-a[j]=t;}mina=in-a[0];minb=in-a[1];del(in,mina);del(in,minb);add(in,mina+minb);returnmina+minb;}intmain(){hufin;inti,j,n;scanf(%d,&n);in.len=n;for(i=0;in;i++)scanf(%d,&in.a[i]);while(1){if(in.len==2){sum=sum+in.a[0]+in.a[1];break;}sum+=find_two_mins(&in);}printf(%d,sum);return0;}#includeiostream#includequeueusingnamespacestd;priority_queueint,vectorint,greaterintpq;//构造从小到大的优先队列intmain(){intn;cinn;while(!pq.empty())pq.pop();intx,s;for(inti=0;in;i++){cinx;pq.push(x);}intsum=0;while(pq.size()1){s=pq.top();pq.pop();s+=pq.top();pq.pop();sum+=s;pq.push(s);}coutsumendl;}基础练习2n皇后问题时间限制：1.0s内存限制：512.0MB查看参考代码锦囊1搜索算法。锦囊2先搜索n皇后的解，在拼凑成2n皇后的解。问题描述给定一个n*n的棋盘，棋盘中有一些位置不能放皇后。现在要向棋盘中放入n个黑皇后和n个白皇后，使任意的两个黑皇后都不在同一行、同一列或同一条对角线上，任意的两个白皇后都不在同一行、同一列或同一条对角线上。问总共有多少种放法？n小于等于8。输入格式输入的第一行为一个整数n，表示棋盘的大小。接下来n行，每行n个0或1的整数，如果一个整数为1，表示对应的位置可以放皇后，如果一个整数为0，表示对应的位置不可以放皇后。输出格式输出一个整数，表示总共有多少种放法。样例输入41111111111111111样例输出2样例输入41011111111111111样例输出0#includestdio.hinta[9][9],n,sum;introw1[9],diagl1[17],diagr1[17],row2[9],diagl2[17],diagr2[17];voiddfs2(inti){intj;if(i==n+1){sum++;return;}for(j=1;j=n;j++){if(a[i][j]==1&&row2[j]!=0&&diagl2[n-i+j]!=0&&diagr2[i+j]!=0){a[i][j]=0;row2[j]=0;diagl2[n-i+j]=0;diagr2[i+j]=0;dfs2(i+1);row2[j]=1;diagl2[n-i+j]=1;diagr2[i+j]=1;a[i][j]=1;}}}voiddfs1(inti){intj,h,r;if(i==n+1){for(h=1,r=1;r=n;r++){if(a[1][r]==1){a[1][r]=0;row2[r]=0;diagl2[n-h+r]=0;diagr2[h+r]=0;dfs2(h+1);row2[r]=1;diagl2[n-h+r]=1;diagr2[h+r]=1;a[1][r]=1;}}}for(j=1;j=n;j++){if(a[i][j]==1&&row1[j]!=0&&diagl1[n-i+j]!=0&&diagr1[i+j]!=0){a[i][j]=0;row1[j]=0;diagl1[n-i+j]=0;diagr1[i+j]=0;dfs1(i+1);row1[j]=1;diagl1[n-i+j]=1;diagr1[i+j]=1;a[i][j]=1;}}}intmain(){inti,j;while(scanf(%d,&n)!=EOF){sum=0;for(i=1;i=n;i++)for(j=1;j=n;j++)scanf(%d,&a[i][j]);for(i=1;i=n;i++)row1[i]=row2[i]=1;for(i=1;i=2*n;i++)diagl1[i]=diagr1[i]=diagl2[i]=diagr2[i]=1;for(i=1,j=1;j=n;j++){if(a[1][j]==1){a[1][j]=0;row1[j]=0;diagl1[n-i+j]=0;diagr1[i+j]=0;dfs1(i+1);row1[j]=1;diagl1[n-i+j]=1;diagr1[i+j]=1;a[1][j]=1;}}printf(%d\n,sum);}return0;}#includecstdiousingnamespacestd;intn;intsum;boolg[9][9];boolwh[9];boolw