【置换群】CH Round #63 - OrzCC杯#2省选热身赛 exchange

第一问置换群裸题。

第二问单独考虑某个循环，任意交换两个元素，稍微画一下就会发现，把该循环拆成了2个，剩下所需的交换次数减少了1，也就是说，第一步我们任意交换，都能够保证交换次数最少。于是一个循环的答案就是n*(n-1)/2，把所有的加起来即可。

进而我们发现，在剩下的步骤里面，我们只需在拆出来的两个循环里任意交换即可。

#include<cstdio>

using namespace std;

#define N 50001

bool vis[N];

int n,op,a[N],sumv,sum2;

int main()

{

	scanf("%d%d",&n,&op);

	for(int i=1;i<=n;++i) scanf("%d",&a[i]);

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

	  if(!vis[i])

	    {

	      vis[i]=1;

	      int cnt=1;

	      int U=a[i];

	      while(U!=i)

	        {

	          vis[U]=1;

	          U=a[U];

	          ++cnt;

	        }

	      sumv+=(cnt-1);

	      sum2+=(cnt*(cnt-1)>>1);

	    }

	if(op==1)

	  printf("%d\n",sumv);

	else

	  printf("%d\n%d\n",sumv,sum2);

	return 0;

}

巴特西

【置换群】CH Round #63 - OrzCC杯#2省选热身赛 exchange

最新文章

热门文章