首页 > 代码库 > codechef Permutation Cycles 题解

codechef Permutation Cycles 题解

2024-07-02 21:13:11   224人阅读

We consider permutations of the numbers 1,..., N
for some N. By permutation we mean a rearrangment of the
number 1,...,N. For example
2  4  5  1  7  6  3  8
is a permutation of 1,2,...,8. Of course,
1  2  3  4  5  6  7  8
is also a permutation of 1,2,...,8.
We can "walk around" a permutation in a interesting way and here
is how it is done for the permutation above:
Start at position 1. At position 1 we have 2 and so we go to
position 2. Here we find 4 and so we go to position 4. Here we find
1, which is a position that we have already visited. This completes
the first part of our walk and we denote this walk by (1 2 4 1). Such
a walk is called a cycle. An interesting property of such
walks, that you may take for granted, is that the position we revisit
will always be the one we started from!


Examples
Sample input 1:
8
2 4 5 1 7 6 3 8
Sample output 1:
4
1 2 4 1
3 5 7 3
6 6
8 8 
Sample input 2:
8
1 2 3 4 5 6 7 8
Sample output 2:
8
1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8


原来permutation有这样的cycle的，很好玩。

下面程序带了个自制的输入输出int的处理。使用getc, putchar这些输入输出的确会快很多的。

#pragma once
#include <vector>
#include <string>
#include <algorithm>
#include <stack>
#include <stdio.h>
#include <iostream>
using namespace std;

namespace
{

int scanInt2()
{
	char c = getc(stdin);
	while (c < ‘0‘ || c > ‘9‘)
	{
		c = getc(stdin);
	}
	int num = 0;
	while (‘0‘ <= c && c <= ‘9‘)
	{
		num = (num<<3) + (num<<1) + c - ‘0‘;
		c = getc(stdin);
	}
	return num;
}

void printInt(int n)
{
	int i = 0;
	char buffer[32] = {0};
	while (n)
	{
		buffer[i++] = n % 10 + ‘0‘;
		n /= 10;
	}
	//buffer[i] = ‘\0‘;
	//fputs(buffer, stdout);
	for (i--; i >= 0; i--)
	{
		fputc(buffer[i], stdout);
	}
}

}

int PermutaionCycles()
{
	const int n = scanInt2();
	int *A = new int[n+1];
	for (int i = 1; i <= n; i++)
	{
		A[i] = scanInt2();
	}
	vector<vector<int> > rs;
	vector<int> tmp;
	for (int i = 1; i <= n; i++)
	{
		if (A[i] != -1)
		{
			tmp.clear();
			int j = i;	
			while (tmp.size() < 2 || tmp.back() != i)
			{
				tmp.push_back(j);
				int t = j;
				j = A[j];
				A[t] = -1;
			}
			rs.push_back(tmp);
		}
	}
	printInt(rs.size());
	putc(‘\n‘, stdout);
	for (int i = 0; i < (int)rs.size(); i++)
	{
		for (int j = 0; j < int(rs[i].size()); j++)
		{
			printInt(rs[i][j]);
			putc(‘ ‘, stdout);
		}
		putchar(‘\n‘);
	}
	delete [] A;
	return 0;
}


联系
我们