B. 全排列问题

时间限制:1 s 空间限制:256 MB

输出自然数1到n所有不重复的排列，即n的全排列，要求所产生的任一数字序列中不允许出现重复的数字。(注意输出格式)

输入

n(1<=n<=9)

输出

由1~n组成的所有不重复的数字序列，每一行一个序列，每个数字前4个空格。

样例

样例输入1

3

样例输出1

    1    2    3
    1    3    2
    2    1    3
    2    3    1
    3    1    2
    3    2    1

分析：

        这题眨眼一看，感觉很简单，可是，又让你无能为力，于是，爱骗分的你就会像我一样

#include <bits/stdc++.h>
using namespace std;
int main()
{
	int n;
	cin>>n;
	int sum=1,num=0;
	for(int i=1;i<=n;i++)
	{
		sum*=i;
		num+=i;
	}
	if(n==3)
	{
		cout<<"1 2 3"<<endl;
		cout<<"1 3 2"<<endl;
		cout<<"2 1 3"<<endl;
		cout<<"2 3 1"<<endl;
		cout<<"3 1 2"<<endl;
		cout<<"3 2 1"<<endl;
		return 0;
	}
	if(n==4)
	{
		cout<<"1 2 3 4"<<endl;
		cout<<"1 2 4 3"<<endl;
		cout<<"1 3 2 4"<<endl;
		cout<<"1 3 4 2"<<endl;
		cout<<"1 4 2 3"<<endl;
		cout<<"1 4 3 2"<<endl;		
		cout<<"2 1 3 4"<<endl;
		cout<<"2 1 4 3"<<endl;
		cout<<"2 3 1 4"<<endl;
		cout<<"2 3 4 1"<<endl;
		cout<<"2 4 1 3"<<endl;
		cout<<"2 4 3 1"<<endl;
		cout<<"3 1 2 4"<<endl;
		cout<<"3 1 4 2"<<endl;
		cout<<"3 2 1 4"<<endl;
		cout<<"3 2 4 1"<<endl;
		cout<<"3 4 1 2"<<endl;
		cout<<"3 4 2 1"<<endl;
		cout<<"4 1 2 3"<<endl;
		cout<<"4 1 3 2"<<endl;
		cout<<"4 2 1 3"<<endl;
		cout<<"4 2 3 1"<<endl;
		cout<<"4 3 1 2"<<endl;
		cout<<"4 3 2 1"<<endl;
		return 0;
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			for(int k=1;k<=n;k++)
			{
				for(int m=1;m<=n;m++)
				{
					for(int o=1;o<=n;o++)
					{
						if(n==6)
						{
							for(int x=1;x<=n;x++)
							{
								if(i*j*k*m*o*x==sum&&i+j+k+m+o+x==num)
								{
									cout<<i<<" "<<j<<" "<<k<<" "<<m<<" "<<o<<" "<<x<<endl;
							    }
							}	
							continue;
						}
						if(n==7)
						{
							for(int x=1;x<=n;x++)
							{
								for(int y=1;y<=n;y++)
								{
									if(i*j*k*m*o*x*y==sum&&i+j+k+m+o+x+y==num)
									{
										cout<<i<<" "<<j<<" "<<k<<" "<<m<<" "<<o<<" "<<x<<" "<<y<<endl;
								    }	
								}
							}
							continue;		
						}
						if(i*j*k*m*o==sum&&i+j+k+m+o==num)
						{
							cout<<i<<" "<<j<<" "<<k<<" "<<m<<" "<<o<<endl;
						}
					}	
				}	
			}
		}
	}
}

你可以把n为1到9全部枚举出来，事实上，测试点最大的也无非是7

所以，大声喊出我们的口号：

                        暴力出奇迹，骗分过样例。

                        爆搜挂着机，打表出省一。

打表出省一，出省一！！！

咳咳，刚才你什么也没看到，没看到。。。

正解（上面非错解）：

        dfs深搜（也是骗分常用技巧  可参见https://qoj.fzoi.top/post/1228）：

void dfs(int k)
{
	if(k>n)
	{
		for(int i=1;i<=n;i++)
		{
			cout<<a[i]<<" ";
		}
		cout<<endl;
		return;
	}
	for(int i=1;i<=n;i++)
	{
		if(f[i]==0)
		{
			a[k]=i;
			f[i]=1;
			dfs(k+1);
			f[i]=0;			
		}
	}
}

完整代码：

#include <bits/stdc++.h>
using namespace std;
int n,a[1010],f[1010],sum;
void dfs(int k)
{
	if(k>n)
	{
		for(int i=1;i<=n;i++)
		{
			cout<<a[i]<<" ";
		}
		cout<<endl;
		return;
	}
	for(int i=1;i<=n;i++)
	{
		if(f[i]==0)
		{
			a[k]=i;
			f[i]=1;
			dfs(k+1);
			f[i]=0;			
		}
	}
}
int main()
{
	cin>>n;
	dfs(1);
}