题解：P13462 [GCJ 2008 #1B] Mousetrap

· · 题解

题目传送门

本文同步发表于博客园

:::info[前情提要] 依旧是树状数组的代码量比线段树少，所以本蒟蒻在这里提供一种树状数组的写法。 :::

正文

那么废话不多说，让我们速速做题。

题目分析

这道题的题目要求是从牌堆里取牌。

先看看是怎么取牌的：每次从牌堆中从上往下计数，第一张计数与牌面数字相同的牌就将它从牌堆中取出来，放在一边，此时这张牌上面的所有牌放进牌堆底部，计数器归零。同时，这里还要注意的是若本轮没有找到符合的牌就从最上面再次开始找牌，计数器不归零。

转换思路

我们不妨来换一种思路，牌堆不变，将它视为一个数列，每次找牌只是移动我们的指针，每次开始从上一个指针位置往后找，跳到末尾的时候就返回数列开头。

由于我们要递增的取牌，所以我们可以想象为从 1 开始到 k 结束的数字依次按照上文的方式放进空位中，当前数字如果为 i，且上一个数字放在了 r 位置，那么这个数字 i 就需要放在从 r 开始往后找到的第 i 个空位。

考虑到每次都会有循环，所以我们令 r 之前的空位的个数为 pref，现在剩下的空位个数为 now。我们现在要找的空位为第 j 个。那么就有以下的式子。

j = \begin{cases} pref + i & i + pref \le now \\ ((i - now + pref + 1)\mod now) +1 & i + pref > now \end{cases}

有了如上的式子就很好解决了，每次在树状数组中二分查找第一个空位数量等于 j 的位置，将这个位置放入数字 i，直到所有数字放完后输出所需要的位置里放牌的数字就行了。

时间复杂度严格小于 O(k \log^2 k)。对于本题一定能跑过。

AC code

:::success[AC code]

#include<bits/stdc++.h>
#define lx (x & (-x))
using namespace std;
const int N = 1e6 + 5;
int T, k, n, d[105], ans[N], tr[N], l, r, cnt;

void add(int x, int y){
    for(; x <= k;x += lx)
        tr[x] += y;
}

int query(int x){
    int sum = 0;
    for(; x > 0;x -= lx)
        sum += tr[x];
    return sum;
}                       //树状数组基本操作

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

    cin >> T;
    for(int j = 1;j <= T;j ++){
        cin >> k >> n;
        for(int i = 1;i <= n;i ++)
            cin >> d[i];
        ans[0] = 0;
        for(int i = 1;i <= k;i ++)
            add(i, 1);
        l = 0, r = 0; //注意 r 的初始值为 0，因为我们要找的 pref 与上一个 r 有关，所以此时的 r 赋值为 0，保证 pref 最初的值为 0
        for(int i = 1;i <= k;i ++){
            int now = query(k), pref = query(r);
            l = 0, r = k + 1;

            if(now - pref < i) cnt = (i - now + pref - 1) % now + 1;
            else cnt = pref + i;  //这里的 cnt 等同于上文所说的 j

            while(l + 1 < r){       //二分查找第一个空位数量为 cnt 的位置
                int mid = (l + r) >> 1;
                if(query(mid) >= cnt) r = mid;
                else l = mid;
            }

            ans[r] = i;
            add(r, -1);
        }

        cout << "Case #" << j << ": ";
        for(int i = 1;i <= n;i ++)
            cout << ans[d[i]] << " ";    //简单的输出

        cout << "\n";
    }
    return 0;
}

:::

完结，撒花✿✿ヽ(°▽°)ノ✿。