ACM高手帮一下忙，解决这道题_百度知道
ACM高手帮一下忙，解决这道题
1003:计数查看 提交 统计 提问 时间限制: 1000ms 内存限制: 10000kB
对于方程 (x^x )*(x+1)= a(mod p), PH想知道对于[0,p-1]内的数，有多少个这样的x满足这个方程。请注意，虽然对于0^0的值有争论，甚至不一定有意义，可是在本题中，PH认为0^0 = 1。...
我有更好的答案
这道题我的想法是 写一个大数运算 然后暴搜加二分
（1）把a%p求出来（大数求模，a用字符串储存）（2）（x^x）%p用二分求复杂度O（p*log（p））
为您推荐：
其他类似问题
acm的相关知识
换一换
回答问题，赢新手礼包
个人、企业类
违法有害信息,请在下方选择后提交
色情、暴力
我们会通过消息、邮箱等方式尽快将举报结果通知您。时间： 19:52:31
&&&& 阅读：77
&&&& 评论：
&&&& 收藏：0
标签：&&&&&&&&&&&&&&&&&&&&&&&&&&&
Problem Description
Sample Input
Sample Output
标签：&&&&&&&&&&&&&&&&&&&&&&&&&&&原文：http://blog.csdn.net/l/article/details/
教程昨日排行
&&国之画&&&& &&&&&&
&& &&&&&&&&&&&&&&
鲁ICP备号-4
打开技术之扣，分享程序人生！当前位置： >>
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 order. The first hole he get into is the one signed with 0. Then he will get into the hole every m holes. For example, m=2 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&). 输出 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&) 输出 每组数据输出一行，如果存在安全洞穴，输出&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& long long greatestCommonDivisor(long long a, long long b)// 最大公约数 { while(b) { t = a % a = b = }
} int main() { int i, long long m, cin && for(i = 0; i & i++) { cin && m && 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, while(scanf(&%d %d&, &a, &b) != EOF) { b = b % 4; if(b == 0) b = 4; a = a % 10; t = 1;for(i = 0; i & i++) { t = t * 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, 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 = i &= 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& int main() { long long m, n, remain, id,//id 表示下标，j 表示当前第几个报数 while(cin && n && m, !(n == 0 && m == 0)) { //得到不大于 n 的 m^x 的值 j = 1; for(id = 1;; id++) { j = j * if(j * m & n) } remain = 0; for(id = 1;;id++) { if(j * id &= n)//得到不大于 n 的 m 的倍数 的个数 remain++; } cout && remain && for(id = 1; id & id++) cout && id * j && & &; cout && id * j && } 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..*..*100=243-24，所以 0.243..=(243-23)/()，然后总结之后得出下面的结论。 不循环部分和循环节构成的的数 减去 不循环部分的差,再除以循环节位数个 9，添上不循环部分的位数个 0。比如： 0.????=(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) { while(b) { t = a % a = b = } } int main() { int i, n, j, long long denominator, numerator, divisor, cyclical, nonC// 分母分子,非循环部分和循环部分 char a[20], nonCyclicalString[20], cyclicalString[20];// 必须用文本，否则会丢失位数，比如 0.001010 这样的会把 0 丢了 scanf(&%d &, &n); for(i = 0; i & 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 =//分子就等于循环节 } 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 = nonC//把分子的值先变成非循环部分 for(j = 0; cyclicalString[j] != '\0'; j++)//往分子尾部加入循环节部分 { numerator = numerator * 10 + (cyclicalString[j] - '0'); } numerator = numerator - nonC//非循环部分和循环部分的组合 - 非循环部分 } //计算分母 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& void display(int a[], int n) { for(i = 0; i & n - 1; i++) cout && a[i] && & &; cout && a[i] && } 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, cin && for(i = 0; i & i++) { cin && int a[n]; for(j = 0; j & j++) cin && a[j]; fullPermutation(a, n);cout && } 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, 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 greatestCommonDivisor(int a, int b) { while(b) { t = a % a = b = } }fraction addFraction(fraction * f1, fraction * f2) { if(f1-&denominator == f2-&denominator || f1-&numerator == 0)//两数分母相同 { s.numerator = f1-&numerator + f2-&//分子相加 s.denominator = f2-& } else { s.denominator = f1-&denominator * f2-&//分母通分 s.numerator = f1-&numerator * f2-&denominator + f2-&numerator * f1-&//分子通分后相加 divisor = greatestCommonDivisor(s.numerator, s.denominator);// 求最大公约数 //约分 s.numerator /= s.denominator /= } } int main() { int a[16001], b[16001], i, j, ca, fraction s, 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] = ca++; } } for(i = 1; i &= b[0]; i++)//b 的所有因子 { if(b[0] % i == 0) { b[cb] = cb++; } } s.denominator = s.numerator = 0; for(i = 1; i & i++)//计算因子组合的和 { for(j = 1; j & j++) { t.numerator = a[j]; t.denominator = b[i]; s = addFraction(&s, &t); }} int divisor = greatestCommonDivisor(s.numerator, s.denominator);// 求最大公约数 //约分 s.numerator /= s.denominator /= 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, 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 & 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 a 2) GCD(p, q) = 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) =即 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)//最大公约数 { while(b) {t = a % a = b = } } int main() { int x, y, i, c, while(scanf(&%d %d&, &x, &y) != EOF) { if(y % x != 0)//如果发现最小公倍数不是最大公约数的倍数，就说明组数为 0 { printf(&0\n&); } c = 0; s = y / for(i = 1; i &= 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
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 %//乘以 a 后对 m 取模 b--; } a = a * a % b &&= 1;//等价于 b/= 2 } } int main() { int z, m, h, i,long long s, a, scanf(&%d&, &z); for(i = 0; i & i++) { s = 0; scanf(&%d&, &m); scanf(&%d&, &h); for(j = 0; j & j++) { scanf(&%I64d %I64d&, &a, &b); s = s + quickMod(a, b, m); s = s % } 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) { t = *a; *a = *b; *b = } 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, 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)//角度 scanf(&%d&, &n); for(i = 0; i & 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& class point { public: double x, point(double x1, double y1) { x = x1; y = y1; } }; class line { public: 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) else
} inline double max(double a, double b) { if(a & b) } int main() { int n, double x1, y1; scanf(&%d&, &n); for(i = 0; i & 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& class point { public: int x, point(int x1, int y1) { x = x1; y = y1; } point(){} }; class line: public point { public: point pa, 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) } inline int max(int a, int b) { if(a & b) } int outerProduct(line & l1, line & l2)// 外积 { return l1.x * l2.y - l2.x * l1.y; } int main(){ int n, i, while(scanf(&%d&, &n), n != 0) { point p[n]; c = 0;//计数器，记录有多少个凸角 for(i = 0; i & 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)//说明凹角 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) } int main() { double x1, x2, y1, y2, r1, r2, a1, a2, s1, s2, s3, pi,//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& //声明 double outerProduct(line & l1, line & l2); double outerProduct(point & l1, point & l2); class point { public: int x, 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,//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 -if(fabs(outerProduct(p21, p31)) & 1e-8 && fabs(outerProduct(p21, p41)) & 1e-8)//如果 p1，p2，p3 共线，p1，p2， p4 共线就说明重合, } }; 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, point p1, p2, p3, p4;//c 用来表示两线的外积 scanf(&%d&, &n); printf(&INTERSECTING LINES OUTPUT\n&); for(i = 0; i & 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 = (l1.y * l2.c - l2.y * l1.c) ///除以外积 x = -(l1.c * l2.x - l2.c * l1.x) / 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, double A;//多边形面积 while(scanf(&%d&, &n), n != 0) { int x[n], y[n]; A = 0; for(i = 0; i & 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/7.html 我们求重心也是利用求面积公式，只是多了一个权(就是要多乘一个坐标) 代码： #include &stdio.h& #include &math.h& int main() { int t, i, n, double xt, yt,//大 A 表示多边形面积，xt，yt 用于表示最终结果scanf(&%d&, &t); for(i = 0; i & i++) { s = xt = yt = 0; scanf(&%d&, &n); int x[n], y[n];//a 表示第 i 个三角形的面积 double m[n]; for(j = 0; j & 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, double r3;//表示 的塔 scanf(&%d&, &n); for(i = 0; i & 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, while(scanf(&%d %d&, &n, &m) != EOF) { scanf(&%d %d&, &x0, &y0); scanf(&%d %d&, &vx, &vy); scanf(&%d&, &t); for(i = 0; i & i++)//模拟 t 秒 { x0 = x0 +//1 秒后的位置 y0 = y0 + if(x0 & n)//x 方向上的处理{ x0 = n - (x0 - n);//反弹回来 vx = - } else if(x0 & 0) { x0 = -x0;//反弹回来了 vx = - } if(y0 & m)//y 方向上的处理 { y0 = m - (y0 - m); vy = - } else if(y0 & 0) { y0 = -y0; 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& //声明 class point {public: int x, 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 * } }; 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 & i++) { while(outerProduct(s[top - 1], s[top], p[i]) &= 0)//由 S 的栈顶元素的下一个元素、S 的栈顶元素以及 pi 构成的折线 段不拐向左侧 {//出栈操作 top--; } //把 p[i]入栈 top++; s[top] = p[i]; } } int main() { int n, i, minY;//用来存储凸包总长度 while(scanf(&%d&, &n), n != 0) { for(i = 0; i & i++) scanf(&%d %d&, &p[i].x, &p[i].y); if(n == 1) { printf(&0.00\n&); } else if(n == 2)//当只有两个点时，长度应该是 p1p2 的两倍，因为即使两线重合，也要算长度 { printf(&%.2lf\n&, 2 * Distance(p[0], p[1])); } //选择法思想找出 y 最小的点，存储到 p[0] minY = 0; for(i = 1; i & i++) if(p[i] & p[minY])//重载的&。比较的时候如果 y 小就返回真，如果 y 一样，就比较 x，x 小就返回真 minY = if(minY != 0)//最小值不是初始的第一个，就交换 0 和 minY {//重载了=，可以直接赋值 point t = p[0]; p[0] = p[minY]; p[minY] = } //对 p[1]到 p[n-1]进行排序，排序标准为 pipj pipj+1 的夹角 sort(p + 1, p + n, compare); int top = hull(n); l = 0; for(i = 0; i & 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, 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, scanf(&%d&, &t); for(i = 0; i & i++) { c = 0;//计数器清零 scanf(&%d %d&, &h, &w); char a[h][w];//h 行 w 列的矩阵 int flag[h][w];//用于标记当前位置是否已经遍历过了 for(j = 0; j & j++) { scanf(&%s&, a[j]); for(k = 0; k & k++) flag[j][k] = 0;//初始化标记 } for(j = 0; j & j++) for(k = 0; k & 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
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&//地图大小//表示最大的可放置碉堡的数量 char map[5][5];//最大 4*4 的方阵,还需要一个位置来存储\0 int canPlace(int x, int y)//判断(x,y)是否能放置碉堡 { 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')//碰到墙壁时就停止搜索了 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')//碰到墙壁时就停止搜索了 return 1;//运行到这里还没说明之前没碰到碉堡，所以返回真 } void dfs(int k, int currentNumber)// 搜索的起始位置 当前已经放置的碉堡数 { int x, if(k == n * n)//搜索的位置是地图最后一个位置之后的一个位置。因为 k 是从 0 开始的，所以当 k==n*n 时，就说明整个地图搜 索完成 { if(currentNumber & max)//如果当前已经放置的碉堡数 比 记录中最大的数 更大，就更新最大值 max = currentN } x = k ///行位置 y = k %//列位置 if(canPlace(x, y)) { map[x][y] = 'b';//放置碉堡 dfs(k + 1, currentNumber + 1);//搜索下一个位置，计数器加 1 map[x][y] = '.';//回溯，这个不好解释，不懂的上网自己查查 } dfs(k + 1, currentNumber);//搜索下一个位置，因为没成功放置，计数器不修改 } int main() { while(scanf(&%d&, &n), n != 0) { for(i = 0; i & 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 'S': the start 'D': the D 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.可走的路程数小于时间 2.奇偶剪枝，最短步数时间 和 开门时间 的差 是奇数，就不可能刚好到达; 3.当前搜索的步数和 t 相同时，应该停止搜索。 4.碰到门时应该停止搜索。 代码：#include &stdio.h& int n,//地图大小//表示第几秒开门 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; } 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, 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] =//回溯 } } return 0;//运行到这里就说明失败 } } int main() { int i, j, sx, sy, ex, ey,//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 & i++)//输入地图 { scanf(&%s&, map[i]); for(j = 0; j & j++) if(map[i][j] == 'S')//狗的位置 { sx = sy = }else if(map[i][j] == 'D')//门的位置 { ex = ey = cr++; } else if(map[i][j] == '.')//碰到点，计数器增加 cr++; } if(cr & t || (t - abs(sx - ex) + abs(sy - ey)) % 2 != 0)//两个剪枝条件 1.可走的路程数小于时间 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