POJ置换群入门[3/3]

时间：2021-04-16 09:16:58

POJ 3270 Cow Sorting

题意：

一个序列变为升序，操作为交换两个元素，代价为两元素之和，求最小代价

题解：

看了黑书...

首先循环因子分解

一个循环完成的最小代价要么是循环中最小元素依次与其他交换，要么引入全局最小值来交换

$sum+min(mn*(len-2),mn+Min*(len+1))$

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

using namespace std;

const int N=1e4+,M=1e5+;

inline int read(){

    char c=getchar();int x=,f=;

    while(c<''||c>''){if(c=='-')f=-; c=getchar();}

    while(c>=''&&c<=''){x=x*+c-''; c=getchar();}

    return x*f;

}

int n,a[N],c[M],Min=M,m;

int f[N],ans;

bool vis[N];

int main(){

    //freopen("in","r",stdin);

    n=read();

    for(int i=;i<=n;i++)

        a[i]=read(),c[a[i]]++,Min=min(Min,a[i]),m=max(m,a[i]);

    for(int i=;i<=m;i++) c[i]+=c[i-];

    for(int i=;i<=n;i++) f[i]=c[a[i]];

    for(int i=;i<=n;i++) if(!vis[i]){

        vis[i]=;

        int u=f[i],sum=a[i],mn=a[i],len=;

        while(u!=i) vis[u]=,sum+=a[u],mn=min(mn,a[u]),len++,u=f[u];

        ans+=sum+min(mn*(len-),mn+Min*(len+));

    }

    printf("%d",ans);

}

POJ2369 Permutations

题意：

求一个置换的几次幂得到自身

题解：

每个循环长度的最小公倍数

注意是几次幂不是转换了几次!!!

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

using namespace std;

const int N=1e3+;

inline int read(){

    char c=getchar();int x=,f=;

    while(c<''||c>''){if(c=='-')f=-; c=getchar();}

    while(c>=''&&c<=''){x=x*+c-''; c=getchar();}

    return x*f;

}

int n,a[N],ans=;

inline int gcd(int a,int b){return b==?a:gcd(b,a%b);}

inline int lcm(int a,int b){return a/gcd(a,b)*b;}

bool vis[N];

int main(){

    //freopen("in","r",stdin);

    n=read();

    for(int i=;i<=n;i++) a[i]=read();

    for(int i=;i<=n;i++) if(!vis[i]){

        vis[i]=;

        int u=a[i],len=;

        while(u!=i) vis[i]=,len++,u=a[u];

        ans=lcm(ans,len);

    }

    printf("%d",ans);

}

POJ1721CARDS

题意：

交换规则为$i \rightarrow a[a[i]]$，进行了$s$次，给出最后的排列求一开始

题解：

一直尝试构造置换的逆一直失败，也许是因为每次合成的置换都不同吧

网上的做法是暴力找整个置换的循环然后把剩下的操作补出来...感觉会被卡...

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

using namespace std;

const int N=;

inline int read(){

    char c=getchar();int x=,f=;

    while(c<''||c>''){if(c=='-')f=-; c=getchar();}

    while(c>=''&&c<=''){x=x*+c-''; c=getchar();}

    return x*f;

}

int n,s,a[N],t[N],b[N];

int main(){

    freopen("in","r",stdin);

    n=read();s=read();

    for(int i=;i<=n;i++) b[i]=a[i]=read();

    int cnt=;

    while(true){

        int flag=;

        cnt++;

        for(int i=;i<=n;i++) t[i]=a[a[i]];

        for(int i=;i<=n;i++){

            a[i]=t[i];

            if(a[i]!=b[i]) flag=;

        }

        if(flag) break;

    }

    cnt=cnt-s%cnt;

    while(cnt--){

        for(int i=;i<=n;i++) t[i]=a[a[i]];

        for(int i=;i<=n;i++) a[i]=t[i];

    }

    for(int i=;i<=n;i++) printf("%d\n",a[i]);

}

相关文章