OpenJudge算法设计与分析习题解答.docx

1、硬币面值组合描述使用1角、2角、5角硬币组成 n 角钱。设1角、2角、5角的硬币各用了a、b、c个，列出所有可能的a, b, c组合。输出顺序为：先按c的值从小到大，若c相同则按b的值从小到大。输入一个整数n（1 = n = 100)，代表需要组成的钱的角数。输出输出有若干行，每行的形式为：i a b c第1列i代表当前行数（行数从001开始，固定3个字符宽度，宽度不足3的用0填充），后面3列a, b, c分别代表1角、2角、5角硬币的个数（每个数字固定12个字符宽度，宽度不足的在左边填充空格）。样例输入10样例输出001 10 0 0002 8 1 0003 6 2 0004 4 3 0005 2 4 0006 0 5 0007 5 0 1008 3 1 1009 1 2 1010 0 0 2源代码：#include#includeint main()int t=1;int i,j,k;int n;scanf(%d,&n);int A=n,B=n/2,C=n/5;for(i=0;i=C;i+)for(j=0;j=B;j+)for(k=0;k=A;k+)if(i*5+j*2+k*1=n)printf(%03d%12d%12d%12dn,t,k,j,i);t+; getchar(); return 0; 2、比赛排名描述5名运动员参加100米赛跑，各自对比赛结果进行了预测：A说：E是第1名。B说：我是第2名。C说：A肯定垫底。D说：C肯定拿不了第1名。E说：D应该是第1名。比赛结束后发现，只有获第1名和第2名的选手猜对了，E不是第2名和第3名，没有出现名次并列的情况。请编程判断5位选手各是第几名。输入无输出输出要求：按ABCDE的顺序输出5行，其中第1行是A的名次，第2行是B的名次，第3行是C的名次，第4行是D的名次，第5行是E的名次。样例输入样例输出源代码：#includeint main() printf(5n); printf(2n); printf(1n); printf(3n); printf(4n); return 0;3、鸡兔同笼描述一个笼子里面关了鸡和兔子（鸡有2只脚，兔子有4只脚，没有例外）。已经知道了笼子里面脚的总数a，问笼子里面至少有多少只动物，至多有多少只动物。输入一行，一个正整数a (a 32768)。输出一行，包含两个正整数，第一个是最少的动物数，第二个是最多的动物数，两个正整数用一个空格分开。如果没有满足要求的答案，则输出两个0，中间用一个空格分开。样例输入20样例输出5 10源代码：#include int main()int n; scanf(%d,&n);if(n % 4= 0)printf(%d %d,n/4,n/2);else if(n % 4!= 0&n % 2= 0)printf(%d %d,n/4 +1, n/2);elseprintf(0 0);return 0;4、谁是你的潜在朋友描述“臭味相投”这是我们描述朋友时喜欢用的词汇。两个人是朋友通常意味着他们存在着许多共同的兴趣。然而作为一个宅男，你发现自己与他人相互了解的机会并不太多。幸运的是，你意外得到了一份北大图书馆的图书借阅记录，于是你挑灯熬夜地编程，想从中发现潜在的朋友。首先你对借阅记录进行了一番整理，把N个读者依次编号为1,2,N，把M本书依次编号为1,2,M。同时，按照“臭味相投”的原则，和你喜欢读同一本书的人，就是你的潜在朋友。你现在的任务是从这份借阅记录中计算出每个人有几个潜在朋友。输入第一行两个整数N,M，2 = N ，M= 200。接下来有N行，第i(i = 1,2,N)行每一行有一个数，表示读者i-1最喜欢的图书的编号P(1=P=M)输出包括N行，每行一个数，第i行的数表示读者i有几个潜在朋友。如果i和任何人都没有共同喜欢的书，则输出“BeiJu”（即悲剧， ）样例输入4 52321样例输出1BeiJu1BeiJu源代码：#include #include int b 222 ;int a 222 ;int n, m;int main() scanf(%d%d, &n, &m); for(int i = 1; i = n; i+ ) scanf(%d, &a i ); b a i +; for( int i = 1; i = 2 ) printf(%dn, b a i - 1 ); return 0;5、称体重描述赵、钱、孙、李四个人中既有大人也有小孩，给他们称体重时发现，他们每个人的体重都不一样，且体重（单位：公斤）恰好是10的整数倍，且他们的体重都不高 于50公斤，已知赵、钱两人的体重之和恰好等于孙、李两人的体重之和；赵、李两人的体重之和大于孙、钱两人的体重之和，并且赵、孙俩人的体重之和还小于钱的体重。请编写一个程序，按照体重从小到大的顺序，打印出四人的姓氏的首字母和体重数。输入无输出打印出四人的姓氏的首字母（小写）和体重数（每人一行，姓名首字母和体重数之间用空格隔开）。样例输入无样例输出z 10q 20s 30l 40（以上输出仅用于说明格式）#include#includeint main() int a4,b4=1,2,3,4,c4=z,q,s,l; int i,j,t;for(a0=1;a0=5;a0+)for(a1=1;a1=5;a1+)for(a2=1;a2=5;a2+)for(a3=1;a3a1+a2)&(a0+a2a1)for(i=0;i4;i+)bi=ai; for(i=0;i4;i+)ai=bi;for(i=0;i4;i+) for(j=i+1;jbj) t=bi; bi=bj; bj=t; for(j=0;j4;j+)for(i=0;i4;i+)if(ai=bj)printf(%c %dn,ci,bj*10);getchar(); return 0; 6、比饭量描述3个人比饭量，每人说了两句话：A说：B比我吃的多，C和我吃的一样多B说：A比我吃的多，A也比C吃的多C说：我比B吃得多，B比A吃的多。事实上，饭量和正确断言的个数是反序的关系。请编程按饭量的大小输出3个人的顺序。输入无输入输出按照饭量大小输出3人顺序，比如：ABC样例输入无样例输出无#include#includeint main() int A,B,C; int a,b,c; for(A=1;A=3;A+) for(B=1;B=3;B+) for(C=1;CA)+(C=A); b=(AB)+(AC); c=(CB)+(BA); if( (AB&ab)|(A=B&a=b)|(Ab) + (AC&ac)|(A=C&a=c)|(Ac) + (Bc)|(B=C&b=c)|(BC&bb&ac) if(bc) printf(ABC); else printf(ACB);if(ba&bc) if(ac) printf(BAC); else printf(BCA);if(ca&cb) if(ab) printf(CAB); else printf(CBA); getchar(); return 0;7、求排列的逆序数描述在Internet上的搜索引擎经常需要对信息进行比较，比如可以通过某个人对一些事物的排名来估计他（或她）对各种不同信息的兴趣，从而实现个性化的服务。对于不同的排名结果可以用逆序来评价它们之间的差异。考虑1,2,n的排列i1，i2，in，如果其中存在j,k，满足 j ik， 那么就称(ij,ik)是这个排列的一个逆序。一个排列含有逆序的个数称为这个排列的逆序数。例如排列 263451 含有8个逆序(2,1),(6,3),(6,4),(6,5),(6,1),(3,1),(4,1),(5,1)，因此该排列的逆序数就是8。显然，由1,2,n 构成的所有n!个排列中，最小的逆序数是0，对应的排列就是1,2,n；最大的逆序数是n(n-1)/2，对应的排列就是n,(n-1),2,1。逆序数越大的排列与原始排列的差异度就越大。现给定1,2,n的一个排列，求它的逆序数。输入第一行是一个整数n，表示该排列有n个数（n = 100000)。第二行是n个不同的正整数，之间以空格隔开，表示该排列。输出输出该排列的逆序数。样例输入62 6 3 4 5 1样例输出8提示1. 利用二分归并排序算法（分治）；2. 注意结果可能超过int的范围，需要用long long存储。#include using namespace std;const int MAX_NUM = 100000 + 5;long long seqMAX_NUM;int N;long long ans;void reSeq(long long* seq, int lef, int righ) /用long long存储，避免结果超过int的范围 if(lef = righ) return ; int mid = lef + (righ - lef) / 2; reSeq(seq, lef, mid); reSeq(seq, mid + 1, righ); int totalSize = righ - lef + 1; long long tmptotalSize; int n = lef; int m = mid + 1; int i = 0; while(n = mid | m righ | (n = mid & seqn = seqm) tmpi+ = seqn+; else tmpi+ = seqm+; ans += mid - n + 1; i = lef; for(int j = 0; j totalSize; j+) seqi+ = tmpj; void reSeqNum(long long* seq, int n) reSeq(seq, 0, n - 1);int main() scanf(%d, &N); for(int i = 0; i N; i+) scanf(%ld, &seqi); ans = 0; reSeqNum(seq, N); printf(%ldn, ans); return 0;8、Grey码描述Grey码是一个长度为2n的序列，序列中无相同元素，且每个元素都是长度为n的二进制位串，相邻元素恰好只有1位不同。例如长度为23的格雷码为(000,001,011,010,110,111,101,100)。设计分治算法对任意的n值构造相应的Grey码。输入每个元素的长度值n。输出将所有相应的Grey码分行输出，即每一行输出一个二进制位串。样例输入3样例输出000001011010110111101100源代码：#include#includeint power(int base,int n) int i,p=1; for(i=1;i=n;+i) p=p*base; return p;void Grey(int a,int b,int *arr,int k)if(b=1)*(int*)arr+k*0+0)=0;/arr00=0;*(int*)arr+k*1+0)=1;/arr10=1;return ;elsefor(int i=0;ia/2;i+) *(int*)arr+k*i+b-1)=0;/arrib-1=0;*(int*)arr+k*(a-i-1)+b-1)=1;/arra-i-1b-1=1;Grey(a/2,b-1,(int *)arr,k);for(int i=a/2;ia;i+)for(int j=0;jb-1;j+)*(int*)arr+k*i+j)=*(int*)arr+k*(a-i-1)+j);/arrij=arra-i-1j;int main()int n;scanf(%d,&n);int m=(int)power(2,n);int arrmn;Grey(m,n,(int *)arr,n);for(int i=0;i=0;j-)printf(%d,arrij); printf(n); getchar();return 0;9、循环比赛描述设有N个选手的循环比赛。其中N=2M(2的M次方)，要求每名选手要与其他N-1名选手都赛一次，每名选手每天比赛一次，循环赛共进行N-1天，要求每天没有选手轮空。输入M输出表格形式的比赛安排表样例输入3样例输出1 2 3 4 5 6 7 8 2 1 4 3 6 5 8 73 4 1 2 7 8 5 64 3 2 1 8 7 6 55 6 7 8 1 2 3 46 5 8 7 2 1 4 37 8 5 6 3 4 1 28 7 6 5 4 3 2 1提示M的大小不会超过8源代码：#include#includevoid arrange(int k,int *a,int n)int t=1,temp=1;*(int*)a+k*0+0)=1;/a00=1;while(t=n)for(int i=0;itemp;i+)for(int j=0;jtemp;j+)*(int*)a+k*i+j+temp)=*(int*)a+k*i+j)+temp;/aij+temp=aij+temp;for(int i=0;itemp;i+)for(int j=0;jtemp;j+)*(int*)a+k*(i+temp)+j)=*(int*)a+k*i+j+temp);/ai+tempj=aij+temp;*(int*)a+k*(i+temp)+j+temp)=*(int*)a+k*i+j);/ai+tempj+temp=aij;temp*=2;t+; int main() int n;scanf(%d,&n);int k=1;for(int i=0;in;+i)k=2*k; int akk; arrange(k,(int *)a,n); for(int i=0;ik;i+) for(int j=0;jk;j+) printf(%d,aij);printf(n);getchar(); return 0; 10、棋盘覆盖问题描述在一个2k2k个方格组成的棋盘中，若恰有一个方格与其他方格不同，称该方格为特殊方格，且称该棋盘为特殊棋盘。显然，特殊方格在棋盘中出现的位置有4k种情形，因而有4k种不同的棋盘，如图1所示是k=2时16种棋盘中的一个。在棋盘覆盖问题中，要求用图2所示的4种不同形状的L型骨牌覆盖给定棋盘上除特殊方格以外的所有方格，且任何两个L型骨牌不得重叠覆盖。输入对每一个测试例有2行，第一行是k（1=k=10），第二行是特殊方格所在的位置坐标x,y（0=x，y1024）。输出边长为2的k次方的方阵，特殊方格的编号为0，所有L型骨牌从1开始编号，数据之间的间隔是空格。样例输入20 1样例输出2 0 3 32 2 1 34 1 1 54 4 5 5提示按分治策略进行算法设计。#include#includeint t=0;int board100100;void ChessBoard(int tr,int tc,int dr,int dc,int size)int s,t1; if(size=1) return ; t1=+t;s=size/2;if(drtr+s&dctc+s) ChessBoard(tr,tc,dr,dc,s); elseboardtr+s-1tc+s-1=t1;ChessBoard(tr,tc,tr+s-1,tc+s-1,s);if(dr=tc+s) ChessBoard(tr,tc+s,dr,dc,s); elseboardtr+s-1tc+s=t1;ChessBoard(tr,tc+s,tr+s-1,tc+s,s);if(dr=tr+s&dc=tr+s&dc=tc+s) ChessBoard(tr+s,tc+s,dr,dc,s); elseboardtr+stc+s=t1;ChessBoard(tr+s,tc+s,tr+s,tc+s,s); int main() int n,size=1; scanf(%d,&n); for(int i=0;in;i+) size=size*2; int dr,dc; scanf(%d%d,&dr,&dc); ChessBoard(0,0,dr,dc,size); for(int i=0;isize;i+) for(int j=0;jsize;j+) printf(%d ,boardij); printf(n); getchar(); return 0; 11、输油管道问题描述某石油公司计划建造一条由东向西的主输油管道。该管道要穿过一个有n 口油井的油田。从每口油井都要有一条输油管道沿最短路经(或南或北)与主管道相连。如果给定n口油井的位置,即它们的x 坐标（东西向）和y 坐标（南北向）,应如何确定主管道的最优位置,即使各油井到主管道之间的输油管道长度总和最小的位置?证明可在线性时间内确定主管道的最优位置。要求给定n口油井的位置,计算各油井到主管道之间的输油管道最小长度总和。输入由文件提供输入数据，文件第一行是油井数n，1=n=10000。接下来n行是油井的位置，每行两个整数x和y，-10000=x,y=10000。输出将结果输出到文件中，文件第一行中的数是油井到主管道之间的输油管道最小长度总和。样例输入51 22 21 33 -23 3样例输出6提示按分治策略进行算法设计。源代码：#include #include #include using namespace std; struct node int x,y; num200000; bool cmp(node a,node b) return a.yb.y; int main() int t; scanf(%d,&t); int i,j; for(i=0;it;i+) scanf(%d%d,&numi.x,&numi.y); int ans; sort(num,num+t,cmp); if(t%2=1) ans=0; int zong=numt/2.y; for(i=0;it;i+) ans+=abs(numi.y-zong); else int zong=numt/2.y+numt/2-1.y; zong/=2; ans=0; for(i=0;it;i+) ans+=abs(numi.y-zong); printf(%dn,ans); return 0; 12、0/1背包问题描述给定n种物品和一个背包，物品i(1in)的重量是wi，其价值为vi，背包的容量为C，对每种物品只有两种选择：装入背包或者不装入背包。如何选择装入背包的物品，使得装入背包中物品的总价值最大？输入输入包含一组或多组测试例。每组测试例的第一行是物品的数量n和背包的容量C，之后的n行是每个物品的重量及其价值。输出输出第一行是装入背包中物品的总价值，后面n行是各个物品装入背包的情况。样例输入5 102 62 36 55 44 6样例输出1511001源代码：#include #include using namespace std;int dp1101010;int n, c, ans110;int w110, v110;void print()int i, j, k; k=c; for(i=n; i=1; i-)if(dpik!=dpi-1k)ansi=1;k=k-wi;elsereturn;int main()int i, j, k;scanf(%d%d, &n, &c);for(i=1; i=n; i+)scanf(%d%d, &wi, &vi);for(i=1; i=n; i+)for(j=1; j=wi)dpij=max(dpi-1j-wi+vi, dpij);printf(%dn, dpnc);print();for(i=1; i=n; i+) printf(%dn, ansi);return 0;13、最少硬币问题描述设有n种不同面值的硬币，各硬币的面值存于数组T1:n中。现要用这些面值的硬币来找钱。可以使用的各种面值的硬币个数存于数组Coins1:n中。对任意钱数0m20001，设计一个用最少硬币找钱m的方法。对于给定的1n10，硬币面值数组T和可以使用的各种面值的硬币个数数组Coins，以及钱数m，0m20001，计算找钱m的最少硬币数。输入由文件提供输入数据，文件的第一行中只有1个整数给出n的值，第2行起每行2 个数，分别是Tj和Coinsj。最后1行是要找的钱数m。输出将计算出的最少硬币数输出到文件中。问题无解时输出-1。样例输入31 32 35 318样例输出5提示运用动态规划法进行算法设计并编程实现。源代码：#include #includeusing namespace std;int w110, v110;int dp11020010;int n, m;void init()for(int i=0; i110; i+)for(int j=0; j20010; j+)dpij=2000000000;int main()int i, j, k;int t, x, cnt=1;scanf(%d, &n);for(i=1; i=n; i+)scanf(%d%d, &t, &x);for(j=1; j=x; j+)wcnt=t;vcnt=1;cnt+;scanf(%d, &m);init();for(i=0; icnt; i+)/cnt+;dpi0=0;for(i=1; icnt; i+)for(j=1; j=wi&dpi-1j-wi!=2000000000)dpij=min(dpij, dpi-1j-wi+1);if(dpcnt-1m=2000000000)printf(-1);elseprintf(%d, dpcnt-1m);return 0;14、矩阵连乘描述给定n个矩阵A1,A2,.,An，考察这n个矩阵的连乘积A1A2.An。由于矩阵乘法满足结合律，故计算矩阵的连乘积可以有许多不同的计算次序，这种计算次序可以用加括号的方式来确定。矩阵连乘积的计算次序与其计算量有密切关系。例如，考察计算3个矩阵A1,A2,A3连乘积的例子。设这3个矩阵的维数分别为10*100，100*5，和5*50。若按(A1A2)A3计算，3个矩阵连乘积需要的数乘次数为10*100*5+10*5*50 = 7500。若按A1(A2A3)计算，则总共需要100*5*50+10*100*50 = 75000次数乘。现在你的任务是对于一个确定的矩阵连乘方案，计算其需要的数乘次数。输入输入数据由多组数据组成。每组数据格式如下：第一行是一个整数n (1n26)，表示矩阵的个数。接下来n行，每行有一个大写字母，表示矩阵的名字，后面有两个整数a,b，分别表示该矩阵的行数和列数，其中1a,b100。第n+1行是一个矩阵连乘的表达式，由括号与大写字母组成，没有乘号与多余的空格。如果表达式中没有括号则按照从左到右的顺序计算，输入的括号保证能够配对。输出对于每组数据，输出仅一行包含一个整数，即将该矩阵连乘方案需要的数乘次数。如果运算过程中出现不满足矩阵乘法法则的情况（即左矩阵列数与右矩阵的行数不同），则输出“error”。样例输入3A 10 100 B 100 5 C 5 50 A(BC) 样例输出75000源代码：# include # include # include # include # include # include using namespace std;int n, ans;string exp, str;int x, y;struct nodeint x,y;node s200;int flage;stack ope;stack v;string change(string t)int length=t.length();string des=;for(int i=0; ilength-1; i+)if(isalpha(ti)if(ti+1=)des=des+ti;elsedes=des+ti+*;else if(ti=()des=des+ti;elseif(ti+1=)des=des+ti;elsedes=des+ti+*;des=des+tlength-1+=;return des;node calc(node a, node b)if(a.y!=b.x)flage=1;node t;ans=ans+a.x*a.y*b.y;t.x=a.x;t.y=b.y;return t;char compare(char i, char j)if(i=)if(j!=)return ;elsereturn =;if(i=()if(j=)return =;elsereturn ;if(i=*)if(j=()return ;int main()int i, j, k;string e;while(cinn)for(i=1; istrxy;sstr0.x=x;sstr0.y=y;cine;flage=0;ans=0;exp=change(e);while(!ope.empty()ope.pop();while(!v.empty()v.pop();ope.push(=);int l=exp.length();for(k=0; k=l-1; )if(isalpha(expk)v.push(sexpk);k+;elseif(compare(ope.top(), expk)=)ope.pop();k+;else if(compare(ope.top(), expk)=)ope.push(expk);k+;elsenode a=v.top();v.pop();node b=v.top();v.pop();v.push(calc(b, a);ope.pop();if(!flage)coutansendl;elsecouterrorendl;return 0;15、多边形游戏描述一个多边形，开始有n个顶点。每个顶点被赋予一个正整数值，每条边被赋予一个运算符“+”或“*”。所有边依次用整数从1到n编号。现在来玩一个游戏，该游戏共有n步：第1步，选择一条边，将其删除随后n-1步，每一步都按以下方式操作：（1）选择一条边E以及由E连接着的2个顶点v1和v2； (2）用一个新的顶点取代边E以及由E连接着的2个顶点v1和v2，将顶点v1和v2的整数值通过边E上的运算得到的结果值赋给新顶点。最后，所有边都被删除，只剩一个顶点，游戏结束。游戏得分就是所剩顶点上的整数值。那么这个整数值最大为多少？输入第一行为多边形的顶点数n（n 20），其后有n行，每行为一个整数和一个字符，整数为顶点上的正整数值，字符为该顶点到下一个顶点间连边上的运算符“+”或“*”（最后一个字符为最后一个顶点到第一个顶点间连边上的运算符）。输出输出仅一个整数，即游戏所计算出的最大值。样例输入44 *5 +5 +3 +样例输出70提示小规模问题可不必用动态规划方法编程求解，仅用递归就可以求解。计算中不必考虑计算结果超出整数表达范围的问题，给出的数据能保证计算结果的有效性。在给的例子中，计算过程为(3+4)*(5+5)=70。源代码：#include#include#include #includeusing namespace std;typedef long long int ll;const ll inf=20000000000000;int n;string s;char op110110;ll dp110110, dpmin110110;ll a110;ll calc(ll a, ll b, char ch)if(ch=*)return a*b;else if(ch=+)return a+b;elsereturn 0;int main()int i, j, k, t;cinn;for(i=1; it;ai=t;cins;opii+1=s0; for(i=n+1; i=2*n; i+) ai=ai-n; / for(i=1; i=2*n; i+)/ printf(%d , ai);/printf(n); for(i=n+1; i2*n; i+) opii+1=opi-ni+1-n;/for(i=1; i2*n; i+)/ printf(%c , opii+1);/printf(n);for(i=1; i=2*n; i+)/初始化为最小值 for(j=i; j=2*n; j+)dpij=-inf;dpminij=inf;for(i=1; i=2*n; i+)dpii=ai;dpminii=ai;for(i=1; i2*n; i+)dpii+1=calc(ai, ai+1, opii+1);dpminii+1=calc(ai, ai+1, opi