自动搬运

查看原文

来自洛谷，原作者为

	xzyxzy 被pku里高三的巨佬们虐惨了啊啊啊啊

搬运于2025-08-24 21:22:58，当前版本为作者最后更新于2018-07-16 21:12:28，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

有一个必须要知道的结论：

虽然我不知道怎么证明（等我知道了我再来更新题解）

Upd7.17：这个式子并不是正确的，比如n=7就不对，但是这是答案的极限，我们从大到小枚举答案然后想方设法构造方案，于是发现在这道题的测试点（n=2,3,4,5,6,8）上我们都可以在答案取到极限时成功构造出相应的方案

但是这个式子的含义是每个数在一种方案中有且仅有一种表示方法

计算有两种方式：

1.枚举一个分割线有n条，另一个分割线有n-1条，共n*(n-1)/2种方案，每种方案会产生两个数，然后加上全部算一起的一种方案

2.除开全部一起的方案，枚举扇区长度有n-1种，每种长度可以产生n个数，共n*(n-1)+1

所以知道了这个结论之后就很好做了，爆搜每一位是啥

注意这里n的范围是8（题面有误）

n=8我本机0.97s洛谷跑不过，所以打个表就好啦

感谢star_city、zykykyk两位大爷的帮助！

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
int n,A[20],s,ans,tot,B[20],tt;
int v[23],tong[60],out[60][10];
inline void Check(int id)
{
	if(n>4&&(!v[2]||(!v[3]&&!v[4])||(!v[5]&&!v[6]&&!v[7]&&!v[8]))) return;
	register int i,l,r,u;
	for(i=n+1;i<=n<<1;++i) A[i]=A[i-n];
	for(i=1;i<=n<<1;++i) B[i]=B[i-1]+A[i];
	for(l=1;l<=n;++l)
		for(r=l,u=l+n-1;r<=u;++r)
			tong[B[r]-B[l-1]]=id;
	for(i=1;i<=ans;++i)
		if(tong[i]!=id) return;tot++;
	for(i=1;i<=n;i++) out[tot][i]=A[i];
}
void DFS(int x)
{
	if(x>n) {if(s==ans) Check(++tt);return;}
	for(int i=1;i<=22;++i)
		if(!v[i])
		{
			A[x]=i;v[i]=1;s+=i;
			if(s<=ans) DFS(x+1);
			v[i]=0;s-=i;
		}
}
void work1();
int main()
{
	cin>>n;A[1]=1;s=1;
	printf("%d\n",ans=n*(n-1)+1);
	if(n==8)work1();DFS(2);
	for(int i=1;i<=tot;i++,puts(""))
		for(int j=1;j<=n;j++)
			printf("%d ",out[i][j]);
}
void work1()
{
	printf("1 2 10 19 4 7 9 5\n1 3 5 11 2 12 17 6\n");
	printf("1 3 8 2 16 7 15 5\n1 4 2 10 18 3 11 8\n");
	printf("1 4 22 7 3 6 2 12\n1 5 9 7 4 19 10 2\n");
	printf("1 5 15 7 16 2 8 3\n1 6 12 4 21 3 2 8\n");
	printf("1 6 17 12 2 11 5 3\n1 8 2 3 21 4 12 6\n");
	printf("1 8 11 3 18 10 2 4\n1 12 2 6 3 7 22 4\n");
	exit(0);
}