[关闭]
@ysner 2018-08-08T20:09:41.000000Z 字数 2154 阅读 1870

[bzoj3274]Circle

搜索 剪枝


题面

个排成一圈的格子,并且已知正整数,你需要往每个格子中填入一个大于等于的正整数。将相邻的一些格子(或一个单独的格子)中的数加起来,可以产生一个新的数。假设使用格子中的数可以产生出,但不能产生。求出往格子中填入哪些数,可以使得尽量大。
对于同一个环,输出字典序最小的方案。

解析

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

算法

卡着复杂度枚举每个数,再枚举两端点找出产生的所有数即可。(好像是)

至于怎么去重,我傻逼地打了哈希,只能过样例。
实际上保证后面每位数不比第一位小就可以了啊。

算法

可以打表发现,填入的数最大为
于是继续暴枚就能过了。
复杂度,然而由于前面枚举的限制,复杂度不满(除以)。

附上题解剪枝:
假设当前已经确定前个格子中的数。将前个格子不能产生的大于等于的数从小到大排序,设为。假设由后面个格子最多可以再产生个数,则第个数不能超过
加上这个剪枝似乎快倍,然而懒得打。

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstdlib>
  4. #include<cstring>
  5. #include<cmath>
  6. #include<algorithm>
  7. #include<map>
  8. #define re register
  9. #define il inline
  10. #define ll long long
  11. #define q 15
  12. #define max(a,b) ((a)>(b)?(a):(b))
  13. #define min(a,b) ((a)<(b)?(a):(b))
  14. #define fp(i,a,b) for(re int i=a;i<=b;i++)
  15. #define fq(i,a,b) for(re int i=a;i>=b;i--)
  16. using namespace std;
  17. const int mod=1e9+7,N=20,M=1e5+100;
  18. int n,m,k,a[N],ans[M][N],tot,p[N],tong[M],anss,top;
  19. ll jc[70];
  20. map<ll,bool>vis;
  21. il ll gi()
  22. {
  23. re ll x=0,t=1;
  24. re char ch=getchar();
  25. while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  26. if(ch=='-') t=-1,ch=getchar();
  27. while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  28. return x*t;
  29. }
  30. il int check()
  31. {
  32. fp(i,n+1,n+n) a[i]=a[i-n];
  33. fp(i,1,n+n) p[i]=p[i-1]+a[i];
  34. fp(i,1,p[n+n]) tong[i]=0;
  35. fp(l,1,n)
  36. fp(r,l,l+n-1)
  37. tong[p[r]-p[l-1]]=1;
  38. re int x=m;
  39. while(tong[x]) ++x;--x;
  40. if(x>anss) {anss=x;tot=0;return 1;}
  41. return (x==anss);
  42. }
  43. int main()
  44. {
  45. freopen("circle.in","r",stdin);
  46. freopen("circle.out","w",stdout);
  47. jc[0]=1;fp(i,1,60) jc[i]=jc[i-1]*2;
  48. n=gi();m=gi();k=gi();
  49. if(n==5)
  50. for(a[1]=k;a[1]<=k+q;a[1]++)
  51. for(a[2]=a[1];a[2]<=k+q;a[2]++)
  52. for(a[3]=a[1];a[3]<=k+q;a[3]++)
  53. for(a[4]=a[1];a[4]<=k+q;a[4]++)
  54. for(a[5]=a[1];a[5]<=k+q;a[5]++)
  55. 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];
  56. if(n==6)
  57. for(a[1]=k;a[1]<=k+q;a[1]++)
  58. for(a[2]=a[1];a[2]<=k+q;a[2]++)
  59. for(a[3]=a[1];a[3]<=k+q;a[3]++)
  60. for(a[4]=a[1];a[4]<=k+q;a[4]++)
  61. for(a[5]=a[1];a[5]<=k+q;a[5]++)
  62. for(a[6]=a[1];a[6]<=k+q;a[6]++)
  63. 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];
  64. printf("%d\n",anss);
  65. fp(i,1,tot)
  66. {
  67. fp(j,1,n) printf("%d ",ans[i][j]);puts("");
  68. }
  69. fclose(stdin);
  70. fclose(stdout);
  71. return 0;
  72. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注