CF1553E Permutation Shift 题解
Post time: 2021-07-24 13:05:12
题面
一道心理阴影题。
题意已经很明显了，\(O(n^2)\) 做法就是，对于每个 \(k\)，求最少多少次交换可以使一个排列变为另一个排列。做法是说，对于同一个数，若它在两个排列中的位置不同（记这样的数的总数为 \(s\)），就建一条连接这两个位置的边，求得图的连通分量数 \(c\)，答案就是 \(s-c\)。
考场上想到这个，但是无论如何都不会优化了。不会优化就直接做啊！
考虑到这个题给了一个限制 \(m\)，最理想的情况下，可以做有 \(2m\) 个数位置不对的两个排列。那么 \(s>2m\) 的肯定都不可以。题目中给了一个 \(m\leq \frac{n}{3}\)，这时候就派上用场了：设旋转参数为 \(k\) 的时候，两个排列位置一样的个数为 \(cnt_k\)，那么 \(\sum_{i=0}^{n-1}cnt_i=n\)。所以，满足 \(s\leq 2m\) 的 \(k\) 的数量最多不超过 \(3\)！直接 \(O(3n)\) 做完了。
点击查看代码
#include
#include
#include
#define pb push_back
using namespace std;
const int N=3e5+13;
int n,m,cnt[N],p[N],ans[N];
vector g[N];
bool vis[N];
inline void add_edge(int u,int v){g[u].pb(v);}
void dfs(int u){
vis[u]=1;
for(auto v:g[u])
if(!vis[v]) dfs(v);
}
inline void solve(){
scanf("%d%d",&n,&m);
for(int i=0;i