https://www.zybuluo.com/ysner/note/1243396
题面
有(n)个排成一圈的格子，并且已知正整数(k)和(m)，你需要往每个格子中填入一个大于等于(k)的正整数。将相邻的一些格子（或一个单独的格子）中的数加起来，可以产生一个新的数。假设使用格子中的数可以产生出(m,m+1,…i)，但不能产生(i+1)。求出往格子中填入哪些数，可以使得(i)尽量大。
对于同一个环，输出字典序最小的方案。
- (30pts nleq5)
- (100pts nleq6,m,kleq20)
解析
看这部分分分布就知道是暴搜＋剪枝。
(30pts)算法
卡着复杂度枚举每个数，再枚举两端点找出产生的所有数即可。(好像是(k～k+18))
至于怎么去重，我傻逼地打了哈希，只能过样例。
实际上保证后面每位数不比第一位小就可以了啊。
(100pts)算法
可以打表发现，填入的数最大为(k+15)。
于是继续暴枚就能过了。
复杂度(O(16^6n^2)=O(6*10^8)),然而由于前面枚举的限制，复杂度不满（除以(6)）。
附上题解剪枝：
假设当前已经确定前(k)个格子中的数。将前(k)个格子不能产生的大于等于(m)的数从小到大排序,设为(a_1,a_2,...)。假设由后面(n-k)个格子最多可以再产生(x)个数,则第(k+1)个数不能超过 (a[x])。
加上这个剪枝似乎快(3)倍，然而懒得打。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<map>
#define re register
#define il inline
#define ll long long
#define q 15
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int mod=1e9+7,N=20,M=1e5+100;
int n,m,k,a[N],ans[M][N],tot,p[N],tong[M],anss,top;
ll jc[70];
map<ll,bool>vis;
il ll gi()
{
re ll x=0,t=1;
re char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
if(ch=='-') t=-1,ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
return x*t;
}
il int check()
{
fp(i,n+1,n+n) a[i]=a[i-n];
fp(i,1,n+n) p[i]=p[i-1]+a[i];
fp(i,1,p[n+n]) tong[i]=0;
fp(l,1,n)
fp(r,l,l+n-1)
tong[p[r]-p[l-1]]=1;
re int x=m;
while(tong[x]) ++x;--x;
if(x>anss) {anss=x;tot=0;return 1;}
return (x==anss);
}
int main()
{
freopen("circle.in","r",stdin);
freopen("circle.out","w",stdout);
jc[0]=1;fp(i,1,60) jc[i]=jc[i-1]*2;
n=gi();m=gi();k=gi();
if(n==5)
for(a[1]=k;a[1]<=k+q;a[1]++)
for(a[2]=a[1];a[2]<=k+q;a[2]++)
for(a[3]=a[1];a[3]<=k+q;a[3]++)
for(a[4]=a[1];a[4]<=k+q;a[4]++)
for(a[5]=a[1];a[5]<=k+q;a[5]++)
if(check()) ans[++tot][1]=a[1],ans[tot][2]=a[2],ans[tot][3]=a[3],ans[tot][4]=a[4],ans[tot][5]=a[5];
if(n==6)
for(a[1]=k;a[1]<=k+q;a[1]++)
for(a[2]=a[1];a[2]<=k+q;a[2]++)
for(a[3]=a[1];a[3]<=k+q;a[3]++)
for(a[4]=a[1];a[4]<=k+q;a[4]++)
for(a[5]=a[1];a[5]<=k+q;a[5]++)
for(a[6]=a[1];a[6]<=k+q;a[6]++)
if(check()) ans[++tot][1]=a[1],ans[tot][2]=a[2],ans[tot][3]=a[3],ans[tot][4]=a[4],ans[tot][5]=a[5],ans[tot][6]=a[6];
printf("%d
",anss);
fp(i,1,tot)
{
fp(j,1,n) printf("%d ",ans[i][j]);puts("");
}
fclose(stdin);
fclose(stdout);
return 0;
}