首页 > 代码库 > 序列中的交换问题
序列中的交换问题
一、逆序对系列问题
题目:http://poj.org/problem?id=1804
题意:给定一个序列a[],每次只允许交换相邻两个数,最少要交换多少次才能把它变成非递降序列.
求逆序对的裸题。
如果我们交换相邻两个数，我们逆序对的个数只能是+1或-1
我们现在需要得到一个非递减数列，即消去所有逆序对，
而我们需要最少交换次数，即统计原数组中逆序对个数。
对于一个序列中，有Ai>Aj，i<j的两个元素，我们把这个二元组称为逆序对
有常见的三种方法求逆序对
1.n^2的冒泡
2.树状数组
可以把数一个个插入到树状数组中,每插入一个数,统计比他小的数的个数，对应的逆序为 i- getsum(data[i])，其中 i 为当前已经插入的数的个数， getsum(data[i])为比 data[i] 小的数的个数,i-getsum(data[i])即比 data[i] 大的个数,即逆序的个数。最后需要把所有逆序数求和,就是在插入的过程中边插入边求和。
const maxn=200001;var val,hash,tree:array [0..maxn] of longint; n:longint;function lowbit(x:longint):longint;begin exit(x and (-x));end;function getsum(pos:longint):longint;var ans:longint;begin ans:=0; while pos>0 do begin inc(ans,tree[pos]); dec(pos,lowbit(pos)); end; exit(ans);end;procedure modify(pos:longint);begin while pos<=n do begin inc(tree[pos]); inc(pos,lowbit(pos)); end;end;procedure qsort(l,r:longint);var i,j,t,p:longint;begin if l>=r then exit; i:=random(r-l+1)+l; t:=val[i]; p:=hash[i]; val[i]:=val[l]; hash[i]:=hash[l]; i:=l; j:=r; while i<j do begin while (i<j) and (t<val[j]) do dec(j); if i=j then break; val[i]:=val[j]; hash[i]:=hash[j]; inc(i); while (i<j) and (val[i]<t) do inc(i); if i=j then break; val[j]:=val[i]; hash[j]:=hash[i]; dec(j); end; val[i]:=t; hash[i]:=p; qsort(l,i-1); qsort(i+1,r);end;procedure main;var i,ans,m:longint;begin ans:=0; m:=0; randomize; read(n); for i:=1 to n do begin read(val[i]); hash[i]:=i; end; qsort(1,n); tree:=val; for i:=1 to n do if tree[i]<>tree[i-1] then begin inc(m); val[hash[i]]:=m; end else val[hash[i]]:=m; fillchar(tree,sizeof(tree),0); for i:=1 to n do begin inc(ans,getsum(m)-getsum(val[i])); modify(val[i]); end; writeln(ans);end;begin main;end.3.归并排序
实际上归并排序的交换次数就是这个数组的逆序对个数，为什么呢？
我们可以这样考虑：
归并排序是将数列a[l,h]分成两半a[l,mid]和a[mid+1,h]分别进行归并排序，然后再将这两半合并起来。
在合并的过程中（设l<=i<=mid，mid+1<=j<=h），当a[i]<=a[j]时，并不产生逆序数；当a[i]>a[j]时，在
前半部分中比a[i]大的数都比a[j]大，将a[j]放在a[i]前面的话，逆序数要加上mid+1-i。因此，可以在归并排序中的合并过程中计算逆序数.
在合并的时候设左数组为1~x,右数组为x+1~y，则当a[i]<a[j]，(1<=i<=x,x+1<=j<=y)必定有a[i]>a[x+1]~a[j-1]，于是它们都是逆序对。
const maxn=100001;var val,hash:array [0..maxn] of longint; ans:longint; procedure merge(l,mid,r:longint);var i,j,k:longint;begin i:=l; j:=m+1; k:=l; while (i<=m) and (j<=r) do begin if val[i]>val[j] then begin hash[k]:=val[j]; inc(k); inc(j); inc(ans,m-i+1); end else begin hash[k]:=val[i]; inc(k); inc(i); end; end;end;procedure merge_sort(l,r:longint);var mid:longint;begin if l<r then begin mid:=(l+r)>>1; merge_sort(l,mid); merge_sort(mid+1,r); merge(l,mid,r); end;end;procedure main;var i,n:longint;begin read(n); for i:=1 to n do read(a[i]); merge_sort(1,n); writeln(ans);end;begin main;end.
二、置换群系列问题
题目:http://poj.org/problem?id=3270
题意:给定一个序列a[],每次只允许交换任意两个数,最少要交换多少次才能把它变成非递降序列.
看上去跟逆序对很像，但是我们发现，我们每交换一次，可能减少很多逆序对
所以显然不是统计逆序对的题目。
怎么搞呢？
1.找出初始状态和目标状态。明显，目标状态就是排序后的状态。
2.画出置换群，在里面找循环。例如，数字是8 4 5 3 2 7
明显，目标状态是2 3 4 5 7 8，能写为两个循环：
(8 2 7)(4 3 5)。
3.观察其中一个循环，明显地，要使交换代价最小，应该用循环里面最小的数字2，去与另外的两个数字，7与8交换。这样交换的代价是：
sum - min + (len - 1) * min
化简后为：
sum + (len - 2) * min
其中，sum为这个循环所有数字的和，len为长度，min为这个环里面最小的数字。
4.考虑到另外一种情况，我们可以从别的循环里面调一个数字，进入这个循环之中，使交换代价更小。例如初始状态：
1 8 9 7 6
可分解为两个循环：
(1)(8 6 9 7)，明显，第二个循环为(8 6 9 7)，最小的数字为6。我们可以抽调整个数列最小的数字1进入这个循环。使第二个循环变为：(8 1 9 7)。让这个1完成任务后，再和6交换，让6重新回到循环之后。这样做的代价明显是：
sum + min + (len + 1) * smallest
其中，sum为这个循环所有数字的和，len为长度，min为这个环里面最小的数字，smallest是整个数列最小的数字。
5.因此，对一个循环的排序，其代价是sum - min + (len - 1) * min和sum + min + (len + 1) * smallest之中小的那个数字。
置换群是啥？
一个置换可以写成若干循环的乘积，那么如果置换求幂的话，一个循环不会跑到另一个循环里面去。
我们可以简单理解为这几个位置的数来回换。
const maxn=100001;type node=record val,cnt:longint;end;var n,minvalue:longint; sum,tot:int64; m,t:array [0..maxn] of longint; flag:array [0..maxn] of boolean; a:array [0..maxn] of node;function min(x,y:longint):longint; inline;begin if x<y then exit(x) else exit(y);end;procedure find(x:longint); inline;var i:longint;begin for i:=0 to n-1 do begin if (t[i]=x) and (not flag[i]) then begin flag[i]:=true; inc(a[tot].cnt); a[tot].val:=min(a[tot].val,t[i]); find(m[i]); end; end;end;procedure qsort(l,r:longint); inline;var i,j,x,y:longint;begin i:=l; j:=r; x:=m[(l+r)>>1]; repeat while m[i]<x do inc(i); while m[j]>x do dec(j); if i<=j then begin y:=m[i]; m[i]:=m[j]; m[j]:=y; inc(i); dec(j); end; until i>j; if i<r then qsort(i,r); if l<j then qsort(l,j);end;procedure main;var i:longint;begin read(n); minvalue:=maxlongint; for i:=0 to n-1 do begin read(m[i]); inc(sum,m[i]); t[i]:=m[i]; minvalue:=min(minvalue,m[i]); end; qsort(0,n-1); tot:=0; for i:=0 to n-1 do begin if flag[i] then continue; a[tot].val:=t[i]; a[tot].cnt:=1; flag[i]:=true; find(m[i]); inc(tot); end; for i:=0 to tot-1 do inc(sum,min(a[i].val*(a[i].cnt-2),minvalue*(a[i].cnt+1)+a[i].val)); writeln(sum);end;begin main;end.题目:http://poj.org/problem?id=2369
题意:给出1-n的一个排列，a1,a2,...,an,表示P(1)=a1,P(2)=a2,...,P(n)=an,P(P(1))=P(a1),P(P(2))=P(a2),
...,P(P(n))=P(an).问经过多少次后使得P(1)=1,...,P(n)=n.
这个是置换群的概念题，找到每个循环节，确定其长度len1,len2,...,lenk,求他们的最小公倍数。
对于题目中给定的一个例子进行分析：
1 2 3 4 5
4 1 5 2 3
上面定义了函数P，那么我们可以看出这个置换可以写成(1 4 2)(3 5),这样循环1中的数绝对不会跑到第二个循环中，每个循环i需要经过leni次后就可以到达目的状态，所以我们只需要确定各个循环节长度的最小公倍数。
const maxn=1001;var val,v:array [0..maxn] of longint; n:longint; function gcd(x,y:int64):longint;begin if x mod y=0 then exit(y) else exit(gcd(y,x mod y));end;procedure main;var i,j,k,sum:longint; ans:int64;begin read(n); ans:=1; for i:=1 to n do read(val[i]); for i:=1 to n do if (v[i]=0) and (val[i]<>i) then begin v[val[i]]:=1; j:=val[i]; k:=2; while val[j]<>i do begin inc(k); v[val[j]]:=1; j:=val[j]; end; v[i]:=1; sum:=gcd(ans,k); ans:=ans*(k div sum); end; writeln(ans);end;begin main;end.题目:http://poj.org/problem?id=1026
题意:首先给出一个置换，然后给出一个字符串，问置换k次之后得到的字符串是什么？
我们求出来子循环，然后对每个子循环计算k次之后置换群变成什么排列，用b[0],b[1],...,b[t-1]表示一个子群，
那么长度为t,经过一次置换后变成b[0]=b[1],b[1]=b[2],..,b[t-1]=b[0],所以经过k次后变成b[(0+k)%t],b[(1+k)%t],..,b[(t-1+k)%t],即b[i]->b[(i+k)%t].
我们预处理出2^k，然后乱搞一下即可
const maxn=201; maxm=31;type arr=array [0..maxn] of longint;var n,i,j,k,l:longint; cache,ans:arr; change:array [0..maxm] of arr; s:string; temp:char; procedure prepare;var i,j:longint;begin for j:=1 to maxm do for i:=1 to n do change[j,i]:=change[j-1,change[j-1,i]];end; procedure main;begin repeat read(n); if n=0 then break; for i:=1 to n do read(change[0,i]); readln; prepare; repeat read(k); if k=0 then break; read(temp); readln(s); l:=length(s); while l<n do begin s:=s+‘ ‘; inc(l); end; for i:=1 to n do ans[i]:=i; while k<>0 do begin j:=trunc(ln(k)/ln(2)); for i:=1 to n do cache[change[j,i]]:=ans[i]; ans:=cache; k:=k-(1<<j); end; for i:=1 to n do write(s[ans[i]]); writeln; until false; writeln; until false;end;begin main;end.再说下循环的概念。
记（a1 a2 ^ an）= 为一个循环。循环亦称做轮换。可以认为是a1到an组成了一个环。而一个置换可以写成多个循环的乘积。比如
=（a1a3a6）(a2a4)(a5)。而循环节的长度就是轮换的个数。这里循环节长度为3。
对于循环有一些操作。比如乘上一个[对换]。
定义(a1,b1)为将a循环中的a1元素和b循环中的b1元素交换。则这是一个两元素在不同轮换中的对换。给循环乘上这个对换。即相当于将原来的两个“环”分别在a1和b1处拆开，再连接成一个新的“环”。也就是说，就是这种对换将两个轮换合并成了一个。
反之，如果对换发生在某轮换内部，那么相当于在(a1,ai)处将此环拆开，然后分别合并为了两个新“环”。也就是说，这种对换将轮换分拆为了两个新的轮换。
如果我们记置换群中元素个数为n，循环节长度为a，可以发生的内部对换数为b。则有下列式子成立：
b = n-a。
想到了神马？对了，最小路径覆盖。
实际上，二分图就是一个置换群。上面一排元素为X集，下面一排元素为Y集。在利用二分图求解最小路径覆盖问题的时候，每次增加一个匹配，路径数就会减少一条。也就是说，匹配数+路径条数=顶点个数。如果想要尽量减小路径条数，大家都看得出来要求最大匹配。
类比一下，匹配数即为轮换内对换数，路径条数即为循环节长度，而顶点个数也就是置换群内的元素个数。所以说，此题其实是求置换群中循环节的长度。
还有一个记忆犹新的例子。那就是某个神奇的DP题。
题目大意大概就是一些钥匙分别对应一些门，但是这些钥匙分别放在不同的门里，并且锁起来了（多么悲催~~）。现在你有两条途径得到这些钥匙。要么破坏门，拿出里面的钥匙。要么用之前得到的钥匙去开现在面对的门。求最少破坏的门的数目。
看出来了，对不对？门看做大括号上面一排元素，钥匙看做下面一排。如果出现“钥匙转圈”的现象，那么即形成一个轮换。此题即变为求循环节的长度。
而用dp求解的时候，我们写方程如下：
f[i,j]:=min{f[i-1,j-1],(i-1)*f[i-1,j]}。这样，第一个式子是设前面i-1个元素组成一个循环，而后一个式子则是通过给前i-1个元素组成的循环乘上一个两元素分属于不同轮换的对换将它和第i个元素的轮换合并为了一个。
这样，不论是DP还是图论，我们都可以统一地用离散数学的群论来总结和解释。
其实，之前在学习群论的过程中，就隐约体会到了其对于其他领域问题的一些本质解释。比如拓扑排序，比如线性代数。
序列中的交换问题