掉大分

 

E

对于一个序列，把它排回去的最小次数是 $\sum置换环大小-1=错位个数-置换环个数$

注意到m小于等于n/3。那么最多修正2m个错位。正确位置的个数必须大于等于n/3才可能在m次内修正。

每个点正确位置只有一个。那么整个序列最多有3个位置，以它们为开头满足条件。找出这些位置再暴力验证即可

 1 #include <queue>
 2 #include <bitset>
 3 #include <vector>
 4 #include <cstdio>
 5 #include <cstring>
 6 #include <algorithm>
 7 #define ll long long 
 8 using namespace std;
 9 const int maxn=3e5, N1=maxn+5;
10 
11 template <typename _T> void read(_T &ret)
12 {
13     ret=0; _T fh=1; char c=getchar();
14     while(c<'0'||c>'9'){ if(c=='-') fh=-1; c=getchar(); }
15     while(c>='0'&&c<='9'){ ret=ret*10+c-'0'; c=getchar(); }
16     ret=ret*fh;
17 }
18 
19 int T,m,n; 
20 int p[N1],cnt[N1];
21 int a[N1],vis[N1];
22 
23 int check(int to)
24 {
25     for(int i=1+to;i<=n;i++) a[i-to]=p[i];
26     for(int i=1;i<=to;i++) a[i+n-to]=p[i];
27     for(int i=1;i<=n;i++) vis[i]=0;
28     int tot=0;
29     for(int i=1,num,x;i<=n;i++)
30     {
31         num=0;
32         if(vis[i]) continue;
33         for(x=i;;x=a[x])
34         {
35             vis[x]=1; num++;
36             if(a[x]==i) break;
37         }
38         tot+=num-1;
39     }
40     return tot<=m;
41 }
42 
43 int main()
44 {
45     // freopen("a.in","r",stdin);
46     read(T);
47     while(T--)
48     {
49         read(n); read(m);
50         for(int i=1,x;i<=n;i++) 
51         {
52             read(p[i]);
53             x=i-p[i]; if(x<0) x+=n;
54             cnt[x]++;
55         }
56         int ans=0, pos[3]={0,0,0}, fl;
57         for(int i=0;i<n;i++) if(cnt[i]>=n/3)
58         {
59             fl=check(i);
60             if(fl) pos[ans++]=i;
61         }
62         printf("%d ",ans);
63         for(int i=0;i<ans;i++) printf("%d ",pos[i]);
64         puts("");
65         for(int i=1;i<=n;i++) cnt[i]=0;
66     }
67     return 0;
68 }

View Code