擂台赛

题目描述

$[0,L]$ 上 $N$ 只速度为 1 的蚂蚁（位置 $p_i$ 、方向 R/L）相遇即反向，走出 $[0,L]$ 跌落（恰在端点不算）。求 $T$ 秒后每只蚂蚁状态：跌落输出 Down，同位置输出 位置 Same，否则 位置方向。

思路

碰撞掉头等价于蚂蚁互穿并交换编号，故直走 $T$ 秒的位置集合即真实终态位置集合；同速下蚂蚁相对顺序不变，按初始排名与直走位置排序一一对应，回填各输入编号即可判断 Down/Same/方向。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-02 19:36
# update_at: 2026-10-02 19:36

import sys


def solve() -> None:
    it = iter(sys.stdin.buffer.read().split())
    L, T, n = int(next(it)), int(next(it)), int(next(it))

    ants = [(int(next(it)), next(it) == b"R") for _ in range(n)]  # (位置, 是否向右)，输入顺序

    # 碰撞瞬间掉头等价于互换身份：终态（位置+方向）的多重集合就是各自直走 T 秒的结果，
    # 且按初始位置排第 r 的蚂蚁领走按终态位置排第 r 个状态。
    final = sorted((pos + (T if right else -T), right) for pos, right in ants)
    order = sorted(range(n), key=lambda i: ants[i][0])  # 初始位置排名 → 蚂蚁编号

    cnt: dict[int, int] = {}
    for pos, _ in final:  # 终点位置计数，出现两次以上 → Same
        cnt[pos] = cnt.get(pos, 0) + 1

    out: list[str] = [""] * n
    for r, i in enumerate(order):  # 排名 r 的蚂蚁拿走终态 r，汇报时按编号归位
        pos, right = final[r]
        out[i] = (
            "Down"
            if pos < 0 or pos > L
            else f"{pos} Same"
            if cnt[pos] > 1
            else f"{pos} {'R' if right else 'L'}"
        )
    print("\n".join(out))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 02:18
 * update_at: 2026-10-06 02:18
 */
#include <iostream>
#include <algorithm>
using namespace std;

typedef long long ll;

const int MAXN = 10005;

struct Ant {
    ll pos;   // 初始位置
    bool right; // true 为 R，false 为 L
} a[MAXN]; // 按输入顺序

struct State {
    ll pos;   // 直走 T 秒后的位置
    bool right; // 该轨迹自带方向
} final_state[MAXN];

int order[MAXN]; // 初始位置第 r 名对应的输入编号
int cnt_pos[MAXN]; // 计数辅助，按排名对应 final_state 的位置
ll pos_list[MAXN]; // 提取位置用于计数

int n;
ll L, T;

bool cmp_order(int x, int y) {
    return a[x].pos < a[y].pos;
}

bool cmp_state(const State &x, const State &y) {
    return x.pos < y.pos;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> L >> T >> n;
    for (int i = 0; i < n; i++) {
        char ch;
        cin >> a[i].pos >> ch;
        a[i].right = (ch == 'R');
    }

    // 计算每只蚂蚁直走 T 秒的轨迹（碰撞掉头等价于互换身份）
    for (int i = 0; i < n; i++) {
        final_state[i].pos = a[i].pos + (a[i].right ? T : -T);
        final_state[i].right = a[i].right;
    }

    // 按初始位置排序得到排名 → 编号的映射
    for (int i = 0; i < n; i++) order[i] = i;
    sort(order, order + n, cmp_order);

    // 按终态位置排序
    sort(final_state, final_state + n, cmp_state);

    // 统计终态位置出现次数，判断 Same
    for (int i = 0; i < n; i++) pos_list[i] = final_state[i].pos;
    for (int i = 0; i < n; i++) {
        cnt_pos[i] = 1;
        if (i > 0 && pos_list[i] == pos_list[i - 1]) cnt_pos[i] = cnt_pos[i - 1] + 1;
    }
    for (int i = n - 2; i >= 0; i--) {
        if (pos_list[i] == pos_list[i + 1]) cnt_pos[i] = cnt_pos[i + 1];
    }

    // 按输入编号顺序输出：先按排名填入结果，再按编号顺序打印
    string out[MAXN];
    for (int r = 0; r < n; r++) {
        int idx = order[r];
        ll p = final_state[r].pos;
        bool right = final_state[r].right;
        if (p < 0 || p > L) {
            out[idx] = "Down";
        } else if (cnt_pos[r] > 1) {
            out[idx] = to_string(p) + " Same";
        } else {
            out[idx] = to_string(p) + " " + (right ? "R" : "L");
        }
    }
    for (int i = 0; i < n; i++) {
        cout << out[i] << "\n";
    }

    return 0;
}

目录

题目描述

思路

参考代码