poj3270 && poj 1026(置换问题)

poj3270 && poj 1026(置换问题)| 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;
}

  

上一篇:struts2所有组件


下一篇:使用C#访问SQLLite