当前位置:首页 >> 其它课程 >> acm算法经典例题

acm算法经典例题


一、数论
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 or

der. 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 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,each line consists 2 positive integer m and n(0<m,n<2147483648). 输出 For each input m n, if safe holes exist, you should output "YES", else output "NO" in a single line. 样例输入 2 1 2 2 2 样例输出 NO YES 翻译: 描述 一座山有 n 个洞,洞被标记为从 0 到 n-1。兔子必须藏在一个洞中。狼会逆时针方向搜索兔子。狼一开始在洞 0,然后他会每 m 个洞进 去一次。例如:m=2,n=6,狼就会依次进入洞 0 2 4 0。如果兔子藏在 1 3 5 就安全。 输入 第一行一个数字 p,表示下面有 p 组测试数据,每组测试数据 2 个数 m n(0<m,n<2147483648) 输出 每组数据输出一行,如果存在安全洞穴,输出"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 的循环,此时没有安全洞穴。 解题关键:这题就转化成了判断两个数是否有公约数。 代码: #include <iostream> 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 < p; i++) { cin >> m >> n; if(greatestCommonDivisor(m, n) == 1)//公约数为 1 说明互斥,没有安全洞穴 cout << "NO\n"; else cout << "YES\n"; } return 0; } 2: a^b 描述 给定 a 和 b,输出 a^b 的最后一个数字。 输入 输入数据有多组,每组数据占一行,每行为 a 和 b 的值(0<a,b<=2^30) 输出 对每组输入数据,输出 a^b 的最后一位数字,每组数据占一行。 样例输入 2 2 3 4 样例输出 4 1 思路/方法:如果你模拟 a^b 次肯定会超时,而且数字还会超出 Int 范围 题目说只要最后一个数字,回想一下小学时学的乘法过程,貌似乘数最后一位和前面的无关 我们大胆的尝试一下用 a 的个位代替 a,然后我们发现循环 b 次还是会超时,这是我们要想办法减少循环的次数,试一下是不是有周期 规律 这时我们来列举一下 2 的 n 次方的个位:2 4 8 6 2 4 8 6 我们发现周期为 4,我们在试试 1-9 的 n 次方,发现周期都是 4,所以,我们可以用 b%4 代替 b,需要注意的是,当 b%4==0 时,我们需 要给他加上 4,不然就不循环了。 代码: #include <stdio.h> 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("%d\n", t); } return 0; } 3: 筛选法求素数 描述 请使用筛选法输出[a, b]之间的所有素数。 输入 输入数据有多组,每组数据占一行,每行 2 个正整数 a 和 b,其中 2<=a<=b<=1000000。 输出 每组数据按从小到大的顺序输出[a, b]中所有的素数,每行最多输出 10 个素数。每组数据之后空一行。 样例输入 2 3 2 50 样例输出 2 3 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 思路/方法:这题测试的数据量很大,所以尽量少循环,尽量少判断,要非常精简才能通过。 1.定义一个全局变量 short s[1000001];//全局变量默认为 0 2.把数组中下标为奇数的值改为 1,偶数不用改,因为除了 2,其他偶数都不是素数 s[2] = 1;//2 也是素数 for(i = 3; i < 1000001; i = i + 2)//把奇数全部假设为素数 s[i] = 1; 3.把素数的倍数挖掉,改为 0。(从 2 开始到根号 1000000 之间的素数的倍数挖掉) for(i = 2; i < 1000; i++)//小于根号 1000000 if(s[i])//判断是否为素数,只有素数的倍数才挖掉 for(j = i * 2; j < 1000001; j = j + i)//把 i 的倍数的值改成 0 s[j] = 0; 4.最后一点是输出格式,每组之间一个空行,另外一行最多 10 个。定义一个变量来记录输出了多少个,达到十个就输出换行。具体看 代码。 代码: #include <stdio.h> short s[1000001];//全局变量默认为 0 int main() { int t, a, b, i, j; s[2] = 1;//2 也是素数 for(i = 3; i < 1000001; i = i + 2)//把奇数全部假设为素数 s[i] = 1; for(i = 2; i < 1000; i++)//小于根号 1000000 if(s[i]) for(j = i * 2; j < 1000001; j = j + i)//把 i 的倍数的值改成 0

s[j] = 0; while(scanf("%d %d", &a, &b) != EOF) { t = 0; for(i = a; i <= b; i++) { if(s[i])//素数就输出 { if(t) if(t == 10) { printf("\n"); t = 0; } else printf(" "); t++; printf("%d", i); } } printf("\n\n"); } 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 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 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, contains 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 should output them in increasing order. 样例输入 10 3 8 3 0 0 样例输出 1 9 2 3 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 个留下来的士兵的编号。 思路/方法: 这题用数组来存储士兵状态就会超时,所以我们需要更精简的算法,很明显可以看出这是道数学题,所以我们多举几个例子,看看是 否有规律。 m=2 时 1 2 2 1 2 3 2 1 2 3 4 2 4 4 1 2 3 4 5 6 2 4 6 4 1 2 3 4 5 6 7 8 2 4 6 8 4 8 8 m=3 时 1 2 3 3 1 2 3 4 3 1 2 3 4 5 6 3 6 1 2 3 4 5 6 7 8 9 3 6 9 9 由上面的几个例子可以看出关键是找到一个不大于 n 的最大的 m^x。 比如 m=2 的时候, 依次是 2^1 他们的结果值一样,并且就是 m^x。 当 m=3 时,依次是 3^1 3^1 3^1 3^2,不难发现,x 一样时,结果的第一个数一样是 m^x。 接下来要找出有多少个结果值,比较 m=3 时的前 3 组数据,发现第三组第二个结果 6 是 3*2 且不大于 n=6,我们大胆推断 m 的个数就是 不大于 n 的 3 的倍数的个数。然后我们继续举个例子检验一下推论。 1 2 3 4 5 6 7 8 9 10 11 12 2^1 2^2 2^2 2^3, 当 x 一样时,

4 8 12 如上,当 m=4 时,只有 m^1 不大于 n,所以结果第一个数为 4,然后后面有 8 12 为 4 的倍数,且不大于 n,所以得到 3 个结果,和例子 的结果一致。 这样就成功推出了解题方法,虽然不严谨,但作为一般人,能做出来就行了。 代码: #include <iostream> using namespace std; int main() { long long m, n, remain, id, j;//id 表示下标,j 表示当前第几个报数 while(cin >> n >> m, !(n == 0 && m == 0)) { //得到不大于 n 的 m^x 的值 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; } 5: 小数化分数 描述 Ray 在数学课上听老师说,任何小数都能表示成分数的形式,他开始了化了起来,很快他就完成了,但他又想到一个问题,如何把一 个循环小数化成分数呢? 请你写一个程序不但可以将普通小数化成最简分数,也可以把循环小数化成最简分数。 输入 第一行是一个整数 N,表示有多少组数据。 每组数据只有一个纯小数,也就是整数部分为 0。小数的位数不超过 9 位,循环部分用()括起来。 输出 对每一个对应的小数化成最简分数后输出,占一行。 样例输入 3 0.(4)

0.5 0.32(692307) 样例输出 4/9 1/2 17/52 思路/方法:这题需要有个数学转化方法,小编看了别人的纯循环小数转分数的方法,然后又花了点时间推出了非纯循环小数转分数方 法,下面分享一下。 1.有限小数: 分子分母乘以 10 的次方,使得没有小数位,然后分子分母分别除以最大公约数就化简完成。比如 0.4,就是 0.4*10/10,最大公约数 为 2,化简后就是 2/5 2.纯循环小数 乘以 10 的次方使得循环部分没有小数位,然后用该数-原数=整数部分。 所以分数形式=循环节/9...9(9 的个数等于循环节数字个数) 例如:0.44..,0.444..*10-0.444..=4。所以(10-1)*0.44..=4。0.44..=4/9。 3.非纯循环小数 乘以 10 的次方使得循环部分没有小数位记为 a*10^x,乘以 10 的次方使得非循环部分没有小数记为 a*10^y,则 a*10^x-a*10^y 就消去 了后面的小数。比如:0.2433..*1000-0.243..*100=243-24,所以 0.243..=(243-23)/(1000-100),然后总结之后得出下面的结论。 不循环部分和循环节构成的的数 减去 不循环部分的差,再除以循环节位数个 9,添上不循环部分的位数个 0。比如: 0.24333333????=(243-24)/900=73/300 0.9545454????=(954-9)/990=945/990=21/22 方法有了,代码也容易写,但小编做的时候犯了一个错误,把循环部分和非循环部分全都当成整数来接受,导致丢失了位数,使得分 母不准确了。比如 0.001(02)这样的,当成整数接受,非循环部分是 1,算长度的时候直接算就是 1,循环部分接受后变成 2,算长度 是 1,导致分母变成了 90,而实际上是 99000。所以必须用字符串来存储,具体看代码了。 代码: #include <stdio.h> #include <string.h> 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;// 分母分子,非循环部分和循环部分 char a[20], nonCyclicalString[20], cyclicalString[20];// 必须用文本,否则会丢失位数,比如 0.001010 这样的会把 0 丢了 scanf("%d ", &n); for(i = 0; i < n; i++) { scanf("0.%s", a); getchar(); if(strchr(a, '(') != NULL)//有循环小数的情况

{ if(a[0] == '(')//如果是纯循环小数 { sscanf(a, "(%s", cyclicalString);//只能这样读取,把括号补充完整也一样的结果 cyclicalString[strlen(cyclicalString) - 1] = '\0';//手动删除后面的括号。读取到了循环部分 sscanf(cyclicalString ,"%I64d", &cyclical); nonCyclicalString[0] = '\0'; numerator = cyclical;//分子就等于循环节 } else { for(j = 0; a[j] != '('; j++)//读取到(就停止。读取非循环部分 nonCyclicalString[j] = a[j]; nonCyclicalString[j] = '\0'; for(k = 0, j = j + 1; a[j] != ')'; j++, k++)// 从(右边一个开始读取到)就停止。读取循环部分 cyclicalString[k] = a[j]; cyclicalString[k] = '\0'; sscanf(nonCyclicalString, "%I64d", &nonCyclical);// 把非循环部分的值放入到变量中 sscanf(cyclicalString, "%I64d", &cyclical);// 把循环部分的值放入到变量中 numerator = nonCyclical;//把分子的值先变成非循环部分 for(j = 0; cyclicalString[j] != '\0'; j++)//往分子尾部加入循环节部分 { numerator = numerator * 10 + (cyclicalString[j] - '0'); } numerator = numerator - nonCyclical;//非循环部分和循环部分的组合 - 非循环部分 } //计算分母 denominator = 0; for(j = 0; cyclicalString[j] != '\0'; j++)//加上循环节个数个 9 denominator = denominator * 10 + 9; for(j = 0; nonCyclicalString[j] != '\0'; j++)//加上非循环部分个 0 denominator = denominator * 10; divisor = greatestCommonDivisor(numerator, denominator); printf("%I64d/%I64d\n", numerator / divisor, denominator / divisor); } else//非循环小数 { sscanf(a, "%I64d", &numerator);//把小数部分存到变量中 denominator = 1; for(j = 0; a[j] != '\0'; j++)//计算分母 denominator = denominator * 10; divisor = greatestCommonDivisor(numerator, denominator); printf("%I64d/%I64d\n", numerator / divisor, denominator / divisor); } } return 0; } 6: 全排列 描述 任意输入 n 个不重复的整数序列,输出序列的全排列。

输入 测试数据有多组,第一行是整数 t(0<t<20),代表测试组数。每组测试数据有两行,第一行是整数的个数 n(0<n<6),第二行是 n 个 不重复的整数。 输出 按递增的顺序输出序列的全排列。每个测试数据后面输出一个空行。 样例输入 1 3 1 3 5 样例输出 1 3 5 1 5 3 3 1 5 3 5 1 5 1 3 5 3 1 思路/方法:全排列有递归和非递归算法,具体网上有,这里我们为了代码简洁,采用 STL 里面的函数来实现,容易理解,而且好写。 首先引用 algorithm 这个库,然后里面有 sort 排序函数和 next_permutation 下一个排列函数。 sort 升序排序,参数分别是首地址和末地址 next_permutation 是判断是否有下一个排列,有返回 true,并且改变数组状态,否则返回 false。参数分别是首地址和末地址 代码: #include <iostream> #include <algorithm> using namespace std; void display(int a[], int n) { int i; for(i = 0; i < n - 1; i++) cout << a[i] << " "; cout << a[i] << endl; } void fullPermutation(int a[], int n)//全排列,STL 实现 { sort(a, a + n);//升序排序 do { display(a, n);//显示出来 }while(next_permutation(a, a + n)); } int main() { int i, n, t, j; cin >> t; for(i = 0; i < t; i++) { cin >> n; int a[n]; for(j = 0; j < n; j++) cin >> a[j]; fullPermutation(a, n);

cout << endl; } return 0; } 7: (1+x)^n 描述 Please calculate the coefficient modulo 2 of x^i in (1+x)^n. 输入 For each case, there are two integers n, i (0<=i<=n<=2^31-1) 输出 For each case, print the coefficient modulo 2 of x^i in (1+x)^n on a single line. 样例输入 3 1 4 2 样例输出 1 0 翻译: 描述 请计算(1+x)^n 中 x^i 的系数对 2 取模的值 输入 每组测试数据有两个整数 n i (0<=i<=n<=2^31-1) 输出 每组输出一行,即对 2 取模的值 思路/方法:(1 + x)^n 展开后 x^i 项的系数的对 2 取余 即求 c(n, i)x^i 中的 c(n, i) % 2 的值 如果我们计算组合数在对 2 取余,就会超时,所以我们需要更简便的算法 既然是对 2 取模,就是奇偶性咯,所以我们需要一个组合数的奇偶性判断的算法 对于组合数 C(n, m) 如果(n&m) == m,那么该组合数是奇数,否则为偶数 代码: #include <stdio.h> int main () { long long n, i; while(scanf("%I64d %I64d", &n, &i) != EOF) if((n&i) == i)//奇数,输出 1 printf("1\n"); else printf("0\n"); return 0; } 8: 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 Euler's function to fractions. Given a positive rational number (i.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 + 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 for example). 样例输入 6/1 2/3 100/49 样例输出 12/1 4/1 1767/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/b)的值,分数最简形式。 思路/方法: 1.定义数组 a 和 b 分别存储输入的两个数的因子。 2.定义一个结构体用来表示分数 3.定义一个函数用来计算分数相加 4.把 a 和 b 因子组合起来的分数累加起来,然后约分为最简。 不太好说,具体看下面代码,不难。 代码: #include <stdio.h> 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 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 a[16001], b[16001], i, j, ca, cb; fraction s, t; while(scanf("%d/%d", a, b) != EOF)//把 a 和 b 存到 a0 b0 { ca = cb = 1; for(i = 1; i <= a[0]; i++)//a 的所有因子 { if(a[0] % i == 0) { a[ca] = i; ca++; } } for(i = 1; i <= b[0]; i++)//b 的所有因子 { if(b[0] % i == 0) { b[cb] = i; cb++; } } s.denominator = s.numerator = 0; for(i = 1; i < cb; i++)//计算因子组合的和 { for(j = 1; j < ca; j++) { t.numerator = a[j]; t.denominator = b[i]; s = addFraction(&s, &t); }

} int divisor = greatestCommonDivisor(s.numerator, s.denominator);// 求最大公约数 //约分 s.numerator /= divisor; s.denominator /= divisor; printf("%d/%d\n", s.numerator, s.denominator); } return 0; } 9: 简单组合问题 描述 对于有 m 个元素的集合,在元素能重复取的情况下,我们可以得到有 r 组合的集合;例如,当 m=2,r=4 时,集合{a,b}可以划分为 5 个不同的 r 组合的集合: {a,a,a,a}; {a,a,a,b}; {a,a,b,b}; {a,b,b,b}; {b,b,b,b}; 输入 输入数据有多组,每行输入 2 个整型数据 m,r,(0<m,r<=20) 输出 输出可以划分的集合个数 样例输入 2 4 样例输出 5 思路/方法:题目指明了是组合问题,就是不考虑顺序。 这题输入的数据范围小,说明不是有公式就能得出答案的,需要经过推算。 我们不妨来举个例子来看一下是否有规律。 当 m=1 是,结果都是 1 当 m=3,r=4 时,假设有 a,b,c 三种数,a 就有 5(即 r+1)种情况,集合中 a 的个数可以为 0 1 2 3 4。a=0 时,就剩下 b,c 来充满 4 个 位置,这种情况的值与 m=2,r=4 时的值一样;a=1 时,就剩下 b,c 来充满 3 个位置,这种情况的值与 m=2,r=3 时的值一样;a=2 时, 就剩下 b,c 来充满 2 个位置,这种情况的值与 m=2,r=2 时的值一样;a=3 时,就剩下 b,c 来充满 1 个位置,这种情况的值与 m=2,r=1 时的值一样;a=4 时,位置充满了,值为 1。 通过上面例子我们发现 s(m=3,r=4)可以转化成 s(m=2,r=4) + s(m=2,r=3) + s(m=2,r=2) + s(m=2,r=1) +1 。 同样的,我们推广出来就是 s(m,r)=s(m-1,r)+s(m-1,r-1)+s(m-1,r-2)+.....+s(m-1,1)+1。 也就是 s(m,r)可以转化成前一行的前 r 列的和+1。 有了这个规律,我们只要知道第一行,就能退出后面的。 这题用递归会超时,所以我们用递推,具体代码如下。 代码: #include <stdio.h> long long a[21][21]; int main() { int m, r, i; for(r = 1; r <= 20; r++)//m=1 时全部都是 1 a[1][r] = 1; for(m = 2; m <= 20; m++) for(r = 1; r <= 20; r++)

{ for(i = 0; i < r; i++)//循环 r 次 a[m][r] = a[m][r] + a[m - 1][r - i]; a[m][r] = a[m][r] + 1; } while(scanf("%d %d", &m, &r) != EOF) printf("%I64d\n", a[m][r]); return 0; } 10: GCD & LCM 描述 Given x and y (2 <= x <= 100,000, 2 <= y <= 1,000,000), you are to count the number of p and q such that: 1) p and q are positive integers; 2) GCD(p, q) = x; 3) LCM(p, q) = y. 输入 There are multiple test cases, each case contains two integers x and y, one line for each test case. 输出 Number of pairs of p and q. 样例输入 3 60 样例输出 4 翻译: 描述 给定 x,y(2 <= x <= 100,000, 2 <= y <= 1,000,000) ,你要像下面那样计算出 p 和 q: 1) p,q 是正整数; 2) GCD(p, q) = x;即 p,q 的最大公约数是 x 3) LCM(p, q) = y.即 p,q 的最小公倍数是 y 输入 输入多组测试数据,每组包含两个整数 x y 输出 每组输出满足条件的 p 和 q 的组数。 思路/方法: 我们要求 p,q 可能的组数,先来推一下 x y p q 之间的关系 最小公倍数=两数之积/最大公约数。也就是 y=p*q/x; 所以得到 xy=pq (范围:x <= p,q <= y) 因为 p 和 q 可以用最大公约数的倍数来表示,即设 p=x*n1,q=x*n2。 我们可以得到 p*q=x*x*n1*n2=x*y。即 n1*n2=y/x。 还可以得到 gcd(p,q)=gcd(x*n1,x*n2)=x 因此 gcd(n1,n2)=1 也就是 n1,n2 是互质的数 (范围:1 <=n1,n2 <= y/x) 所以,确定 n1,n2 就确定了 p,q,我们只需要知道这样的 n1,n2 有多少组,就知道有多少组 p,q 代码: #include <stdio.h> int gcd(int a, int b)//最大公约数 { int t; while(b) {

t = a % b; a = b; b = t; } return a; } int main() { int x, y, i, c, s; while(scanf("%d %d", &x, &y) != EOF) { if(y % x != 0)//如果发现最小公倍数不是最大公约数的倍数,就说明组数为 0 { printf("0\n"); continue; } c = 0; s = y / x; for(i = 1; i <= s; i++) if(s % i == 0)//能除尽,因为 n1*n2=y/x=s。这里是用 i 表示 n1,s/i 表示 n2 if(gcd(i, s / i) == 1)//判断 n1 和 n2 是否互质 c++; printf("%d\n", c); } return 0; } 11: Raising Modulo Numbers(快速取模) 描述 People are different. Some secretly read magazines full of interesting girls' pictures, others create an A-bomb in their cellar, others like using Windows, and some like difficult mathematical games. Latest marketing research shows, that this market segment was so far underestimated and that there is lack of such games. This kind of game was thus included into the KOKODDáKH. The rules follow: Each player chooses two numbers Ai and Bi and writes them on a slip of paper. Others cannot see the numbers. In a given moment all players show their numbers to the others. The goal is to determine the sum of all expressions AiBi from all players including oneself and determine the remainder after division by a given number M. The winner is the one who first determines the correct result. According to the players' experience it is possible to increase the difficulty by choosing higher numbers. You should write a program that calculates the result and is able to find out who won the game. 输入 The input consists of Z assignments. The number of them is given by the single positive integer Z appearing on the first line of input. Then the assignements follow. Each assignement begins with line containing an integer M (1 <= M <= 45000). The sum will be divided by this number. Next line contains number of players H (1 <= H <= 45000). Next exactly H lines follow. On each line, there are exactly two numbers Ai and Bi separated by space. Both numbers cannot be equal zero at the same time. 输出 For each assingnement there is the only one line of output. On this line, there is a number, the result of expression (A1B1 + A2B2 + ... + AHBH) mod M. 样例输入 3 16 4

2 3 3 4 4 5 5 6 36123 1 2374859 3029382 17 1 3 18132 样例输出 2 13195 13 翻译: 描述 人们都不同。有些人私下的看满是令人感兴趣的美女图片的杂志,一些人在他们地下室造炸弹,一些人喜欢使用窗户,一些人喜欢复 杂的数学游戏。最新的市场调查表明,市场部分太过低估,缺乏这样的游戏。这种游戏是这样的包含在 KOKODDáKH。规则如下: 每个玩家选择两个数字 Ai 和 Bi,在光滑的纸上写下他们。其他人不能看见这些数字,在给定的时间所有的玩家展示他们的数字给别 人看。目标是决定所有的表达式 AiBi 的和对 M 取模。第一个得出答案的是胜利者。根据玩家的表达式,很有可能通过选择大的数来增 加难度。 你应该写一个程序来计算结果,并且能够造出是谁赢家。 输入 第一行输入一个整数 z 表示有 z 组测试数据。每组数据第一行是一个整数 M(1 <= M <= 45000)。所有表达式的和对 M 取模。下一行是 玩家个数 H(1<=H<=45000)。下面 H 行是每个玩家的两个数字 Ai Bi,两个数不会同时为 0 输出 每组数据输出一行表达式(A1B1 + A2B2 + ... + AHBH) mod M.的结果。 思路/方法:如果找常规方法算即使是 64 位整数也不够存储,所以我们需要快速取模的算法。这算法推起来不简单,这里就不讲为什 么,记住这么做就行,下面代码也有注释,至少能保证你看得懂代码,至于为什么这么写,可以百度“快速取模”。 代码: #include <stdio.h> long long quickMod(long long a, long long b, int m)//a 的 b 次方 对 m 取模 { long long s = 1; while(b)//b 次方就循环 b 次 { if(b&1)//等价于 b%2,如果 b 是奇数 { s = s * a % m;//乘以 a 后对 m 取模 b--; } a = a * a % m; b >>= 1;//等价于 b/= 2 } return s; } int main() { int z, m, h, i, j;

long long s, a, b; scanf("%d", &z); for(i = 0; i < z; i++) { s = 0; scanf("%d", &m); scanf("%d", &h); for(j = 0; j < h; j++) { scanf("%I64d %I64d", &a, &b); s = s + quickMod(a, b, m); s = s % m; } printf("%I64d\n", s); } return 0; } 12: Euclid's Game(简单博弈论) 描述 Two players, Stan and Ollie, play, starting with two natural numbers. Stan, the first player, subtracts any positive multiple of the lesser of the two numbers from the greater of the two numbers, provided that the resulting number must be nonnegative. Then Ollie, the second player, does the same with the two resulting numbers, then Stan, etc., alternately, until one player is able to subtract a multiple of the lesser number from the greater to reach 0, and thereby wins. For example, the players may start with (25,7): 25 7 11 7 4 7 4 3 1 3 1 0 an Stan wins. 输入 The input consists of a number of lines. Each line contains two positive integers giving the starting two numbers of the game. Stan always starts. 输出 For each line of input, output one line saying either Stan wins or Ollie wins assuming that both of them play perfectly. The last line of input contains two zeroes and should not be processed. 样例输入 34 12 15 24 0 0 样例输出 Stan wins Ollie wins 翻译: 描述 两个玩家,Stan 和 Ollie,以两个自然数开始。Stan,第一个玩家,用两数中较大的数 减去 两数中较小数的倍数,保证非负数。第 二个玩家 Ollie 对上个结果进行同样的处理。下一轮有是 Stan,像这样轮流。直到其中一个玩家能使得较大的数字减成 0,则那个玩 家就赢了。例如,玩家开始的数字是(25,7): 25 7

11 7 4 7 4 3 1 3 1 0 Stan 赢了。 输入 输入多组测试数据,每组一行两个正整数,Stan 总是第一个开始。 输出 每组数据输出一行,谁赢了比赛。输入两个 0 0 就不处理结束运行。 思路/方法:这题还是需要找规律。 我们假设 a<=b,如果 a>b 就交换 a b。 1.很明显,如果 a 或者 b 为 1,则 Stan 必胜。如果 a==b 则 Stan 也必胜。 2.如果 b==2*a,显然 Stan 必胜。如果 b>2*a,我们可以假设 b%a=c,(c<a<b) 如果(c,a)是必败态,则 Stan 肯定会将 b 减成 c,这时是 O 面临此种情况,可使得 O 必败。如果(c,a)是必胜态,则 S 可减 b,使得 b(要 知道 b>2*a 啊,那就是说 b=n*a+c,其中 n>=2)成为 a+c,局面成为(a,a+c),这是 O 只有一种选择,那就是将 a+c 减一个 a(仔细想想, 按照游戏规则,他真的没别的办法了),局面变成了 Stan 面临的(c,a)是一种必胜态,也就是说,当 b>2*a 的时候,无论(c,a)是必胜 态还是必败态,S 都必胜。 3.如果 a< b < 2 * a。这时只有一种选择,但我们仍然不知道是否能赢,所以我们用递归就行了,注意递归(b-a, a)时下一个状态, 即对手的状态,所以我们要取反才是自己的状态。 上面就包含了所有的情况,同样的当 a > b 时,也是一样的,选手是从中选择一个大的数减去小的,所以谁大无所谓。 代码: #include <stdio.h> void swap(long long * a, long long * b) { long long t; t = *a; *a = *b; *b = t; } int game(long long a, long long b) { if(a > b)//保证 b 较大 swap(&a, &b); if(a == b || b >= 2 * a) return 1; else return !game(b - a, a);//下一个状态是对手状态,对手赢了自己就输了,所以需要加一个!才是自己的状态 } int main() { long long a, b; while(scanf("%I64d %I64d", &a, &b), !(a == 0 && b == 0)) if(game(a, b)) printf("Stan wins\n"); else printf("Ollie wins\n"); return 0; }

二.几何基础
1: 求两直线的夹角 描述 有两条直线,AB 和 CD,A、B、C、D 的坐标已知,求这两条直线的所成夹角中较小的一个。 输入 输入包括多组数据,第一行为测试数据的组数 n,接下来后面有 n 行,每一行有 8 个整数,依次代表 A 点的 x 坐标、A 点的 y 坐标,B 点的 x 坐标、B 点的 y 坐标,C 点的 x 坐标、C 点的 y 坐标,D 点的 x 坐标、D 点的 y 坐标。 输出 输出夹角的近似值(角度值而非弧度值,保留 1 位小数)。 样例输入 2 0 0 0 1 0 0 1 0 0 0 1 1 1 1 1 0 样例输出 90.0 45.0 思路/方法:两直线夹角等价于求两直线的向量的夹角。即 cos<n1,n2>=n1*n2/(|n1|*|n2|),两向量点积 / 两向量模 = 角的余弦值 然后把余弦值转化成弧度再转化成角度。acos 函数就是 arccos。 代码: #include <stdio.h> #include <math.h> int main() { int a[8], n, i, j, x1, x2, y1, y2;//两个向量(x1,y1)(x2,y2) double angle;//角度 scanf("%d", &n); for(i = 0; i < n; i++) { for(j = 0; j < 8; j++) scanf("%d", a + j);//输入到数组中 x1 = a[2] - a[0]; y1 = a[3] - a[1]; x2 = a[6] - a[4]; y2 = a[7] - a[5]; angle = fabs((x1 * x2 + y1 * y2) / (sqrt(x1 * x1 + y1 * y1) * sqrt(x2 * x2 + y2 * y2)));//cos<n1,n2>=n1*n2/(|n1|*|n2|) angle = acos(angle) / 3.1415926 * 180;//arccos 反三角求弧度,转成度数 先除以π ,在乘以 180 printf("%.1lf\n", angle); } return 0; } 2: 计算几何练习题——线段相交 描述 线段相交测试在计算几何中是经常用到的,给定线段 P1P2(P1 和 P2 是线段的两端点,且不重合)、P3P4(P3 和 P4 是线段的两端点, 且不重合),判断 P1P2 和 P3P4 是否相交。P1P2 和 P3P4 不重合,即指只存在一个点 P,它既落在 P1P2 上又落在 P3P4 上(含线段的端 点)。 输入 输入数据有多组,第一行为测试数据的组数 N,下面包括 2N 行,每组测试数据含 2 行,第一行为 P1P2 的坐标值,第二行为 P3P4 的坐 标值,比如下面的数据

1 0 0 1 1 2 2 3 3 表示 P1、P2、P3、P4 的坐标分别为:P1(0,0),P2(1,1),P3(2,2),P4(3,3) 输出 判断每组数据中的线段 P1P2 和 P3P4 是否相交,如果相交输出 YES,否则输出 NO。每组数据输出占一行。 样例输入 1 0 0 1 1 2 2 3 3 样例输出 NO 思路/方法:判断线段相交,我这里介绍一种常见的方法。 快速排斥(两个由线段做对角线的矩形是否有交集) + 跨立(一个线段的两个端点在另一线段的两端) 判断是否有交集就是把所有不相交的情况取反,也就是 !( max(p1.x, p2.x) < min(p3.x, p4.x) || max(p3.x, p4.x) < min(p1.x, p2.x) || max(p1.y, p2.y) < min(p3.y, p4.y) || max(p3.y, p4.y) < min(p1.y, p2.y) ) 判断跨立就是(AC X AB) * (AD X AB) <= 0 && (CA X CD) * (CB X CD) <= 0 叉乘 X 的公式是 p1 X p2 = p1.x * p2.y - p1.y * p2.x 所以代码就好写了。 代码: #include <iostream> #include <cstdio> using namespace std; class point { public: double x, y; point(double x1, double y1) { x = x1; y = y1; } }; class line { public: point n; line(point & p1, point &p2): n(p2.x - p1.x, p2.y - p1.y){} friend double X(line & l1, line & l2);//叉乘 }; double X(line & l1, line & l2)//叉乘 { return l1.n.x * l2.n.y - l1.n.y * l2.n.x; } inline double min(double a, double b) { if(a < b) return a; else

return b; } inline double max(double a, double b) { if(a > b) return a; else return b; } int main() { int n, i; double x1, y1; scanf("%d", &n); for(i = 0; i < n; i++) { scanf("%lf %lf", &x1, &y1); point p1(x1, y1); scanf("%lf %lf", &x1, &y1); point p2(x1, y1); scanf("%lf %lf", &x1, &y1); point p3(x1, y1); scanf("%lf %lf", &x1, &y1); point p4(x1, y1); if( max(p1.x, p2.x) < min(p3.x, p4.x) || max(p3.x, p4.x) < min(p1.x, p2.x) || max(p1.y, p2.y) < min(p3.y, p4.y) || max(p3.y, p4.y) < min(p1.y, p2.y) )// 如果是两线段对角线的矩形都不相交,线段就不相交 printf("NO\n"); else//在判断 { line p12(p1, p2), p34(p3, p4), p13(p1, p3), p14(p1, p4), p31(p3, p1), p32(p3, p2); if(X(p31, p34) * X(p32, p34) <= 0 && X(p13, p12) * X(p14, p12) <= 0) printf("YES\n"); else printf("NO\n"); } } return 0; } 3: 判断多边形凹凸 描述 任意给定一个多边形,判断它是凸还是凹。多边形的顶点以逆时针方向的序列来表示。 输入 输入包含多组测试数据,每组数据占 2 行,首先一行是一个整数 n,表示多边形顶点的个数,然后一行是 2×n 个整数,表示逆时针顺 序的 n 个顶点的坐标(xi,yi),n 为 0 的时候结束输入。 输出 对于每个测试实例,如果地块的形状为凸多边形,请输出“convex”,否则输出”concave”,每个实例的输出占一行。 样例输入 4 0 0 1 0 1 1 0 1 0 样例输出

convex 思路/方法:判断多边形凹凸性就是判断他每个角的凹凸性,若所有角都是凸的,则为凸多边形,否则就为凹多边形。 所以问题转化为判断角的凹凸性, 角的凹凸性可以用三个点构成的两条直线的外积(叉乘)来判断, 若外积小于 0, 则说明角度大于 180, 即为凹角,否则就为凸角,记录凸角个数就能知道是不是凸多边形了。具体看代码 代码: #include <iostream> #include <cstdio> using namespace std; class point { public: int x, y; point(int x1, int y1) { x = x1; y = y1; } point(){} }; class line: public point { public: point pa, pb; line(point & p1, point & p2): pa(p1), pb(p2) { x = p2.x - p1.x; y = p2.y - p1.y; } line(){} }; inline int min(int a, int b) { if(a < b) return a; else return b; } inline int max(int a, int b) { if(a > b) return a; else return b; } int outerProduct(line & l1, line & l2)// 外积 { return l1.x * l2.y - l2.x * l1.y; } int main()

{ int n, i, c; while(scanf("%d", &n), n != 0) { point p[n]; c = 0;//计数器,记录有多少个凸角 for(i = 0; i < n; i++) scanf("%d %d", &p[i].x, &p[i].y); for(i = 0; i < n - 2; i++)//前 n-2 个角是否符合条件 { line l1(p[i], p[i + 1]), l2(p[i + 1], p[i + 2]);// 造出三点构成的两条直线 if(outerProduct(l1, l2) < 0)//说明凹角 break; else c++; } //最后两个角 line l1(p[n - 2], p[n - 1]), l2(p[n - 1], p[0]), l3(p[n - 1], p[0]), l4(p[0], p[1]); if(outerProduct(l1, l2) >= 0) c++; if(outerProduct(l3, l4) >= 0) c++; if(c == n) printf("convex\n"); else printf("concave\n"); } return 0; } 4: 两圆相交面积 描述 There are two circles in the plane (shown in the below picture), there is a common area between the two circles. The problem is easy that you just tell me the common area. 输入 There are many cases. In each case, there are two lines. Each line has three numbers: the coordinates (X and Y) of the centre of a circle, and the radius of the circle. 输出 For each case, you just print the common area which is rounded to three digits after the decimal point. For more details, just look at the sample. 样例输入 0 0 2 2 2 1 样例输出 0.108 翻译: 描述 平面内有两个圆,两个圆之间有一个公共区域。问题很简单,你告诉我公共区域的面积。 输入 输入多组测试数据,每组两行,每行三个数字:圆心的坐标(x,y),圆的半径。 输出

每组数据输出一个公共面积,精确到小数点后 3 位。更多详细,请看例子。 思路/方法:如下面的图,公共区域面积=s1+s2-s3。就是两个扇形面积和 减去 四边形面积。

扇形面积=弧度所占比率*圆面积 四边形面积可以分解为两个对称的三角形,利用正弦定理可以求出 所以关键是圆心与两交点形成的夹角,因为 c1c2 平分了四边形,所以,可以先求夹角的一半。 利用余弦定理,cos(a1) = (d*d + r1*r1 - r2*r2) / (2 * d * r1) 同理,可以求出 cos(a2),然后利用 acos 得到弧度。 到这里还没做完这题,这题没说给定的两圆一定相交,所以我们也要考虑相离外切、包含内切等情况。 d >= r1 + r2, 相离或外切时,面积为 0 d <= r1 - r2, 包含或内切时,面积为小圆面积 代码: #include <stdio.h> #include <math.h> double min(double a, double b) { if(a < b) return a; else return b; } int main() { double x1, x2, y1, y2, r1, r2, a1, a2, s1, s2, s3, pi, d;//a 表示扇形弧度, s1 s2 表示两个扇形面积,s3 为两个三角形 面积和 pi = acos(-1);//acos(-1)表示π while(scanf("%lf %lf %lf %lf %lf %lf", &x1, &y1, &r1, &x2, &y2, &r2) != EOF) { d = sqrt(fabs((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)));//辆圆心距离 if(d >= r1 + r2)//说明相离或相切 printf("0.000\n"); else if(d <= fabs(r1 - r2))//说明内含或内切 printf("%.3lf\n", pi * min(r1, r2) * min(r1, r2));//后面是表示更小的半径的平方 else//相交的情况 { a1 = 2 * acos((d * d + r1 * r1 - r2 * r2) / (2 * r1 * d));//余弦定理 a2 = 2 * acos((d * d + r2 * r2 - r1 * r1) / (2 * r2 * d));//余弦定理 s1 = a1 / (2 * pi) * pi * r1 * r1;//扇形面积=弧度所占比率*圆面积 s2 = a2 / (2 * pi) * pi * r2 * r2;//扇形面积=弧度所占比率*圆面积 s3 = d * r1 * sin(a1 / 2); printf("%.3lf\n", s1 + s2 - s3); }

} return 0; } 5: Intersecting Lines 描述 We all know that a pair of distinct points on a plane defines a line and that a pair of lines on a plane will intersect in one of three ways: 1) no intersection because they are parallel, 2) intersect in a line because they are on top of one another (i.e. they are the same line), 3) intersect in a point. In this problem you will use your algebraic knowledge to create a program that determines how and where two lines intersect. Your program will repeatedly read in four points that define two lines in the x-y plane and determine how and where the lines intersect. All numbers required by this problem will be reasonable, say between -1000 and 1000. 输入 The first line contains an integer N between 1 and 10 describing how many pairs of lines are represented. The next N lines will each contain eight integers. These integers represent the coordinates of four points on the plane in the order x1y1x2y2x3y3x4y4. Thus each of these input lines represents two lines on the plane: the line through (x1,y1) and (x2,y2) and the line through (x3,y3) and (x4,y4). The point (x1,y1) is always distinct from (x2,y2). Likewise with (x3,y3) and (x4,y4). 输出 There should be N+2 lines of output. The first line of output should read INTERSECTING LINES OUTPUT. There will then be one line of output for each pair of planar lines represented by a line of input, describing how the lines intersect: none, line, or point. If the intersection is a point then your program should output the x and y coordinates of the point, correct to two decimal places. The final line of output should read "END OF OUTPUT". 样例输入 5 0 0 4 4 0 4 4 0 5 0 7 6 1 0 2 3 5 0 7 6 3 -6 4 -3 2 0 2 27 1 5 18 5 0 3 4 0 1 2 2 5 样例输出 INTERSECTING LINES OUTPUT POINT 2.00 2.00 NONE LINE POINT 2.00 5.00 POINT 1.07 2.20 END OF OUTPUT 翻译: 描述 我们都知道平面上两点定义一条直线,平面上两条线会有三种关系:1.平行 2.重合 3.相交。 在这个问题中你将会使用几何知识来解决问题,决定两条线的位置关系。 你的问题是重复的读取 4 个点,定义两条线在 x-y 平面的位置关系。所有需要的数字都会给出。范围在-1000 到 1000 之间。 输入 第一行一个整数 N(1<=n<=10)表示有多少条线。后面 N 行给出 8 个整数。这些整数分别代表四个点的平面坐标 x1y1x2y2x3y3x4y4。因 此每行代表平面上的两条线:一条线穿过(x1,y1)(x2,y2),另一条穿过(x3,y3)(x4,y4)。 点(x1,y1)不和(x2,y2)一样,类似的(x3,y3)(x4,y4)也不同。 输出 应该输出 N+2 行。第一行输出 "INTERSECTING LINES OUTPUT" 。后面有 n 行每行输出该行两条直线的关系: none, line, 或 point。 如果关系是 point,你的问题是应该输出交点坐标 x,y(精确度小数点后两位)。 最后一行输出"END OF OUTPUT"。

思路/方法:下面是各种情况的判断方法,我们采用向量法更为简洁一点,但是公式难推,所以记住就行。 平行:两条线的向量的外积 等于 0 就说明平行。 重合:如果 p1,p2,p3 共线 并且 p1,p2,p4 共线,那么两条直线共线。三点是否共线可以用外积(叉乘),例如:如果 p1 p2 p3 共 线,则(p2-p1)X(p3-p1)=0 相交:不是上面的情况就是相交了。交点需要用公式,推导好麻烦,总之就是难以解释公式,能记住就记住,不能就算了,反正用的 时候百度就行了,比赛中几何一般较少,一般不会考这样的,考了也会给公式的。 注意:应该先判断是否重合在判断平行,否则重合就包含在平行里面了。 代码: #include <iostream> #include <cstdio> #include <cmath> using namespace std; //声明 class point; class line; double outerProduct(line & l1, line & l2); double outerProduct(point & l1, point & l2); class point { public: int x, y; point(int x1, int y1) { x = x1; y = y1; } point(){} point operator -(point & p) { point p1; p1.x = x - p.x; p1.y = y - p.y; return p1; } }; class line: public point { public: point pa, pb; double c;//c 用来计算两线交点的 line(point & p1, point & p2): pa(p1), pb(p2) { x = p2.x - p1.x; y = p2.y - p1.y; c = outerProduct(p1, p2);//点的外积 } line(){} bool operator ==(line & l)//重载==用于表示两线是否重合 {//如果(p2-p1)X(p3-p1)=0,则 p1,p2,p3 共线 point p21 = pb - pa, p31 = l.pa - pa, p41 = l.pb - pa;

if(fabs(outerProduct(p21, p31)) < 1e-8 && fabs(outerProduct(p21, p41)) < 1e-8)//如果 p1,p2,p3 共线,p1,p2, p4 共线就说明重合, return true; else return false; } }; double outerProduct(line & l1, line & l2)//线的外积 { return l1.x * l2.y - l2.x * l1.y; } double outerProduct(point & l1, point & l2)// 点的外积 { return l1.x * l2.y - l2.x * l1.y; } int main() { int n, i; point p1, p2, p3, p4; double c;//c 用来表示两线的外积 scanf("%d", &n); printf("INTERSECTING LINES OUTPUT\n"); for(i = 0; i < n; i++) { scanf("%d %d %d %d %d %d %d %d", &p1.x, &p1.y, &p2.x, &p2.y, &p3.x, &p3.y, &p4.x, &p4.y); line l1(p1, p2), l2(p3, p4); c = outerProduct(l1, l2);//两线外积 if(l1 == l2)//重合 printf("LINE\n"); else if(fabs(c) < 1e-8)//判断外积是否为 0,如果为 0 说明平行。这里为了精确,用小于无穷小来判断是否为 0 printf("NONE\n"); else { double x, y; y = (l1.y * l2.c - l2.y * l1.c) / c;//除以外积 x = -(l1.c * l2.x - l2.c * l1.x) / c; printf("POINT %.2lf %.2lf\n", x, y); } } printf("END OF OUTPUT\n"); return 0; } 6: 改革春风吹满地 描述 “ 改革春风吹满地, 不会 AC 没关系; 实在不行回老家, 还有一亩三分地。 谢谢!(乐队奏乐)” 话说部分学生心态极好,每天就知道游戏,这次考试如此简单的题目,也是云里雾里,而且,还竟然来这么几句打油诗。 好呀,老师的责任就是帮你解决问题,既然想种田,那就分你一块。

这块田位于浙江省温州市苍南县灵溪镇林家铺子村,多边形形状的一块地,原本是 linle 的,现在就准备送给你了。不过,任何事情 都没有那么简单,你必须首先告诉我这块地到底有多少面积,如果回答正确才能真正得到这块地。 发愁了吧?就是要让你知道,种地也是需要 AC 知识的!以后还是好好练吧... 输入 输入数据包含多个测试实例,每个测试实例占一行,每行的开始是一个整数 n(3<=n<=100),它表示多边形的边数(当然也是顶点数), 然后是按照逆时针顺序给出的 n 个顶点的坐标(x1, y1, x2, y2... xn, yn),为了简化问题,这里的所有坐标都用整数表示。 输入数据中所有的整数都在 32 位整数范围内,n=0 表示数据的结束,不做处理。 输出 对于每个测试实例,请输出对应的多边形面积,结果精确到小数点后一位小数。 每个实例的输出占一行。 样例输入 3 0 0 1 0 0 1 4 1 0 0 1 -1 0 0 -1 0 样例输出 0.5 2.0 思路/方法:这题没什么难度,就是考了一个多边形面积的公式。 多边形面积=|Xi |Xi+1 写成代码就是下面的 代码: #include <stdio.h> int main() { int i, n; double A;//多边形面积 while(scanf("%d", &n), n != 0) { int x[n], y[n]; A = 0; for(i = 0; i < n; i++) scanf("%d %d", x + i, y + i); for(i = 0; i < n - 1; i++)//前 n-1 个,最后一个要特殊处理 A = A + (x[i] * y[i + 1] - y[i] * x[i + 1]); A = A + (x[i] * y[0] - y[i] * x[0]);//最后一个是和开头的点 A = A / 2.0; printf("%.1lf\n", A); } return 0; } 7: The centre of polygon 描述 Given a polygon, your task is to find the centre of gravity for the given polygon. 输入 The input consists of T test cases. The number of them (T) is given on the first line of the input file. Each test case begins with a line containing a single integer N (3 <= N <= 1000000) indicating the number of points that form the polygon. This is followed by N lines, each containing two integers Xi and Yi (|Xi|, |Yi| <= 20000). These numbers are the coordinates of the i-th point. When we connect the points in the given order, we get a polygon. You may assume that the edges never Yi|求和(i = 1 到 n) / 2.0 Yi+1|

touch each other (except the neighboring ones) and that they never cross. The area of the polygon is never zero, i.e. it cannot collapse into a single line. 输出 Print exactly one line for each test case. The line should contain exactly two numbers separated by one space. These numbers are the coordinates of the centre of gravity. Round the coordinates to the nearest number with exactly two digits after the decimal point (0.005 rounds up to 0.01). Note that the centre of gravity may be outside the polygon, if its shape is not convex. If there is such a case in the input data, print the centre anyway. 样例输入 2 4 5 0 0 5 -5 0 0 -5 4 1 1 11 1 11 11 1 11 样例输出 0.00 0.00 6.00 6.00 翻译: 描述 给你一个图像,你的任务是找出它的重心。 输入 输入包括 T 组测试数据。第一行给出一个数字 T。每组测试数据一行,以一个整数 N(3 <= N <= 1000000) 开头,表示有 N 个点构成几 何图像。后面有 N 行,每行两个整数 Xi Yi(|Xi|, |Yi| <= 20000)。这些数字是第 i 个点的坐标。当我们按顺序连接这些点,我们就 得到一个图形。你可以假设这些边不想交,图形面积一定不为 0,即一定能构成多边形。 输出 每组测试数据输出一行以空格分隔的两个数字。这两个数字为图形的重心坐标,精确到小数点后两位。提示:如果不是凸面,重心可 能在图形外面。 思路/方法: 三角形的重心 (x1+x2+x3) / 3,(y1+y2+y3) / 3 多边形的重心 剖分成 N 个三角形,分别求出其重心和面积,这时可以想象,原来质量均匀分布在内部区域上,而现在质量仅仅分布在这 N 个重心点 上(等假变换),这时候就可以利用刚才的质点系重心公式了。 不过,要稍微改一改,改成加权平均数,因为质量不是均匀分布的,每个质点代表其所在三角形,其质量就是该三角形的面积(有向 面积!),——这就是权! 求多边形的面积可以参考之前的文章 http://www.ittianyu.com/a/OJxiangjie/2015/0514/157.html 我们求重心也是利用求面积公式,只是多了一个权(就是要多乘一个坐标) 代码: #include <stdio.h> #include <math.h> int main() { int t, i, n, j; double xt, yt, s;//大 A 表示多边形面积,xt,yt 用于表示最终结果

scanf("%d", &t); for(i = 0; i < t; i++) { s = xt = yt = 0; scanf("%d", &n); int x[n], y[n];//a 表示第 i 个三角形的面积 double m[n]; for(j = 0; j < n; j++) scanf("%d %d", x + j, y + j); for(j = 0; j < n - 1; j++)//前 n-1 的处理 { m[j] = (x[j] * y[j + 1] - y[j] * x[j + 1]) / 2.0;//求面积公式 s = s + m[j];//s 为总面积 xt = xt + (x[j] + x[j + 1]) * m[j];//乘上了坐标的分面积 yt = yt + (y[j] + y[j + 1]) * m[j];//乘上了坐标的分面积 } //最后一个的处理 m[j] = (x[j] * y[0] - y[j] * x[0]) / 2.0; s = s + m[j]; xt = xt + (x[j] + x[0]) * m[j];//乘上了坐标的分面积 yt = yt + (y[j] + y[0]) * m[j];//乘上了坐标的分面积 xt = xt / s / 3;//除以 3 是因为 3 个点构成一个三角形,是三角形面积*重心的求和/总面积。前面没有处理坐标,总的就 要除以 3 yt = yt / s / 3; printf("%.2lf %.2lf\n", xt, yt); } return 0; } 8: 外切圆 描述 给定 2 个外切圆的半径,求与两圆相切,并且同时与 2 个已知圆的外公切线相切的圆半径大小 m。如图所示: 输入 输入数据有多组,第一行为正整数 n,表示数据的组数,每行 2 个正整数 r 和 s,表示 2 个外切的圆半径大小。 输出 每组输出数据个数如下: Case #n: m n 表示数据编号,从 1 开始。m 为一个实数,表示待求圆的半径大小,保留 2 位小数。如: 3.454 应该输出 3.45,3.455 应该输出 3.46 样例输入 3 1 1 1 2 19 88 样例输出 Case #1: 0.25 Case #2: 0.34 Case #3: 8.86 思路/方法:如下图(r1 r2 r3 分别为三个圆的半径)。我们可以通过勾股定理建立以下等式 d^2=(r1+r2)^2 - (r2-r1)^2 d1^2=(r1+r3)^2 - (r1-r3)^2

d2^2=(r2+r3)^2 - (r2-r3)^2 d=d1+d2

将上面前 3 个式子带入第 4 个中,我们可以得到 sqrt((r1+r2)^2 - (r2-r1)^2) = sqrt((r1+r3)^2 - (r1-r3)^2) + sqrt((r2+r3)^2 - (r2-r3)^2) 下面是化简步骤 sqrt(r1*r2)= sqrt(r1*r3) + sqrt(r2*r3) r1*r2=r1*r3 + r2*r3 + 2*sqrt(r1*r2)*r3 r1*r2=r3(r1+r2+2*sqrt(r1*r2)) r3=r1*r2/(r1+r2+2*sqrt(r1*r2)) 最后我们得到了 r3 的公式,所以代码就非常容易写了。 注意:有些人可能看到了中间那个斜三角形,把它当成了直角三角形,用勾股定理,结果算出来是错的,因为 c1 c2 c3 三个点构成的 三角形不一定是直角三角形,无法证明,所以我们要用 d=d1+d2 来推出 r3 的公式。 代码: #include <stdio.h> #include <math.h> int main() { int i, n, r1, r2, t; double r3;//表示 的塔 scanf("%d", &n); for(i = 0; i < n; i++) { scanf("%d %d", &r1, &r2); //开始求值 r3=r1*r2/(r1+r2+2*sqrt(r1*r2)) t = r1 * r2; r3 = t / (r1 + r2 + 2 * sqrt(t)); printf("Case #%d: %.2lf\n", i + 1, r3); } return 0; } 9: Collision detection 描述 Given a rectangular wall represented by the upper left point (0,0) and the lower right point (n,m). There is one ball at (x0,y0) in the rectangle,and its' initial speed (vx, vy), vx and vy are the x and y direction speed (per second). Now, we want to know where is the ball after t seconds. We can guarantee with the wall. 输入 There are multiple test cases, in each case: the ball will occurred a perfect elastic collision

First line has two integers n , m (10<=n,m<=500); Second line has two integers x0 , y0 representing the coordinate of the ball.(1<=x0<=n , 1<=y0<=m) Third line has two integers xv , yv representing the speed in x direction and the speed in y direction .(0<=xv<=n , 0<=yv<=m) In the last line , there is a integer t stand for the time. All of the input value are integer. 输出 For each case, output two integers representing the coordinate of the ball after t seconds. 样例输入 10 10 1 1 4 6 3 样例输出 7 1 提示 If the ball just crashed into the corner , it will go back in the reverse direction 翻译: 描述 给一个以左上角点为(0,0)右下角点为(n,m)的矩形墙。有一个球在矩形内(x0,y0),它的初始速度 (vx, vy), vx 和 vy 是 x and y 方 向上的速度(每秒). 现在,我们想知道球在经过 t 秒后的位置。我们可以保证球和墙发生完全弹性碰撞。 输入 输出多组测试数据,每组测试数据如下: 第一行两个整数 n m(10<=n,m<=500) 第二行有两个整数 x0 y0 代表球的坐标(1<=x0<=n , 1<=y0<=m) 第三行有两个整数 xv, yv 代表在 x 和 y 方向上的速度(0<=xv<=n , 0<=yv<=m) 最后一行一个整数 t 代表时间 所有输入的值都是整数 输出 对于每组测试数据,输出两个整数代表 t 秒后球的坐标。 思路/方法:这题很简单,循环 t 次,模拟球的运动,对于 x,当发现 x0 > m 或 x0 < 0 时速度改变方向,然后调整当前球的的位置; 对于 y 也一样。 很多人可能知道 x0 > m 时要调整反弹后的位置,然后速度反向,当却忘了速度反向后坐标是减少的,所以要考虑 x0 < 0 时的情况。 知道上面的后就容易写代码了,下面的代码应该一看就明白了。 代码: #include <stdio.h> int main() { int i, n, m, x0, y0, vx, vy, t; while(scanf("%d %d", &n, &m) != EOF) { scanf("%d %d", &x0, &y0); scanf("%d %d", &vx, &vy); scanf("%d", &t); for(i = 0; i < t; i++)//模拟 t 秒 { x0 = x0 + vx;//1 秒后的位置 y0 = y0 + vy; if(x0 > n)//x 方向上的处理

{ x0 = n - (x0 - n);//反弹回来 vx = -vx; } else if(x0 < 0) { x0 = -x0;//反弹回来了 vx = -vx; } if(y0 > m)//y 方向上的处理 { y0 = m - (y0 - m); vy = -vy; } else if(y0 < 0) { y0 = -y0; vy = -vy; } } printf("%d %d\n", x0, y0); } return 0; } 10: Surround the Trees 描述 There are a lot of trees in an area. A peasant wants to buy a rope to surround all these trees. So at first he must know the minimal required length of the rope. However, he does not know how to calculate it. Can you help him? The diameter and length of the trees are omitted, which means a tree can be seen as a point. The thickness of the rope is also omitted which means a rope can be seen as a line.

There are no more than 100 trees. 输入 The input contains one or more data sets. At first line of each input data set is number of trees in this data set, it is followed by series of coordinates of the trees. Each coordinate is a positive integer pair, and each integer is less than 32767. Each pair is separated by blank. Zero at line for number of trees terminates the input for your program. 输出 The minimal length of the rope. The precision should be 10^-2. 样例输入 2 1 1 2 2 9 12 7

24 9 30 5 41 9 80 7 50 87 22 9 45 1 50 7 0 样例输出 2.83 243.06 翻译: 描述 一个区域有很多树。一个农民想要买一条绳子来围住所有的树。因此一开始他必须知道绳子最短需要多长。然而,他不知道怎么去计 算。你能帮助他吗? 树的直径和长度被忽略,意思是树可以被看作一个点。绳子的厚度也被忽略,意思是绳子能被看作一条线。 树数量不超过 100。 输入 输入包括多组数据集合。每组数据第一行是一个数字表示有多少棵树,后面跟着一系列树的坐标。每个坐标是一组正整数,每个整数 小于 32767,坐标之间以空格分隔。 输入 0 结束 输出 最小的绳子长度。精确到 10^-2。 思路/方法:这题是典型的凸包题。 凸包主要思想: 对于一个有三个或以上点的点集 Q 令 p0 为 Q 中 Y-X 坐标排序下最小的点 Q 设<p1,p2,...pm>为对其余点按以 p0 为中心的极角逆时针排序所得的点集(如果有多个点有相同的极角,除了距 p0 最远的点外全部移 除) 压 p0 进栈 S,压 p1 进栈 S,压 p2 进栈 S for(i=3;i<=m; i++) { while(由 S 的栈顶元素的下一个元素、S 的栈顶元素以及 pi 构成的折线段不拐向左侧) 对 S 弹栈 压 pi 进栈 S } return S 这题需要注意的是,当 n=2 时,也就是只有两个点时,绳子长度为 2*d,因为要围住两点,必须要绕一圈,也就是两倍的距离。 具体实现请看代码,已经给出了详细注释。 代码: #include <iostream> #include <cstdio> #include <cmath> #include <algorithm> using namespace std; //声明 class point {

public: int x, y; point(int x1, int y1) { x = x1; y = y1; } point(){} bool operator <(point & p) { if(fabs(y - p.y) < 1e-10)//就是 y 相同时 return x < p.x;//比较 x else return y < p.y;//否则比较 y } point & operator =(point p)//这里不能用引用,否则提交会编译错误 { x = p.x; y = p.y; return *this; } }; point p[100];//定义 100 个点 point s[100];//当作栈来用 double Distance(point & a, point & b) { return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y)); } double outerProduct(point & a, point & b, point & c)//向量的外积,就是 ab x ac { return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x); } bool compare(point a, point b) { double d = outerProduct(p[0], a, b);//判断 p0a X p0b 的值 if(fabs(d) < 1e-10)//如果外积为 0,说明平行 return Distance(a, p[0]) < Distance(b, p[0]);//如果 pa 和 pb 平行,就判断那个点更远 else return d > 0;//不平行就判断夹角是否为 0-180 度之间 } int hull(int n)//完成后 s 里面存储的就要最小的围成的点,返回点的个数 { int i, top = 2; //先将 p0 p1 p2 压入栈 s[0] = p[0]; s[1] = p[1]; s[2] = p[2]; for(i = 3; i < n; i++) { while(outerProduct(s[top - 1], s[top], p[i]) <= 0)//由 S 的栈顶元素的下一个元素、S 的栈顶元素以及 pi 构成的折线 段不拐向左侧 {

//出栈操作 top--; } //把 p[i]入栈 top++; s[top] = p[i]; } return top; } int main() { int n, i, minY; double l;//用来存储凸包总长度 while(scanf("%d", &n), n != 0) { for(i = 0; i < n; i++) scanf("%d %d", &p[i].x, &p[i].y); if(n == 1) { printf("0.00\n"); continue; } else if(n == 2)//当只有两个点时,长度应该是 p1p2 的两倍,因为即使两线重合,也要算长度 { printf("%.2lf\n", 2 * Distance(p[0], p[1])); continue; } //选择法思想找出 y 最小的点,存储到 p[0] minY = 0; for(i = 1; i < n; i++) if(p[i] < p[minY])//重载的<。比较的时候如果 y 小就返回真,如果 y 一样,就比较 x,x 小就返回真 minY = i; if(minY != 0)//最小值不是初始的第一个,就交换 0 和 minY {//重载了=,可以直接赋值 point t = p[0]; p[0] = p[minY]; p[minY] = t; } //对 p[1]到 p[n-1]进行排序,排序标准为 pipj pipj+1 的夹角 sort(p + 1, p + n, compare); int top = hull(n); l = 0; for(i = 0; i < top; i++)//一直到 i+1=n 的那个点 l = l + Distance(s[i], s[i + 1]); l = l + Distance(s[i], s[0]);//最后一个点和第一个点的线段长度 printf("%.2lf\n", l); } return 0; }

三、深搜
1: Counting Sheep 描述 A while ago I had trouble sleeping. I used to lie awake, staring at the ceiling, for hours and hours. Then one day my grandmother suggested I tried counting sheep after I'd gone to bed. As always when my grandmother suggests things, I decided to try it out. The only problem was, there were no sheep around to be counted when I went to bed. Creative as I am, that wasn't going to stop me. I sat down and wrote a computer program that made a grid of characters, where # represents a sheep, while . is grass (or whatever you like, just not sheep). To make the counting a little more interesting, I also decided I wanted to count flocks of sheep instead of single sheep. Two sheep are in the same flock if they share a common side (up, down, right or left). Also, if sheep A is in the same flock as sheep B, and sheep B is in the same flock as sheep C, then sheeps A and C are in the same flock. Now, I've got a new problem. Though counting these sheep actually helps me fall asleep, I find that it is extremely boring. To solve this, I've decided I need another computer program that does the counting for me. Then I'll be able to just start both these programs before I go to bed, and I'll sleep tight until the morning without any disturbances. I need you to write this program for me. 输入 The first line of input contains a single number T, the number of test cases to follow. Each test case begins with a line containing two numbers, H and W, the height and width of the sheep grid. Then follows H lines, each containing W characters (either # or .), describing that part of the grid. 输出 For each test case, output a line containing a single number, the amount of sheep flock son that grid according to the rules stated in the problem description. Notes and Constraints 0 < T <= 100 0 < H,W <= 100 样例输入 2 4 4 #.#. .#.# #.## .#.# 3 5 ###.# ..#.. #.### 样例输出 6 3 翻译: 描述 刚才我有睡觉问题。我过去常常躺着睡不着。瞪着天花板,一个小时又一个小时。然后一天我祖母建议我睡觉时尝试数绵羊。一如既 往祖母建议这个。我决定尝试一次。唯一的问题是,周围没有绵羊可以数当我睡觉的时候。 富有创意的我,没有被阻止。我坐起来写了一个字符格子计算机程序。#代表羊。.是草坪(或者其他你认为的东西,只要不是羊)。为 了使计算更有趣一点。我也决定去计算羊群而不是一只羊。两只羊如果在同一边(上,下,右或左),则在同一个群。如果 A 和 B 在 同一个群,B 和 C 同一个群,则 A 和 C 同一个群。 现在,我得到了一个新问题。尽管数这些羊确实帮助我入睡。我发现这非常无聊。为了解决这问题,我决定我需要另外一个计算机程 序为我计算。我只要在我睡觉前将这两个程序启动,我就能够安稳睡到早上没有打扰。我需要你为我写这个程序。 输入 第一行输入保护一个整数 T,接下来有 T 组测试数据。

每组测试数据以一行两个整数 H W 开头。表示格子的高度和宽度。然后接下来 H 行,每行 W 个字符(#或.)描述格子的各个部分。 输出 每组测试数据输入一行包含一个整数,根据规则计算的羊群的数量。 0 < T <= 100 0 < H,W <= 100 思路/方法:这题可以用深搜来做。 简单说就是从一个点开始搜索周围,直到所有的路都走完,无路可走时返回。 下面代码有详细注释,应该能看得懂。 代码: #include <stdio.h> const int d[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};//分别为向下、右、上、左方向的搜索 void dfs(int x, int y, int h, int w, char a[h][w], int flag[h][w]) { int i, dx, dy; for(i = 0; i < 4; i++) {//循环四次,每次代表一个方向的搜索 dx = x + d[i][0]; dy = y + d[i][1]; if(dx >= 0 && dx < h && dy >= 0 && dy < w && flag[dx][dy] == 0 && a[dx][dy] == '#') { flag[dx][dy] = 1; dfs(dx, dy, h, w, a, flag);//继续搜索(dx,dy)四周是否符合条件 } } } int main() { int c, i, t, j, k, h, w; scanf("%d", &t); for(i = 0; i < t; i++) { c = 0;//计数器清零 scanf("%d %d", &h, &w); char a[h][w];//h 行 w 列的矩阵 int flag[h][w];//用于标记当前位置是否已经遍历过了 for(j = 0; j < h; j++) { scanf("%s", a[j]); for(k = 0; k < w; k++) flag[j][k] = 0;//初始化标记 } for(j = 0; j < h; j++) for(k = 0; k < w; k++) if(a[j][k] == '#' && flag[j][k] == 0)//如果是羊。且未被统计过 { c++; flag[j][k] = 1;//把当前搜索过的进行标记 dfs(j, k, h, w, a, flag);//再对该位置的四个方向进行搜索,直到碰壁为止 } printf("%d\n", c);

} return 0; } 2: Fire Net 描述 Suppose that we have a square city with straight streets. A map of a city is a square board with n rows and n columns, each representing a street or a piece of wall. A blockhouse is a small castle that has four openings through which to shoot. The four openings are facing North, East, South, and West, respectively. There will be one machine gun shooting through each opening. Here we assume that a bullet is so powerful that it can run across any distance and destroy a blockhouse on its way. On the other hand, a wall is so strongly built that can stop the bullets. The goal is to place as many blockhouses in a city as possible so that no two can destroy each other. A configuration of blockhouses is legal provided that no two blockhouses are on the same horizontal row or vertical column in a map unless there is at least one wall separating them. In this problem we will consider small square cities (at most 4x4) that contain walls through which bullets cannot run through. The following image shows five pictures of the same board. The first picture is the empty board, the second and third pictures show legal configurations, and the fourth and fifth pictures show illegal configurations. For this board, the maximum number of blockhouses in a legal configuration is 5; the second picture shows one way to do it, but there are several other ways.

Your task is to write a program that, given a description of a map, calculates the maximum number of blockhouses that can be placed in the city in a legal configuration. 输入 The input file contains one or more map descriptions, followed by a line containing the number 0 that signals the end of the file. Each map description begins with a line containing a positive integer n that is the size of the city; n will be at most 4. The next n lines each describe one row of the map, with a '.' indicating an open space and an uppercase 'X' indicating a wall. There are no spaces in the input file. 输出 For each test case, output one line containing the maximum number of blockhouses that can be placed in the city in a legal configuration. 样例输入 4 .X.. .... XX.. .... 2 XX .X 3 .X. X.X .X. 3 ...

.XX .XX 4 .... .... .... .... 0 样例输出 5 1 5 2 4 翻译: 描述 加速我们有一个带有笔直街道的正方形城市。城市的地图是一个 n 行 n 列的正方形,每个代表街道或一堵墙。 一个碉堡是一个小的城堡有四个开放的通道可以去射击。四个方向分别是北,东,南,西。那有一个机器枪可以射击穿过四个方向的 通道。 我们假设子弹足够强大能够穿过任何距离并且破坏在它方向上的碉堡。另一个方面,墙足够坚固能够阻挡子弹。 目标是尽可能的多放置碉堡在一个城市中。一个碉堡的布局合法的要求是两个碉堡不在同一个水平或垂直线上,除非中间至少有一堵 墙分隔他们。在这个问题我们会考虑小的正方形城市(最大 4*4)包含子弹不能穿透的墙。 下面展示了 5 张有相同框架的图片。第一张图片是空的框架,第二和第三张展示了合法的布局,第四和第五张图片展示了非法的布局。 对于这个框架,在合法布局中最大的碉堡数是 5,第二张图片展示的是其中一种方式,也有一些其他方式。 你的任务是写一个程序,给定地图的描述,计算城市中合法布局的碉堡的最大数量。 输入 输入包含多组测试数据,以数字 0 表示输入结束。 每组测试数据第一行包含一个正整数 n 表示城市的大小;n 最大是 4。接下来 n 行每行描述地图的一行,'.'表示一个开发的空间,大 写的'X'表示墙。 输出 每组测试数据输出一行整数,表示城市中合法布局的碉堡的最大数量。 思路/方法:这题是简单的深搜+回溯。 这里不过多的说这些算法,不懂的先学习算法在来看代码。代码已经给出了详细的注释。 代码: #include <stdio.h> int n;//地图大小 int max;//表示最大的可放置碉堡的数量 char map[5][5];//最大 4*4 的方阵,还需要一个位置来存储\0 int canPlace(int x, int y)//判断(x,y)是否能放置碉堡 { int i; if(map[x][y] == 'X')//是障碍物,不能放置 return 0; for(i = x - 1; i >= 0; i--)//循环 x-1 次,判断从 0 到 x-1 的行位置是否已经放置了碉堡 if(map[i][y] == 'b')//表示碰到碉堡了 return 0; else if(map[i][y] == 'X')//碰到墙壁时就停止搜索了 break; for(i = y - 1; i >= 0; i--)//循环 y-1 次,判断从 0 到 y-1 的列位置是否已经放置了碉堡

if(map[x][i] == 'b')//表示碰到碉堡了 return 0; else if(map[x][i] == 'X')//碰到墙壁时就停止搜索了 break; return 1;//运行到这里还没说明之前没碰到碉堡,所以返回真 } void dfs(int k, int currentNumber)// 搜索的起始位置 当前已经放置的碉堡数 { int x, y; if(k == n * n)//搜索的位置是地图最后一个位置之后的一个位置。因为 k 是从 0 开始的,所以当 k==n*n 时,就说明整个地图搜 索完成 { if(currentNumber > max)//如果当前已经放置的碉堡数 比 记录中最大的数 更大,就更新最大值 max = currentNumber; return; } x = k / n;//行位置 y = k % n;//列位置 if(canPlace(x, y)) { map[x][y] = 'b';//放置碉堡 dfs(k + 1, currentNumber + 1);//搜索下一个位置,计数器加 1 map[x][y] = '.';//回溯,这个不好解释,不懂的上网自己查查 } dfs(k + 1, currentNumber);//搜索下一个位置,因为没成功放置,计数器不修改 } int main() { int i; while(scanf("%d", &n), n != 0) { for(i = 0; i < n; i++)//输入地图 scanf("%s", map[i]); max = 0;//每组测试前清零 dfs(0, 0); printf("%d\n", max); } return 0; } 3: Tempter of the Bone 描述 The doggie found a bone in an ancient maze, which fascinated him a lot. However, when he picked it up, the maze began to shake, and the doggie could feel the ground sinking. He realized that the bone was a trap, and he tried desperately to get out of this maze. The maze was a rectangle with sizes N by M. There was a door in the maze. At the beginning, the door was closed and it would open at the T-th second for a short period of time (less than 1 second). Therefore the doggie had to arrive at the door on exactly the T-th second. In every second, he could move one block to one of the upper, lower, left and right neighboring blocks. Once he entered a block, the ground of this block would start to sink and disappear in the next second. He could not stay at one block for more than one second, nor could he move into a visited block. Can the poor doggie survive? Please help him. 输入

The input consists of multiple test cases. The first line of each test case contains three integers N, M, and T (1 < N, M < 7; 0 < T < 50), which denote the sizes of the maze and the time at which the door will open, respectively. The next N lines give the maze layout, with each line containing M characters. A character is one of the following: 'X': a block of wall, which the doggie cannot enter; 'S': the start point of the doggie; 'D': the Door; or '.': an empty block. The input is terminated with three 0's. This test case is not to be processed. 输出 For each test case, print in one line "YES" if the doggie can survive, or "NO" otherwise. 样例输入 4 4 5 S.X. ..X. ..XD .... 3 4 5 S.X. ..X. ...D 0 0 0 样例输出 NO YES 翻译: 描述 小狗在一个古代迷宫发现了一根非常吸引它的骨头。然而,当它要去捡起来时,迷宫开始摇动,小狗能感觉到地面在下降。他意识到 骨头是一个陷阱,它绝望的尝试着走出迷宫。 迷宫是一个尺寸为 N*M 的矩形。那有一扇门在迷宫中。一开始,门是关闭的,它将会在第 T 秒开启一小段时间(小于 1 秒)。因此小狗 不得不在确切的第 T 秒到达门。在任意一秒,它能从一个块区域移动到上下左右相邻的另一个区域。一旦它进入一个区域,这个区域 的地面将会开始下降并且在 1 秒后消失。它不能待在一块区域上超过 1 秒,也不能移动到一个障碍物上。这条可怜的小狗能否生存? 请帮助它。 输入 输入包含多组测试数据。每组测试数据第一行包含三个整数 N,M,T (1 < N, M < 7; 0 < T < 50),分别表示迷宫的尺寸和门开的时间。 后面 N 行给出了迷宫的布局。 'X':一堵墙,小狗不能通过 'S':小狗的起始点 'D':门 '.':空的区域 输出 每组测试数据输出一行,如果小狗能生成,输出"YES",否则输出"NO"。 思路/方法:深搜+剪枝。 需要剪枝的地方有: 1.可走的路程数小于时间 t ; 2.奇偶剪枝,最短步数时间 和 开门时间 的差 是奇数,就不可能刚好到达; 3.当前搜索的步数和 t 相同时,应该停止搜索。 4.碰到门时应该停止搜索。 代码:

#include <stdio.h> int n, m;//地图大小 int t;//表示第几秒开门 char map[7][8];//最大 7*7 的方阵,还需要一个位置来存储\0 int d[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};//四个方向 int abs(int a)//整数绝对值 { if(a < 0) a = -a; return a; } int search(int x, int y, int c)//表示当前位置 和 当前秒数 { if(c == t)//当前方案的步数已经大于 t 就直接返回 return map[x][y] == 'D';//如果刚好是门,说明成功了 else if(map[x][y] == 'D')//如果发现门了但步数不对,直接返回 return 0; else { int i, dx, dy; for(i = 0; i < 4; i++) { dx = x + d[i][0]; dy = y + d[i][1]; if(dx >= 0 && dx < n && dy >= 0 && dy < m && map[dx][dy] != 'X')// 在地图范围内 { char ch = map[dx][dy]; if(map[dx][dy] != 'D')//D 不能被改了 map[dx][dy] = 'X'; if(search(dx, dy, c + 1))//如果成功就直接返回 return 1; map[dx][dy] = ch;//回溯 } } return 0;//运行到这里就说明失败 } } int main() { int i, j, sx, sy, ex, ey, cr;//sx, sy, dx, dy 分别表示起点坐标和终点坐标 cq 表示墙的个数 while(scanf("%d %d %d", &n, &m, &t), !(n == 0 && m == 0 && t == 0)) { cr = 0; for(i = 0; i < n; i++)//输入地图 { scanf("%s", map[i]); for(j = 0; j < m; j++) if(map[i][j] == 'S')//狗的位置 { sx = i; sy = j; }

else if(map[i][j] == 'D')//门的位置 { ex = i; ey = j; cr++; } else if(map[i][j] == '.')//碰到点,计数器增加 cr++; } if(cr < t || (t - abs(sx - ex) + abs(sy - ey)) % 2 != 0)//两个剪枝条件 1.可走的路程数小于时间 t ; 2.最短步数时 间 和 开门时间 的差 是奇数,就不可能刚好到达 printf("NO\n"); else { map[sx][sy] = 'X';//走过的地方都变成障碍,防止重复走 if(search(sx, sy, 0)) printf("YES\n"); else printf("NO\n"); } } return 0; } 4: Mine Sweeper 描述 The game Minesweeper is played on an n by n grid. In this grid are hidden m mines, each at a distinct grid location. The player repeatedly touches grid positions. If a position with a mine is touched, the mine explodes and the player loses. If a positon not containing a mine is touched, an integer between 0 and 8 appears denoting the number of adjacent or diagonally adjacent grid positions that contain a mine. A sequence of moves in a partially played game is illustrated below.

Here, n is 8, m is 10, blank squares represent the integer 0, raised squares represent unplayed positions, and the figures resembling asterisks represent mines. The leftmost image represents the partially played game. From the first image to the second, the player has played two moves, each time choosing a safe grid position. From the second image to the third, the player is not so lucky; he chooses a position with a mine and therefore loses. The player wins if he continues to make safe moves until only m unplayed positions remain; these must necessarily contain the mines. Your job is to read the information for a partially played game and to print the corresponding board. 输入 The first line of input contains a single postitive integer n <= 10. The next n lines represent the positions of the mines. Each line represents the contents of a row using n characters: a period indicates an unmined positon while an asterisk indicates a mined position. The next n lines are each n characters long: touched positions are denoted by an x, and untouched positions by a period. The sample input corresponds to the middle figure above.

输出 Your output should represent the board, with each position filled in appropriately. Positions that have been touched and do not contain a mine should contain an integer between 0 and 8. If a mine has been touched, all positions with a mine should contain an asterisk. All other positions should contain a period. 样例输入 8 ...**..* ......*. ....*... ........ ........ .....*.. ...**.*. .....*.. xxx..... xxxx.... xxxx.... xxxxx... xxxxx... xxxxx... xxx..... xxxxx... 样例输出 001..... 0013.... 0001.... 00011... 00001... 00123... 001..... 00123... 翻译: 描述 游戏扫雷是一个格子游戏,在这个格子中隐藏了 m 个雷,每个都在确切的位置。玩家重复的触碰格子位置。如果有雷的位置被触碰, 雷将会爆炸并且玩家输了。如果一个没有雷的位置被触碰,一个 0-8 之间的整数表示相邻或对角相邻格子位置包含雷的个数。一个移 动顺序的部分游戏片段在下面图中表示出来。 这儿 n 是 8,m 是 10,空白的方格代表数字 0,凸起的方格代表未触碰的位置,像玫瑰的图像星号代表雷。最左边图片代表部分游戏片 段。从第一张图到第二张,玩家移动了两步,每次选择了一个安全的格子位置。从第二张图到第三张图,王家没那么幸运;他选择了 一个带有雷的位置,因此输了。如果他继续选择了安全的位置,知道只剩下 m 个位置,他就赢了;这些一定必然包含雷。 你的工作是去读这些部分游戏片段的信息并且答应出相应的边框。 输出 第一行输入包含一个正整数 n <= 10。后面 n 行代表雷的状态位置。每行用 n 个字符代表一行的内容:一个点号表示没雷的位置而一个 星号代表一个有雷的位置。后面 n 行每行都是 n 个字符长度:用 x 代表触碰过的位置,用点号代表未触碰过的位置。样例输出了上述 相应的图形。 输出 你的输出应该表示框架,每个位置填充合适的字符。位置已经被触碰并且不包含雷的应该包括一个 0-8 之间的整数。如果一个雷被触 碰,所有含雷的位置都应该包括一个星号。所有其他位置应该包括一个点号。 思路/方法:从雷的位置开始搜索周围,如果是数字,就把它累加 1,否则不处理。 需要注意的地方是,先把雷的数量求出来,最后判断是否触碰到雷,碰到雷就把所有雷都翻起来。因为碰到雷一定是最后一步操作, 所以需要先计数,后判断碰雷。

代码: #include <stdio.h> int n;//地图大小 char map[10][11];//最大 10*10 的方阵,还需要一个位置来存储\0 char touched[10][11];//表示触碰的位置 char result[10][11];//存储结果的数组 int d[8][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};//8 个方向 void dfs(int x, int y) { int i, dx, dy; for(i = 0; i < 8; i++) { dx = x + d[i][0]; dy = y + d[i][1]; if(dx >= 0 && dx < n && dy >= 0 && dy < n && result[dx][dy] != '.')// 如果在地图内 且 不是点 result[dx][dy] = result[dx][dy] + 1;//把累周围的数字累加 1 } } void failure() { int i, j; for(i = 0; i < n; i++) for(j = 0; j < n; j++) if(map[i][j] == '*') result[i][j] = '*'; } void display() { int i; for(i = 0; i < n; i++) printf("%s\n", result[i]);//因为前面有行结束标记\0,所以可以这样输出 } int main() { int i, j;//sx, sy, dx, dy 分别表示起点坐标和终点坐标 cq 表示墙的个数 scanf("%d", &n); for(i = 0; i < n; i++) scanf("%s", map[i]); for(i = 0; i < n; i++) { scanf("%s", touched[i]); for(j = 0; j < n; j++) { if(touched[i][j] == 'x')//如果是触碰过了,就先初始化为 0 result[i][j] = '0'; else result[i][j] = '.'; } result[i][j + 1] = '\0';//增加一个行结尾标记 }

//开始搜索 for(i = 0; i < n; i++) { for(j = 0; j < n; j++) if(map[i][j] == '*')//如果碰到累,就开始标记周围 dfs(i, j); } //处理翻出雷的问题 for(i = 0; i < n; i++) for(j = 0; j < n; j++) if(map[i][j] == '*')//如果碰到累,就开始标记周围 if(touched[i][j] == 'x')//如果累被翻开了 { failure(); i = n + 1;//用于跳出外面的大循环 break;//跳出当前循环 } display();//输出 return 0; } 5: Additive equations 描述 We all understand that an integer set is a collection of distinct integers. Now the question is: given an integer set, can you find all its addtive equations? To explain what an additive equation is, let's look at the following examples: 1+2=3 is an additive equation of the set {1,2,3}, since all the numbers that are summed up in the left-hand-side of the equation, namely 1 and 2, belong to the same set as their sum 3 does. We consider 1+2=3 and 2+1=3 the same equation, and will always output the numbers on the left-hand-side of the equation in ascending order. Therefore in this example, it is claimed that the set {1,2,3} has an unique additive equation 1+2=3. It is not guaranteed that any integer set has its only additive equation. For example, the set {1,2,5} has no addtive equation and the set {1,2,3,5,6} has more than one additive equations such as 1+2=3, 1+2+3=6, etc. When the number of integers in a set gets large, it will eventually become impossible to find all the additive equations from the top of our minds -- unless you are John von Neumann maybe. So we need you to program the computer to solve this problem. 输入 The input data consists of several test cases. The first line of the input will contain an integer N, which is the number of test cases. Each test case will first contain an integer M (1<=M<=30), which is the number of integers in the set, and then is followed by M distinct positive integers in the same line. 输出 For each test case, you are supposed to output all the additive equations of the set. These equations will be sorted according to their lengths first( i.e, the number of integer being summed), and then the equations with the same length will be sorted according to the numbers from left to right, just like the sample output shows. When there is no such equation, simply output "Can't find any equations." in a line. Print a blank line after each test case. 样例输入 3 3 1 2 3 3 1 2 5 6 1 2 3 5 4 6 样例输出 1+2=3 Can't find any equations.

1+2=3 1+3=4 1+4=5 1+5=6 2+3=5 2+4=6 1+2+3=6 翻译: 描述 我们都知道整数集合是不同整数的集合。现在问题是:给出一个整数集合,你能找出它的所有的相加等式吗?为了解释什么是一个相 加等式,让我们来看下面的例子: 1+2=3 是集合{1,2,3}的一个相加等式,因为所有的数字都被加到了等式的左手边,也就是 1 和 2,属于相同集合因为他们和是 3。我们 考虑 1+2=3 和 2+1=3 是相同的等式,总是以升序方式输出左手边的数字。因此在这个例子,它声明集合{1,2,3}有唯一一个相加等式 1+2=3。 不保证所有的整数集合都有唯一的相加等式。 例如, 集合{1,2,5}没有相加等式, 集合{1,2,3,5,6}有多个相加等式, 像 1+2=3, 1+2+3=6 等。当整数集合的数字变大时,最终从我们的思维找到所有的相加等式变得不可能--除非你是 John von Neumann 才有可能。因此我们 需要你去编写一个程序去解决这个问题。 输入 输入数据包括多组测试数据。 第一行包含一个整数 N,表示测试组数。 每组测试数据第一行包含一个整数 M(1<=M<=30),代表整数集合中整数的个数,接下来包含 M 个不同的正整数在同一行。 输出 每组测试数据,你应该输出集合的所有的相加等式。这些等式将会先根据他们的长度被排序,然后根据等式左边数字从左到右的大小 进行排序,就像样例输出所展示的。当没有相加等式的时候,简单的输出一行"Can't find any equations."。每组测试数据后输出一 个空行。 思路/方法:注意每组数据输出后还需要一个空的换行。主要是深搜的应用,代码有详细的注释。 代码: #include <cstdio> #include <algorithm> using namespace std; int n, m;//代表组数, 数字个数 int a[30];//存储数字集合 short visited[30];//标识是否被使用过 short flag;//用于表示是否存在加法式子 int sum;//表示当前的和 void dfs(int start, int length) { int i, j, tempSum = sum;//用个临时变量来代替 sum,防止 sum 被改变 if(length == 0)//用于找式子 { for(i = start; i < m && tempSum >= a[i]; i++) { if(tempSum == a[i])//式子和等于集合中一个元素 { flag = 1;//说明找到了 for(j = 0; j <= i; j++)//开始求出整个式子,肯定是在前 i 个里面找 { if(visited[j])//在用过的数字里面找

{ if(tempSum == a[j])//表示输出最后一个加数的情况 printf("%d=%d\n", a[j], a[i]);//输出格式不一样,所以需要用个 if 来判断 else printf("%d+", a[j]); tempSum = tempSum - a[j];//输出后就减去,用于判断是否到最后一个了 } } } } } else//还有长度说明式子还没弄完 { for(i = start; i < m; i++) { if(sum + a[i] <= a[m - 1])//数组最后一个是最大值,加的和肯定不能大于它 { sum = sum + a[i];//不超过就累加上 visited[i] = 1;//标记为使用过 length--;//式子长度减一 dfs(i + 1, length);//搜索下一个位置 //回溯 sum = sum - a[i]; visited[i] = 0; length++; } } } } int main() { int i, j; scanf("%d", &n); for(i = 0; i < n; i++) { scanf("%d", &m); for(j = 0; j < m; j++) { scanf("%d", a + j); visited[j] = 0;//初始化 } flag = 0; sort(a, a + m);//千万记得排序 for(j = 2; j < m; j++) { sum = 0;//每次清零 dfs(0, j);//从 0 位置开始,加法式子长度为 j } if(!flag) printf("Can't find any equations.\n"); printf("\n");//每组数据后面要一个空行 }

return 0; } 6: 速算 24 点 描述 速算 24 点相信绝大多数人都玩过。就是随机给你四张牌,包括 A(1),2,3,4,5,6,7,8,9,10,J(11),Q(12),K(13) 。要求只用 '+','-','*','/'运算符以及括号改变运算顺序,使得最终运算结果为 24(每个数必须且仅能用一次)。游戏很简单,但遇到无解的情况 往往让人很郁闷。你的任务就是针对每一组随机产生的四张牌,判断是否有解。我们另外规定,整个计算过程中都不能出现小数。 输入 每组输入数据占一行,给定四张牌。 输出 每一组输入数据对应一行输出。如果有解则输出"Yes",无解则输出"No"。 样例输入 A 2 3 6 3 3 8 8 样例输出 Yes No 思路/方法:主要是深搜算法。 4 个点的全排列有 4!种,而 4 个数字之间可以有 3 个位置插入运算符,运算符可以重复,所以一共有 4!*4^4 种情况, 我们可以每次拿到 2 个数做运算(+,-,*,/),得到 1 个数,再放回原来的集合,那么集合就从 4 个元素降至 3 个,减少了一个,就可以 用递归处理接下来的同类型的子问题。 注意:当输入 10 时,一个字符就放不下,所以需要用字符串来存储每个数字,然后转换成数字。 c++代码: #include <iostream> #include <string> using namespace std; int a[4]; bool dfs(int length) { int i, j; if(length == 1) if(a[0] == 24)//判断结果是否为 24 return true; else return false; for(i = 0; i < length; i++) for(j = i + 1; j < length; j++) { int c = a[i], d = a[j]; a[j] = a[length - 1];//压缩级数,就是经过运算后,集合中的可用数字减少了一个,这里为了方便,把计算结果放在 a[i],把右边未使用的移到 a[j],这样下次用时还是计算 a[i]和 a[j] //开始四则运算 a[i] = c + d; if(dfs(length - 1)) return true; a[i] = c - d; if(dfs(length - 1)) return true; a[i] = d - c;

if(dfs(length - 1)) return true; a[i] = c * d; if(dfs(length - 1)) return true; if(d != 0 && c % d == 0) { a[i] = c / d; if(dfs(length - 1)) return true; } if(c != 0 && d % c == 0) { a[i] = d / c; if(dfs(length - 1)) return true; } a[i] = c; a[j] = d; } return false; } int toNumber(const string & s)//文本转数字 { int n; if(s == "A") n = 1; else if(s == "J") n = 11; else if(s == "Q") n = 12; else if(s == "K") n = 13; else if(s == "10") n = 10; else n = s[0] - '0'; return n; } int main() { int i; string t[4]; while(cin >> t[0] >> t[1] >> t[2] >> t[3]) { for(i = 0; i < 4; i++) a[i] = toNumber(t[i]);//数字存储到 a 中 if(dfs(4)) cout << "Yes\n"; else cout << "No\n"; }

return 0; }

7: Anagrams by Stack 描述 How can anagrams result from sequences of stack operations? There are two sequences of stack operators which can convert TROT to TORT: [ i i i i o o o o i o i i o o i o ] where i stands for Push and o stands for Pop. Your program should, given pairs of words produce sequences of stack operations which convert the first word to the second. 输入 The input will consist of several lines of input. The first line of each pair of input lines is to be considered as a source word (which does not include the end-of-line character). The second line (again, not including the end-of-line character) of each pair is a target word. The end of input is marked by end of file. 输出 For each input pair, your program should produce a sorted list of valid sequences of i and o which produce the target word from the source word. Each list should be delimited by [ ] and the sequences should be printed in "dictionary order". Within each sequence, each i and o is followed by a single space and each sequence is terminated by a new line. Process A stack is a data storage and retrieval structure permitting two operations: Push - to insert an item and Pop - to retrieve the most recently pushed item We will use the symbol i (in) for push and o (out) for pop operations for an initially empty stack of characters. Given an input word, some sequences of push and pop operations are valid in that every character of the word is both pushed and popped, and furthermore, no attempt is ever made to pop the empty stack. For example, if the word FOO is input, then the sequence: i i o i o o is valid, but i i o is not (it's too short), neither is i i o o o i (there's an illegal pop of an empty stack) Valid sequences yield rearrangements of the letters in an input word. For example, the input word FOO and the sequence i i o i o o produce the anagram OOF. So also would the sequence i i i o o o. You are to write a program to input pairs of words and output all the valid sequences of i and o which will produce the second member of each pair from the first. 样例输入 madam adamm bahama bahama long short eric rice 样例输出 [ i i i i o o o i o o i i i i o o o o i o

i i o i o i o i o o i i o i o i o o i o ] [ i o i i i o o i i o o o i o i i i o o o i o i o i o i o i o i i i o o o i o i o i o i o i o i o ] [ ] [ i i o i o i o o ] 翻译: 描述 混字游戏如何由一组顺序的栈操作得到?有两个栈操作序列能把 TROT 转变成 TORT: [ i i i i o o o o i o i i o o i o ] i 代表入栈,o 代表出栈。你的程序应该通过给定的两组文本产生一组栈操作序列把第一组文本转化成第二组文本。 输入 输入保护多组测试数据。每组数据第一行保护一个原文本。第二行是目标文本。以文本尾表示输入结束。 输出 每组数据应该用下面的符号类分隔 [ ] 序列应该按字典顺序输出。在每组操作中,i 和 o 都跟着一个空格,每组序列后有一个换行。 过程 栈是一个数据存储和提取的结构,允许的两个操作: Push - 放入一个物体 Pop - 取出最新放入的物体 我们能使用 i 代表 push,o 代表 pop 操作对于一个最初的空栈的字符。给出一个输入的文本,一些 push 和 pop 有效的操作序列在每一 个文本的字符中是入栈和出栈,而且,不能尝试对一个空栈出栈。例如,如果文本 FOO 被输入,然后序列如下: i i o i o o is valid, but i i o is not (it's too short), neither is i i o o o i (there's an illegal pop of an empty stack) 有效的序列产生的对输入文本的重新排列。例如,输入文本 FOO 和序列 i i o i o o 产生了变形词 OOF。序列 i i i o o o 也同样可 以达到目的。你应该去写一个程序来输入一组文本并且输出所有合法能够把第一组文本变成第二组文本的的 i 和 o 序列。 思路/方法:这题是模拟栈操作。我们可以用深搜+回溯。 用一个文本来模拟栈,一个文本来模拟出栈的字符,一个文本来存储栈操作,这样思路就清晰多了。 下面代码有非常详细的注释,这里不多说了。 c++代码: #include<iostream> #include<string> using namespace std; string sourceWord, targetWord;//初始文本和目标文本

void dfs(string stackWord, string outputWord, string method)// 分别是栈中的文本 出栈的文本 操作方法文本 { //判断是否可以进栈出栈 if(stackWord.length() + outputWord.length() < targetWord.length())// 如果在栈内和出栈的长度 小于 目标文本长度,说 明可以入栈 dfs(stackWord + sourceWord[stackWord.length() + outputWord.length()], outputWord, method + "i ");// 模拟入栈 if(stackWord.length() > 0 && stackWord[stackWord.length() - 1] == targetWord[outputWord.length()])// 栈内还有文本 并 且 栈顶元素等于下一个目标元素,就说明可以出栈 dfs(stackWord.erase(stackWord.length() - 1), outputWord + targetWord[outputWord.length()], method + "o ");// 模拟出栈 //判断是否已经得到结果,事实证明这个判断放到后面效率高,放到开头会多出一些不必要的搜索分支 if(outputWord.length() == targetWord.length())// 当出栈文本长度和目标文本长度一样是,把方法输出 {//提交后发现 PE,原来是每行最后都有一个空格,没必要去掉,坑爹哇,所以屏蔽了下面一行代码,如有需要请自行取消屏蔽 //method.erase(method.length() - 1);//删去最后一个多余的空格 cout << method << endl;//输出方法 return; } } int main() { while(cin >> sourceWord >> targetWord) { cout << "[\n";//起始符号 if(sourceWord.length() == targetWord.length())// 只有初始文本和目标文本长度一样的才有可能 dfs("", "", "");//空栈开始搜索 cout << "]\n";//结束符号 } return 0; } 8: Hero In Maze II 描述 500 年前,Jesse 是我国最卓越的剑客。他英俊潇洒,而且机智过人^_^。 突然有一天,Jesse 心爱的公主被魔王困在了一个巨大的迷宫中。Jesse 听说这个消息已经是两天以后了,他急忙赶到迷宫,开始到处 寻找公主的下落。令人头痛的是,Jesse 是个没什么方向感的人,因此,他在行走过程中,不能转太多弯了,否则他会晕倒的。 我们 假定 Jesse 和公主所在的位置都是空地, 初始时, Jesse 所面向的方向未定, 他可以选择 4 个方向的任何一个出发, 而不算成一次转弯。 希望你帮他判断一下他是否有机会找到心爱的公主。 输入 题目包括多组测试数据. 第 1 行为一个整数 T(1 ≤ T≤ 100),表示测试数据的个数,接下来为 T 组测试数据. 每组测试数据以两个整数 N,M,K(1<=N, M≤100, 0<K<=10)开头,分别代表迷宫的高,长和 Jesse 最多能转的弯数,(紧接着有 N 行,M 列字符,由".","*","P","S"组成。其中 "." 代表能够行走的空地。 "*" 代表墙壁,Jesse 不能从此通过。 "P" 是公主所在的位置。 "S" 是 Jesse 的起始位置。 每个时间段里 Jesse 只能选择“上、下、左、右”任意一方向走一步。 输出 如果 Jesse 能在晕之前找到公主,输出“YES”,否则输出“NO”。 样例输入 2 5 5 1 合理剪枝

P..** *.**. S.... ..... *.... 5 5 2 P..** *.**. S.... ..... *.... 样例输出 NO YES 思路/方法:每个方向搜索前判断一样方向和当前方向是否一样,不一样就计数器加一,然后判断是否超出了转弯次数,没有就开始搜 索该位置是否可通或是目标。 需要注意的是,这题可能有很多条路径,走每一条路径的时候,我们为了防止重复走,就会把走过的路标记,但要记得走下一条路径 的时候要还原地图。 代码: #include <stdio.h> const short d[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};//四个方向 char map[100][101];//最多 100 行 100 列,每一行多一个列来存储\0 short rescue;//标识是否能被救出来 int n, m, k;//列 和 行数 void dfs(int x, int y, int count, int direction)// 代表坐标 转弯的的次数 方向 { int dx, dy, i; for(i = 0; i < 4; i++) { dx = x + d[i][0]; dy = y + d[i][1]; if(dx >= 0 && dx < n && dy >= 0 && dy < m && map[dx][dy] != '*')// 未超界 不是墙壁 { if(direction != i)//方向不一样就说明转弯了 count++; if(count > k)//转弯次数过多直接返回 return; if(map[dx][dy] == 'P')//如果找到了公主 { rescue = 1;//标记为成功营救 return; } char c = map[dx][dy];//用于回溯的记录 map[dx][dy] = '*';//在一次路径寻找中,访问过就标记为墙壁,防止重复访问 dfs(dx, dy, count, i);//继续搜索该点的四周 if(direction != i)//方向不一样就说明转弯了 count--;//回溯 map[dx][dy] = c;//下一条路径时,要把路还原。回溯 if(rescue) return;

} } } int main() { int i, j, t; scanf("%d", &t); while(t) { scanf("%d %d %d", &n, &m, &k); for(i = 0; i < n; i++)//n 行 scanf("%s", map[i]);//第 i 行赋值 rescue = 0;//初始化 for(i = 0; i < n; i++)//m 行 for(j = 0; j < m; j++)//n 列 if(map[i][j] == 'S')//从起点开始搜索 { map[i][j] = '*';//访问过的标记为墙壁,防止重复访问 dfs(i, j, -1, -1);//搜索(i,j)周围, 次数和方向都标记为-1 i = n;//用于跳出大循环 break; } if(rescue) printf("YES\n"); else printf("NO\n"); t--; } return 0; } 9: Sum It Up 描述 Given a specified total t and a list of n integers, find all distinct sums using numbers from the list that add up to t. For example, if t=4, n=6, and the list is [4,3,2,2,1,1], then there are four different sums that equal 4: 4,3+1,2+2, and 2+1+1.(A number can be used within a sum as many times as it appears in the list, and a single number counts as a sum.) Your job is to solve this problem in general. 输入 The input will contain one or more test cases, one per line. Each test case contains t, the total, followed by n, the number of integers in the list, followed by n integers x1,...,xn. If n=0 it signals the end of the input; otherwise, t will be a positive integer less than 1000, n will be an integer between 1 and 12(inclusive), and x1,...,xn will be positive integers less than 100. All numbers will be separated by exactly one space. The numbers in each list appear in nonincreasing order, and there may be repetitions. 输出 For each test case, first output a line containing 'Sums of', the total, and a colon. Then output each sum, one per line; if there are no sums, output the line 'NONE'. The numbers within each sum must appear in nonincreasing order. A number may be repeated in the sum as many times as it was repeated in the original list. The sums themselves must be sorted in decreasing order based on the numbers appearing in the sum. In other words, the sums must be sorted by their first number; sums with the same first number must be sorted by their second number; sums with the same first two numbers must be sorted by their third number; and so on. Within each test case, all sums must be distince; the same sum connot appear twice. 样例输入 4 6 4 3 2 2 1 1

5 3 2 1 1 400 12 50 50 50 50 50 50 25 25 25 25 25 25 0 0 样例输出 Sums of 4: 4 3+1 2+2 2+1+1 Sums of 5: NONE Sums of 400: 50+50+50+50+50+50+25+25+25+25 50+50+50+50+50+25+25+25+25+25+25 翻译: 描述 给你一个特定的总的 t 和一列 n 个的整数,找出所有使用一列中的数组相加和为 t 的不同的和式。例如,如果 t=4,n=6,列表是 [4,3,2,2,1,1],然后有 4 个不同的和式等于 4: 4,3+1,2+2,2+1+1。(一个数字最多能被使用他在列表中出现的次数,并且一个数字 也可当作和式)你的工作是通用的解决这个问题。 输入 输入将包括一个或多个测试数据, 一组一行。 每组测试数据包含 t, 总和, 接着是 n, 列表中整数的个数, 接下来是 n 个整数 x1,...,xn。 如果 n=0 表示输入结束;否则 t 是一个小于 1000 的正整数,n 是一个 1 到 12 之间的整数, x1,...,xn 是小于 100 的正整数。所有的 数字将会以一个确切的空格分开。每个列表的数以非递增的顺序出现,并且可能有重复。 输出 每组测试数据,第一行输出包括'Sums of',总和,和一个冒号。然后输出每个和式,每个一行;如果没有和式,输出一行'NONE'。和 式的每一个数字必须以非递增顺序出现。一个数字在和式中最多重复出现他在列表中出现的次数。和式必须根据数字以降序的方式排 序。换句话说,和式必须以第一个数字降序排序;如果第一个数字相同,就根据第二个;前两个数字相同,就根据第三个;依此类推。 在给定的每个测试数据,所有的和式必须不同;相同的和式不能出现两次。 思路/方法:简单深搜。需要注意的是,每个分支搜索时,需要判断一下当前的数和下一个数是否一样,如果一样就没有两个都搜索的 必要。 代码中有详细的注释,我多解释了。 代码: #include <iostream> #include <string> #include <sstream> #include <algorithm> using namespace std; short a[12], t, n;//最多 12 个整数序列 目标和 数组长度 bool flag;//标记是否存在加式 int cmp(const short & p, const short & q)// 降序 { return p > q; } //采用文本来存储表达式,可能比较费时,但容易写代码,个人觉得更容易理解 void dfs(short start, string expression, short sum)//起始位置,加法表达式,当前和 { short i; if(t == sum)//判断是否能构成表达式 {

flag = true; cout << expression.erase(expression.length() - 1) << endl;//去掉末尾的+ return; } for(i = start; i < n; i++)//在数组中找能组成和的 { if(sum + a[i] <= t)//加上一个数不超过目标和 { stringstream temp; temp << a[i]; dfs(i + 1, expression + temp.str() + "+", sum + a[i]);// 从 i+1 的位置开始搜索 表达式长度减一 } while(i + 1 < n && a[i] == a[i + 1])//防止重复,如果当前数和下一个数一样,就把往前移 i++; } } int main() { short i; while(cin >> t >> n, n != 0) { for(i = 0; i < n; i++) cin >> a[i]; flag = false; sort(a, a + n, cmp);//降序排序 cout << "Sums of " << t << ":\n";//开头格式 dfs(0, "", 0);//起始位置 0 表达式文本空 当前和 0 if(!flag) cout << "NONE\n"; } return 0; } 10: Accepted Necklace 描述 I have N precious stones, and plan to use K of them to make a necklace for my mother, but she won't accept a necklace which is too heavy. Given the value and the weight of each precious stone, please help me find out the most valuable necklace my mother will accept. 输入 The first line of input is the number of cases. For each case, the first line contains two integers N (N <= 20), the total number of stones, and K (K <= N), the exact number of stones to make a necklace. Then N lines follow, each containing two integers: a (a<=1000), representing the value of each precious stone, and b (b<=1000), its weight. The last line of each case contains an integer W, the maximum weight my mother will accept, W <= 1000. 输出 For each case, output the highest possible value of the necklace. 样例输入 1 2 1 1 1 1 1

3 样例输出 1 翻译: 描述 我有 n 个珍贵的宝石,并且计划使用 K 个宝石为我母亲制作一个项链,但他不会接受过重的项链。给定每个珍贵宝石的价值和重量, 请帮我找出母亲会接受的最大价值的项链。 输入 第一行输入测试组数。 每组测试数据,第一行包括两个整数 N (N <= 20),宝石的总数量,和 K (K <= N),确切的制作项链的宝石数量。 然后有 N 行,每行包括两个整数:a (a<=1000),代表每个宝石的价值,并且 b (b<=1000),它的质量。 最后一行包含一个整数 W,母亲能接受的最大的质量,W <= 1000。 输出 每组数据,输出项链最大的价值。 思路/方法:一维数组的这种深搜都是规定一个搜索起点,然后往后搜索。代码有很详细的注释。 c 语言代码: #include <stdio.h> typedef struct Stone { short value, weight;//价值和重量 }stone; stone a[20];//最多 20 个石头 short n, k, w; int maxValue;//最大价值 char visited[20];//用于判断是否访问过 void dfs(short start, short currentNumber, int currentValue, int currentWeight)// 搜索起点,当前使用宝石数量,当前价值, 当前质量 { if(currentNumber == k)//使用宝石数量达到上限 { if(currentValue > maxValue)//如果当前这个方案产生的价值比当前最大的价值还大,就更新记录 maxValue = currentValue; return; } int i; for(i = start; i < n; i++) { if(visited[i] == 0)//未使用过的宝石 if(currentWeight + a[i].weight <= w)//如果加上一个宝石不超过承载重量 { visited[i] = 1;//标记为试用过了 dfs(i + 1, currentNumber + 1, currentValue + a[i].value, currentWeight + a[i].weight); visited[i] = 0;//回溯 } } } int main() { short t, i;

scanf("%hd", &t); while(t) { scanf("%hd %hd", &n, &k); for(i = 0; i < n; i++) { scanf("%hd %hd", &a[i].value, &a[i].weight); visited[i] = 0;//初始化 } maxValue = 0;//初始化 scanf("%hd", &w); dfs(0, 0, 0, 0);//起始搜索位置,当前使用宝石数量,初始价值,初始重量 都为 0 printf("%d\n", maxValue); t--; } return 0; } 11: 自然数的拆分 描述 自然数的拆分:任何一个大于 1 的自然数 N,总可以拆分为若干个自然数之和,并且有多种拆分方法。例如,自然数 5,可以有以下一 些拆分方法: 5=1+1+1+1+1 5=1+1+1+2 5=1+1+3 5=1+2+2 5=1+4 ( 5=4+1 看成同一种拆分) 5=2+3 请设计一个对任意自然数,找出所有拆分方法的程序。每行输出顺序规则看上面例子可以观察出来吧(自己琢磨下吧 o(∩_∩)o )。 为简单起见,每行数据之间没有空格,行末也没空格。 输入 输入多组数据。每行输入一个正整数 n,2=<n<=35。 输出 输出拆分状况。 样例输入 5 6 样例输出 5=1+1+1+1+1 5=1+1+1+2 5=1+1+3 5=1+2+2 5=1+4 5=2+3 6=1+1+1+1+1+1 6=1+1+1+1+2 6=1+1+1+3 6=1+1+2+2 6=1+1+4 6=1+2+3 6=1+5 6=2+2+2

6=2+4 6=3+3 思路/方法:这题拆分的规律是从小到大,然后后面的因子不比前面的小。 看出这个规律就好做了。下面代码中关键就是 i 从上一个因子大小开始循环,这样就避免了了从 1 开始的重复。 c++代码: #include <iostream> using namespace std; short n;//目标和 short result[36];//最多分成 35 个 1 相加 void dfs(short currentSum, short currentSchedule)//当前目标和,当前进度 { short i; if(currentSum == n)//当前和 == 目标和 { cout << n << '=';//先输出 n= for(i = 1; i < currentSchedule; i++) cout << result[i] << '+'; cout << result[i] << endl;//最后一项后面没空格,然后输出换行 return; } for(i = result[currentSchedule]; i < n; i++)//要使用的数字 i 不小于 前一个因子,所以直接就从上一个因子的大小开始判 断 if(i + currentSum <= n)//加上因子小于 目标和 { result[currentSchedule + 1] = i;//把因子放到结果数组中 dfs(currentSum + i, currentSchedule + 1); } } int main() { result[0] = 1;//数组第一项不用于存储结果。因为 dfs 函数中从 i = result[currentSchedule]开始循环,所以这里必须为 1。 否则当 currentSchedule 为 0 时,就会出问题 while(cin >> n) dfs(0, 0);//当前目标和,当前进度 都为 0 return 0; } 12: 走迷宫 描述 Dr.Kong 设计的机器人卡多非常爱玩,它常常偷偷跑出实验室,在某个游乐场玩之不疲。这天卡多又跑出来了,在 SJTL 游乐场玩个不 停,坐完碰碰车,又玩滑滑梯,这时卡多又走入一个迷宫。整个迷宫是用一个 N * N 的方阵给出,方阵中单元格中填充了一个整数, 表示走到这个位置的难度。这个迷宫可以向上走,向下走,向右走,向左走,但是不能穿越对角线。走迷宫的取胜规则很有意思,看 谁能更快地找到一条路径,其路径上单元格最大难度值与最小难度值之差是最小的。当然了,或许这样的路径不是最短路径。 条路径。你能找到吗? 输入 第一行: 接下来有 N 行, 输出 输出为一个整数,表示路径上最高难度与和最低难度的差。 样例输入 N 表示迷宫是 N*N 方阵 (2≤ N≤ 100) 每一行包含 N 个整数,用来表示每个单元格中难度 (0≤任意难度≤120)。 机 器人卡多现在在迷宫的左上角(第一行,第一列)而出口在迷宫的右下角(第 N 行,第 N 列)。卡多很聪明,很快就找到了这样的一

5 1 1 3 6 8 1 2 2 5 5 4 4 0 3 3 8 0 2 3 4 4 3 0 2 1 样例输出 2 提示 样例中机器人卡多选择的路径为:1->1->2->2->0->2->0->2->1 思路/方法:这题用深搜暴力很难过,因为地图大,很容易超时。我这里用的是二分法来搜索难度间距。 我们可以用 mid 来表示难度间距。判断是否存在难度间距小于等于 mid 的路径,若存在,就把 mid 缩小一半,继续判断。如果不存在, 就把 mid 放大 1/2。 至于怎么缩放,我们可以定义 left 和 right,当要缩小时,把 right=mid,这样就把右边界缩小了;当要放大时,令 left=mid+1。当 left==right 时,就不需要继续二分了,已经确定了最小的难度差。 判断是否存在难度间距小于等于 mid 的路径可以循环 n 次,从 i=min 到 i+mid=max,例如:mid=4,min=0,max=8,则从 i=0 开始到 i=4, 判断(0,4)(1,5)(2,6)(3,7)(4,8)介于之间的路径是否存在。 c 语言代码: #include <stdio.h> #include <string.h> short map[100][100];//地图最大 100*100 char visited[100][100];//用于判断是否访问过 const short d[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};//四个方向 short flag;//标记是否能到达 short n;//地图大小 short min, max;//存储地图上最小难度和最大难度 void dfs(short x, short y, short left, short right)//行 列坐标,当前最小难度和最大难度 { short dx, dy, i; for(i = 0; i < 4; i++)//搜索四个方向 { dx = x + d[i][0]; dy = y + d[i][1]; if(dx >= 0 && dx < n && dy >= 0 && dy < n && visited[dx][dy] == 0)// 在地图范围内,未走过的路径 { if(map[dx][dy] >= left && map[dx][dy] <= right)// 判断难度是否介于 left 和 right 之间 { if(dx == n - 1 && dy == n - 1)//到达目标 { flag = 1; return; } visited[dx][dy] = 1;//标记为搜索过 dfs(dx, dy, left, right); //visited[dx][dy] = 0; if(flag)//如果成功到达,就直接返回,结束搜索 return; } } }

} //二分法思想 short canArrive(short mid)//判断间距为 mid 的路径是否存在 { short i; for(i = min; i + mid <= max; i++)//判断间距为 mid 的路径是否存在 { if(!(map[0][0] >= i && map[0][0] <= i + mid))// 如果入口不在范围内,肯定不行 continue; flag = 0;//初始化标志 memset(visited, 0, sizeof(visited));//初始化 visited[0][0] = 1;//标记为访问过 dfs(0, 0, i, i + mid);//因为 i 从 min 开始增加到 max-mid,例如,mid=4,min=0,max=8,则从 i=0 开始到 i=4,判断 (0,4)(1,5)(2,6)(3,7)(4,8)介于之间的路径是否存在 if(flag)//有一条存在,就返回真 return 1; } return 0;//不存在就返回假 } int main() { short i, j; short left, right, mid; scanf("%hd", &n); max = 0;//这样初始化才能达到记录数据中的最大最小难度 min = 120; for(i = 0; i < n; i++) for(j = 0; j < n; j++) { scanf("%hd", &map[i][j]); if(min > map[i][j]) min = map[i][j]; else if(max < map[i][j]) max = map[i][j]; } // 二分法开始 left = 0; right = max - min;//右边先保存最大难度差 //right-left 就是难度差,mid 是取难度差的中点 while(left < right) { mid = (left + right) / 2;//mid 表示难度间距中点 if(canArrive(mid))//判断是否存在难度间距小于等于 mid 的路径 //存在就把范围缩小一半 right = mid;//把右边范围变成中点,这样下一次中点就缩小了 else//不存在就增加一半 left = mid + 1;//把左边扩大到中点,这样,下一个中点就变大了 } printf("%hd\n", right);//最小难度差 return 0; }

四、查找和排序
1: 二分查找 描述 将 n 个从小到大排序的整数(n<1000000)从 1~n 进行编号,并一个待查找的整数 m,请使用二分法进行查找。 输入 输入包括 3 行,第一行为整数 n,第二行包括 n 个整数,以空格分隔,第三行为整数 m。 输出 如果能够在序列中找到整数 m,则输出编号(如果存在多个编号,返回编号最小的),如果不存在,则输出 None。 样例输入 10 1 2 4 5 6 7 8 9 10 11 10 10 1 2 4 5 6 7 8 9 10 11 12 样例输出 9 None 思路/方法:二分法思想,见下面代码的函数。这题需要注意的是,如果存在多个编号,返回编号最小的,所以,在二分法找到值后, 需要往前试探是否存在一样的值。 c 语言代码: #include <stdio.h> int g_nNumber[1000000]; // 失败返回-1, 否则返回位置 int BinaryChop(int nNumber[], int nCount, int nTarget) { int nLow = 0, nHigh = nCount - 1, nMid; while(nLow <= nHigh) { nMid = (nLow + nHigh) / 2; if(nTarget < nNumber[nMid])// 目标小于中间值,在左区域 nHigh = nMid - 1; else if(nTarget > nNumber[nMid])// 右区域 nLow = nMid + 1; else// 找到了 return nMid; } return -1; } int main () { int nCount, nTarget, nPosition, nIndex; while(EOF != scanf("%d", &nCount)) { for(nIndex = 0; nIndex < nCount; nIndex++)// 输入 nCount 个数字 scanf("%d", &g_nNumber[nIndex]); scanf("%d", &nTarget); nPosition = BinaryChop(g_nNumber, nCount, nTarget);// 查找值出现的位置 if(-1 == nPosition)

{ printf("None\n"); continue; } // 如果一个值存在多个编号,返回编号最小的 while(nPosition - 1 >= 0 && g_nNumber[nPosition] == g_nNumber[nPosition - 1])//和前一个相同 nPosition--;// 往左边走 printf("%d\n", nPosition + 1);// 输出的是第几个,所以+1 } return 0; } 2: 排序 描述 输入一行数字,如果我们把这行数字中的‘5’都看成空格,那么就得到一行用空格分割的若干非负整数(可能有些整数以‘0’开头, 这些头部的‘0’应该被忽略掉,除非这个整数就是由若干个‘0’组成的,这时这个整数就是 0)。 你的任务是对这些分割得到的整数依从小到大的顺序排序。 输入 输入数据包含多行,每行为一串数字(数字之间没有空格),这行数字的长度不大于 1000。 输入数据保证:分割得到的非负整数不会大于 100000000;输入数据不可能全由‘5’组成。处理到文件结束为止。 输出 对每行数字串进行分割并从小到大排序,输出排序后的结果,相邻的两个整数之间用一个空格分开。 样例输入 50051 0051231232050775 样例输出 0 1 0 77 12312320 思路/方法:先把字符串中的 5 替换成空格,然后从字符串中读取数字存储到数组中,然后排序输出。具体看代码。 c++代码: #include <iostream> #include <sstream> using namespace std; // 选择排序 void Sort(int arrnNumber[], int nCount) { int nI, nJ, nMin; for(nI = 0; nI < nCount - 1; nI++) { nMin = nI;// 假定最小值下标 for(nJ = nI + 1; nJ < nCount; nJ++) if(arrnNumber[nJ] < arrnNumber[nMin])// 当前值比最小值还小,更新记录 nMin = nJ; if(nMin != nI)// 最小值就是当前位置就不用交换 { int nTemp = arrnNumber[nMin]; arrnNumber[nMin] = arrnNumber[nI]; arrnNumber[nI] = nTemp; } }

} int main() { char szNumber[1001];// 一行数字文本 int arrnNumber[1000];// 分割后的数字数组 int nCount, nIndex;// 分割后数字的个数 { // 把 5 替换成空格 for(nIndex = 0; szNumber[nIndex] != '\0'; nIndex++) if('5' == szNumber[nIndex])// 是数字 5 szNumber[nIndex] = ' ';// 替换成空格 // 把 5 替换成空格 结束 // 把分割后的数字存储到数组 nCount = 0; stringstream ssNumber; ssNumber << szNumber;// 那字符串先输入到流中 while(ssNumber >> arrnNumber[nCount])// 输入到数组中 nCount++; // 把分割后的数字存储到数组 结束 Sort(arrnNumber, nCount);// 排序 for(nIndex = 0; nIndex < nCount - 1; nIndex++)// 输出数组内容 前 n-1 个 cout << arrnNumber[nIndex] << ' '; cout << arrnNumber[nIndex] << '\n';// 输出最后一个 } return 0; } 3: Sort ZOJ7 描述 Given a string of no more than 1000 characters. You are supposed to sort the characters into a substring of all Z's followed by O's, J's, 7's, and the rest of the other characters. 输入 Each case gives a string described by the problem. The string given contains no space. 输出 For each test case, output the resulting string. Note the order of the characters other than Z, O, J and 7 must be kept after sorting. 样例输入 t7ZJ7OhO7B7O7irZtOhZdayJ77 样例输出 ZZZOOOOJJ7777777thBirthday 思路方法:这题考察的是自定义顺序的稳定排序,小编比较懒,直接用了 STL 里面的稳定排序,自己写了个排序比较函数。 c++代码: #include <cstdio> #include <cstring> #include <algorithm> // { if('Z' == cA) 比较函数 bool Compare(char cA, char cB) 索引 while(cin >> szNumber)// 读入一行数字文本

return true; if('Z' == cB) return false; if('O' == cA) return true; if('O' == cB) return false; if('J' == cA) return true; if('J' == cB) return false; if('7' == cA) return true; if('7' == cB) return false; return false; } int main () { char szString[1001]; while(scanf("%s", szString) != EOF)// 读入个数 { std::stable_sort(szString, szString + strlen(szString), Compare);// 稳定排序 printf("%s\n", szString); } return 0; } 4: DNA Sorting 描述 One measure of "unsortedness" in a sequence is the number of pairs of entries that are out of order with respect to each other. For instance, in the letter sequence "DAABEC", this measure is 5, since D is greater than four letters to its right and E is greater than one letter to its right. This measure is called the number of inversions in the sequence. The sequence "AACEDGG" has only one inversion (E and D)--it is nearly sorted--while the sequence "ZWQM" has 6 inversions (it is as unsorted as can be--exactly the reverse of sorted). You are responsible for cataloguing a sequence of DNA strings (sequences containing only the four letters A, C, G, and T). However, you want to catalog them, not in alphabetical order, but rather in order of "sortedness", from "most sorted" to "least sorted". All the strings are of the same length. 输入 The first line contains two integers: a positive integer n (0 < n ≤ 50) giving the length of the strings; and a positive integer m (1 < m ≤ 100) giving the number of strings. These are followed by m lines, each containing a string of length n. 输出 Output the list of input strings, arranged from "most sorted" to "least sorted". If two or more strings are equally sorted, list them in the same order they are in the input. 样例输入 10 6 AACATGAAGG TTTTGGCCAA TTTGGCCAAA GATCAGATTT CCCGGGGGGA

ATCGATGCAT 样例输出 CCCGGGGGGA AACATGAAGG GATCAGATTT ATCGATGCAT TTTTGGCCAA TTTGGCCAAA 翻译: DNA 排序 描述 一个方法“unsortedness”在一个遵守彼此规则的序列是成对条目的数量。例如,在字母序列"DAABEC",测量的值是 5,因为 D 比它右 边的 4 个字母大,E 比它右边的一个字母大。这个方法叫做逆序数。序列"AACEDGG"有唯一的逆序数(E 和 D)--这接近排序--然而序列 "ZWQM"有 6 逆转(这是尽可能不排序--确切倒转排序)。 你的责任是编目一个 DNA 字符串序列(序列包含只有 4 个字母 A, C, G, 和 T)。然而,你想要去编目他们,不按字母顺序,而是按 "sortedness",从 "most sorted" 到 "least sorted"。所有的字符串是相同长度。 输入 第一行包含两个整数:一个正整数 n(0 < n ≤ 50)给定字符串的长度;和一个正整数 m (1 < m ≤ 100) 给定字符串的数量。下面接 着 m 行,每行包含长度为 n 的字符串。 输出 输出输入的字符串,根据从 "most sorted" 到 "least sorted"排序。如果两个或多个字符串相同,根据他们输入的次序。 思路方法:看懂题意后就简单了,题目要求根据字符串逆序数来排序,逆序数为线性代数中的名词,不懂的可以百度看一下。 题目还要求是稳定排序,我直接调用了 STL 中的 stable_sort c++代码: #include <cstdio> #include <algorithm> #include <cstring> typedef struct UNSORTEDNESS { char szString[51]; int nValue; }T_UNSORTEDNESS; // 升序 bool Compare(T_UNSORTEDNESS tA, T_UNSORTEDNESS tB) { return tA.nValue < tB.nValue; } // 计算序列的逆序数 int Unsortedness(char szString[]) { int nI, nJ, nCount = 0, nLength = strlen(szString); for(nI = 0; nI < nLength - 1; nI++) for(nJ = nI + 1; nJ < nLength; nJ++) if(szString[nI] > szString[nJ])//如果前面的比后面的大,计数器加一 nCount++; return nCount; } int main () {

int nLength, nCount, nIndex; T_UNSORTEDNESS arrtData[100]; scanf("%d %d", &nLength, &nCount); for(nIndex = 0; nIndex < nCount; nIndex++)// 输入并结算逆序数 { scanf("%s", arrtData[nIndex].szString); arrtData[nIndex].nValue = Unsortedness(arrtData[nIndex].szString); } std::stable_sort(arrtData, arrtData + nCount, Compare);// 稳定排序 for(nIndex = 0; nIndex < nCount; nIndex++)// 输出 printf("%s\n", arrtData[nIndex].szString); return 0; } 5: Scramble Sort 描述 In this problem you will be given a series of lists containing both words and numbers. The goal is to sort these lists in such a way that all words are in alphabetical order and all numbers are in numerical order. Furthermore, if the nth element in the list is a number it must remain a number, and if it is a word it must remain a word. 输入 The input will contain multiple lists, one per line. Each element of the list will be separated by a comma followed a space, and the list will be terminated by a period. The input will be terminated by a line containing only a single period. 输出 For each list in the input, output the scramble sorted list, separating each element of the list with a comma followed by a space, and ending the list with a period. 样例输入 0. banana, strawberry, OrAnGe. Banana, StRaWbErRy, orange. 10, 8, 6, 4, 2, 0. x, 30, -20, z, 1000, 1, Y. 50, 7, kitten, puppy, 2, orangutan, 52, -100, bird, worm, 7, beetle. . 样例输出 0. banana, OrAnGe, strawberry. Banana, orange, StRaWbErRy. 0, 2, 4, 6, 8, 10. x, -20, 1, Y, 30, 1000, z. -100, 2, beetle, bird, 7, kitten, 7, 50, orangutan, puppy, 52, worm. 翻译: 争夺排序 描述 在这个问题你将会被给与一些列数据包含单词和数字。目标是去把这些数据像这样排序,所有的单词按字母顺序,所有的数字按数字 顺序排序。而且,如果第 n 个元素在列表示中数字,它必须保持为一个数字,如果是一个单词,必须保持为一个单词。 输入 输入包含多组数据,一组一行。列表中每个元素将会以一个逗号和空格分隔,一组数据以"."号结束。输入将会以一个单独的"."结束 输出 对于每一组输入数据,输出争夺排序数据,用逗号和一个空格分隔每一个元素,以"."结束

思路方法: 这题有几个小麻烦 1.读取数据,仔细观察后,发现个数据后面都有一个空格,所以可以用 scanf "%s"或 cin 来接收到临时变量。然后接收数据后,我们 通过判断最后一个字符是否为"."来判断这一行是否结束。输入结束就是判断一下字符串长度为 1,且等于"."。 2.存储数据,需要先判断是否为数字,分别存储。 3.排序,数字排序简单,单词排序不能直接用库函数,需要自己写一个比较函数,忽略大小写比较,字符串长度是最后考虑的因素。 c++代码: #include <cstdio> #include <cstring> #include <algorithm> typedef struct WORD { char szWord[20]; }T_WORD; // 到小写 inline char ToLowercase(char cCharacter) { if(cCharacter >= 'A' && cCharacter <= 'Z')// 大写字母 cCharacter += 32; return cCharacter; } // 和库函数里面的不同之处是:长度是最后比较的根据 int MyStricmp(const char szA[],const char szB[]) { int nLengthA = strlen(szA), nLengthB = strlen(szB); int nIndex, nCount, nResult; nCount = nLengthA > nLengthB? nLengthA: nLengthB; for(nIndex = 0; nIndex < nCount; nIndex++) { nResult = ToLowercase(szA[nIndex]) - ToLowercase(szB[nIndex]); if(nResult != 0) return nResult; } return nLengthA - nLengthB;// 最后比较长度,一样返回 0 } // 升序 bool Compare(T_WORD tA, T_WORD tB) { return MyStricmp(tA.szWord, tB.szWord) < 0;// 不区分大小写的比较第一个字符 } // 计算序列的逆序数 bool IsNumber(char szString[]) { int nIndex; // 第一个既不是数字, 也不是if(!(szString[0] >= '0' && szString[0] <= '9') && szString[0] != '-') return false; for(nIndex = 1; szString[nIndex] != '\0'; nIndex++) if(!(szString[nIndex] >= '0' && szString[nIndex] <= '9')) return false; return true;

} int main () { int nIndex, nLength, nLengthNumber, nLengthWord; int nNumber, nWord; char szTemp[20], cFlag;// 临时接收变量 T_WORD arrtWord[60];// 单词数组 int arrnNumber[60];// 数字数组 bool arrbMemoryNumber[120];// 记忆当前位置是数字还是单词 do { nLengthNumber = nLengthWord = 0;// 初始化 do { scanf("%s", szTemp); nLength = strlen(szTemp); cFlag = szTemp[nLength - 1]; if(nLength == 1 && szTemp[0] == '.')// 结束标志 return 0; szTemp[nLength - 1] = '\0';// 删除数字或单词后面的逗号或点号 if(IsNumber(szTemp))// 是数字 { sscanf(szTemp, "%d", &arrnNumber[nLengthNumber]);// 存储到数组 arrbMemoryNumber[nLengthNumber + nLengthWord] = true;// 记录当前位置为数字 nLengthNumber++; } else { strcpy(arrtWord[nLengthWord].szWord, szTemp); arrbMemoryNumber[nLengthNumber + nLengthWord] = false;// 记录当前位置为数字 nLengthWord++; } } while(cFlag != '.'); if(nLengthNumber) std::sort(arrnNumber, arrnNumber + nLengthNumber);// 数字排序,默认升序 if(nLengthWord) std::sort(arrtWord, arrtWord + nLengthWord, Compare);// 字母排序 for(nNumber = nWord = nIndex = 0; nIndex < nLengthNumber + nLengthWord - 1; nIndex++)// 输出前 n-1 个 { if(arrbMemoryNumber[nIndex])// 数字 { printf("%d, ", arrnNumber[nNumber]); nNumber++; } else// 字母 { printf("%s, ", arrtWord[nWord].szWord); nWord++; } } if(arrbMemoryNumber[nIndex])// 数字

printf("%d.\n", arrnNumber[nNumber]); else// 字母 printf("%s.\n", arrtWord[nWord].szWord); }while(szTemp); return 0; } 6: Copying Books(最大值最小化) 描述 Before the invention of book-printing, it was very hard to make a copy of a book. All the contents had to be re-written by hand by so called scribers. The scriber had been given a book and after several months he finished its copy. One of the most famous scribers lived in the 15th century and his name was Xaverius Endricus Remius Ontius Xendrianus (Xerox). Anyway, the work was very annoying and boring. And the only way to speed it up was to hire more scribers. Once upon a time, there was a theater ensemble that wanted to play famous Antique Tragedies. The scripts of these plays were divided into many books and actors needed more copies of them, of course. So they hired many scribers to make copies of these books. Imagine you have m books (numbered 1, 2 ... m) that may have different number of pages (p1, p2 ... pm) and you want to make one copy of each of them. Your task is to divide these books among k scribes, k <= m. Each book can be assigned to a single scriber only, and every scriber must get a continuous sequence of books. That means, there exists an increasing succession of numbers 0 = b0 < b1 < b2, ... < bk-1 ≤ bk = m such that i-th scriber gets a sequence of books with numbers between bi-1+1 and bi. The time needed to make a copy of all the books is determined by the scriber who was assigned the most work. Therefore, our goal is to minimize the maximum number of pages assigned to a single scriber. Your task is to find the optimal assignment. 输入 The input consists of N cases. The first line of the input contains only positive integer N. Then follow the cases. Each case consists of exactly two lines. At the first line, there are two integers m and k, 1 ≤ k ≤ m ≤ 500. At the second line, there are integers p1, p2, ... pm separated by spaces. All these values are positive and less than 10000000. 输出 For each case, print exactly one line. The line must contain the input succession p1, p2, ... pm divided into exactly k parts such that the maximum sum of a single part should be as small as possible. Use the slash character ('/') to separate the parts. There must be exactly one space character between any two successive numbers and between the number and the slash. If there is more than one solution, print the one that minimizes the work assigned to the first scriber, then to the second scriber etc. But each scriber must be assigned at least one book. 样例输入 2 9 3 100 200 300 400 500 600 700 800 900 5 4 100 100 100 100 100 样例输出 100 200 300 400 500 / 600 700 / 800 900 100 / 100 / 100 / 100 100 翻译: 复制书 描述 在发明印刷术之前,复制书很难。所有的内容都需要人工手写,因此叫做抄写员。抄写员被给予一本书,几个月后完成复制。最有名 的抄书员生活中 15 世纪,他的名字是 Xaverius Endricus Remius Ontius Xendrianus (Xerox) 。无论如何,工作都非常烦人和无聊。 唯一提升速度的方法是雇更多的抄书员。 从前,那有一个剧场合奏想要去表演有名的<<古代悲剧>>。这些戏剧的剧本被分成很多本,当然演员需要更多的副本。因此他们雇佣 了很多抄书员来复制这些书。假设你有 m 本书(标记为 1, 2 ... m),每本有很多不同的页码数字 (p1, p2 ... pm),你想要去复制它们。 你的任务是把这些书分给 k 个抄书员。k <= m。每本书只能分给一个抄书员,并且每个抄书员必须得到书的连续的页码。存储一个增

长的连续数字 0 = b0 < b1 < b2, ... < bk-1 ≤ bk = m,第 i 个抄书员取得书的连续页码,范围是 bi-1+1 到 bi。复制所有书的时 间取决于承担了最多工作的抄书员。因此,我们的目标是最小化承担给一个抄书员的最大数量的页码。你的任务是找出最佳的分配方 案。 输入 输入包括 N 组数据。第一行输入一个正整数 N。然后接下来,每组数据包含确切的两行。第一行,有两个整数 m 和 k, 1 ≤ k ≤ m ≤ 500。第二行,有整数 p1,p2...pm 以空格分隔。所有的值是整数并且小于 10000000。 输出 对于每组数据,输出一行。这行必须包含输入的连续 p1, p2, ... pm 被划分为 k 部分,最大化单个部分的和应该尽可能小。使用字 符斜杠('/')来分隔各个部分。在两个连续的数字、数字和斜杠 之间必须存在一个空格。 如果多余一种解决方案,输出最小化分配给第一个抄书员的工作,然后第二个抄书员,依此类推。但是每个抄书员必须承担至少一本 书。 翻译的不太好,题目大意: 要抄 N 本书,编号为 1,2,3...N, 每本书有 1<=x<=10000000 页, 把这些书分配给 K 个抄写员,要求分配给某个抄写员的那些书的编号 必须是连续的。每个抄写员的速度是相同的,求所有书抄完所用的最少时间的分配方案。 思路方法:典型的最大值最小化问题。 举个经典的例子 问题描述: 把一个包含 n 个正整数的序列划分成 m 个连续的子序列。设第 i 个序列的各数之和为 S(i),求所有 S(i)的最大值最小是多少?例如序 列 1 2 3 2 5 4 划分为 3 个子序列的最优方案为 1 2 3 | 2 5 | 4,其中 S(1),S(2),S(3)分别为 6,7,4,那么最大值为 7;如果划分 为 1 2 | 3 2 | 5 4,则最大值为 9,不是最小。 问题分析: 能否使 m 个连续子序列所有的 s(i)均不超过 x,则该命题成立的最小的 x 即为答案。该命题不难判断,只需贪心,每次尽量从左向右 尽量多划分元素即可。我们把该问题转化为递归分治问题,类似于二分查找。首先取 Sum 和元素最大值的中值 x,如果命题为假,那么 答案比 x 大;如果命题为真,则答案小于等于 x。问题得解,复杂度为 O(n*logSum) c++代码: #include <cstdio> #include <cstring> // 判断 nMid 是否符合条件 bool Divide(long long nMid, long long arrnBook[], int nPage, int nScriber) { int nIndex, nGroup = 1;// 不分组就是一个组 long long nSum = 0; for(nIndex = nPage - 1; nIndex >= 0; nIndex--)// 从末尾开始分组 { if(nSum + arrnBook[nIndex] > nMid)// 当前分组已经不能容纳了 { // 新开一个分组,初始化 nGroup++; nSum = 0; if(nGroup > nScriber)// 如果分组数大于抄书员数量,表示不能分隔失败 return false; } nSum += arrnBook[nIndex]; } return true;// 如果没有出现意外情况,就说明 nMid 符合条件 } // 二分试探符合条件的最小值 long long Binary(long long nLow, long long nHigh, long long arrnBook[], int nPage, int nScriber) {

long long nMid; while(nLow <= nHigh) { nMid = (nLow + nHigh) / 2; if(Divide(nMid, arrnBook, nPage, nScriber))// 如果假设 nMid 为划分的最大值,能通过,则继续缩小 nHigh = nMid - 1; else// 如果当前划分值不行,则扩大 mid nLow = nMid + 1; } return nLow;// 运行到这里时,nLow 和 nHigh 值一样,表示最小的符合条件的 nMid } // 输出结果 void Print(long long nValue, long long arrnBook[], bool arrbDivided[], int nPage, int nScriber) { // 标记斜杠的位置 memset(arrbDivided, 0, sizeof(bool) * nPage);// 全部初始化为假 int nIndex, nGroup = 1;// 不分组就是一个组 long long nSum = 0; for(nIndex = nPage - 1; nIndex >= 0; nIndex--)// 从末尾开始分组 { if(nSum + arrnBook[nIndex] > nValue)// 当前分组已经不能容纳了 { // 新开一个分组,初始化 nGroup++; nSum = 0; arrbDivided[nIndex] = true;// 新分组,标记斜杠 } nSum += arrnBook[nIndex]; if(nScriber - nGroup == nIndex + 1)// 凑满 nScriber-1 个斜杠 { for(int nJ = 0; nJ <= nIndex; nJ++) arrbDivided[nJ] = true; break; } } // 标记斜杠的位置 结束 for(nIndex = 0; nIndex < nPage - 1; nIndex++)// 输出前 n-1 个 { printf("%I64d ", arrnBook[nIndex]); if(arrbDivided[nIndex])// 判断是否在这里分隔 printf("/ "); } printf("%I64d\n", arrnBook[nIndex]);// 输出最后一个 } int main() { int nCount, nPage, nScriber, nI, nJ; long long nMax, nMin, arrnBook[510];// 最大范围,最小范围,存储书页码的数组 bool arrbDivided[510];// 标记是否被斜线分隔 scanf("%d", &nCount);// 读入测试组数 for(nI = 0; nI < nCount; nI++) {

nMax = nMin = 0;// 初始化 scanf("%d %d", &nPage, &nScriber);// 读入书页码 和 抄书员人数 for(nJ = 0; nJ < nPage; nJ++)// 读入书 { scanf("%I64d", &arrnBook[nJ]); nMax += arrnBook[nJ];// 最大值为所有页码之和 if(arrnBook[nJ] > nMin)// 最小值为页码中最大的一个 nMin = arrnBook[nJ]; } int nResult = Binary(nMin, nMax, arrnBook, nPage, nScriber);// 查找符合条件的最小值 Print(nResult, arrnBook, arrbDivided, nPage, nScriber);// 输出结果 } return 0; }

五、贪心
1100: Home Work 描述 临近开学了,大家都忙着收拾行李准备返校,但 I_Love_C 却不为此担心! 因为他的心思全在暑假作业上:目前为止还未开动(-_-!!还以为他有多冷静呢)。 暑假作业是很多张试卷,我们这些从试卷里爬出来的人都知道,卷子上的题目有选择题、填空题、简答题、证明题等。 而做选择题的好处就在于工作量很少,但又因为选择题题目都普遍很长。 如果有 5 张试卷,其中 4 张是选择题,最后一张是填空题,很明显做最后一张所花的时间要比前 4 张长很多。 但如果你只做了选择题,虽然工作量很少,但表面上看起来也已经做了 4/5 的作业了。 I_Love_C 决定就用这样的方法来蒙混过关。 他统计出了做完每一张试卷所需的时间以及它做完后能得到的价值(按上面的原理,选择题越多价值当然就越高咯)。 现在就请你帮他安排一下,用他仅剩的一点时间来做最有价值的作业,如果一张试卷只做了一部分,那么他也将按比例获得部分价值。 输入 测试数据包括多组。 每组测试数据以两个整数 M,N(1≤M≤20, 1≤N≤10000)开头,分别表示试卷的数目和 I_Love_C 剩下的时间。 接下来有 M 行,每行包括两个整数 T,V(1≤T≤N,0<V<10000),分别表示做完这张试卷所需的时间以及做完后能得到的价值! 输入以 0 0 结束。 输出 对应每组测试数据输出 I_Love_C 能获得的最大价值。 保留小数点 2 位 样例输入 4 20 4 10 5 22 10 3 1 2 0 0 样例输出 37.00 提示 float 的精度可能不够。 你应该使用 double 类型。 思路方法:典型贪心问题,根据价值和时间比进行排序,优先选着价值比高的,题目中也说了,可以只完成部分试卷,也就是当时间 不够时,可以只完成剩余时间能完成的部分。 c++代码: #include <algorithm> #include <cstdio> typedef struct WORK { int nTime;// 时间 int nValue;// 价值 double dValue;// 单位时间内的价值 }T_WORK; //降序比较函数 bool Compare(T_WORK tA, T_WORK tB) { return tA.dValue > tB.dValue; } int main()

{ int nCount, nIndex; int nTime;// 剩余时间 double dValue;// 当前做完的价值 T_WORK arrtWork[20]; while(scanf("%d %d", &nCount, &nTime), !(nCount == 0 && nTime == 0))// 读入一行数字文本 { dValue = 0; for(nIndex = 0; nIndex < nCount; nIndex++) { //输入 scanf("%d %d", &arrtWork[nIndex].nTime, &arrtWork[nIndex].nValue); // 计算单位时间的价值 arrtWork[nIndex].dValue = ((double)arrtWork[nIndex].nValue) / arrtWork[nIndex].nTime; } std::sort(arrtWork, arrtWork + nCount, Compare);// 降序排序 // 开始计算剩余时间能完成的任务 for(nIndex = 0; nIndex < nCount; nIndex++) { // 加上这个任务后,时间超过了或满了 if(arrtWork[nIndex].nTime >= nTime) { // 剩余时间完成试卷的一部分 dValue += arrtWork[nIndex].dValue * nTime; break; } nTime -= arrtWork[nIndex].nTime;// 消耗掉时间 dValue += arrtWork[nIndex].nValue;// 累加上价值 } printf("%.2lf\n", dValue); } return 0; } 1313: 搬桌子 描述 The famous ACM (Advanced Computer Maker) Company has rented a floor of a building whose shape is in the following figure.

The floor has 200 rooms each on the north side and south side along the corridor. Recently the Company made a plan to reform its system. The reform includes moving a lot of tables between rooms. Because the corridor is narrow and all the tables are big, only one table can pass through the corridor. Some plan is needed to make the moving efficient. The manager figured out the following plan: Moving a table from a room to another room can be done within 10 minutes. When moving a table from room i to room j, the part of the corridor between the front of room i and the front of room j is used. So, during each 10 minutes, several moving between two rooms not sharing the same part of the corridor will be done simultaneously. To make it clear the manager illustrated the possible cases and impossible cases of simultaneous moving.

For each room, at most one table will be either moved in or moved out. Now, the manager seeks out a method to minimize the time to move all the tables. Your job is to write a program to solve the manager ’s problem. 输入 The input consists of T test cases. The number of test cases ) (T is given in the first line of the input. Each test case begins with a line containing an integer N , 1<=N<=200 , that represents the number of tables to move. Each of the following N lines contains two positive integers s and t, representing that a table is to move from room number s to room number t (each room number appears at most once in the N lines). From the N+3-rd line, the remaining test cases are listed in the same manner as above. 输出 The output should contain the minimum time in minutes to complete the moving, one per line. 样例输入 3 4 10 20 30 40 50 60 70 80 2 1 3 2 200 3 10 100 20 80 30 50 样例输出 10 20 30 翻译 搬桌子 描述 有名的 ACM 公司租了一层楼形状如下。 层楼北边有 200 个房间,南边也有 200 个房间,中间隔着走廊。最近公司打算改革系统。改革包括移动房间里的很多的桌子。因为走 廊很狭窄并且所有的桌子很大,只能同时通过一张桌子。一些计划需要高效的移动。经理想出了下面的计划:10 分钟内从一个房间把 桌子移到另一个房间。当把桌子从房间 i 移动到 j,从 i 到 j 的那部分走廊被使用。因此,在 10 分钟,一些移动在两个房间之间不能 分享相同的走廊部分。为了使得清晰,经理给可能的情况和不可能的同时移动情况画了个表。 对于每个房间,只多一张桌子移入或移除。现在,经理在寻找一个方法使得移动所有桌子的时间最小化。你的工作是写一个程序解决 经理的问题。 输入 输入包含 T 组测试数据。测试组数 T 在第一行被给出。每组测试数据以一行包含一个整数 N , 1<=N<=200 , 代表移动桌子的数量。接 下来 N 行包含两个正整数 s 和 t,代表一个桌子从房间 s 移动到房间 t(每个房间在 N 行中最多出现一次)。从 N+3-r 行,剩下的测试数 据列和上面相同的方法一样。 输出 输出应该包含完成移动的最小时间,一组一行。

思路方法:这个题目是要移完所有的桌子,所以无论你怎么排序,结果都是一样的。我们需要做的是尽量充分利用走廊。 我们可以用一个数组来模拟走廊长度,当有桌子从这经过,就把数组这一位置计数器加一。 完成所有移动工作后,计算走廊某处最大的经过桌子的次数,因为不能同时经过,所以,所用时间就是次数*10。 而起点终点和走廊的长度是不一致的,所以我们需要进行转换,即 nStart = (nStart - 1) / 2; nEnd = (nEnd - 1) / 2; c++代码: #include <cstdio> #include <cstring> int main() { int nCount, nIndex, nCase; int nRegion[200];// 走廊区间,用于记录走廊当前位置被用过几次 int nStart, nEnd; scanf("%d", &nCase); while(nCase--) { memset(nRegion, 0, sizeof(nRegion)); scanf("%d", &nCount); for(nIndex = 0; nIndex < nCount; nIndex++) { //输入 scanf("%d %d", &nStart, &nEnd); // 把起点和终点改成对应走廊长度的位置 nStart = (nStart - 1) / 2; nEnd = (nEnd - 1) / 2; // 起点大于终点,交换 if(nStart > nEnd) { int nTemp = nEnd; nEnd = nStart; nStart = nTemp; } // 开始计算耗时 for(int nJ = nStart; nJ <= nEnd; nJ++) nRegion[nJ]++; } int nMax = 0;// 记录走廊某区域最大公用次数 for(nIndex = 0; nIndex < 200; nIndex++) if(nRegion[nIndex] > nMax) nMax = nRegion[nIndex]; printf("%d\n", nMax * 10); } return 0; }


更多相关文档:

acm算法经典例题

acm算法经典例题_其它课程_高中教育_教育专区 暂无评价|0人阅读|0次下载|举报文档acm算法经典例题_其它课程_高中教育_教育专区。acm算法经典例题 ...

ACM经典算法超级大集合

ACM经典算法超级大集合_计算机软件及应用_IT/计算机_专业资料。超 34.Algorithm ...举个例子来说,假设有一未 排序的数字如右: 12 65 97 89 61 81 27 2 61...

ACM经典算法及配套练习题

ACM经典算法及配套练习题_计算机软件及应用_IT/计算机_专业资料。ACM入门算法习题POJ 上的一些水题(可用来练手和增加自信) (poj3299,poj2159,poj2739,poj1083,...

ACM超级经典算法大集合

ACM超级经典算法大集合_计算机软件及应用_IT/计算机_专业资料。经典编程算法,值得...如果不太理解这个例子的话,举个图就知道了,注意新生的小免子需一个月成长期...

ACM算法总结大全——超有用!

ACM算法总结大全——超有用!_工学_高等教育_教育专区。介绍在ACM比赛中常用到...(poj3096,poj3007) (2)较为复杂的模拟题的训练(poj3393,poj1472,poj3371,...

ACM算法题以及答案

ACM算法题以及答案_计算机软件及应用_IT/计算机_专业资料。ACM算法题以及答案ACM...非变动性操作 c.size(); c.empty(); //返回当前元素数量 //判断大小...

ACM算法设计实验题目汇总

ACM 算法设计实验题目汇总 1020 Permutation with Repetition 1021 双色 Hanoi 塔...with Repetition Description R={ r1,r2,… ,rn }是要进行排列 n 个元素...

ACM经典算法

ACM经典算法_计算机软件及应用_IT/计算机_专业资料。算法完整版,包含递归、排列...四、习题: 1、 用递归求 n!. 程序如下: 因担心超 program sample1_1; ...

ACM必做50题的解题-模拟

ACM必做50题的解题-模拟_理学_高等教育_教育专区。POJ 1029 False coin Slyar:又是假币判断问题,跟 POJ1013 类似,不过这个题用 1013 那个算法 WA 了...后来...

ACM经典的题目代码

ACM经典的题目代码 51页 2下载券 ACM经典代码 131页 1下载券 ACM经典代码 123页 1下载券 ACM经典代码 123页 免费 几个ACM经典算法代码 42页 1下载券 ACM经典...
更多相关标签:
动态规划算法经典例题 | 分治算法经典例题 | 贪心算法经典例题 | 作业调度算法经典例题 | acm经典算法 | acm例题 | acm map 例题 | 银行家算法例题 |
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com