P2586 [ZJOI2008]杀蚂蚁题解

Troubadour · 2021-09-04 00:23:22 · 题解

真是不得不说，这是一道考验耐心、毅力和阅读能力的一道好题。作为紫题大模拟，思维难度和代码实现难度倒不是很高；但是众多细节，或者是一个对题目的误解就足以让你面对屏幕自闭上一整天。

在这里，膜拜考场上做出这道题的大佬们，同时向所有过掉这道题，或者正在努力调这道题的同学们致以敬意。

废话不多说，我们分析分析这道题。

题意：P2586 [ZJOI2008]杀蚂蚁

（默认大家已经知道题意了）

我们可以得出，需要实现以下操作：

产生新蚂蚁；
蚂蚁选择方向并移动；
蚂蚁抢蛋糕；
大炮攻击蚂蚁；
清理死亡的蚂蚁；
其他琐碎的操作，比如放信息素，大炮 AOE 伤害，蛋糕 buff 等。

毫无疑问，我们需要对这一大堆信息进行维护，写一大堆函数来维护它们。在这里，为了便于实现，我借助了 OOP 的思想来维护这些信息。

因为 OOP 这玩意儿在 OI 中很少专门提及，这里简单说一下（摘自维基百科）：

面向对象程序设计（英语：Object-oriented programming，缩写：OOP）是种具有对象概念的编程典范，同时也是一种程序开发的抽象方针。它可能包含数据、特性、代码与方法。对象则指的是类（class）的实例。它将对象作为程序的基本单元，将程序和数据封装其中，以提高软件的重用性、灵活性和扩展性，对象里的程序可以访问及经常修改对象相关连的数据。面向对象程序设计可以看作一种在程序中包含各种独立而又互相调用的对象的思想。

翻译成人话就是，我们把需要跟踪维护的东西作为程序的单元封装起来，并让它们彼此关联，访问并修改信息。

回到这个题。用这样的思想分析一下，得到这些结果：

我要维护的是什么？地图、蚂蚁、炮和蛋糕。好的，蛋糕可以程序中一笔带过。以蚂蚁为例，我们要就需要一个对象来表示蚂蚁的各个方面，比如坐标、生命值、是否持有蛋糕等。是的，这将是基本数据单元——一个表示蚂蚁的各种信息和状态的对象。我需要一些方法来处理该对象。其次，计算机需要一些方法来执行计算，比如减少生命值什么的。最后，蚂蚁要和大炮进行交互，所以我也要有相关的实现。

好的，我们像这样分析，得出了程序的基本框架。接下来就可以愉快的写代码了。

在下面的代码里，我采取了类+对象的写法，本质上和结构体没什么区别。

首先我们对地图造一个类出来。这个类需要存储以下信息：

地图上的信息素；
地图上的不可达点。

这里，我们把长和宽定义成全局变量。

方便起见，这里把信息素为 -1 的点作为不可达的点。周围一圈直接设成 -1，就不用额外考虑边界情况了。

我们需要让它支持以下操作：

初始化；
每一回合信息素减一；
修改信息素数据。

所以，我们可以得到这样一个类：

int n, m;
class map
{
private:
    struct node
    {
        struct nodee
        {
            int a[20];
            int&operator[](int x)
            {
                return a[x + 3];
            }
        }a[20];
        nodee&operator[](int x)
        {
            return a[x + 3];
        }
    }g;//因为可能出现负数下标，所以这里需要处理一下。
public:
    map();
    void decrase();//信息素减少
    void init();//初始化
    int &operator()(int x, int y);
}mp;

直接给出函数实现代码：

map::map()
{
    for (int i = -2;i <= 15;i++)
    {
        for (int j = -2;j <= 15;j++)
        {
            g[i][j] = -1;
        }
    }
}
void map::init()
{
    for (int i = 0;i <= n;i++)
    {
        for (int j = 0;j <= m;j++)
        {
            g[i][j] = 0;
        }
    }
}
int &map::operator()(int x, int y)
{
    return g[x][y];
}

每一回合信息素减少的操作后面另外说。

接着，我们写蚂蚁的类。对于一只蚂蚁，我们需要以下数据：

蚂蚁的坐标；
蚂蚁的年龄、生命值；
蚂蚁的 LV 值。（什么，你问 LV 是什么意思？当然是 LOVE 了！）；
蚂蚁是否持有蛋糕；
蚂蚁上一次的坐标，这一次和上一次所在位置的信息素值。

记下上一次坐标和位置所在信息素值，有两个原因：

蚂蚁所在的位置信息素为 -1 ，我们必须开一个变量记下信息素值；
蚂蚁不能走回头路，这些位置也需要置为 -1。

同样，我们也要写一堆函数来维护它们。

那么类的框架如下：

bool cake;
int cnt;
class ant
{
private:
    bool iscarrying;
    int age;
    int hp;
    int LOVE;
    int x, y, tmpm;//tmpm：当前位置的信息素值。
    int lstx, lsty, lsttmpm;//lsttmpm：上一位置的信息素值。
protected:
    int selectdir(map &mp);
    void carrycake();//背着蛋糕走了
    double calchp();
    void move(map &mp, int dir);
public:
    ant();
    void decrase();//信息素减少
    void release(map &mp);//把信息素放回原位
    void attacked(int atk);//受到攻击
    bool isdead();//判断是否死亡
    void information();//放信息素
    void action(map &mp);
    int &xpos(), &ypos();
    int &getage();
    void output();//输出相关，后面输出蚂蚁信息用的
    bool iscarryingcake();
};

考虑实现函数。这里有几个细节要注意：

蚂蚁初始年龄是 0。
若最大的信息素不止一个，则按照东南西北的顺序选择有最多信息素的格点。（就因为这个问题，我调了一整天）
当蚂蚁年龄 \bmod 4=1 的时候，我们就需要让它逆时针转，至少转一次。这种情况下，只要找到合适的位置就走。
蚂蚁的 Hp 要用浮点数保存。
蚂蚁必须在移动之后才能获得蛋糕，其他时间都不行（比如说你在 (n,m) 的位置，然后一轮开炮之后扛蛋糕的那位挂了，蛋糕飞回来，你也不能立刻捡）。

那么我们如何保证蚂蚁不走回头路呢？在前面的声明中，我记录了上一次的位置和信息素，每次选方向之前置为 -1，选完方向再改回来即可。

给出实现：

ant::ant()
{
    iscarrying = 0,age = 0;
    LOVE = cnt / 6 + 1;cnt++;
    hp = calchp();
    x = y = 0;  tmpm = mp(x, y);
    lstx = lsty = 0,lsttmpm = -1;
    mp(0, 0) = -1;
}
void ant::information()
{
    if (iscarrying)
    {
        tmpm += 5;
    }
    else
    {
        tmpm += 2;
    }
}
void ant::attacked(int atk)
{
    hp -= atk;
}
bool ant::isdead()
{
    return hp < 0;
}
void ant::carrycake()
{
    iscarrying = 1,cake = 0;
    hp = std::min(hp + calchp() / 2.0, calchp());
}
int ant::selectdir(map &mp)
{
    lsttmpm = mp(lstx, lsty);
    mp(lstx, lsty) = -1;//上一次的位置不可达
    int res = 0;
    //////#3
    //////1:E  2:S  3:W  4:N
    struct node
    {
        int dir, val;
        bool operator<(const node x)const
        {
            return val == x.val ? dir<x.dir : val>x.val;
        }
    }a[10];
    for (int i = 1;i <= 4;i++)a[i].dir = i;
    a[1].val = mp(x, y + 1);
    a[2].val = mp(x + 1, y);
    a[3].val = mp(x, y - 1);
    a[4].val = mp(x - 1, y);
    std::sort(a + 1, a + 1 + 4);
    if (a[1].val == -1)//四个方向都是-1，蚂蚁被卡住了
    {
        return 0;
    }
    res = a[1].dir;
    if (age % 5 == 4)//蚂蚁开始逆时针转圈
    {
        int xxx = 5;
        while (xxx--)
        {
            res--;
            if (res == 0)res = 4;
            int xx = x, yy = y;
            if (res == 1)yy++;
            if (res == 2)xx++;
            if (res == 3)yy--;
            if (res == 4)xx--;
            if (mp(xx, yy) != -1)break;
        }
    }
    return res;
}
void ant::move(map &mp, int dir)
{
    mp(lstx, lsty) = lsttmpm;
    release(mp);//先把信息素地图复原
    lstx = x, lsty = y;
    if (dir == 1)y += 1;
    if (dir == 2)x += 1;
    if (dir == 3)y -= 1;
    if (dir == 4)x -= 1;
    tmpm = mp(x, y);
    mp(x, y) = -1;//自己的位置
}
double ant::calchp()//注意，这里要用浮点数来存
{
    double res = 4 * pow(1.1, LOVE);
    return res;
}
void ant::action(map &mp)//一次完整的行动
{
    int dir = selectdir(mp);
    move(mp, dir);
    if (x == n && y == m && cake == 1)cake = 0, carrycake();//如果可以拿蛋糕就拿走，顺便获得buff
}
void ant::release(map &mp)
{
    mp(x, y) = tmpm;
}
void ant::decrase()
{
    tmpm = std::max(tmpm - 1, 0);
}
void ant::output()
{
    printf("%d %d %d %d %d\n", age, LOVE, hp, x, y);
}
int &ant::getage()
{
    return age;
}
bool ant::iscarryingcake()
{
    return iscarrying;
}
int &ant::xpos()
{
    return x;
}
int &ant::ypos()
{
    return y;
}
std::vector<ant*>enemy;

根据题意，我们需要时刻保证蚂蚁的行动顺序是按照年龄顺序。那么我们可以把这些蚂蚁依次塞到一个 vector 中，每次从头到尾遍历蚂蚁并进行操作。

再考虑这样一种情况：假如大炮架在蚂蚁窝门口，攻击力还特别高（秒杀），每次出生一只蚂蚁就被打死，持续 20 万次，这种排队枪毙的情况非常占用时空。我们已经利用 vector 避免了每次遍历引起的超时。可以发现，死掉的蚂蚁对后面的操作没有任何贡献，完全可以直接报废掉，考虑动态为每一只蚂蚁分配内存。这样做的一个代价就是，vector 里将不得不存储一堆指针。

现在回过头来说每次的信息素减一的情况，我们分为两步：

地图上，只要是空位，就考虑信息素减 1（因为有蚂蚁的地方信息素就是 -1）；
每一只蚂蚁的位置上的信息素减 1。

那么，代码的实现就是这样：

void map::decrase()
{
    for (int i = 0;i <= n;i++)
    {
        for (int j = 0;j <= m;j++)
        {
            if (g[i][j] != -1)g[i][j] = std::max(0, g[i][j] - 1);
        }
    }
    for (std::vector<ant*>::iterator it = enemy.begin();it != enemy.end();it++)
    {
        (*it)->decrase();
    }
}

最后，我们再来写大炮的代码。

对于每一台炮，我们都记录下它的坐标、射程和攻击力。

支持的操作很显然了，一个是选择目标，一个是攻击。

根据题意，只要目标在其射程内，塔到目标蚂蚁圆心的连线上的所有蚂蚁（这里“被打到”的判定变成了表示激光的线段与表示蚂蚁的圆有公共点）都会被打到并损 d 格血，所以我们还要判断其他的蚂蚁是否在这一条线上，就需要写一个计算几何模板了。还好还好，蚂蚁最多只有 6，直接遍历所有蚂蚁就行。

计算几何模板就不放出来了，整个类的实现如下：

class nuclear
{
private:
    int range;
    int x, y;
    int atk;
protected:
    void attack(int target);
    int selecttarget();
public:
nuclear(int _x, int _y, int _atk, int _range);
    void action();
};
nuclear::nuclear(int _x, int _y, int _atk, int _range)
{
    x = _x, y = _y;
    atk = _atk, range = _range;
    mp(x, y) = -1;
}
int nuclear::selecttarget()
{
    int res = -1;
    double dis = 10000;
    for (int i = 0;i < enemy.size();i++)
    {
        double now = GetDis(x, y, enemy[i]->xpos(), enemy[i]->ypos());//GetDis：获取距离
        if (now - 1.0*range <= eps)
        {
            if (enemy[i]->iscarryingcake())
            {
                return i;//优先选择拿着蛋糕的蚂蚁
            }
            else if (now < dis)//不然就选择最近的那个
            {
                dis = now;
                res = i;
            }
        }
    }
    return res;
}
void nuclear::attack(int target)
{
    if (target == -1)return;
    Point A = { (double)x,(double)y }, B = { (double)enemy[target]->xpos(),(double)enemy[target]->ypos() };
    //point：存储相关点的坐标
    enemy[target]->attacked(atk);
    for (int i = 0;i < enemy.size();i++)//判断 AOE 的情况
    {
        if (i == target)continue;
        Point P = { (double)enemy[i]->xpos(),(double)enemy[i]->ypos() };
        if (checkcircle(P, A, B) - 0.5 <= eps)//checkcircle：检测圆和线段是否有交点
        {
            enemy[i]->attacked(atk);
        }
    }
}
void nuclear::action()
{
    attack(selecttarget());
}
std::vector<nuclear>tower;

收尾工作就更简单了，直接按照题目给出的顺序模拟就行。因为前面已经实现了这些函数，我们写主函数的时候将会非常轻松愉快。完美。

void clear()
{
    for (int i = 0;i < enemy.size();i++)
    {
        if (enemy[i]->isdead())
        {
            if (enemy[i]->iscarryingcake())cake = 1;//如果蚂蚁扛着蛋糕，就把蛋糕传送回去
            enemy[i]->release(mp);//蚂蚁所在位置的信息素
            delete enemy[i];
            enemy.erase(enemy.begin() + i);
            i--;
        }
    }
}
int s, d, r, t;
void end()
{
    for (std::vector<ant*>::iterator it = enemy.begin();it != enemy.end();it++)
    {
        (*it)->output();
    }
    exit(0);
}
void work()
{
    using std::cin;
    cin >> n >> m >> s >> d >> r;
    mp.init();
    for (int i = 1;i <= s;i++)
    {
        int x, y;
        cin >> x >> y;
        mp(x, y) = 1;
        tower.push_back(nuclear(x, y, d, r));
    }
    cin >> t;
    for (int o = 1;o <= t;o++)//一秒开始了
    {
        if (enemy.size() < 6 && mp(0, 0) != -1)
        {
            enemy.push_back(new ant());//首先出生蚂蚁
        }
        for (int i = 0;i < enemy.size();i++)
        {
            enemy[i]->information();//蚂蚁放信息素
        }
        for (int i = 0;i < enemy.size();i++)
        {
            enemy[i]->action(mp);//蚂蚁移动
        }
        for (std::vector<nuclear>::iterator it = tower.begin();it != tower.end();it++)
        {
            it->action();//二营长，开炮！
        }
        clear();//清除掉死亡蚂蚁的尸体
        mp.decrase();//信息素减1
        for (std::vector<ant*>::iterator it = enemy.begin();it != enemy.end();it++)
        {
            if ((*it)->iscarryingcake() && (*it)->xpos() == 0 && (*it)->ypos() == 0)//蚂蚁方条件达成，游戏结束
            {
                printf("Game over after %u seconds\n%d\n", o, enemy.size());
                end();
            }
        }
        for (std::vector<ant*>::iterator it = enemy.begin();it != enemy.end();it++)
        {
            (*it)->getage()++;//所有蚂蚁年龄+1
        }
    }
    printf("The game is going on\n%d\n", enemy.size());
    end();
}

时空复杂度：不用那么费尽心思去分析，只要知道绝对不会裂开就是了。

假如你面对一个问题改了好久改不出来，建议看看自己是否没注意到某些细节或者对题面的理解有误。同时，建议采用输出调试。

给出调试的代码吧，这里为了方便，就把所有的类成员全设成了 public，所以可以直接调用。

namespace DEBUG//调试的情况下，所有类成员全部设为public
{
    void printmap(int t)//当前地图的信息素
    {
        printf("time:%d\ninformationmap:\n", t);
        map tmp = mp;
        for (std::vector<ant*>::iterator it = enemy.begin();it != enemy.end();it++)
        {
            tmp((*it)->xpos(), (*it)->ypos()) = (*it)->tmpm;
        }
        for (int i = 0;i <= n;i++)
        {
            for (int j = 0;j <= m;j++)
            {
                std::cout << tmp(i, j) << ' ';
            }
            puts("");
        }
        std::cout << "\n-----------------\n-----------------\n";
    }
    void printantpos(int t)//当前蚂蚁的分布情况，序号按照年龄顺序排列。
    {
        printf("time:%d\nantmap:\n", t);
        map tmp;
        tmp.init();
        for (int i = 0;i < enemy.size();i++)
        {
            tmp(enemy[i]->xpos(), enemy[i]->ypos()) = i + 1;
        }
        for (int i = 0;i <= n;i++)
        {
            for (int j = 0;j <= m;j++)
            {
                std::cout << tmp(i, j) << ' ';
            }
            puts("");
        }
        std::cout << "\n-----------------\n-----------------\n";
    }
    void printallants(int t)//所有蚂蚁的详细数据
    {
        printf("time:%d\nmap:\n", t);
        for (std::vector<ant*>::iterator it = enemy.begin();it != enemy.end();it++)
        {
            //tmp((*it)->xpos(), (*it)->ypos()) = (*it)->tmpm;
            printf("id:%d\nlove:%d\nage:%d\nhp:%d\nlstx:%d lsty:%d\n   x:%d    y:%d\niscarryingcake:%d\n-------------------\n",
                (*it)->id + 1, (*it)->love, (*it)->age, (*it)->hp, (*it)->lstx, (*it)->lsty, (*it)->x, (*it)->y, (*it)->iscarryingcake());
        }
        puts("\n----------------------------------------\n");
    }
}

彩蛋：我们记录下了每一只蚂蚁的 LV。LV，也就是 LOVE。但那绝不是 love，而是一个缩写。意思是，暴力指数（level of violence），一种量化你对蚂蚁造成伤害的数值。你杀得越多，这个值就越高，蚂蚁的生命力也就越顽强，干掉一只蚂蚁就越困难，你的计算也就更容易偏离方向，出现错误的结果。

P2586 [ZJOI2008]杀蚂蚁 题解

P2586 [ZJOI2008]杀蚂蚁题解