P10619 [ICPC2013 WF] Harvard 题解

_•́へ•́╬_ · 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);
}