cf1553E. Permutation Shift

題意：

給出一個1到n的排列，每次可以交換兩個數，問在交換最多m次(m <= n/3)之后能不能得到由1 2 3 … n循環右移所得到的的排列，輸出所有能得到的排列和循環右移的次數。
數據范圍：n <= 3e5

題解：

如何求每次置換操作后的數組？
每次置換操作k相當于b[i]=（i-k+n）%n

我們逆向考慮，對于每次移動k，來判斷是否可以通過最多m次操作回到原本排列(原本1到n的排列)。
我們最終的目的是想要n個自環。假設當前b中有t個環，每次交換都可以使得自環的個數+1，所以至少需要n-t次交換才可以達到目的，也就是如果m>=n-t即k符合要求

顯然每次檢測都是O(n)的，我們不可能對每個K都檢測一遍，總復雜度就是O(n^2)
最多可以交換m次，那么最多就會影響到2 * m個環，也就是初始就最少有n-2 * m個環才行。
我們設num[i]表示偏移量為i時的自環個數
num[i]要>=n-2m
Σnum[i]=n，m<=n/3,
所以num[i]>=n/3,說明這樣的k最多有3個
所以最多三次O(n)計算最小交換次數
總復雜度O(n)

代碼：

// Problem: E. Permutation Shift // Contest: Codeforces - Harbour.Space Scholarship Contest 2021-2022 (open for everyone, rated, Div. 1 + Div. 2) // URL: https://codeforces.com/contest/1553/problem/E // Memory Limit: 256 MB // Time Limit: 3000 ms // Data:2021-08-10 13:46:54#include <bits/stdc++.h> #define debug(a, b) printf("%s = %d\n", a, b); using namespace std; typedef long long ll; typedef pair<int, int> PII; clock_t startTime, endTime; //Fe~Jozky const ll INF_ll= 1e18; const int INF_int= 0x3f3f3f3f; inline ll read() {ll s= 0, w= 1ll;char ch= getchar();while (ch < '0' || ch > '9') {if (ch == '-')w= -1ll;ch= getchar();}while (ch >= '0' && ch <= '9')s= s * 10ll + ((ch - '0') * 1ll), ch= getchar(); //s=(s<<3)+(s<<1)+(ch^48);return s * w; } void rd_test() { #ifdef ONLINE_JUDGE #elsestartTime= clock();freopen("in.txt", "r", stdin); #endif } void Time_test() { #ifdef ONLINE_JUDGE #elseendTime= clock();printf("\nRun Time:%lfs\n", (double)(endTime - startTime) / CLOCKS_PER_SEC); #endif } const int maxn= 3e5 + 9; int a[maxn]; int p[maxn], num[maxn], n, m; bool vis[maxn]; void init() {for (int i= 1; i <= n; i++)num[i]= 0; } bool check(int k) {for (int i= 1; i <= n; i++)vis[i]= 0;int ant= 0;//將移動k位置后的情況記錄for (int i= k + 1; i <= n; i++) {p[++ant]= a[i];}for (int i= 1; i <= k; i++) {p[++ant]= a[i];}//置換群int crinum= n;for (int i= 1; i <= n; i++) {if (vis[i])continue;crinum--;int pos= i;while (!vis[pos]) {vis[pos]= 1;pos= p[pos];}}return crinum <= m; } int main() {//rd_test();int t= read();while (t--) {init();n= read(), m= read();for (int i= 1; i <= n; i++) {a[i]= read();num[(i - a[i] + n) % n]++;}vector<int> vec;for (int i= 0; i < n; i++) //偏移量{if (num[i] >= n - 2 * m && check(i)) {vec.push_back(i);//if (vec.size() >= 3)// break;}}printf("%d", vec.size());for (auto i : vec) {printf(" %d", i);}printf("\n");}//Time_test(); }

總結

以上是生活随笔為你收集整理的cf1553E. Permutation Shift的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。