题解 P5506 【封锁】
stone_juice石汁 · · 题解
一道大模拟题
先吐槽一下吧：
这是一个比赛的
比赛前，出题人说：“这次比赛难度 普及- 到 省选 难度吧，
你告诉我这题 普及-？？？
言归正传
听说有人打这道题而且我对我的码风很自信。题解已经尽力写的很详细了，绝对的逐步求解，希望能帮到大家。
再怎么说，也是一道
所以我们一步一步来~，做这种题不能急。
-
1、存储
这道题共有
于是，这里开结构体一定是最稳健的。不管后面有没有什么排序一类的操作，打包一堆数据总比一堆零散的数据容错率要高一些。
struct feiji
{
int x, y, z, h, f, atk, deg, mat, mdf, hp, fix, ti;//ti代表飞机的号数。
string s;//代表操作
}f[205];另外，我在比赛上想过开二维数组来模拟飞机的位置状况，但是坐标是有负值的。而且在我强行把坐标加上一个较大值，不让坐标为负时，事实证明还是会炸，（其实是我太蒟了）。所以我们不选择开数组模拟位置。
-
2、移动
每驾存活的无人机，每回合都会移动一轮。而移动方向则是他们面向的方向。
这里需要注意：所有飞机都移动完之后，各个飞机才会执行各个指令（如转向，攻击）
既然我们刚刚把方向的表给打出来了，移动就变得很简单了。
for(int j = 1; j <= n; j ++)//枚举每驾飞机
{
if(f[j].hp > 0)//存活的飞机才能移动
{
f[j].x += dx[f[j].f][f[j].h]; //向自己的方向移动
f[j].y += dy[f[j].f][f[j].h];
f[j].z += dz[f[j].f][f[j].h];
}
}由于我们存储移动方向的单位 正好是前方一格，所以直接加在原坐标上即可。
有个表是不是很方便？
-
3、转向（U/D/L/R操作）
转向是一个大坑，甚至出题人自己都弄错了。
最开始这题是没有我也看不懂。出题人就弄了一个表。
然后出题人还把表打错了，后来才改回来
既然有了表，就很简单了。我们把表打上去就可以了。 也用不着写函数计算什么之类的，这样代码复杂，写错了
int dx[8][5] = {{0, 1, 1, 1, 0},{0, 1, 1, 1, 0},{0, 0, 0, 0, 0},{0, -1, -1, -1, 0},{0, -1, -1, -1, 0},{0, -1, -1, -1, 0},{0, 0, 0, 0, 0},{0, 1, 1, 1, 0}};
int dy[8][5] = {{0, 0, 0, 0, 0},{0, 1, 1, 1, 0},{0, 1, 1, 1, 0},{0, 1, 1, 1, 0},{0, 0, 0, 0, 0},{0, -1, -1, -1, 0},{0, -1, -1, -1, 0},{0, -1, -1, -1, 0}};
int dz[8][5] = {{-1, -1, 0, 1, 1},{-1, -1, 0, 1, 1},{-1, -1, 0, 1, 1},{-1, -1, 0, 1, 1},{-1, -1, 0, 1, 1},{-1, -1, 0, 1, 1},{-1, -1, 0, 1, 1},{-1, -1, 0, 1, 1}};其中
于是，只要有了无人机的
表打好了，接下来还有修改操作。即修改无人机的
在这里，
而
对于这两个值的处理，特判就可以了。
//这里，我用char型字符c储存的指令信息，后面也一样。
if(c == 'U') if(f[j].h < 4) f[j].h ++;
if(c == 'D') if(f[j].h > 0) f[j].h --;
if(c == 'L')
{
f[j].f ++;
if(f[j].f > 7) f[j].f = 0;
}
if(c == 'R')
{
f[j].f --;
if(f[j].f < 0) f[j].f = 7;
}//这组代码没什么好说的，看就可以看懂-
4、修复（F操作）
这个是最简单的操作了，对自己的飞机
题目没说什么生命条上限之类的东西，不用特判。
if(c == 'F') f[j].hp += f[j].fix;-
5、子弹，激光（A，M操作）
接下来才是重头戏！ 两个攻击操作是全题最难的点了。
方法Ⅰ、
这种方法也是我用的方法。
我们现在来想象一下：
无人机发出了子弹/激光。
无人机 面向方向的前面一格就会出现一颗 子弹/激光束。（必须是前面一格，因为打不到与自己重叠的飞机）
子弹保持无人机面向的方向飞去 / 激光束保持无人机面向的方向扩散。
我们现在使用慢放的高超技术，我们可以看到每一时刻，子弹 / 激光束每次以原来的方向移动一格.....
直到碰到了飞机，子弹消失 / 激光束穿了过去，继续向前飞去....
于是乎，在想象中，我们的算法就完成了：记录无人机位置的前面一格，使用
怎么判断攻击是否击中了其他飞机呢？？由于我太蒟了，只能用一种笨拙的方法：
我们在每次子弹/激光束移动完成后，就枚举一遍所有存活的飞机，看是否有飞机的坐标正好与 子弹/激光束 的坐标相同。相同的话就说明打到飞机了，造成伤害即可。
可以看到，这种方法十分的笨拙，但好在本题数据不大，最高也就开到了
代码：
if(c == 'A')
{
bool flag = false;
for(int k = 1; k <= 100; k ++)//循环，模拟子弹/激光束移动
{
for(int v = 1; v <= n; v ++)//枚举每驾飞机，看是否被攻击。
if(f[j].x + dx[f[j].f][f[j].h] * k == f[v].x && f[j].y + dy[f[j].f][f[j].h] * k == f[v].y && f[j].z + dz[f[j].f][f[j].h] * k == f[v].z && f[v].hp != 0) //子弹遇上飞机，且那架飞机存活，就减血
{
if(f[j].atk > f[v].deg)f[v].hp -= (f[j].atk - f[v].deg);
flag = true;//由于子弹会消失，所以要及时break;
break;
}
if(flag) break;
}
}
if(c == 'M')
{
for(int k = 1; k <= 100; k ++)
for(int v = 1; v <= n; v ++)
if(f[j].x + dx[f[j].f][f[j].h] * k == f[v].x && f[j].y + dy[f[j].f][f[j].h] * k == f[v].y && f[j].z + dz[f[j].f][f[j].h] * k == f[v].z) //激光遇上飞机，且那架飞机存活
if(f[j].mat > f[v].mdf)f[v].hp -= (f[j].mat - f[v].mdf);
}提一句：我的判断里写的是：
f[j].x/y/z + dx/y/z[f[j].f][f[j].h] * k == f[v].x/y/z其实这也是很好理解的，把累加换成了乘法而已。因为加上的数是相同的。
这就和
顺带吐槽一句：这道题 水 好。
方法Ⅱ、
方法Ⅰ时间复杂度不稳，很悬？怎么办？
这里给出方法Ⅱ，这需要一颗数学的大脑。
我们可以求出无人机面向方向的直线方程式（就是所谓的
拿这个方程式去代入所有飞机的坐标，如果在这条直线上，那么就会被攻击到。
这里倒是有一个前提：必须是攻击发起者无人机面对的方向。 毕竟背对无人机方向的飞机也有可能在这条直线上，所以要特判。
如果是激光，上述所说的就已经完成操作了。但子弹遇到第一架飞机会消失，这里就比较麻烦了。
我们需要计算所有满足上述要求无人机 与 攻击发起者 的距离。距离最短的就是被攻击的目标了。
由于这种方法是省下了时间，但是代码很容易出错，我也就没去用这种方法。当然也没有代码。有自信的童鞋们可以去试试 awa。
6、合并
上述就是所有操作的讲解及代码了。
（请不要问我为什么无视要
由于在所有飞机移动之后，剩下的飞机就会按编号顺序，每次执行一个指令。所以上述的指令代码全部都套在一个
最后的最后，由于时间为
于是我们把代码合并下来。
#include<bits/stdc++.h>
#define mian main
#define QWQ puts("QWQ");
using namespace std;
struct feiji
{
int x, y, z, h, f, atk, deg, mat, mdf, hp, fix, ti;
string s;
}f[205];
int n, t;
int dx[8][5] = {{0, 1, 1, 1, 0},{0, 1, 1, 1, 0},{0, 0, 0, 0, 0},{0, -1, -1, -1, 0},{0, -1, -1, -1, 0},{0, -1, -1, -1, 0},{0, 0, 0, 0, 0},{0, 1, 1, 1, 0}};
int dy[8][5] = {{0, 0, 0, 0, 0},{0, 1, 1, 1, 0},{0, 1, 1, 1, 0},{0, 1, 1, 1, 0},{0, 0, 0, 0, 0},{0, -1, -1, -1, 0},{0, -1, -1, -1, 0},{0, -1, -1, -1, 0}};
int dz[8][5] = {{-1, -1, 0, 1, 1},{-1, -1, 0, 1, 1},{-1, -1, 0, 1, 1},{-1, -1, 0, 1, 1},{-1, -1, 0, 1, 1},{-1, -1, 0, 1, 1},{-1, -1, 0, 1, 1},{-1, -1, 0, 1, 1}};
int main()
{
scanf("%d%d", &n, &t);//输入部分
for(int i = 1; i <= n; i ++)
{
scanf("%d%d%d%d%d%d%d%d%d%d%d", &f[i].x, &f[i].y, &f[i].z, &f[i].h, &f[i].f, &f[i].atk, &f[i].deg, &f[i].mat, &f[i].mdf, &f[i].hp, &f[i].fix);
cin >> f[i].s;
f[i].ti = i;//这里记录了每驾无人机的编号
}
for(int i = 1; i <= t; i ++)//t表示时间，所以要循环t轮
{
for(int j = 1; j <= n; j ++)
{
if(f[j].hp > 0)
f[j].x += dx[f[j].f][f[j].h], f[j].y += dy[f[j].f][f[j].h], f[j].z += dz[f[j].f][f[j].h];
}
for(int j = 1; j <= n; j ++)
{
if(f[j].hp <= 0)//坠毁的飞机就不操作了
continue;
char c = f[j].s[i - 1];
//由于字符串是从 s[0]开始存的（而不是1），所以这里要 -1。
if(c == 'N')continue;//没有操作就continue掉
if(c == 'U') if(f[j].h < 4) f[j].h ++;
if(c == 'D') if(f[j].h > 0) f[j].h --;
if(c == 'L')
{
f[j].f ++;
if(f[j].f > 7) f[j].f = 0;
}
if(c == 'R')
{
f[j].f --;
if(f[j].f < 0) f[j].f = 7;
}
if(c == 'F') f[j].hp += f[j].fix;
if(c == 'A')
{
bool flag = false;
for(int k = 1; k <= 100; k ++)
{
for(int v = 1; v <= n; v ++)
if(f[j].x + dx[f[j].f][f[j].h] * k == f[v].x && f[j].y + dy[f[j].f][f[j].h] * k == f[v].y && f[j].z + dz[f[j].f][f[j].h] * k == f[v].z && f[v].hp != 0)
{
if(f[j].atk > f[v].deg)f[v].hp -= (f[j].atk - f[v].deg);
flag = true;
break;
}
if(flag) break;
}
}
if(c == 'M')
{
for(int k = 1; k <= 100; k ++)
for(int v = 1; v <= n; v ++)
if(f[j].x + dx[f[j].f][f[j].h] * k == f[v].x && f[j].y + dy[f[j].f][f[j].h] * k == f[v].y && f[j].z + dz[f[j].f][f[j].h] * k == f[v].z)
if(f[j].mat > f[v].mdf)f[v].hp -= (f[j].mat - f[v].mdf);
}
}
}
for(int i = 1; i <= n; i ++)
{
printf("%d %d %d ", f[i].x, f[i].y, f[i].z);
if(f[i].hp <= 0) printf("0\n");//如果坠毁，生命值输出0
else printf("%d\n", f[i].hp);
}
return 0;
} 看代码好像很长...其实我觉得这个算短的了。
7、注意点：
-
1、如果同一坐标里有多组无人机，编号最小的会被子弹攻击。
这个我们已经在无形之中处理掉了。因为我们枚举每驾飞机就是从
1 开始枚举的。一旦有飞机被攻击，就会立即break ，后面编号大的飞机就不会处理了。 -
2、激光和子弹 分别对应了伤害值和防御值。
（我在打子弹的代码时不小心把激光的伤害值和防御值套进去了，搞得我调了半天代码...awa）
8、后记
不得不说啊...这种大模拟打起来真的很累人。但是多练这种题，代码能力会明显提高。
毕竟套算法的就是考你算法学习，套模拟就是考你代码能力。
这篇题解总计码了点赞)。希望大家能看懂 QAQ。
有不懂的可以发评论 或者 讨论版 at我，我尽量会看的 awa。