[bzoj3274]Circle

https://www.zybuluo.com/ysner/note/1243396

题面

有\(n\)个排成一圈的格子，并且已知正整数\(k\)和\(m\)，你需要往每个格子中填入一个大于等于\(k\)的正整数。将相邻的一些格子（或一个单独的格子）中的数加起来，可以产生一个新的数。假设使用格子中的数可以产生出\(m,m+1,…i\)，但不能产生\(i+1\)。求出往格子中填入哪些数，可以使得\(i\)尽量大。

对于同一个环，输出字典序最小的方案。

\(30pts\ n\leq5\)
\(100pts\ n\leq6,m,k\leq20\)

解析

看这部分分分布就知道是暴搜＋剪枝。

\(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\n",anss);

      fp(i,1,tot)

	{

	  fp(j,1,n) printf("%d ",ans[i][j]);puts("");

	}

  fclose(stdin);

  fclose(stdout);

  return 0;

}

巴特西

[bzoj3274]Circle

https://www.zybuluo.com/ysner/note/1243396

题面

解析

\(30pts\)算法

\(100pts\)算法

最新文章

热门文章