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

1、1、硬币面值组合描述使用1角、2角、5角硬币组成 n角钱。组合。设1角、2角、5角的硬币各用了 a、b、c个，列出所有可能的 a, b, c输出顺序为：先按 c的值从小到大，若c相同则按b的值从小到大。输入一个整数n （1 = n = 100），代表需要组成的钱的角数。输出输出有若干行，每行的形式为:i a b c3的用0填充），12个字符宽度，第1列i代表当前行数（行数从001开始，固定3个字符宽度，宽度不足后面3列a, b, c分别代表1角、2角、5角硬币的个数（每个数字固定 宽度不足的在左边填充空格）。样例输入10样例输出006050007501008311009121010 0 0 2

2、源代码：#in clude#in cludeint mai n()int t=1;int i,j,k;int n;scan f(%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* 仁=门)prin tf(%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 应该是第

3、 1 名。比赛结束后发现，只有获第 1 名和第 2 名的选手猜对了， E 不是第 2 名和第 3 名，没有 出现名次并列的情况。请编程判断 5 位选手各是第几名。输入无输出输出要求：按 ABCDE 的顺序输出 5 行，其中第 1 行是 A 的名次，第 2 行是 B 的名次， 第 3 行是 C 的名次，第 4 行是 D 的名次，第 5 行是 E 的名次。样例输入样例输出 源代码： #include int main()printf(5n); printf(2n);printf(1n);printf(3n);printf(4n); return 0;3 、鸡兔同笼描述一个笼子里面关了鸡和兔子（鸡有

4、2 只脚，兔子有 4 只脚，没有例外）。已经知道了笼子里面脚的总数 a ，问笼子里面至少有多少只动物，至多有多少只动物。输入一行，一个正整数a (a 32768)输出一行，包含两个正整数，第一个是最少的动物数， 第二个是最多的动物数， 两个正整数用一 个空格分开。如果没有满足要求的答案，则输出两个0,中间用一个空格分开。样例输入20样例输出5 10源代码：#i nclude int mai n()int n;sca nf(%d,&n);if(n % 4= 0)prin tf(%d %d, n/4, n/2);else if(n % 4!= 0&n % 2= 0)prin tf(%d %d, n

5、/4 +1, n/2);elseprin tf(0 0);return 0;4、谁是你的潜在朋友描述臭味相投”一一这是我们描述朋友时喜欢用的词汇。两个人是朋友通常意味着他们存在着许多共同的兴趣。然而作为一个宅男， 你发现自己与他人相互了解的机会并不太多。幸运的是，你意外得到了一份北大图书馆的图书借阅记录，于是你挑灯熬夜地编程， 想从中发现潜在的朋友。首先你对借阅记录进行了一番整理，把 N个读者依次编号为1,2,N , 号为1,2,M。同时，按照 臭味相投”的原则，和你喜欢读同一本书的人, 朋友。你现在的任务是从这份借阅记录中计算出每个人有几个潜在朋友。输入第一行两个整数 N,M , 2 = N

6、 , M= 200 。接下来有 N行，第i(i =行有一个数，表示读者i- 1最喜欢的图书的编号 P(1=P=M)输出包括N行，每行一个数，第i行的数表示读者i有几个潜在朋友。如果i同喜欢的书，则输出“BeiJu”(即悲剧，A A )把M本书依次编就是你的潜在1,2,N)行每一和任何人都没有共样例输入4 52321样例输出1BeiJu1BeiJu源代码：#i nclude #in clude int b 222 ;int a 222 ;int n, m;int mai n()scan f(%d%d, &n, & m);for(i nt i = 1; i = n; i+ )scanf(%d, &

7、a i );b a i +;for( int i = 1; i = 2 )prin tf(%dn, b a i - 1 );return 0;5、称体重描述赵、钱、孙、李四个人中既有大人也有小孩，给他们称体重时发现，他们每个人的体重都不一样，且体重(单位：公斤)恰好是 10的整数倍，且他们的体重都不高于50公斤，已知赵、钱两人的体重之和恰好等于孙、李两人的体重之和；赵、李两人的体重之和大于孙、钱两人的体重之和，并且赵、孙俩人的体重之和还小于钱的体重。请编写一个程序，按照体重从小到大的顺序，打印出四人的姓氏的首字母和体重数。输入无输出打印出四人的姓氏的首字母(小写)和体重数(每人一行， 姓名首字

8、母和体重数之间用空格隔开)。样例输入无样例输出z 10q 20s 30l 40（以上输出仅用于说明格式）#in clude#in cludeint mai n()int a4,b4=1,2,3,4,c4=z,q,s,T;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+

9、)for(i=0;i4;i+)if(ai=bj)prin tf(%c %dn,ci,bj*10);getchar();return 0;6、比饭量描述3个人比饭量，每人说了两句话：A说：B比我吃的多，C和我吃的一样多B说：A比我吃的多，A也比C吃的多C说：我比B吃得多，B比A吃的多。 事实上，饭量和正确断言的个数是反序的关系。 请编程按饭量的大小输出 3个人的顺序。输入无输入输出按照饭量大小输出 3人顺序，比如：ABC样例输入无样例输出无#in clude#in cludeint mai n()int A,B,C; int a,b,c; for(A=1;A=3;A+) for(B=1;B=3;

10、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 、求排列的逆序数描述在 Inter

11、net 上的搜索引擎经常需要对信息进行比较， 比如可以通过某个人对一些事物的排名来估计他(或她)对各种不同信息的兴趣，从而实现个性化的服务。对于不同的排名结果可以用逆序来评价它们之间的差异。考虑1,2,n的排列i1 i2 ,in，如果其中存在j,k，满足j i k,那么就称(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

12、;最大的逆序数是n(n-1)/2，对应的排列就是 n,(n- 1),2,1。逆序数越大的排列与原始排列的差异度就越大。现给定1,2,n的一个排列，求它的逆序数。输入第一行是一个整数 n ,表示该排列有n个数(n = 100000)第二行是n个不同的正整数，之间以空格隔开，表示该排列。输出输出该排列的逆序数。样例输入62 6 3 4 5 1样例输出提示1. 利用二分归并排序算法(分治)；2. 注意结果可能超过int的范围，需要用long long 存储。#in elude using n amespace std;con st int MAX_NUM = 100000 + 5; long lon

13、g 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;i

14、nt 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;

15、 reSeqNum(seq, N); printf(%ldn, ans);return 0;8、Grey 码描述Grey码是一个长度为 2的序列，序列中无相同元素，且每个元素都是长度为n的二进制位串，相邻元素恰好只有1位不同。例如长度为 23的格雷码为(000,001,011,010,110,111,101,100)。设计分治算法对任意的n值构造相应的Grey 码。输入每个元素的长度值 n。输出将所有相应的Grey码分行输出，即每一行输出一个二进制位串。样例输入3样例输出000001011010110111101100源代码：#in clude#in cludeint power(int ba

16、se,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

17、,k); for(int i=a/2;ia;i+)for(int j=0;jb -1;j+)*(int*)arr+k*i+j)=*(int*)arr+k*(a/arrij=arra -i-1j;int main()int n;-i-1)+j);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次方），要求每名选手要与其他

18、 N-1名选手都赛一次，每名选手每天比赛一次，循环赛共进行N-1天，要求每天没有选手轮空。输入M输出表格形式的比赛安排表样例输入3样例输出1 2 3 4 5 6 7 82 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源代码：#in clude#in cludevoid arran ge(i nt k,i nt *a,i nt n) int t=1,temp=1;*(int*)a+k*0+0)=1;/a00=1;w

19、hile(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 ma

20、in()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 、棋盘覆盖问题描述在一个2 k X2k个方格组成的棋盘中，若恰有一个方格与其他方格不同，称该方格为特殊方格，且称该棋盘为特殊棋盘。显然，特殊方格在棋盘中出现的位置有4 k种情形，因而有4k种不同的棋盘，如图 1所示是k=2时16种棋盘中的一个。在棋盘覆盖问题中，要

21、求用图2所示的4种不同形状的L型骨牌覆盖给定棋盘上除特殊方格以外的所有方格，且任何两个L型骨牌不得重叠覆盖。输入对每一个测试例有 2行，第一行是k ( 1=k=10 )，第二行是特殊方格所在的位置坐标x,y ( 0=x ， y1024)。输出边长为2的k次方的方阵，特殊方格的编号为 0 ,所有L型骨牌从1开始编号，数据之间 的间隔是空格。样例输入样例输出2 0 3 32 2 1 34 1 1 54 4 5 5提示按分治策略进行算法设计。#in clude#in cludeint t=0;int board100100;void ChessBoard(i nt tr,i nt tc,i nt d

22、r,i nt dc,i nt size) int s,t1;if(size=1) retur n ;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) ChessBo

23、ard(tr+s,tc+s,dr,dc,s);else boardtr+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 、输油管

24、道问题描述某石油公司计划建造一条由东向西的主输油管道。该管道要穿过一个有 n 口油井的油田。 从每口油井都要有一条输油管道沿最短路经(或南或北 )与主管道相连。 如果给定 n 口油井的位置 ,即它们的 x 坐标(东西向)和 y 坐标(南北向) ,应如何确定主管道的最优位置 ,即使 各油井到主管道之间的输油管道长度总和最小的位置?证明可在线性时间内确定主管道的最优位置。要求给定 n 口油井的位置 ,计算各油井到主管道之间的输油管道最小长度总和。输入由文件提供输入数据，文件第一行是油井数n ， 1=n=10000 。接下来 n 行是油井的位置，每行两个整数 x 和 y ，- 10000=x,y=1

25、0000。输出将结果输出到文件中，文件第一行中的数是油井到主管道之间的输油管道最小长度总和。样例输入51 22 21 33 -23 3样例输出6提示按分治策略进行算法设计。 源代码：#in clude#in clude#in clude using n amespace std; struct nodeint x,y; num200000;bool cmp( node a,node b) return a.yb.y;int mai n()int t;scan f(%d, &t); int i,j;for(i=0;it;i+)scan f(%d%d,&nu mi.x，&nu mi.y);int

26、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);elseint 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(1 i w的重量是w i，其价值为Vi，背包的容量为 C,对每种物品只有两种选择： 装入背包或者不装入背包。 如何选择装

27、入背包的物品， 使得装入背 包中物品的总价值最大？输入输入包含一组或多组测试例。每组测试例的第一行是物品的数量n和背包的容量 C,之后的n行是每个物品的重量及其价值。输出输出第一行是装入背包中物品的总价值，后面n行是各个物品装入背包的情况。样例输入5 102 62 36 55 44 6样例输出1511001源代码：#i nclude #i nclude using n amespace std;int dp1101010;int n, c, an s110;int w110, v110;void prin t()int i, j, k;k=c;for(i=n; i=1; i_) if(dpik

28、!=dpi -1k) an si=1; k=k-wi;else return; int mai n()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 种不同面值的硬币，各硬币的面值存于数组 T

29、1:n 中。现要用这些面值的硬币来找钱。可以使用的各种面值的硬币个数存于数组Coi ns1: n中。对任意钱数 Ow m 20001设计一个用最少硬币找钱 m 的方法。对于给定的1wnw 10,硬币面值数组 T和可以使用的各种面值的硬币个数数组Coins，以及钱数 m ， 0w mw 20001，计算找钱 m 的最少硬币数。输入由文件提供输入数据, 文件的第一行中只有 1 个整数给出 n 的值, 第 2 行起每行 2 个数,分别是 Tj 和 Coinsj 。最后 1 行是要找的钱数 m 。输出将计算出的最少硬币数输出到文件中。问题无解时输出样例输入31 32 35 318样例输出5提示运用动态

30、规划法进行算法设计并编程实现。 源代码：#in clude#in cludeusing n amespace std;int w110, v110;int dp11020010;int n, m;void in it()for(int i=0; i110; i+)for(i nt j=0; j20010; j+) dpij=2000000000;int mai n()int i, j, k;int t, x, cn t=1;scanf(%d, &n);for(i=1; i=n; i+)scan f(%d%d, &t, &x);for(j=1; j=x; j+)wc nt=t;vcnt=1; c

31、nt+;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 。由于矩阵乘法满足结合律， 故计算矩阵的连乘积可以有许多不同的计算次

32、序，这种计算次序可以用加括号的方式来确定。矩阵连乘积的计算次序与其计算量有密切关系。例如，考察计算 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 (1 nW 26)，表示矩

33、阵的个数。接下来n行，每行有一个大写字母，表示矩阵的名字，后面有两个整数a,b，分别表示该矩阵的行数和列数，其中 1a,b100 。第n+1行是一个矩阵连乘的表达式，由括号与大写字母组成，没有乘号与多余的空格。如果表达式中没有括号则按照从左到右的顺序计算，输入的括号保证能够配对。输出对于每组数据，输出仅一行包含一个整数，即将该矩阵连乘方案需要的数乘次数。如果运算过程中出现不满足矩阵乘法法则的情况(即左矩阵列数与右矩阵的行数不同)，则输出a?error 。样例输入3A 10 100B 100 5C 5 50A(BC)样例输出75000源代码：# in elude # in elude # in

34、elude # in elude # in elude # in elude using n amespaee 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; else des=des+ti+*;else

35、 if(ti=() des=des+ti;elseif(ti+1=) des=des+ti; else des=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=*)

36、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+;else if(compare(ope.top(), exp

37、k)=) 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;else couterrorendl;return 0;15 、多边形游戏描述一个多边形， 开始有 n 个顶点。 每个顶点被赋予一个正整数值， 每条边被赋予一个运算符“ +或”“ *。”所有边依次用整数从 1 到 n 编号。现在来玩一个游戏，该游

38、戏共有 n 步：第1步，选择一条边，将其删除随后n- 1步，每一步都按以下方式操作：(1 )选择一条边E以及由E连接着的2 顶点v1和v2 ； (2 )用一个新的顶点取代边 E以及由E连接着的2个顶点v1和v2 将顶点v1和v2的整数值通过边 E上的运算得到的结果值赋给新顶点。最后，所有边都被删除，只剩一个顶点，游戏结束。游戏得分就是所剩顶点上的整数值。那么这个整数值最大为多少？输入第一行为多边形的顶点数 n (nw 20 )，其后有n行，每行为一个整数和一个字符，整数 为顶点上的正整数值，字符为该顶点到下一个顶点间连边上的运算符“+”或“* ”(最后一字符为最后一个顶点到第一个顶点间连边上的

39、运算符)。输出输出仅一个整数，即游戏所计算出的最大值。样例输入44 *5 +5 +3 +样例输出70提示小规模问题可不必用动态规划方法编程求解，仅用递归就可以求解。计算中不必考虑计算结果超出整数表达范围的问题，给出的数据能保证计算结果的有效性。在给的例子中，计算过程为(3+4)*(5+5)=70。源代码：#include #include #include #include using namespace std; typedef long long int ll;const ll inf=20000000000000; int n;string s;char op110110;ll dp11

40、0110, 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

41、-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, opii+1);for(i=3; i=n; i+)for(j=1; j+i -1=2*n; j+)for(k=j; ki+j -1; k+)dpji+j -1