2 条题解

  • 0
    @ 2025-10-8 17:02:42

    【题解】洛谷 P2586 [ZJOI2008] 杀蚂蚁 [模拟]-CSDN博客

    #include<bits/stdc++.h>
using namespace std;

const int N = 30;
const double eps = 1e-10;

int n, m, s, d, r;
int phe[N][N];
bool v[N][N];

struct Point {
    int x, y;
};

struct Coo {
	double x, y;
};

bool operator==(Point a, Point b) {
    return (a.x == b.x) && (a.y == b.y);
}
 
bool operator!=(Point a, Point b) {
    return !((a.x == b.x) && (a.y == b.y));
}

Point operator+(Point a, Point b) {
    return {a.x + b.x, a.y + b.y};
}
 
Point operator-(Point a, Point b) {
    return {a.x - b.x, a.y - b.y};
}
 
Coo operator*(Point a, double b) {
    return (Coo) {(a.x * b), (a.y * b)};
}
 
double operator*(Point a, Point b) { // 点积
    return 1.0 * a.x * b.x + 1.0 * a.y * b.y;
}
 
double calc_len(Point a, Point b) {
    return sqrt(1.0 * (a.x - b.x) * (a.x - b.x) + 1.0 * (a.y - b.y) * (a.y - b.y));
}

double calc_len(Point a, Coo b) {
    return sqrt(1.0 * (a.x - b.x) * (a.x - b.x) + 1.0 * (a.y - b.y) * (a.y - b.y));
}

bool judge_int(Point p, Point a, Point b) {     // 圆心点 p 的圆和线段 ab 是否有交点
    // 计算线段向量
    Point ab = b - a;
    // 计算 ap 向量
    Point ap = p - a;

    // 计算 t = (ap · ab) / |ab|^2
    double t_numer = ap * ab; // 点积
    double t_denom = ab * ab; // |ab|^2

    if (t_denom < eps) { // 线段退化为点
        return calc_len(p, a) <= 0.5 + eps;
    }

    double t = t_numer / t_denom;

    if (t < 0.0 - eps) { // p 在 a 点一侧
        return calc_len(p, a) <= 0.5 + eps;
    }
    else if (t > 1.0 + eps) { // p 在 b 点一侧
        return calc_len(p, b) <= 0.5 + eps;
    }
    else { // p 在线段 a, b 的垂足附近
        // 计算垂足 q
        Coo q = (Coo){a.x + (t * ab.x), a.y + (t * ab.y)};
        return calc_len(p, q) <= 0.5 + eps;
    }
}

Point f_dr[4] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
bool can_reach(const Point &);

struct Ant {
    Point from, pos;     // �上一位置，当前位置
    int age, lev;   // 年龄，等级
    double blo;       // 当前血量
    bool cake;           // 是否扛蛋糕，是为 1
	
    Ant (int k) : 
        age(0), lev(k), blo(4 * pow(1.1, k)),
        from({-1, -1}), pos({0, 0}), cake(0)
    {}
	
    void ant_move() {
        phe[pos.x][pos.y] += (cake? 5 : 2);
        int dir = -1;
        int max_p = -1;
        for (int i = 0; i <= 3; i ++) {
            Point n_pos = pos + f_dr[i];
            if (can_reach(n_pos) && (n_pos != from)) {
                if ( phe[n_pos.x][n_pos.y] > max_p ) {
                    max_p = phe[n_pos.x][n_pos.y];
                    dir = i;
                }
            }
        }
		
        if ( ((age + 1) % 5 == 0) && dir != -1) {
            for (int i = 0; i <= 3; i ++) {
                dir = (dir - 1 + 4) % 4;
                Point n_pos = pos + f_dr[dir];
                if (can_reach(n_pos) && (n_pos != from)) {
                    break;
                }
            }
        }
		
        from = pos;
        if (dir != -1) {
            pos = pos + f_dr[dir];
        }
    }
};

list<Ant> ant;

bool can_reach(const Point &x) {
    // 修正：Point 为 int，检查边界
    if (x.x < 0 || x.x > n || x.y < 0 || x.y > m) return False;
    if (v[x.x][x.y]) return False; // 有炮塔
    for (auto &i: ant) if (i.pos == x) { // 有蚂蚁
        return False; 
    }
    return True;
}

Point nearest_ant(Point a) {
    if (ant.empty()) return {-1, -1}; // 如果没有蚂蚁，返回无效点
    Point res = ant.front().pos;
    for (auto &i : ant) {
        if (calc_len(i.pos, a) < calc_len(res, a)) {
            res = i.pos; 
        }
    }
    return res;
}

// 修正：变量名和结构体成员名一致
int Cake = 0; // 全局变量，蛋糕是否被拿走

struct Gun {
    Point pos;
    void kill_ant(Point a) {
        if (a == (Point){-1, -1}) {
            return ;
        }
        // 修正：在迭代器删除元素时需要小心
        for (auto it = ant.begin(); it != ant.end();) {
            if (judge_int(it->pos, pos, a)) {
                it->blo -= d;
                if (it->blo < 0) {
                    if (it->cake) {
                        Cake = 0; // 修正：变量名
                    }
                    it = ant.erase(it); // erase 返回下一个有效迭代器
                    continue; // 跳过 it++，因为 it 已经指向下一个元素
                }
            }
            ++it; // 只有当元素未被删除时才递增迭代器
        }
    }
	
    Point lck; // 炮塔当前锁定的目标坐标

    void lock() {
        // 1. 优先锁定扛蛋糕的蚂蚁
        if (Cake) { 
            for (auto &i : ant) {
                if (i.cake && calc_len(i.pos, pos) <= r + eps) { // 修正：函数调用，增加 eps
                    lck = i.pos; 
                    return; 
                }	
            }
        }

        // 2. 寻找最近的非蛋糕蚂蚁
        Point p = nearest_ant(pos); 
        if (p.x != -1 && p.y != -1 && calc_len(p, pos) <= r + eps) { // 检查 nearest_ant 是否返回有效点
            lck = p;
            return;
        }

        // 3. 没有目标
        lck = {-1, -1};   
    }
} gt[N];

int sum;      // 全局变量，总出生蚂蚁数
bool flag = 0;   // 全局变量，游戏是否结束

void round() {
    // 1. 尝试出生新蚂蚁 
    if (ant.size() < 6) {
        bool canb = 1;
        for (auto &i : ant) if (i.pos == (Point){0, 0}){
            canb = 0;
            break;
        }
        if (canb) {
            // 添加新蚂蚁，等级根据蚂蚁总数 sum 计算
            ant.push_back(Ant(sum / 6 + 1));
            sum ++; // 增加总出生数
        }
    }
    	
    // 2. 所有蚂蚁移动
    for (auto &i : ant) {
        i.ant_move();
    }
	
    // 3. 检查是否拾取蛋糕
    for (auto &i : ant) {
        if (i.pos.x == n && i.pos.y == m && !Cake) {
            i.cake = 1;
            Cake = 1;
            // 修正: pow 的参数改为 double，使用 floor 获取整数部分
            double base_hp = 4 * pow(1.1, i.lev);
            i.blo = min(base_hp, i.blo + floor(base_hp / 2.0));
        }
    } 
	
    // 4. 炮塔锁定目标
    for (int i = 1; i <= s; i ++) {
        gt[i].lock();
    }
    // 5. 炮塔攻击
    for (int i = 1; i <= s; i ++) {
        gt[i].kill_ant(gt[i].lck);
    }
	
    // 6. 检查胜利条件
    for (auto &i : ant) {
        if (i.cake && i.pos.x == 0 && i.pos.y == 0) { 
            flag = 1;
            return ;
        }
    }
	
    // 7. 信息素衰减
    for (int i = 0; i <= n; i ++) {
        for (int j = 0; j <= m; j ++) if (phe[i][j] > 0) {
            phe[i][j] --;
        }
    }
    // 8. 年龄增加
    for (auto &i : ant) {
        i.age ++;
    }
}

int main () {
    ios::sync_with_stdio(False);
    cin.tie(0); 

    cin >> n >> m >> s >> d >> r; 

    for (int i = 1; i <= s; i++) {
        cin >> gt[i].pos.x >> gt[i].pos.y;
        v[gt[i].pos.x][gt[i].pos.y] = 1; 
    }

    int T; cin >> T; 

	sum = 0;
    for (int t = 1; t <= T; t++) { 
        flag = 0;                  // 每轮开始重置 flag
        round();                // 执行一轮模拟
        if (flag) { 
            cout << "Game over after " << t << " seconds\n";
            break; 
        }
    }

    if (!flag) {
        cout << "The game is going on\n"; 
    }

    cout << ant.size() << '\n';

    for (const auto &i : ant) {
        cout << i.age << " " << i.lev << " " << 
        (int)i.blo << " " << i.pos.x << " " << i.pos.y << "\n";
    }

    return 0;
}
    • 0
      @ 2025-10-8 17:02:09

      【题解】洛谷 P2586 [ZJOI2008] 杀蚂蚁 [模拟]-CSDN博客

      #include<bits/stdc++.h>
using namespace std;

      const int N = 30;
const double eps = 1e-10;
      

      int n, m, s, d, r;
int phe[N][N];
bool v[N][N];
      

      struct Point {
int x, y;
};
      

      struct Coo {
double x, y;
};
      

      bool operator==(Point a, Point b) {
return (a.x == b.x) && (a.y == b.y);
}
      

      bool operator!=(Point a, Point b) {
return !( (a.x == b.x) && (a.y == b.y) );
}
      

      Point operator+(Point a, Point b) {
return {a.x + b.x, a.y + b.y};
}
      

      Point operator-(Point a, Point b) {
return {a.x - b.x, a.y - b.y};
}
      

      Coo operator*(Point a, double b) {
return (Coo) {(a.x * b), (a.y * b)};
}
      

      double operator*(Point a, Point b) { // 点积
return 1.0 * a.x * b.x + 1.0 * a.y * b.y;
}
      

      double calc_len(Point a, Point b) {
return sqrt(1.0 * (a.x - b.x) * (a.x - b.x) + 1.0 * (a.y - b.y) * (a.y - b.y));
}
      

      double calc_len(Point a, Coo b) {
return sqrt(1.0 * (a.x - b.x) * (a.x - b.x) + 1.0 * (a.y - b.y) * (a.y - b.y));
}
      

      bool judge_int(Point p, Point a, Point b) {     // 圆心点 p 的圆和线段 ab 是否有交点
// 计算线段向量
Point ab = b - a;
// 计算 ap 向量
Point ap = p - a;
      

      // 计算 t = (ap · ab) / |ab|^2
double t_numer = ap * ab; // 点积
double t_denom = ab * ab; // |ab|^2

if (t_denom &lt; eps) { // 线段退化为点
    return calc_len(p, a) &lt;= 0.5 + eps;
}

double t = t_numer / t_denom;

if (t &lt; 0.0 - eps) { // p 在 a 点一侧
    return calc_len(p, a) &lt;= 0.5 + eps;
}
else if (t &gt; 1.0 + eps) { // p 在 b 点一侧
    return calc_len(p, b) &lt;= 0.5 + eps;
}
else { // p 在线段 a, b 的垂足附近
    // 计算垂足 q
    Coo q = (Coo){a.x + (t * ab.x), a.y + (t * ab.y)};
    return calc_len(p, q) &lt;= 0.5 + eps;
}

      

      }
      

      Point f_dr[4] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
bool can_reach(const Point &);
      

      struct Ant {
Point from, pos;     // 上一位置，当前位置
int age, lev;   // 年龄，等级
double blo;       // 当前血量
bool cake;           // 是否扛蛋糕，是为 1
      

      Ant (int k) : 
    age(0), lev(k), blo(4 * pow(1.1, k)),
    from({-1, -1}), pos({0, 0}), cake(0)
{}

void ant_move() {
    phe[pos.x][pos.y] += (cake? 5 : 2);
    int dir = -1;
    int max_p = -1;
    for (int i = 0; i &lt;= 3; i ++) {
        Point n_pos = pos + f_dr[i];
        if (can_reach(n_pos) &amp;&amp; (n_pos != from)) {
            if ( phe[n_pos.x][n_pos.y] &gt; max_p ) {
                max_p = phe[n_pos.x][n_pos.y];
                dir = i;
            }
        }
    }
	
    if ( ((age + 1) % 5 == 0) &amp;&amp; dir != -1) {
        for (int i = 0; i &lt;= 3; i ++) {
            dir = (dir - 1 + 4) % 4;
            Point n_pos = pos + f_dr[dir];
            if (can_reach(n_pos) &amp;&amp; (n_pos != from)) {
                break;
            }
        }
    }
	
    from = pos;
    if (dir != -1) {
        pos = pos + f_dr[dir];
    }
}

      

      };
      

      list<Ant> ant;
      

      bool can_reach(const Point &x) {
// 修正：Point 为 int，检查边界
if (x.x < 0 || x.x > n || x.y < 0 || x.y > m) return False;
if (v[x.x][x.y]) return False; // 有炮塔
for (auto &i: ant) if (i.pos == x) { // 有蚂蚁
return False;
}
return True;
}
      

      Point nearest_ant(Point a) {
if (ant.empty()) return {-1, -1}; // 如果没有蚂蚁，返回无效点
Point res = ant.front().pos;
for (auto &i : ant) {
if (calc_len(i.pos, a) < calc_len(res, a)) {
res = i.pos;
}
}
return res;
}
      

      // 修正：变量名和结构体成员名一致
int Cake = 0; // 全局变量，蛋糕是否被拿走
      

      struct Gun {
Point pos;
      

      void kill_ant(Point a) {
    if (a == (Point){-1, -1}) {
        return ;
    }
    // 修正：在迭代器删除元素时需要小心
    for (auto it = ant.begin(); it != ant.end();) {
        if (judge_int(it-&gt;pos, pos, a)) {
            it-&gt;blo -= d;
            if (it-&gt;blo &lt; 0) {
                if (it-&gt;cake) {
                    Cake = 0; // 修正：变量名
                }
                it = ant.erase(it); // erase 返回下一个有效迭代器
                continue; // 跳过 it++，因为 it 已经指向下一个元素
            }
        }
        ++it; // 只有当元素未被删除时才递增迭代器
    }
}

Point lck; // 炮塔当前锁定的目标坐标

void lock() {
    // 1. 优先锁定扛蛋糕的蚂蚁
    if (Cake) { 
        for (auto &amp;i : ant) {
            if (i.cake &amp;&amp; calc_len(i.pos, pos) &lt;= r + eps) { // 修正：函数调用，增加 eps
                lck = i.pos; 
                return; 
            }
        }
    }

    // 2. 寻找最近的非蛋糕蚂蚁
    Point p = nearest_ant(pos); 
    if (p.x != -1 &amp;&amp; p.y != -1 &amp;&amp; calc_len(p, pos) &lt;= r + eps) { // 检查 nearest_ant 是否返回有效点
        lck = p;
        return;
    }

    // 3. 没有目标
    lck = {-1, -1};   
}

      

      } gt[N];
      

      int sum;      // 全局变量，总出生蚂蚁数
bool flag = 0;   // 全局变量，游戏是否结束
      

      void round() {
// 1. 尝试出生新蚂蚁
if (ant.size() < 6) {
bool canb = 1;
for (auto &i : ant) if (i.pos == (Point){0, 0}){
canb = 0;
break;
}
if (canb) {
// 添加新蚂蚁，等级根据蚂蚁总数 sum 计算
ant.push_back(Ant(sum / 6 + 1));
sum ++; // 增加总出生数
}
}
      

      // 2. 所有蚂蚁移动
for (auto &amp;i : ant) {
    i.ant_move();
}

// 3. 检查是否拾取蛋糕
for (auto &amp;i : ant) {
    if (i.pos.x == n &amp;&amp; i.pos.y == m &amp;&amp; !Cake) {
        i.cake = 1;
        Cake = 1;
        // 修正：pow 的参数改为 double，使用 floor 获取整数部分
        double base_hp = 4 * pow(1.1, i.lev);
        i.blo = min(base_hp, i.blo + floor(base_hp / 2.0));
    }
} 

// 4. 炮塔锁定目标
for (int i = 1; i &lt;= s; i ++) {
    gt[i].lock();
}
// 5. 炮塔攻击
for (int i = 1; i &lt;= s; i ++) {
    gt[i].kill_ant(gt[i].lck);
}

// 6. 检查胜利条件
for (auto &amp;i : ant) {
    if (i.cake &amp;&amp; i.pos.x == 0 &amp;&amp; i.pos.y == 0) { 
        flag = 1;
        return ;
    }
}

// 7. 信息素衰减
for (int i = 0; i &lt;= n; i ++) {
    for (int j = 0; j &lt;= m; j ++) if (phe[i][j] &gt; 0) {
        phe[i][j] --;
    }
}
// 8. 年龄增加
for (auto &amp;i : ant) {
    i.age ++;
}

      

      }
      

      int main () {
ios::sync_with_stdio(False);
cin.tie(0);
      

      cin &gt;&gt; n &gt;&gt; m &gt;&gt; s &gt;&gt; d &gt;&gt; r; 

for (int i = 1; i &lt;= s; i++) {
    cin &gt;&gt; gt[i].pos.x &gt;&gt; gt[i].pos.y;
    v[gt[i].pos.x][gt[i].pos.y] = 1; 
}

int T; cin &gt;&gt; T; 

sum = 0;
for (int t = 1; t &lt;= T; t++) { 
    flag = 0;                  // 每轮开始重置 flag
    round();
    if (flag) { 
        cout &lt;&lt; "Game over after " &lt;&lt; t &lt;&lt; " seconds\n";
        break; 
    }
}

if (!flag) {
    cout &lt;&lt; "The game is going on\n"; 
}

cout &lt;&lt; ant.size() &lt;&lt; '\n';

for (const auto &amp;i : ant) {
    cout &lt;&lt; i.age &lt;&lt; " " &lt;&lt; i.lev &lt;&lt; " " &lt;&lt; 
    (int)i.blo &lt;&lt; " " &lt;&lt; i.pos.x &lt;&lt; " " &lt;&lt; i.pos.y &lt;&lt; "\n";
}

return 0;

      

      }

      </p>
      • 1

      [ZJOI2008] 杀蚂蚁

      信息

      ID
      2686
      时间
      2500ms
      内存
      512MiB
      难度
      7
      标签
      递交数
      29
      已通过
      7
      上传者
      1. Language
      2. 兼容模式
      3. 主题
      3. Worker 0, 13ms
      4. Powered by Hydro v5.0.1 Community