codechef Permutation Cycles 题解

原来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;
}

codechef Permutation Cycles 题解,布布扣,bubuko.com

codechef Permutation Cycles 题解

原文：http://blog.csdn.net/kenden23/article/details/24958079