首页 > ACM题库 > HDU-杭电 > HDU 1027 Ignatius and the Princess II-模拟-[解题报告] C++
2013
11-26

HDU 1027 Ignatius and the Princess II-模拟-[解题报告] C++

Ignatius and the Princess II

问题描述 :

Now our hero finds the door to the BEelzebub feng5166. He opens the door and finds feng5166 is about to kill our pretty Princess. But now the BEelzebub has to beat our hero first. feng5166 says, "I have three question for you, if you can work them out, I will release the Princess, or you will be my dinner, too." Ignatius says confidently, "OK, at last, I will save the Princess."

"Now I will show you the first problem." feng5166 says, "Given a sequence of number 1 to N, we define that 1,2,3…N-1,N is the smallest sequence among all the sequence which can be composed with number 1 to N(each number can be and should be use only once in this problem). So it’s easy to see the second smallest sequence is 1,2,3…N,N-1. Now I will give you two numbers, N and M. You should tell me the Mth smallest sequence which is composed with number 1 to N. It’s easy, isn’t is? Hahahahaha……"
Can you help Ignatius to solve this problem?

输入:

The input contains several test cases. Each test case consists of two numbers, N and M(1<=N<=1000, 1<=M<=10000). You may assume that there is always a sequence satisfied the BEelzebub’s demand. The input is terminated by the end of file.

输出:

For each test case, you only have to output the sequence satisfied the BEelzebub’s demand. When output a sequence, you should print a space between two numbers, but do not output any spaces after the last number.

样例输入:

6 4
11 8

样例输出:

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

pku1703,并查集的应用,比较常见的一种。

刚开始没什么思路,,想到一种方法,就是记录下每一个节点到根节点的距离,根据两个节点的距离之和的奇偶性来判断是敌是友。

这个代码没有写,不知道能行不能行。。

disscuss发现一种方法:用两个数组,一个存友f[],一个存敌d[]。

如果是D  a  b

就把a与的d[b]进行Union,b与d[a] 进行Union,

如果是A  a  b

先判断find(a) 是否等于find(b)

是就输入the same。

否的话判断find(a)是否等于find(f[b])

是的话输出the different

else 输出 条件不足。代码就不贴了。。

1027 和2062是两道模拟题,以前都没有做,感觉太麻烦了。。

今天闲来无事就给写了下,, 对于这类型的,关键是要理解透彻,细节要处理好。。

1027由于m最大只有10000  小于8的阶乘,所以只需要对n的后8位进行判断即可。。

2062 f[i]=i*(f[i-1]+1),m可以用__int64 来存储,其余的都和1027差不多。。

贴一下1027题得代码吧:

# include<stdio.h>
# include<string.h>
int f[10],visit[1005];
int max(int a,int b)
{
	return a>b?a:b;
}
int main()
{
	int i,j,n,m,k,t,ans,flag;
	f[0]=1;
	for(i=1;i<=8;i++)
		f[i]=f[i-1]*i;
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		flag=0;
		memset(visit,0,sizeof(visit));
		for(i=1;i<=n;i++)
		{
			ans=n-i+1;
			if(ans>8)
			{
				visit[i]=1;
				if(flag==0) {printf("%d",i);flag=1;}
				else printf(" %d",i);
			}
			else 
			{
				t=m/f[ans-1];
				if(m%f[ans-1]!=0) t++;
				k=0;
				for(j=max(1,n-9);j<=n;j++)
				{
					if(visit[j]==0) k++;
					if(k==t) break;
				}
				visit[j]=1;
				if(flag==0) {printf("%d",j);flag=1;}
				else printf(" %d",j);
				m-=(t-1)*f[ans-1];
			}
		}
		printf("\n");
	}
	return 0;
}

  1. A猴子认识的所有猴子和B猴子认识的所有猴子都能认识,这句话用《爱屋及乌》描述比较容易理解……

  2. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。