| 1 2 3 4 5 6 |
| 3 6 5 1 4 2 |
在一个置换下,x1->x2,x2->x3,...,xn->x1,
每一个置换都可以唯一的分解为若干个不交的循环
如上面那个 可以 =>（1,3,5,4） 1的下面是3 ；3的下面是5 一直循环。 （2,6）
一个循环，有两种处理方法：
①用这个循环中最小的元素，依次与相应元素交换，直到该循环内所有元素归位
②用这个循环中最小的元素与所有数中最小的元素交换，然后用所有数中最小的元素依次与相应元素交换，直到该循环内所有元素归位这样(x1,x2,...,xn)就构成了一个循环
思路：（参考北大的群论以及ACM_cxiove）
poj 3270
所以先计算出所有数的和sum，然后再在这个基础上选择是和 循环中最小的元素or所有数中最小的元素 交换。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#define N 10100
typedef long long ll;
using namespace std;
int a[N];
int p[N];
int flag[N];
int tot;
struct node
{
int val;
int cnt;
} q[N];
int n;
void dfs(int u)
{
for(int i = 1; i <=n ; i++)
{
if(a[i] == u && !flag[i])
{
flag[i] = 1;
q[tot].val = min(q[tot].val,a[i]);
q[tot].cnt++;
dfs(p[i]);
}
}
} int main()
{
while(scanf("%d",&n)!=EOF)
{
int minx = 0x3f3f3f3f;
memset(flag,0,sizeof(flag));
int sum = 0;
for(int i = 1; i <= n; i++)
{
scanf("%d",&a[i]);
p[i] = a[i];
sum += a[i];
minx = min(minx,a[i]);
}
sort(p+1,p+1+n);
tot= 0; for(int i = 1; i <= n; i++)
{
if(flag[i]) continue;
q[tot].val = a[i];
q[tot].cnt = 1;
flag[i] = 1;
dfs(p[i]);
tot++;
} for(int i = 0; i < tot; i++)
{
sum += min(q[i].val*(q[i].cnt-2),minx*(q[i].cnt+1)+q[i].val);
}
printf("%d\n",sum);
}
return 0;
}
题意：
对于一个长度为n的字符串，有一个数组表示第i个字符放到那个位置。
输入多个字符串，问这样操作k次后的字符串是什么样子
找出循环的最小周期，求余计算
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#define N 205
typedef long long ll;
using namespace std;
int a[N],p[N];
char ans[N],str[N];
int k,n; int fin(int i,int k) //肯能会产生循环，寻找最小周期；并且找出第i个字符会落在的某位
{
int j,t=i+1;
i++;
for(j=1; j<=k; j++)
{
i=a[i];
if(i==t)
{
for(i=t,t=0; t<(k%j); t++) //利用最小周期
i=a[i];
return i;
}
}
return i;
} int main()
{
while(scanf("%d",&n)!=EOF && n)
{
for(int i = 1; i <= n; i++)
scanf("%d",&a[i]); while(scanf("%d",&k) && k)
{
getchar();
gets(ans);
int L = strlen(ans);
if(L < n)
for(int i = L; i < n; i++)
ans[i] = ' ';
for(int i = 0; i < n; i++)
{
//printf("%d ",fin(i,k) - 1);
str[fin(i,k) - 1] = ans[i];
}
for(int i=n-1;; i--)
if(str[i]!=' ')
{
str[i+1]='\0';
break;
}
printf("%s\n",str);
}
printf("\n");
}
return 0;
}