acm算法精彩资料规范标准示范例题.doc

《acm算法精彩资料规范标准示范例题.doc》由会员分享，可在线阅读，更多相关《acm算法精彩资料规范标准示范例题.doc（90页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、一、数论1: Wolf and Rabbit描述There is a hill with n holes around. The holes are signed from 0 to n-1.A rabbit must hide in one of the holes. A wolf searches the rabbit in anticlockwise order. The first hole he get into is the one signed with 0. Then he will get into the hole every m holes. For example, m

2、=2 and n=6, the wolf will get into the holes which are signed 0,2,4,0. If the rabbit hides in the hole which signed 1,3 or 5, she will survive. So we call these holes the safe holes.输入The input starts with a positive integer P which indicates the number of test cases. Then on the following P lines,e

3、ach line consists 2 positive integer m and n(0m,n2147483648).输出For each input m n, if safe holes exist, you should output YES, else output NO in a single line.样例输入21 22 2样例输出NOYES翻译：描述一座山有n个洞，洞被标记为从0到n-1。兔子必须藏在一个洞中。狼会逆时针方向搜索兔子。狼一开始在洞0，然后他会每m个洞进去一次。例如：m=2，n=6，狼就会依次进入洞0 2 4 0。如果兔子藏在1 3 5就安全。输入第一行一个数字p

4、，表示下面有p组测试数据，每组测试数据2个数m n(0m,n2147483648)输出每组数据输出一行，如果存在安全洞穴，输出YES，否则输出NO思路/方法：你是不是觉得总是无法通过，看看下面的解析假设有n=6个洞 0 1 2 3 4 5当m=4时，狼进的洞是0 4 2 0，也就是形成了一个循环，永远也到不了其他洞穴当m=5时，狼进的洞是0 5 4 3 2 1 0，这时所有的洞都遍历了一遍。思考：当m=4和m=5时，到底有什么区别？当n和m有公约数(非1)时，就会形成一个数字个数小于n的循环当n和m无公约数时，就会形成一个数字个数为n的循环，此时没有安全洞穴。解题关键：这题就转化成了判断两个数

5、是否有公约数。代码：#include using namespace std;long long greatestCommonDivisor(long long a, long long b)/最大公约数 long long t; while(b) t = a % b; a = b; b = t; return a;int main() int i, p; long long m, n; cin p; for(i = 0; i m n; if(greatestCommonDivisor(m, n) = 1)/公约数为1说明互斥，没有安全洞穴 cout NOn; else cout YESn;

6、return 0;2: ab描述给定a和b，输出ab的最后一个数字。输入输入数据有多组，每组数据占一行，每行为a和b的值（0a,b=230）输出对每组输入数据，输出ab的最后一位数字，每组数据占一行。样例输入2 23 4样例输出41思路/方法：如果你模拟ab次肯定会超时，而且数字还会超出Int范围题目说只要最后一个数字，回想一下小学时学的乘法过程，貌似乘数最后一位和前面的无关我们大胆的尝试一下用a的个位代替a，然后我们发现循环b次还是会超时，这是我们要想办法减少循环的次数，试一下是不是有周期规律这时我们来列举一下2的n次方的个位：2 4 8 6 2 4 8 6我们发现周期为4，我们在试试1-9

7、的n次方，发现周期都是4，所以，我们可以用b%4代替b，需要注意的是，当b%4=0时，我们需要给他加上4，不然就不循环了。代码：#include int main() int a, b, i, t; while(scanf(%d %d, &a, &b) != EOF) b = b % 4; if(b = 0) b = 4; a = a % 10; t = 1; for(i = 0; i b; i+) t = t * a; t = t % 10; printf(%dn, t); return 0;3: 筛选法求素数描述请使用筛选法输出a, b之间的所有素数。输入输入数据有多组，每组数据占一行，每

8、行2个正整数a和b，其中2=a=b=1000000。输出每组数据按从小到大的顺序输出a, b中所有的素数，每行最多输出10个素数。每组数据之后空一行。样例输入2 32 50样例输出2 3 2 3 5 7 11 13 17 19 23 2931 37 41 43 47思路/方法：这题测试的数据量很大，所以尽量少循环，尽量少判断，要非常精简才能通过。1.定义一个全局变量short s1000001;/全局变量默认为02.把数组中下标为奇数的值改为1，偶数不用改，因为除了2，其他偶数都不是素数s2 = 1;/2也是素数for(i = 3; i 1000001; i = i + 2)/把奇数全部假设为

9、素数 si = 1;3.把素数的倍数挖掉，改为0。(从2开始到根号1000000之间的素数的倍数挖掉)for(i = 2; i 1000; i+)/小于根号1000000 if(si)/判断是否为素数，只有素数的倍数才挖掉 for(j = i * 2; j 1000001; j = j + i)/把i的倍数的值改成0 sj = 0;4.最后一点是输出格式，每组之间一个空行，另外一行最多10个。定义一个变量来记录输出了多少个，达到十个就输出换行。具体看代码。 代码：#include short s1000001;/全局变量默认为0int main() int t, a, b, i, j; s2

10、= 1;/2也是素数 for(i = 3; i 1000001; i = i + 2)/把奇数全部假设为素数 si = 1; for(i = 2; i 1000; i+)/小于根号1000000 if(si) for(j = i * 2; j 1000001; j = j + i)/把i的倍数的值改成0 sj = 0; while(scanf(%d %d, &a, &b) != EOF) t = 0; for(i = a; i = b; i+) if(si)/素数就输出 if(t) if(t = 10) printf(n); t = 0; else printf( ); t+; printf(

11、%d, i); printf(nn); return 0;4: The ones to remain描述There are N soldiers standing in one line. They are marked from 1 to N, from right to left. And they are given a number m. Then the soldiers numbered off, straight from the right-hand man. The one who reported a number that is the multiple of m was

12、 kept in the line. Others have to leave the line. They continue doing this till the number of people in the line is less than m. For example, if there are 10 soldiers, and m = 3. For the first time the soldiers who are marked 3, 6, 9 remain in the line. For the second time the soldier who is marked

13、9 remains in the line. Because the number of soldiers in the line is less than m, so the soldier marked 9 was the only one to remain in the line. Now we want to know who will be the ones to remain, can you tell us ?输入There are several test cases in the input. Each test cases is only one line, contai

14、ns two integers n and m.(3 = n = 109, 2 = m = n). The input ends when n = 0 and m = 0.输出For each test case, output two lines. The first line contains one integer x, the number of soldiers to remain. The second line contains x integers, the numbers marked on the soldiers who remain in the line. You s

15、hould output them in increasing order.样例输入10 38 30 0样例输出1923 6翻译：描述有N个士兵站在一行。他们被从右到左标记为1到N。他们被给与了一个数字m。然后士兵直接从右面报数。报的数是m的倍数的留下来，其他人离开。然后继续上述操作，直到人数少于m。例如，有10个士兵，m=3。第一次士兵报数为3 6 9的留下，第二次士兵报数为9的留下。输入有多组测试数据。每组一行两个数n m(3 = n = 109, 2 = m = n)，以0 0结束输出每组输出两行，第一行输出一个x表示留下来的士兵数量，第二行输出x个留下来的士兵的编号。思路/方法：这题用

16、数组来存储士兵状态就会超时，所以我们需要更精简的算法，很明显可以看出这是道数学题，所以我们多举几个例子，看看是否有规律。m=2时1 22 1 2 32 1 2 3 42 44 1 2 3 4 5 62 4 64 1 2 3 4 5 6 7 82 4 6 84 88m=3时1 2 33 1 2 3 43 1 2 3 4 5 63 6 1 2 3 4 5 6 7 8 93 6 99由上面的几个例子可以看出关键是找到一个不大于n的最大的mx。比如m=2的时候，依次是21 21 22 22 23，当x一样时，他们的结果值一样，并且就是mx。当m=3时，依次是31 31 31 32，不难发现，x一样时，

17、结果的第一个数一样是mx。接下来要找出有多少个结果值，比较m=3时的前3组数据，发现第三组第二个结果6是3*2且不大于n=6，我们大胆推断m的个数就是不大于n的3的倍数的个数。然后我们继续举个例子检验一下推论。1 2 3 4 5 6 7 8 9 10 11 124 8 12如上，当m=4时，只有m1不大于n，所以结果第一个数为4，然后后面有8 12为4的倍数，且不大于n，所以得到3个结果，和例子的结果一致。这样就成功推出了解题方法，虽然不严谨，但作为一般人，能做出来就行了。代码：#include using namespace std;int main() long long m, n, re

18、main, id, j;/id表示下标，j表示当前第几个报数 while(cin n m, !(n = 0 & m = 0) /得到不大于n的 mx 的值 j = 1; for(id = 1; id+) j = j * m; if(j * m n) break; remain = 0; for(id = 1;id+) if(j * id = n)/得到不大于n的 m的倍数 的个数 remain+; else break; cout remain endl; for(id = 1; id remain; id+) cout id * j ; cout id * j endl; return 0;

19、5: 小数化分数描述Ray 在数学课上听老师说，任何小数都能表示成分数的形式，他开始了化了起来，很快他就完成了，但他又想到一个问题，如何把一个循环小数化成分数呢?请你写一个程序不但可以将普通小数化成最简分数，也可以把循环小数化成最简分数。输入第一行是一个整数N，表示有多少组数据。每组数据只有一个纯小数，也就是整数部分为0。小数的位数不超过9位，循环部分用()括起来。输出对每一个对应的小数化成最简分数后输出，占一行。样例输入30.(4)0.50.32(692307)样例输出4/91/217/52思路/方法：这题需要有个数学转化方法，小编看了别人的纯循环小数转分数的方法，然后又花了点时间推出了非纯

20、循环小数转分数方法，下面分享一下。1.有限小数：分子分母乘以10的次方，使得没有小数位，然后分子分母分别除以最大公约数就化简完成。比如0.4，就是0.4*10/10，最大公约数为2，化简后就是2/52.纯循环小数乘以10的次方使得循环部分没有小数位，然后用该数-原数=整数部分。所以分数形式=循环节/9.9(9的个数等于循环节数字个数)例如：0.44.，0.444.*10-0.444.=4。所以(10-1)*0.44.=4。0.44.=4/9。3.非纯循环小数乘以10的次方使得循环部分没有小数位记为a*10x，乘以10的次方使得非循环部分没有小数记为a*10y，则a*10x-a*10y就消去了后

21、面的小数。比如：0.2433.*1000-0.243.*100=243-24，所以0.243.=(243-23)/(1000-100)，然后总结之后得出下面的结论。不循环部分和循环节构成的的数 减去 不循环部分的差,再除以循环节位数个9，添上不循环部分的位数个0。比如：0.24333333=(243-24)/900=73/3000.9545454=(954-9)/990=945/990=21/22 方法有了，代码也容易写，但小编做的时候犯了一个错误，把循环部分和非循环部分全都当成整数来接受，导致丢失了位数，使得分母不准确了。比如0.001(02)这样的，当成整数接受，非循环部分是1，算长度的时

22、候直接算就是1，循环部分接受后变成2，算长度是1，导致分母变成了90，而实际上是99000。所以必须用字符串来存储，具体看代码了。代码：#include #include long long greatestCommonDivisor(long long a, long long b) long long t; while(b) t = a % b; a = b; b = t; return a;int main() int i, n, j, k; long long denominator, numerator, divisor, cyclical, nonCyclical;/分母分子,非循

23、环部分和循环部分 char a20, nonCyclicalString20, cyclicalString20;/必须用文本，否则会丢失位数，比如0.001010这样的会把0丢了 scanf(%d , &n); for(i = 0; i n; i+) scanf(0.%s, a); getchar(); if(strchr(a, () != NULL)/有循环小数的情况 if(a0 = ()/如果是纯循环小数 sscanf(a, (%s, cyclicalString);/只能这样读取，把括号补充完整也一样的结果 cyclicalStringstrlen(cyclicalString) -

24、1 = 0;/手动删除后面的括号。读取到了循环部分 sscanf(cyclicalString ,%I64d, &cyclical); nonCyclicalString0 = 0; numerator = cyclical;/分子就等于循环节 else for(j = 0; aj != (; j+)/读取到(就停止。读取非循环部分 nonCyclicalStringj = aj; nonCyclicalStringj = 0; for(k = 0, j = j + 1; aj != ); j+, k+)/从(右边一个开始读取到)就停止。读取循环部分 cyclicalStringk = aj;

25、 cyclicalStringk = 0; sscanf(nonCyclicalString, %I64d, &nonCyclical);/把非循环部分的值放入到变量中 sscanf(cyclicalString, %I64d, &cyclical);/把循环部分的值放入到变量中 numerator = nonCyclical;/把分子的值先变成非循环部分 for(j = 0; cyclicalStringj != 0; j+)/往分子尾部加入循环节部分 numerator = numerator * 10 + (cyclicalStringj - 0); numerator = numera

26、tor - nonCyclical;/非循环部分和循环部分的组合 - 非循环部分 /计算分母 denominator = 0; for(j = 0; cyclicalStringj != 0; j+)/加上循环节个数个9 denominator = denominator * 10 + 9; for(j = 0; nonCyclicalStringj != 0; j+)/加上非循环部分个0 denominator = denominator * 10; divisor = greatestCommonDivisor(numerator, denominator); printf(%I64d/%

27、I64dn, numerator / divisor, denominator / divisor); else/非循环小数 sscanf(a, %I64d, &numerator);/把小数部分存到变量中 denominator = 1; for(j = 0; aj != 0; j+)/计算分母 denominator = denominator * 10; divisor = greatestCommonDivisor(numerator, denominator); printf(%I64d/%I64dn, numerator / divisor, denominator / divis

28、or); return 0;6: 全排列描述任意输入n个不重复的整数序列，输出序列的全排列。输入测试数据有多组，第一行是整数t（0t20），代表测试组数。每组测试数据有两行，第一行是整数的个数n(0n6)，第二行是n个不重复的整数。输出按递增的顺序输出序列的全排列。每个测试数据后面输出一个空行。样例输入131 3 5样例输出1 3 51 5 33 1 53 5 15 1 35 3 1 思路/方法：全排列有递归和非递归算法，具体网上有，这里我们为了代码简洁，采用STL里面的函数来实现，容易理解，而且好写。首先引用algorithm这个库，然后里面有sort排序函数和next_permutatio

29、n下一个排列函数。sort升序排序，参数分别是首地址和末地址next_permutation是判断是否有下一个排列，有返回true，并且改变数组状态，否则返回false。参数分别是首地址和末地址代码：#include #include using namespace std;void display(int a, int n) int i; for(i = 0; i n - 1; i+) cout ai ; cout ai t; for(i = 0; i n; int an; for(j = 0; j aj; fullPermutation(a, n); cout endl; return 0

30、;7: (1+x)n描述Please calculate the coefficient modulo 2 of xi in (1+x)n.输入For each case, there are two integers n, i (0=i=n=231-1)输出For each case, print the coefficient modulo 2 of xi in (1+x)n on a single line.样例输入3 14 2样例输出10翻译：描述请计算(1+x)n中xi的系数对2取模的值输入每组测试数据有两个整数n i (0=i=n=231-1)输出每组输出一行，即对2取模的值思路/

31、方法：(1 + x)n展开后xi项的系数的对2取余即求 c(n, i)xi中的c(n, i) % 2的值如果我们计算组合数在对2取余，就会超时，所以我们需要更简便的算法既然是对2取模，就是奇偶性咯，所以我们需要一个组合数的奇偶性判断的算法对于组合数C(n, m) 如果(n&m) = m，那么该组合数是奇数，否则为偶数代码：#include int main () long long n, i; while(scanf(%I64d %I64d, &n, &i) != EOF) if(n&i) = i)/奇数，输出1 printf(1n); else printf(0n); return 0; 8

32、: Summing divisors描述In the 18th century, L. Euler invented a function he called sigma to study properties of whole numbers. He was interested in comparing a positive number to the sum of its positive divisors. In this problem we extend Eulers function to fractions.Given a positive rational number (i

33、.e., a fraction) in simplest terms a/b, we define S(a/b) to be the sum of all positive numbers of the form x/y where x is a positive divisor of a and y is a positive divisor of b. For example, the positive divisors of 4 are 1, 2 and 4 and the positive divisors of 3 are 1 and 3, so S(4/3) = 1/1 + 2/1

34、 + 4/1 + 1/3 + 2/3 + 4/3 = 28/3.输入Each line of input will be of the form a/b (with no white space) where a and b are integers in the range from 1 to 16000.输出Each line of output is of the form a/b where a and b are integers, and the fraction is in simplest terms (so 1/2 will be output instead of 2/4

35、for example).样例输入6/12/3100/49样例输出12/14/11767/7翻译：描述在18世纪，L. Euler发明了一个功能去研究数字的特性，他称之为sigma。他对比较整数的正因子的和感兴趣。在这个问题我们扩展Euler的功能到分数。给一个正分数最简形式a/b，我们定义 S(a/b) 是所有整数x/y的和，x/y是正因子组成，x来自a的因子，y来自b的因子。例如，4的正因子是1 2 4；3的正因子是1 3。所以S(4/3) = 1/1 + 2/1 + 4/1 + 1/3 + 2/3 + 4/3 = 28/3。输入每行输入a/b，a b范围1到16000.输出每行输出S(a

36、/b)的值，分数最简形式。思路/方法：1.定义数组a和b分别存储输入的两个数的因子。2.定义一个结构体用来表示分数3.定义一个函数用来计算分数相加4.把a和b因子组合起来的分数累加起来，然后约分为最简。不太好说，具体看下面代码，不难。代码：#include typedef struct Fraction/分数 int numerator;/分子 int denominator;/分母fraction;int greatestCommonDivisor(int a, int b) int t; while(b) t = a % b; a = b; b = t; return a;fraction

37、 addFraction(fraction * f1, fraction * f2) fraction s; int divisor; if(f1-denominator = f2-denominator | f1-numerator = 0)/两数分母相同 s.numerator = f1-numerator + f2-numerator;/分子相加 s.denominator = f2-denominator; else s.denominator = f1-denominator * f2-denominator;/分母通分 s.numerator = f1-numerator * f2-denominator + f2-numerator * f1-denominator;/分子通分后相加 divisor = greatestCommonDivisor(s.numerator, s.denominator);/求最大公约数 /约分 s.numerator /= divisor; s.denominator /= divisor; return s;int main() int a16001, b16001, i, j, ca, cb; fraction