题解 P1254 【扇区填数】
xzyxzy
2018-07-16 21:12:28
有一个必须要知道的结论：
$$ans=n*(n-1)+1$$
虽然我不知道怎么证明（等我知道了我再来更新题解）
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两位大爷的帮助！
```cpp
#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);
}
```