2015
04-15

# 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

(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”);
}
}

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