Codeforces 652F 解题报告

题意

有n只蚂蚁在长度为m个格子的环上,环上的格子以逆时针编号,每只蚂蚁每秒往它面向的方向移动一格。如果有两只蚂蚁相撞则相互调换方向,问t秒后每只蚂蚁的位置。

题解

首先通过观察可以发现

  • 蚂蚁相撞产生的轨迹可以看成两只蚂蚁穿过对方
  • 由于相撞后只会互相调换方向,每只蚂蚁的相对编号不会发生变化,即每只蚂蚁的“邻居”不会发生变化

也就是说:

  • 我可以通过计算每只蚂蚁毫无阻碍产生的轨迹知道t秒后哪些位置上有蚂蚁
  • 又由于每只蚂蚁的相对编号不变,我只要知道某只蚂蚁t秒后的位置就可以推算出剩下的所有蚂蚁的位置

现在的问题就由第一个问题转换成第二个问题:

  • t秒后第x个蚂蚁的位置是哪
  • t秒后第x个位置的蚂蚁编号是多少

对于第二个问题,我们只要求出t秒后蚂蚁按位置编号大小排序的序列就可以算出答案。假设一开始蚂蚁按初始位置编号的大小顺序排好,位置0(位置1与位置m的中间)是一个临界点,考虑两种情况来求出t秒后蚂蚁的顺序:

  • t秒内所有蚂蚁没有发生碰撞:当有蚂蚁从1经过0走到m时,那么这只蚂蚁就会变成最后一只蚂蚁,第二只蚂蚁会变成第一只,以此类推。同理,当有蚂蚁从m经过0走到1时,这只蚂蚁就会变成第一只蚂蚁。因此我们只要计算t秒内蚂蚁有多少次从右至左走过0点或从左至右走过0点,求差就可以得到蚂蚁在t秒后的顺序。

  • t秒内有蚂蚁发生碰撞:如果有蚂蚁发生碰撞,因为蚂蚁的轨迹可以看成穿过对方,因此我们还是可以忽略掉碰撞的情况去计算蚂蚁从两个方向通过0点的次数,就当成上面那种情况。每从右向左通过0点一次,蚂蚁的排列序列就左移一次,向右同理。

举个例子,假如一开始蚂蚁编号的排列顺序为[1,3,2],在某一秒2从m点通过了0点到1点,序列变成[2,1,3]。假如2与1发生碰撞,2再次反向通过0点,排列顺序又变回[1,3,2]。看上去好像要判断蚂蚁2从不同方向经过了0点,但是我们完全可以忽略碰撞看成蚂蚁2从左边经过了一次0点和蚂蚁1从右边经过了一次0点,对于复杂的情况也完全适应。

此时我们已知:

  • t秒后那些位置上有蚂蚁
  • t秒后蚂蚁按位置的排序

我们就可以直接一一对应上蚂蚁的位置了

#include<bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i=(a); i<(b); i++)
#define per(i, a, b) for(int i=(a-1); i>=(b); i--)
typedef long long ll;
const int maxn = 300005;
const int inf = 0x3f3f3f3f;
struct A {
    ll pos;
    char f;
    bool operator<(const A &x) const {
        return pos < x.pos;
    }
}a[maxn];
int id[maxn], ans[maxn];
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    ll n, m, t;
    cin >> n >> m >> t;
    int offset = 0;
    rep(i, 0, n) {
        id[i] = i;
        cin >> a[i].pos >> a[i].f;
        a[i].pos--;
    }
    //排序得到蚂蚁的初始排列
    sort(id, id + n, [&](int x, int y) { return a[x].pos < a[y].pos; });
    //计算蚂蚁t秒后的排列,顺便算出t秒后哪些位置出现了蚂蚁
    rep(i, 0, n) {
        if (a[i].f == 'L') {
            offset = (offset + (a[i].pos - t - m + 1) / m) % n;
            a[i].pos = ((a[i].pos - t)%m + m) % m;
        }
        else {
            offset = (offset + (a[i].pos + t) / m) % n;
            a[i].pos = (a[i].pos + t) % m;
        }
    }
    offset = (offset + n) % n;
    //对位置排序
    sort(a, a + n);
    //此时初始次序为i编号为id[x]的蚂蚁在t秒后变成了次序为(i+offset)%n的蚂蚁
    rep(i, 0, n) ans[id[i]] = a[(i + offset)%n].pos + 1;
    rep(i, 0, n) cout << ans[i] << ' ';
    return 0;
}
相关文章
相关标签/搜索