P11463 题解

copper_ingot · 2024-12-25 13:11:43 · 题解

题目传送门

首先传球 k 次相当于传球 (k \bmod 2n) 次，其他题解讲得很清楚了，这里就不证明了。

然后观察数据范围，发现 O(Tn) 的时间可以过。

想到要用一个可以 O(1) 时间删除和插入元素，并且可以 O(1) 时间维护正中间数的数据结构，就是链表。

我们建一个双向链表，维护 head,tail,mid 三个指针，mid 为中间的元素，即本轮持球的人。

每次先判断方向，如果这次传球是向右传的，就把 mid 断开并接到 tail 后面，接着更新 tail 为 mid，mid 变为下一个元素。如果向左传则反之，mid 要变为上一个元素。

最后从头输出每个元素即可。

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
int t, n, x, k, pre[200001], nex[200001], mid, head, tail;
signed main(){
    scanf("%lld", &t);
    while (t--){
        scanf("%lld%lld%lld", &n, &x, &k); k %= n * 2;
        for (int i = 2; i < n; i++) pre[i] = i - 1, nex[i] = i + 1;
        pre[1] = -1, nex[1] = 2, head = 1;
        pre[n] = n - 1, nex[n] = -1, tail = n;
        mid = (n + 1) / 2;
        for (int i = 1; i <= k; i++){
            if (i % 2 == x){
                nex[pre[mid]] = nex[mid], pre[nex[mid]] = pre[mid];
                nex[tail] = mid, pre[mid] = tail;
                tail = mid; mid = nex[mid];
                nex[tail] = -1;
            }
            else{
                nex[pre[mid]] = nex[mid], pre[nex[mid]] = pre[mid];
                pre[head] = mid, nex[mid] = head;
                head = mid; mid = pre[mid];
                pre[head] = -1;
            }
        }
        int tmp = head;
        while (tmp != -1){printf("%lld ", tmp); tmp = nex[tmp];}
        puts("");
    }
    return 0;
}