2014
03-03

# HDU 3133-Ye Holy Hand Grenades!-DFS-[解题报告]HOJ

Holy Hand Grenades have found multiple uses throughout history. Most notably, King Arthur did use a Holy Hand Grenade (HHG) to dispatch a vicious rabbit which was guarding the entrance to a cave. The instructions for its use are in the Book of Armaments (Chapter 2, verses 9-21), and are read as follows:

Unfortunately, the Book of Armaments faileth to mention that the HHG must come to a complete stop (i.e. rest stably) before it can explodeth and blow a rabbit to tiny bits. As long as it rolleth or wobbeleth, it refuseth to explodeth. Unknown is the reason why the authors of the Book of Armaments neglected to mention this pertinent fact. Further complicating matters, different HHGs have different radii of destruction (RD). Once a HHG resteth stably, and explodeth, everything within or equal to its RD shalt be snuffed out. Presumably, this is what happened to the rabbit with big, pointy teeth; however, there remaineth some controversy over this matter. Because of this controversy, the king hath decreed a simulation to be run that may possibly answer this question.

• The grenade must always be at rest in order to detonate. All HHGs have a radius R=1 and a variable radius of destruction (RD). At the instant of detonation, the rabbit could be mid-leap, on the ground, or underground.
• For each simulation the terrain remaineth unchanged. It consisteth of two intersecting curves,  y = e-x  and  y = ln(x)  as we have revealed unto you in the illustrious illustration. The curves reside in the plane formed by the rabbit, the grenade, and the center of the earth. The terrain is impervious to detonations, and changeth not between tests.
• If a bunny’s center of mass is strictly below the ground level (as denoted by the intersecting curves) when a HHG explodeth, that bunny shalt remaineth un-snuffedeth and thus shalt live to bite another day.
• If the bunny resideth strictly outside of the range of a stably resting HHG’s radius of destruction, that bunny shalt also remain un-snuffedeth out.
• Each result shalt be dependent upon computations accurate even unto 8 significant figures.
• There shalt not be an input value smaller even than 1.0E-15 or greater even than 1.0E+15.
• Because the bunny’s center of mass doth be its location, a bunny might possibly end up inside both the RD and the R=1 of a HHG. This simply means the bunny is curled around the grenade. If the center of mass of such a bunny be strictly inside the RD it shall most surely be snufféd out. Amen.

.

The first line of input doth contain yea verily a single integer indicating the number of holy hand grenades in the data file. Each line of the file doth contain the radius of destruction of this particular holy hand grenade, and finally doth contain the rabbit’s x coordinate (xb) and y coordinate (yb) during this particular test run.

The first line of input doth contain yea verily a single integer indicating the number of holy hand grenades in the data file. Each line of the file doth contain the radius of destruction of this particular holy hand grenade, and finally doth contain the rabbit’s x coordinate (xb) and y coordinate (yb) during this particular test run.

2
1.5 3.0 3.0
5.5 3.0 3.0

Bunny Biteth Knights
Bunny Bits

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <stack>
#include <queue>
#include <map>
#include <algorithm>
#include <iostream>
using namespace std;

#define Maxn 30
#define Maxm 2005

struct Point
{
int vis;
int lchild,rchild;
int child;

}point[Maxn];

int vis[Maxn];
int ma[Maxn][Maxn];

vector <int> v[Maxm];
int vnum = 0;
map <int,int> just;
map <int,int> to;

bool cmp(vector<int> a,vector<int> b)
{
if(a.size() == b.size())
{
for(int i=0;i<a.size();i++)
{
if(a[i]!=b[i]) return a[i]<b[i];
}
}
else return a.size() < b.size();
}
void print(vector<int> has)
{
int flag = 1;
for(int i = has.size()-1;i>0;i--)
{
flag = flag & ma[has[i]][has[i-1]];
ma[has[i]][has[i-1]] = 1;
}
if(flag) return;
for(int i=0;i<has.size();i++)
{
v[vnum].push_back(to[has[i]]);
}
vnum++;
}
void dfs(int s,vector<int> has)
{
if(point[s].vis == 0)
{
point[s].vis = 1;
if(point[s].rchild!=-1 && point[s].lchild!=-1)
{
vector<int> t1 = has;
t1.push_back(point[s].rchild);
dfs(point[s].rchild,t1);
vector<int> t2 = has;
t2.push_back(point[s].lchild);
dfs(point[s].lchild,t2);
}
else if(point[s].child!=-1)
{
vector<int> t3 = has;
t3.push_back(point[s].child);
dfs(point[s].child,t3);
}
else print(has);
point[s].vis = 0;
}
else print(has);
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif
int s;
char str[20];
int a,b;
char d;
while(scanf(" %d",&s)!=EOF)
{
for(int i=0;i<Maxn;i++)
{
point[i].vis = 0;
point[i].lchild = point[i].rchild = point[i].child = -1;
}
memset(ma,0,sizeof(ma));
for(int i=0;i<Maxm;i++)
{
v[i].clear();
}
vnum = 0;
just.clear();
to.clear();
int hh = 0;
if(just.find(s) == just.end()) just[s] = ++hh;
to[just[s]] = s;
s = just[s];
while(scanf(" %s",str)!=EOF && str[0]!='E')
{
sscanf(str,"%d->%d,%c",&a,&b,&d);
if(just.find(a) == just.end()) just[a] = ++hh;
if(just.find(b) == just.end()) just[b] = ++hh;
to[just[a]] = a;
a = just[a];
to[just[b]] = b;
b = just[b];
if(d == 'T') point[a].lchild = b;
else if(d == 'F') point[a].rchild = b;
else point[a].child = b;
}
vector <int> has;
has.push_back(s);
dfs(s,has);
sort(v,v+vnum,cmp);
printf("CC=%d\n",vnum);
for(int i=0;i<vnum;i++)
{
for(int j=0;j<v[i].size();j++)
{
if(j == v[i].size()-1) printf("%d\n",v[i][j]);
else printf("%d,",v[i][j]);
}
}
}
return 0;
}

1. 我的闺蜜们啊，情绪迥异但是却能玩到一起，说实在的这的确是个很奇怪的事情呢，大家在一起十年了吧？我今年也就12岁，我们一共四个人，最大的13岁最小的11岁，从小就都住在一个院子里，也可以说小区吧，那里住的都是大部分都是退休的老人们，当然他们的子女大部分也跟

2. 漂亮。佩服。
P.S. unsigned 应该去掉。换行符是n 不是/n
还可以稍微优化一下，
int main() {
int m,n,ai,aj,bi,bj,ak,bk;
while (scanf("%d%d",&m,&n)!=EOF) {
ai = sqrt(m-1);
bi = sqrt(n-1);
aj = (m-ai*ai-1)>>1;
bj = (n-bi*bi-1)>>1;
ak = ((ai+1)*(ai+1)-m)>>1;
bk = ((bi+1)*(bi+1)-n)>>1;
printf("%dn",abs(ai-bi)+abs(aj-bj)+abs(ak-bk));
}
}

3. 学算法中的数据结构学到一定程度会乐此不疲的，比如其中的2－3树，类似的红黑树，我甚至可以自己写个逻辑文件系统结构来。

4. 题本身没错，但是HDOJ放题目的时候，前面有个题目解释了什么是XXX定律。
这里直接放了这个题目，肯定没几个人明白是干啥