自动搬运

查看原文

来自洛谷，原作者为

	kouylan 这人真的菜 | 已AFO

搬运于2025-08-24 22:02:25，当前版本为作者最后更新于2021-07-02 23:32:27，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

首先，我们先把 $I$ 当成 $0$，$X$ 当成 $1$，一个石头就变成了一个二进制数。

然后一看就可以二分答案。我们二分一个 mid，那之后的问题就变成求在 mid 以内有多少符合要求的二进制数，用类似数位 dp 的方法即可。

设 dp 状态为 $f(x,j,a,b,lim,c)$ 表示

$x,j$：填了前 $x$ 位和后 $x$ 位的数字，用了 $j$ 次相邻不同数位

$a,b$ :（都是 $0/1$）正数第 $x$ 位是 $a$，倒数第 $x$ 位是 $b$

$lim$ :（是 $0/1/2$）当前数在上限内 / 恰好压着上限 / 超过了上限（显然，最后一种情况想要合法，就只能是后 $x$ 位超上限）

$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 代码

/*
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 愉快！