E. Permutation Shift（置换群）

题目

题意

给你一个数组然后问你有几种k操作在m此交换下，变成给出的数组
k操作为让后k个数到前面去

做题方法

\(m<=\frac{n}{3}\)所以\(m\)最多影响\(\frac{2n}{3}\)个数字,所以还有\(\frac{n}{3}\)个数字需要\(k\)操作影响
\(cnt[k]+2m>=n\)而\(\sum sum[i]=n\)所以\(k\)最多有3个
然后就回归到经典题目给定一个数组回到另一个数组

\(a\)数组为入点\(b\)数组为出点 然后找会形成环 每个环都需要交换的次数为环上的点-1个

代码
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
typedef pair pii;
#define endl '\n'
const int N = 1e6+10, M = N * 2, inf = 1e8;
int t, n, m, f[N], b[N], a[N];
int find(int x){
    return f[x] == x ? x : f[x] = find(f[x]);
}
bool check(){
    int sum = 0;
    for(int i = 1; i <= n; i++) f[i] = i;
    for(int i = 1; i <= n; i++){
        if(find(a[i]) != find(b[i])) {
            f[a[i]] = b[i];
            sum++;
        }
    }
    cout<>t;
    while(t--){
        cin>>n>>m;
        for(int i = 1; i <= n; i++) cin>>b[i];
        map mp;
        for(int i = 1; i <= n; i++) mp[(i-b[i]+n) % n]++;
        vector ans;
        for(int k = 0; k < n; k++){
            if(mp[k] < (n+2)/3) continue;
            int flag = 0;
            for(int j = 1; j <= n; j++){
                a[j] = (j - k + n) % n;
                if(a[j] == 0) a[j] = n;
            }
            if(check()) ans.push_back(k);
        }
        cout<
专题

相关

dp专题练习

Java进阶专题(十四) 从电商系统角度研究多线程(上)

Java进阶专题(九) 设计模式之总结

Java进阶专题(十三) 探究JMM

简单 Python 快乐之旅之：Python 基础语法之输入输出操作专题

暑期专题四 CDQ分治

专题 树形dp

专题学习

[Git专题] 环境搭建

长连接网关技术专题(六)：石墨文档单机50万WebSocket长连接架构实践

基于Vue的天地图入门专题(二)

组合数公式专题

标签