首页 > ACM题库 > HDU-杭电 > HDU 4030-Tank-枚举-[解题报告]HOJ
2015
04-15

HDU 4030-Tank-枚举-[解题报告]HOJ

Tank

问题描述 :

Surprisingly, the king of the Quadruple Island Kingdom suddenly declares war on its neighbor country, the Utopia Land. After that, the King dispatches a large number of tanks for first attack. You, as the Defense Minister of Utopia Land, are certainly under mass of pressure. In order to defense the enemy, you decide to use the new secret weapon: laser cannon. This kind of weapon is so powerful that can easily destroy any thing at a line in a moment, or course, including tanks.
However, Because of some designing flaw, you can use such weapon just once during the war. The only hope is that you can choose a good moment and right way to use it so that as many tanks as possible can be destroyed.
A tank can be described as a point whose coordinate is (Xi, Yi) on a 2D-plain with speed vector (VXi, VYi) per second. Starting at time 0, you can use your laser cannon at any position and in any direction at any INTEGER number of seconds after time 0. It is possible that some tanks will meet at the same point while moving, and they will not influence each other anyway.

输入:

There are multiple test cases and the number of test cases is no more than 100.
For each test cases, The first line contains a single integer N (1 <= N <= 100) indicating the number of tanks. Then N lines are following that describing the tanks respectively. Each of them consists of four nonzero integer Xi, Yi, VXi and VYi separated by single space where |Xi|,|Yi| <= 100,000,000 and |VXi|,|VYi| <= 100 denoting the initial position of a tank and the speed vector. Input will end when N = 0.

输出:

There are multiple test cases and the number of test cases is no more than 100.
For each test cases, The first line contains a single integer N (1 <= N <= 100) indicating the number of tanks. Then N lines are following that describing the tanks respectively. Each of them consists of four nonzero integer Xi, Yi, VXi and VYi separated by single space where |Xi|,|Yi| <= 100,000,000 and |VXi|,|VYi| <= 100 denoting the initial position of a tank and the speed vector. Input will end when N = 0.

样例输入:

4
10 10 -1 -1
3 1 4 6
2 8 5 -1
1 3 1 4
0

样例输出:

3


就是一道很恶心的枚举题,但只需要列举出第一个人赢的情况就行了,如果没有出现第一个人赢的情况,那就是输出“No”了。(只需要细心枚举就行了)
(include里的头文件总是不显示出来,哎~)
#include<<iostream>>
using namespace std;
char a[20],b[20];
int so[20],st[20];
int expair(int *a,int have=0)
{
 int yes=0;
 for(int i=17;i>0;i–)
 {
  if(a[i]>=2&&i!=have)
  {
   yes=i;
   break;
  }
 }
 return yes;
}
int big(int *a)
{
 int yes=0;
 for(int i=17;i>0;i–)
 {
  if(a[i])
  {
   yes=i;
   break;
  }
 }
 return yes;
}
int if_pair(int *a)
{
 int yes=0;
 for(int i=17;i>0;i–)
 {
  if(a[i]>=2)
  {
   yes=i;
   break;
  }
 }
 return yes;
}
int if_thr(int *a)
{
 int yes=0;
 for(int i=17;i>0;i–)
 {
  if(a[i]>=3)
  {
   yes=i;
   break;
  }
 }
 return yes;
}
int if_bomb(int *a)
{
 int yes=0;
 for(int i=0;i<=17;i++)
 {
  if(a[i]>=4)
  {
   yes=i;
   break;
  }
 }
 return yes;
}
bool if_super(int *a)
{
 if(a[16]&&a[17]) return 1;
 else return 0;
}
void ended()
{
 printf(“Yes\n”);
}
int main()
{
 //freopen(“d://1010.in”,”r”,stdin);
 //freopen(“d://1010out.txt”,”w”,stdout);
 int t;
 scanf(“%d”,&t);
 while(t–)
 {
  memset(so,0,sizeof(so));
  memset(st,0,sizeof(st));
  scanf(“%s”,a);
  scanf(“%s”,b);
  int len1=strlen(a);
  int len2=strlen(b);
  for(int i=0;i
  {
   if(a[i]>=’3′&&a[i]<=’9′)
so[a[i]-’0′]++;
   else
if(a[i]==’T') so[10]++;
   else
if(a[i]==’J') so[11]++;
   else
if(a[i]==’Q') so[12]++;
   else
if(a[i]==’K') so[13]++;
   else
if(a[i]==’A') so[14]++;
   else
if(a[i]==’2′) so[15]++;
   else
if(a[i]==’X') so[16]++;
   else
if(a[i]==’Y') so[17]++;
  }
  for(int i=0;i
  {
   if(b[i]>=’3′&&b[i]<=’9′)
st[b[i]-’0′]++;
   else
if(b[i]==’T') st[10]++;
   else
if(b[i]==’J') st[11]++;
   else
if(b[i]==’Q') st[12]++;
   else
if(b[i]==’K') st[13]++;
   else
if(b[i]==’A') st[14]++;
   else
if(b[i]==’2′) st[15]++;
   else
if(b[i]==’X') st[16]++;
   else
if(b[i]==’Y') st[17]++;
  }
  ///one time win
  if(len1==1) { printf(“Yes\n”);
continue;}
  if(so[16]&&so[17]) {
printf(“Yes\n”);continue;}
  if(len1==2&&if_pair(so))
{ ended();continue;}
  if(len1==3&&if_thr(so)){
ended();continue;}
  if(len1==4&&(if_bomb(so)||if_thr(so))){
ended();continue;}
  if(len1==5)
  {
   int
thr=if_thr(so);int pair=expair(so,thr);
   if(thr&&pair&&thr!=pair)
{ ended(); continue;}
  }
  if(len1==6&&if_bomb(so)){
ended();continue;}
  //cout<<”#1″<<endl;//
  ///bigger
  if(!if_super(st)&&!if_bomb(st))
  {
   if(big(so)>=big(st))
{ ended();continue;}
   //if(so[17])
{ ended();continue;}
   if(if_pair(so)>=if_pair(st)&&if_pair(so)
){ended();continue;}
   if(if_thr(so)>if_thr(st)&&if_thr(so)){
ended(); continue;}
   int
thra=if_thr(so),paira=expair(so,thra);
   int
thrb=if_thr(st),pairb=expair(st,thrb);
   if(thra&&paira&&thra!=paira&&(!thrb||pairb==0))
{ ended(); continue;}
   if(thra&&thrb&&len1>=4&&len2==3)
{ ended();continue;}
    //cout<<”#2″<<endl;
  }
  else
if(if_bomb(st)&&!(if_super(st)))
  {
   int
bomba=if_bomb(so);
   int
bombb=if_bomb(st);
   if(bomba>bombb)
{ ended();continue;}
  }
  //cout<<”#3″<<endl;
  printf(“No\n”);
 }
}
参考:http://blog.sina.com.cn/s/blog_7325cb5f0102v0g2.html


  1. 这道题目虽然简单,但是小编做的很到位,应该会给很多人启发吧!对于面试当中不给开辟额外空间的问题不是绝对的,实际上至少是允许少数变量存在的。之前遇到相似的问题也是恍然大悟,今天看到小编这篇文章相见恨晚。

  2. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。