题解【[BalticOI 2008]魔法石】
kouylan
·
·
题解
首先，我们先把 I 当成 0，X 当成 1，一个石头就变成了一个二进制数。
然后一看就可以二分答案。我们二分一个 mid，那之后的问题就变成求在 mid 以内有多少符合要求的二进制数，用类似数位 dp 的方法即可。
设 dp 状态为 f(x,j,a,b,lim,c) 表示
$a,b$ :（都是 $0/1$）正数第 $x$ 位是 $a$，倒数第 $x$ 位是 $b
$c$ :（是 $0/1$）当前填进去的串从前往后读和从后往前读 小于 / 相等（如果大于就不合法，所以不记录）
这些之后可以填数字的方案数。每次 $x$ 扫到超过一半就停止，最终总个数就是 $f(n,0,0,0,1,1)$。
转移采用记忆化搜索，每次枚举当前状态下，前后两位要天的数，记为 $a1,b1$。那新的 $j$ 和 $c$ 就很好算了，所以主要讲新的 $lim$（记为 $lim1$）的计算方式。
如果 $a1$ 大于当前位上限，那转移过来的 $lim$ 就必须等于 $0$。
如果 $a1$ 小于当前位上限，那 $lim1$ 就直接等于 $0$。
否则 $a1$ 等于当前位上限，如果 $b1$ 大于当前位上限，$lim1=2$（后面超了），如果 $b1$ 小于当前位上限，$lim1=1$（把后面超的消掉了，但依然要保证前面的不能超上限）。
这样转移就做完了，二分复杂度 $O(n)$，dp 复杂度 $O(24nk)$，总复杂度 $O(24n^2k)$，是 $O(n^3)$ 级的，虽然能过，但依然可以不用二分优化到 $O(n^2)$ 级。
下面是 AC 代码
```cpp
/*
luogu P4663
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,m,rk,ans,f[65][65][2][2][3][2];
int dig[65],num;
int dp(int x,int j,int a,int b,int lim,int c)
{
if(j>m)
return 0;
if(x==(n+1)/2)
{
if(n%2==0)
{
if(lim==2)
return 0;
j += (a!=b);
return j<=m ? 1 : 0;
}
if(n%2==1)
{
int res=0;
for(int d=0;d<=1;d++)
{
if(lim==2 && d>=dig[n/2+1])
break;
if(lim==1 && d>dig[n/2+1])
break;
int t=(d!=a)+(d!=b);
if(j+t<=m)
res++;
}
return res;
}
}
if(f[x][j][a][b][lim][c]>=0)
return f[x][j][a][b][lim][c];
int res=0;
for(int a1=0;a1<=1;a1++)
for(int b1=0;b1<=1;b1++)
{
if(lim>=1 && a1>dig[x])
break;
int t=0,c1=c;
if(x<n)
{
if(a!=a1)
t++;
if(b!=b1)
t++;
}
if(a1>b1 && c==1)
continue;
if(a1==b1)
c1 = c;
if(a1<b1)
c1 = 0;
if(lim==0)
res += dp(x-1,j+t,a1,b1,lim,c1);
else
{
int lim1=lim;
if(a1<dig[x])
lim1 = 0;
else if(b1>dig[n-x+1])
lim1 = 2;
else if(b1<dig[n-x+1])
lim1 = 1;
res += dp(x-1,j+t,a1,b1,lim1,c1);
}
}
return f[x][j][a][b][lim][c] = res;
}
int calc(int x)
{
num = x;
memset(dig,0,sizeof(dig));
memset(f,-1,sizeof(f));
int tmp=x;
for(int i=1;i<=n;i++)
dig[i] = tmp%2, tmp /= 2;
return dp(n,0,0,0,1,1);
}
signed main()
{
cin>>n>>m>>rk;
int l=0,r=(1ll<<n)-1;
while(l<=r)
{
int mid=l+r>>1;
int res=calc(mid);
if(res>=rk)
ans = mid, r = mid-1;
else
l = mid+1;
}
if(calc(ans)<rk)
return puts("NO SUCH STONE"), 0;
for(int i=n;i>=1;i--)
if(ans>>i-1&1)
cout<<'X';
else
cout<<'I';
return puts(""), 0;
}
```
祝大家 AC 愉快！