首页 > 代码库 > BZOJ1166 : [Baltic2008]Magical Stones
BZOJ1166 : [Baltic2008]Magical Stones
考虑二分答案，转化为求有多少$\leq lim$的数满足条件。
从两侧往中间进行数位DP，设$f[l][r][j][x][y][z][pre][suf]$表示当前准备填的两个位置是$l$和$r$，已经有$j$对相邻的数不同，$l-1$填的是$x$，$r+1$填的是$y$，正序串和逆序串的大小关系为$z$，正序串和$lim$的大小关系为$pre$，逆序串和$lim$的大小关系为$suf$的方案数。
注意到$r=n-l+1$，因此可以省去$r$这一维，然后枚举接下来填什么数进行转移即可。
时间复杂度$O(2^6n^2k)$。
#include<cstdio>typedef long long ll;const ll inf=1LL<<61;const int N=65;int n,m,i,j,S,l,r,x,y,z,p,s,nj,nz,np,ns,A,B,a[N];ll L,R,mid,K,ans=-1,f[N][N][1<<5];inline void up(ll&a,ll b){a+=b;if(a>inf)a=inf;}inline ll check(ll mid){ for(i=n;i;i--)a[i]=mid&1,mid>>=1; for(i=1;i<=n;i++)for(j=0;j<=m;j++)for(S=0;S<32;S++)f[i][j][S]=0; ll ret=0; for(f[0][0][0]=l=1,r=n;l<=r;l++,r--)for(j=0;j<=m;j++)for(S=0;S<32;S++)if(f[l-1][j][S]){ x=S&1,y=S>>1&1,z=S>>2&1,p=S>>3&1,s=S>>4&1; if(l<r)for(A=0;A<2;A++)for(B=0;B<2;B++){ nj=j; if(l>1)nj+=(A^x)+(B^y); if(nj>m)continue; if(z)nz=1; else{ if(A>B)continue; nz=A<B; } if(p)np=1; else{ if(A>a[l])continue; np=A<a[l]; } if(B==a[r])ns=s;else ns=B>a[r]; up(f[l][nj][A|(B<<1)|(nz<<2)|(np<<3)|(ns<<4)],f[l-1][j][S]); } if(l==r)for(A=0;A<2;A++){ if(l>1&&j+(A^x)+(A^y)>m)continue; if(!p&&(A>a[l]||A==a[l]&&s))continue; up(ret,f[l-1][j][S]); } } if(n%2==0)for(j=0;j<=m;j++)for(S=0;S<32;S++)if(f[l-1][j][S]){ x=S&1,y=S>>1&1; if(j+(x^y)>m)continue; p=S>>3&1,s=S>>4&1; if(!p&&s)continue; up(ret,f[l-1][j][S]); } return ret;}int main(){ scanf("%d%d%lld",&n,&m,&K); L=0;R=(1LL<<n)-1; while(L<=R)if(check(mid=(L+R)>>1)>=K)R=(ans=mid)-1;else L=mid+1; if(ans<0)puts("NO SUCH STONE");else for(i=n-1;~i;i--)putchar(ans>>i&1?‘X‘:‘I‘); return 0;}
BZOJ1166 : [Baltic2008]Magical Stones
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。