首页 > ACM题库 > HDU-杭电 > HDU 3430-Shuffling[解题报告]HOJ
2014
03-23

HDU 3430-Shuffling[解题报告]HOJ

Shuffling

问题描述 :

A casino owns an expensive card shuffling machine which may shuffle up to 520 cards at a time (there are 52 cards in each deck). For convenience, we will simply label the cards 1, 2, 3, …, N where N is the total number of cards, and copies of the same card (e.g. Ace of Spades) from different decks are considered different. Unfortunately, the card shuffling machine is defective, and it always shuffles the cards the same way. The company that produces these machines is out of business because of the economic downturn. There is no one who can fix the machine, and a new machine is too expensive.

Being a brilliant employee of the casino, you realized that all is not lost. You can shuffle the cards differently simply by using the machine zero or more times. For example, suppose that the machine shuffles the cards 1, 2, 3, 4 into the order 2, 3, 4, 1. If you put the cards into the machine, take the shuffled cards out and insert them into the machine again (without changing the order), you will get the order 3, 4, 1, 2. That way, it is possible to shuffle the cards in many different ways even though it may take longer. But this is not a significant issue since decks do not have to be reshuffled often, and used decks can be shuffled while other decks are being used to avoid any waiting time.

Unfortunately, not all shufflings can be produced in this way in general, and you wish to know if this procedure "stack the decks" in a favorable way for the casino or the player. As a first step, you wish to know which shufflings are possible to produce, and how many times you need to use the machine on the deck in order to produce the shuffling.

输入:

The input for each case consists of three lines. The first line consists of a single integer N indicating the number of cards to shuffle. The number of cards is a positive integer up to 520. The second line consists of the integers 1, 2, …, N listed in some order and separated by a space. The list gives the order of the shuffling performed by the machine when the input cards are ordered 1, 2, …, N. The third line is in the same format as the second line, and gives the shuffling we wish to obtain. The end of input is indicated by a line in which N = 0.

输出:

The input for each case consists of three lines. The first line consists of a single integer N indicating the number of cards to shuffle. The number of cards is a positive integer up to 520. The second line consists of the integers 1, 2, …, N listed in some order and separated by a space. The list gives the order of the shuffling performed by the machine when the input cards are ordered 1, 2, …, N. The third line is in the same format as the second line, and gives the shuffling we wish to obtain. The end of input is indicated by a line in which N = 0.

样例输入:

4
2 3 4 1
3 4 1 2
4
2 3 4 1
1 3 2 4
10
2 1 3 5 6 7 8 9 10 4
1 2 3 9 10 4 5 6 7 8
0

样例输出:

2
-1
12

#include<cstdio>
#include<cstring>
using namespace std;

bool use[530];
int p[530],t[530];

void  exgcd(long long a,long long b,long long &x,long long &y,long long &g)
{
	if(b)
	{
		exgcd(b,a%b,y,x,g);
		y-=a/b*x;
	}
	else
	{
		x=1;
		y=0;
		g=a;
	}
}
long long mod(long long x,long long m)
{
	x%=m;
	if(x<0)
	{
		x+=m;
	}
	return x;
}
bool check(int i,int cnt,int r)
{
	int tmp=i;
	int idx=i;

	for(int j=0;j<r;j++)
	{
		idx=p[idx];
	}
	for(int j=1;j<=cnt;j++)
	{
		if(idx!=t[tmp])
		{
			return false;
		}
		idx=p[idx];
		tmp=p[tmp];
	}
	return true;
}
int main()
{
	int n;

	while(scanf("%d",&n),n)
	{
		long long  lcm=0,c,x,y,g;
		bool flag=true;
		memset(use,0,sizeof(use));

		for(int i=1;i<=n;i++)
		{
			scanf("%d",p+i);
		}
		for(int i=1;i<=n;i++)
		{
			scanf("%d",t+i);
		}
		
		for(int i=1;i<=n;i++)
		{
			if(use[i]==false)
			{
				int cnt=0;
				int tmp=i;
				do
				{
					use[tmp]=true;
					cnt++;
					tmp=p[tmp];
				}
				while(use[tmp]==false);

				tmp=i;
				int r=0;

				while(tmp!=t[i]&&r<cnt)
				{
					tmp=p[tmp];
					r++;
				}
				if(check(i,cnt,r))
				{
					if(lcm==0)
					{
						lcm=cnt;
						c=r;
					}
					else
					{
						exgcd(lcm,cnt,x,y,g);
						r=mod(r-c,cnt);
						if(r%g)
						{
							printf("-1\n");
							flag=false;
							break;
						}
						else
						{
							lcm=lcm/g*cnt;
							x=mod(r/g*x,cnt);
							c=mod(lcm/cnt*g*x+c,lcm);
						}
					}
				}
				else
				{
					printf("-1\n");
					flag=false;
					break;
				}
			}
		}
		if(flag)
		{
			printf("%lld\n",c);
		}
	}
	return 0;
}

  1. Often We don’t set up on weblogs, but I would like to condition that this established up really forced me individually to do this! considerably outstanding publish

  2. 您没有考虑 树的根节点是负数的情况, 若树的根节点是个很大的负数,那么就要考虑过不过另外一边子树了