[数据结构与算法]codeforces做题记录（Twist the Permutation）（DIV3 D）

codeforces做题记录

这个系列将是我在codeforces上遇到的好题分享。
在刷codeforces的过程中遇到的有趣的题目，我都会尽量写在这个专栏的，希望大家可以订阅我这个专栏。
今天分享的是Codeforces Round #776 (Div. 3)的D题

看原题请点击我

简单翻译：

给一个包含n个元素的数组，是[ 1, 2, 3, 4, 5, …, n ]，可以做n次操作，第 i 次操作可以将前 i 个元素循环右移任意个位置，循环右移看我

问题：给你一个目标数组，问，在第 i 次操作中需要对元素循环右移多少位。输出第 i 次需要循环右移的次数。

思路：

我们使用逆向思维，反过来想这个问题。

第 i 次的变化是不会影响到 i + 1及以上的数字的，所以数字n一定是最后一次变化从n号的位置一次变化到所给的数组的位置。这样就可以确定最后一位循环右移了多少位。

确定了最后一位移动了多少位，我们将状态还原为最后一位移动之前，再看倒数第二位，和最后一位的思路是一样的。

通过一个循环即可求得答案，当然中间在转换的过程中涉及到一些细节，取模的时候需要注意，每次进行转换的时候，模都会减去1。这样通过倒叙就可以把得到这个数组所需要进行的次数依次输出出来了。

c++代码：

#include"bits/stdc++.h"
#define all(x) x.begin(),x.end()
#define len(x) x.size()
#define INF (1e9)
#define vi vector<int>
#define ll long long
#define db double
using namespace std;
void solve() {
    int n;
    cin >> n;
    vi a(n);
    vi b(n + 1);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        b[a[i]] = i;
    }
    vi re(n);
    int t = 0;
    for (int i = n; i > 0; i--) {
        int s = b[i];
        re[i - 1] = (s + 1) % i; 
        for (int j = 1; j <= i; j++) {
            b[j] = (b[j]- 1- s + i) % i;
        }
    }
    for (int i = 0; i < n; i++) {
        cout << re[i] << " ";
    }
    cout << endl;
}
int main(){
    int n;
    cin >> n;
    while(n--) {
        solve();
    }
 
    return 0;
}