题解：P8910 [RC-06] Operation Sequence

· · 题解

写在前面

::::warning[warning] 不要抄题解！ ::::

认为是一道好题，特地来写写题解以回报自己一小时的战果。

思路

做完这道题，看了看楼下两篇题解，感觉我的代码像是两篇题解综合起来。

首先，看到这道题，首先想到的是部分分（是因为我太弱了）。

但是部分分没有啊！那就只好骗分，注意到 k=0 或 k = n 的时候答案一定是 0，于是特判一下。

但是我也不知道多少分。因为接下来我想到了正解。

接下来来思考正解。

手搓自己造的样例，发现这个 a_{n+1} 非常重要，可以用来当临时使用。

那么，我们让任意一个数赋值到 n+1，不妨设为 1，令一个指针 p，初始指向 1，代表当前可以赋值为目标的地方。

那我们就可以不断地让当前数赋值为应该目标数，然后让 p 指向目标数所在的下标。

但是，在手搓了自己又造了的几组略大的数据之后，发现好像会有一些问题诶。

可能会出现多个环，而不是理想状态下的 p 指针一直移动最终全部赋值成目标值。

那么每次在发现环的时候就可以让 p 指针随便指向一个地方就可以了，我这里让 p 指针直接指向下一个地方。

代码实现 & 细节

首先，判断是否形成环。只需要存一个 begin 指针，表示一个环的开头，一开始 begin 指向 1，以后每次发现 p = begin 的时候就形成了环，这是 p 指针会指向下一个地方，而我们让 begin 指向 p 即可。

其次，形成环时需要实现的步骤：

  1. 让当前 a_p 赋值为 a_{n + 1} 因为 a_{n+1} 存储了 a_{begin} 原本的值。
  2. 移动 p 指针，更新 begin 指针。
  3. 让 a_{n+1} 赋值为 a_p 这样才可以在下次发现形成环的时候正确的赋值。

这一部分的注意点是在第 3 步中，需要判断是不是还有需要修改的地方。可能不用，因为 a_{n+1} 最终赋值什么值都可以。但是我懒没有尝试可不可以。

其他注意事项和小技巧：

  1. 前面所说的骗分同时也是特判记得加上。
  2. 可以直接用 vector 来存储答案，不需要楼下的 n + \gcd(n,k)。（当然我只是偷懒而已） 顺便吐槽：楼下怎么还把加法打成了乘法啊……

代码 & 代码解释

::::success[code]

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;

int t, n, k, to[N];

int gcd(int a, int b){
    return (!b ? a : gcd(b, a % b));
}

int main(){
    cin >> t;
    while (t -- ){
        cin >> n >> k;
        if (k == 0 || k == n){
            cout << "0\n";
            continue;
        }

        for (int i = 1; i <= n; i ++ ) to[i] = (i <= k ? n - k + i : i - k);

        vector <pair<int, int> > res;

        res.push_back({n + 1, 1});
        int now = 1, beg = 1, cnt = 0;
        while (cnt < n){
            if (to[now] != beg){
                res.push_back({now, to[now]});
                now = to[now];
            }
            else{
                res.push_back({now, n + 1});
                beg = now = now % n + 1;
                if (cnt != n - 1) res.push_back({n + 1, now});
            }
            cnt ++;
        }

        cout << res.size() << "\n";
        for (auto [i, j] : res) cout << i << " " << j << "\n";
    }
}

::::

代码解释：

  1. 代码中的 now 为文中的 p。
  2. 代码中的 beg 为文中的 begin。
  3. 代码中的 res 为文中小技巧部分所提到的记录答案的 vector。
  4. 代码中的 to 为存储目标值的数组。