自动搬运

查看原文

来自洛谷，原作者为

	•́へ•́╬ Unsuccessful Leaving Something attempt

搬运于2025-08-24 22:59:41，当前版本为作者最后更新于2024-06-21 10:30:05，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

赛时思路

枚举所有本质不同的 $13$ 个变量的分配方法。队友写的，搜出来几百万个方案。

然后做个矩阵，$a[i][j]$ 表示一段程序，初始 BSR 在 $i$，最后 BSR 在 $j$，最少多少步。然后矩乘一下即可。

前面的几百万乘上后面 $\mathcal O(nm^3\log)$。

思路

把分配到 bank $0$ 的变量单独拉出来搜。

然后把程序里的这些变量删了。它们固定能一次访问到。

对于剩下的程序，统计 $a[i][j]$ 表示上一个访问变量 $i$，下一个访问变量 $j$，这种情况出现的次数。如果 $i,j$ 不在同一个 bank，那么这之间就要切换 BSR，额外耗时 $a[i][j]+a[j][i]$。

然后搜剩下变量的分配。复杂度对了。

code

#include<stdio.h>
#define N 1111
#define int long long
int b,s,v,n,a[14],cnt[14],ans=1ll<<60,now,st[N],sz,rgt[N];char cmd[N][9];
struct node
{
	int l,r,a[14][14];
	inline node()
	{
		l=r=0;
		for(int i=1;i<=v;++i)for(int j=1;j<=v;a[i][j++]=0);
	}
	inline node operator*(const node&kkk)const
	{
		if(!l)return kkk;
		if(!kkk.l)return*this;
		node ans;
		ans.l=l;ans.r=kkk.r;
		for(int i=1;i<=v;++i)for(int j=1;j<=v;++j)
			ans.a[i][j]=a[i][j]+kkk.a[i][j];
		++ans.a[r][kkk.l];
		return ans;
	}
}c;
inline node parse(int l,int r)
{
	if(l==r)
	{
		node ans;
		int aa;sscanf(cmd[l]+1,"%lld",&aa);
		if(a[aa])ans.l=ans.r=aa;
		return ans;
	}
	if(cmd[l][0]=='V')return parse(l,l)*parse(l+1,r);
	if(rgt[l]^r)return parse(l,rgt[l])*parse(rgt[l]+1,r);
	node a=parse(l+1,r-1),ans;
	if(!a.l)return a;
	int b;sscanf(cmd[l]+1,"%lld",&b);
	for(;b;b>>=1,a=a*a)if(b&1)ans=ans*a;
	return ans;
}
inline void dfs1(int i)
{
	if(ans<=now)return;
	if(i==v+1)
	{
		if(c.l)++now;
		if(ans>now)ans=now;
		if(c.l)--now;
		return;
	}
	if(!a[i]){dfs1(i+1);return;}
	for(int j=1;j<b;++j)if(cnt[j]<s)
	{
		a[i]=j;++cnt[j];int lst=now;
		for(int k=1;k<i;++k)if(a[k]^j)now+=c.a[k][i]+c.a[i][k];
		dfs1(i+1);
		--cnt[j];now=lst;
		if(!cnt[j])break;
	}
}
inline void dfs0(int i)
{
	if(i==v+1)
	{
		int c0=0;
		for(int i=1;i<=v;++i)c0+=!a[i];
		if(c0^s)return;
		c=parse(0,n-1);
		dfs1(1);
		return;
	}
	a[i]=0;dfs0(i+1);
	a[i]=1;dfs0(i+1);
}
main()
{
	scanf("%lld%lld",&b,&s);v=b*s;v>13&&(v=13);
	if(b>1+(v-s-1)/(s+2>>1)+1)b=1+(v-s-1)/(s+2>>1)+1;
	for(;(scanf("%s",cmd[n])^EOF)&&(cmd[n][0]^'a');++n);
	for(int i=n-1;i>=0;--i)if(cmd[i][0]=='E')st[sz++]=i;
	else if(cmd[i][0]=='R')rgt[i]=st[--sz];
	dfs0(1);
	for(int i=0,s=1;i<n;++i)if(cmd[i][0]=='E')s/=st[--sz];
	else if(cmd[i][0]=='R'){sscanf(cmd[i]+1,"%lld",st+sz);s*=st[sz++];}
	else ans+=s;
	printf("%lld",ans);
}