首页 > ACM题库 > HDU-杭电 > hdu 2541 棒球防守-DFS-[解题报告]other
2014
02-10

hdu 2541 棒球防守-DFS-[解题报告]other

棒球防守

问题描述 :

在棒球比赛中,当对方打击者将投手投来的球击打出去以后,投手的队友们所要做的就是尽量把这个球防守下来,尽可能让对方出局。通常,防守的方法有两种:
(1)  如果打出的球是高飞球,则防守方可以在球落地之前用手套把球接住,称之为“接杀”,直接让打击者出局。
(2)  如果打出的球是滚地球,则防守方的内场防守员(定义见下面)可以跑到球的线路上将球接住,并且传给一垒的防守员,如果一垒手接住球时打击者还没有跑到一垒(在本题中,假设这个条件一定成立。也就是内场防守员接到球的话打者就出局了),则称之为“封杀”,也可以让打击者出局。
在本题中,输入给出打出的球的类型(高飞还是滚地),以及球的落点和飞行时间(对于高飞球)或者球的方向和速度(对于滚地球),和所有的防守队员的初始站位和移动速度,判断能不能让打者出局。
假设防守队员接球、传球都没有失误。
防守队员需要而且必须在球到之前(或同时)跑到高飞球的落地点上才能使打出高飞球的打者出局。
初始位置离本垒距离20以上(含)的防守员规定为外场防守员,否则为内场防守员。
内场防守员需要而且必须在球到之前(或同时)跑到滚地球的线路上才能接住滚地球(并使打者出局)。如果他跑到了外场把球接住,打者也出局。
如果所有的内场防守者都不能接住一个滚地球,尽管可能有外场防守者能接到(即使他可以在内场接到球),打者仍然是安全的,不会出局。
假设球场是+x轴和+y轴夹成的一块区域,并向右、上无限延伸。
坐标原点是本垒,假设所有的球都是从本垒正中打出的,而且朝球场的方向飞,且速度一直不变。

输入:

输入包含多组数据。每组数据第一行是两个整数N和M(4<=N<=10,0<M<=100),分别表示防守队员的人数和打出来的球数。N=M=0表示输入结束。接下来有N行,每行都有三个整数X、Y、V(0<=X,Y<=100,0<V<=10),表示对应的防守队员的坐标和速度。最后有M行,每行首先是一个字符(’F’和’G’之一),如果是’F’,则表示这是一个高飞球,之后会跟上三个整数XX、YY、T(0<=XX,YY<=100,0<T<=10),分别表示球的落点的X、Y坐标和飞行时间;如果是’G’,表示这是一个滚地球,之后会跟上一个分数H/L和一个整数VV(1<=H,L<=100,0<VV<=100),分别表示球的飞行方向与+X轴夹角的正切值和球的速度。

输出:

输入包含多组数据。每组数据第一行是两个整数N和M(4<=N<=10,0<M<=100),分别表示防守队员的人数和打出来的球数。N=M=0表示输入结束。接下来有N行,每行都有三个整数X、Y、V(0<=X,Y<=100,0<V<=10),表示对应的防守队员的坐标和速度。最后有M行,每行首先是一个字符(’F’和’G’之一),如果是’F’,则表示这是一个高飞球,之后会跟上三个整数XX、YY、T(0<=XX,YY<=100,0<T<=10),分别表示球的落点的X、Y坐标和飞行时间;如果是’G’,表示这是一个滚地球,之后会跟上一个分数H/L和一个整数VV(1<=H,L<=100,0<VV<=100),分别表示球的飞行方向与+X轴夹角的正切值和球的速度。

样例输入:

4 4
10 0 2
0 10 2
25 0 5
0 25 5
F 30 30 6
F 30 30 7
G 1/1 3
G 1/1 2
0 0

样例输出:

SAFE
OUT
SAFE
OUT

提示:
所有输入数据允许时间有1e-5的计算误差。即不能杀的球至少快了1e-5的时间落地(高飞)或者滚过(滚地),
能杀的球则至少慢了1e-5的时间。
直接用double来计算和比较应该不会存在精度问题。

/*
*Time: 93ms
*题目大意:
*        求i+(i+1)+(i+2)的结果对于有没有进位,没有进位的称为Simple Addition Expression
*        给定一个n,求i < n有多少个数可以称为simple Addition Expression.
*解题思路:
*        总共有786432个符合要求的数据。所以可以用暴力。
*        求出所有的满足的simple Addition Expression的数。之后用二分查找位置即可。
*/
#include <iostream>
 #include <algorithm>
 #include <iterator>
 using namespace std;
 
 const int MAX = 1000000;
 int num[10], cnt;
 __int64 res[MAX];
 
 __int64 arrayToInt64(int arr[], int n)
 {
     __int64 digit = 1, sum = 0;
     for(int i = n; i >= 0; i--)
     {
         sum += arr[i] * digit;
         digit *= 10;
     }
     return sum;
 }
 
 void dfs(int digit)
 {
     if(digit != 9)
     {
         for(int i = 0; i < 4; i++)
         {
             num[digit] = i;
             dfs(digit + 1);
         }
     }
     else
     {
         for(int i = 0; i < 3; i++)
         {
             num[digit] = i;
             res[cnt++] = arrayToInt64(num, digit);
         }
     }
 
     return ;
 }
 
 void viewArr(__int64 a[], int n)
 {
     for(int i = 0; i < n; i++)
         cout << a[i] << endl;
     return ;
 }
 
 int countNum(__int64 n)
 {
     __int64 *p;
     p = lower_bound(res, res+ cnt, n);
     return p - res;
 }
 
 int main(void)
 {
     //freopen("in.txt", "r", stdin);
     cnt = 0;
     dfs(0);
     //viewArr(res, 10);
     __int64 n;
     while(scanf("%I64d", &n) == 1)
     {
         printf("%d\n", countNum(n));
     }
     return 0;
 }
 
 
 /*
 *Time: 0ms
 *还是不怎么理解这种做法
 */
 #include <stdio.h>
 #include <math.h>
 #include <string.h>
 char s[15];
 /*
 传入数组下标i和,从当前位置开始剩余的数组长度。
 */
 int solve(int i,int p)
 {
     if(p==1)
         return s[i]>'2'?3:s[i]-'0'+1;
     /*当前值大于3,当然就可以取遍0-3的数字,这样子排列组合出的数值也一定比它小*/
     if (s[i]>'3')
         return (int)pow(4.0,p-1)*3;
     else
     {
         /*如果s[i] = 2,则取0-1时,后面的数字可以取遍0-3,除个位为3*/
         int tem1 = (int)(pow(4.0,p-2)*3*(s[i]-'0'));
         /*s[i]取2时,后面的数值就又是一次迭代计算啦*/
         int tem2 = solve(i+1,p-1);
         return tem1+tem2;
     }
 }
 
 int main()
 {
     int len;
     __int64 n;
     while (scanf("%I64d",&n)!=EOF)
     {
         n--;/*排列组合最大的数字就是n-1啦*/
         sprintf(s,"%I64d",n);
         len = strlen(s);
         printf("%d\n",solve(0,len));
     }
     return 0;
 }

解题转自:http://www.cnblogs.com/cchun/archive/2012/07/24/2606369.html


  1. 嗯 分析得很到位,确实用模板编程能让面试官对你的印象更好。在设置辅助栈的时候可以这样:push时,比较要push的elem和辅助栈的栈顶,elem<=min.top(),则min.push(elem).否则只要push(elem)就好。在pop的时候,比较stack.top()与min.top(),if(stack.top()<=min.top()),则{stack.pop();min.pop();},否则{stack.pop();}.

  2. 可以根据二叉排序树的定义进行严格的排序树创建和后序遍历操作。如果形成的排序树相同,其树的前、中、后序遍历是相同的,但在此处不能使用中序遍历,因为,中序遍历的结果就是排序的结果。经在九度测试,运行时间90ms,比楼主的要快。

  3. Thanks for using the time to examine this, I truly feel strongly about it and enjoy finding out far more on this subject matter. If achievable, as you achieve knowledge