其实我10.9就做了这套题，当时瞎jb搞都有230，可见这套题有多水。不过我今天才把这套题搞完，就来写个总结。

小G搭积木(box)

当时我写的二分答案，下界是1，上界是n，然后贪心看能不能放得下即可。不过只有60分，具体原因尚不明确。

int n,m,x[5005],lef[5005];

inline bool cmp(int a,int b)
{
    return a>b;
}

inline bool can(int num)
{
    for (int i=1;i<=n;i++) lef[i]=x[i];
    for (int i=num+1;i<=n;i++)
    {
        int mx=0,mxleft=0;
        for (int j=num;j;j--)
        {
            if (lef[j]>mxleft)
            {
                mx=j;
                mxleft=lef[j];
            }
        }
        if (mxleft<1) return 0;
        else lef[mx]=min(lef[mx]-1,x[i]);
    }
    return 1;
}

int main()
{
    n=read();
    for (int i=1;i<=n;i++) x[i]=read();
    sort(x+1,x+n+1,cmp);
    int l=0,r=n,mid;
    while (l<r)
    {
        mid=(l+r)/2;
        if (can(mid)) r=mid-1;
        else l=mid+1;
    }
    printf("%d",l);
    return 0;
}

看了题解才知道这题就是一个裸的贪心。

很容易想到，承重量大的肯定要放在下面才会最优。所以我们把积木按照承重量从小到大排序，然后枚举每一列看能否把当前积木放在它的下面。如果有多列都可以放，那么肯定放积木个数最多的那列最优；如果都放不下，就新开一列。

int f[5005],n,m,s[5005];

int main()
{
    n=read();
    for (int i=1;i<=n;i++) s[i]=read();
    sort(s+1,s+n+1);
    m=1;
    f[1]=1;
    for (int i=2;i<=n;i++)
    {
        bool putin=0;
        int mx=0,mxid=0;
        for (int j=1;j<=m;j++)
        {
            if (f[j]>s[i]) continue;
            putin=1;
            if (f[j]>mx)
            {
                mx=f[j];
                mxid=j;
            }
        }
        if (!putin) f[++m]=1;
        else f[mxid]++;
    }
    printf("%d",m);
    return 0;
}

小G的城堡(castle)

真·大水题

把题意翻译成人话就是前k个点必须能到达1号点，后面的点都不能到达1号点。

我们先考虑后面的点。因为前k个点都能与1号点相连，所以后面的点不能与前k个点相连，那么它们只能互相连，方案数就是 $ \left( n-k\right) ^{n-k} $。

然后考虑前k个点。我当时不知道用什么公式，但是发现k很小 $ (k<=\min (8,n)) $ ，所以就暴搜枚举每个点连哪个点即可：

get_ans1()枚举连哪个点，dfs()验证每个点是否与1相连

bool dfs(int x)
{
    if (x==1) return 1;
    vis[x]=1;
    int y=to[x];
    if (can[y]) return 1;
    if (vis[y]) return 0;
    return can[x]=dfs(y);
}

void get_ans1(int x)
{
    if (x==k+1)
    {
        memset(can,0,sizeof(can));
        can[1]=1;
        for (int i=2;i<=k;i++)
        {
            if (can[i]) continue;
            memset(vis,0,sizeof(vis));
            if (!dfs(i)) return;
        }
        ans2++;
        return;
    }
    for (int i=1;i<=k;i++)
    {
        if (x==i && x!=1) continue;
        to[x]=i;
        get_ans1(x+1);
        to[x]=0;
    }
    return;
}

然后得到一个表：

int ans2_table[10]={0,1,2,9,64,625,7776,117649,2097152};

不过好像有个结论是方案数为 $ k ^{k-1} $

最后把两种方案数乘起来就是答案了。

#define ll long long
#define ha 1000000007

ll n,k,cnt=1,ans2,to[10],ans2_table[10]={0,1,2,9,64,625,7776,117649,2097152};
bool vis[10],can[10];

inline ll get_ans()
{
    ll x=n-k,y=n-k;
    ll z=1;
    while (y!=0)
    {
        if (y%2) z=(z*x)%ha;
        y/=2;
        x=((x%ha)*(x%ha))%ha;
    }
    return z;
}

int main()
{
    n=read(); k=read();
    ll ans=get_ans();
    ans=(ans*ans2_table[k])%ha;
    printf("%lld",ans);
    return 0;
}

跳跃(jump)

我当时一拿到题就直接无脑记忆化搜索。$ f[pos][last] $ 表示当前位置是pos，上一次跳了last距离。

int dfs(int pos,int last)
{
    if (pos>mx) return 0;
    if (f[pos][last]!=-1) return f[pos][last];
    f[pos][last]=have_gold[pos];
    int maxx=max(dfs(pos+last,last),dfs(pos+last+1,last+1));
    if (last>1) maxx=max(maxx,dfs(pos+last-1,last-1));
    f[pos][last]+=maxx;
    return f[pos][last];
}

然后70分就get了。当时还很开心，殊不知改下数组大小就能A了

看了题解才发现即使最开始 $ d=1 $ ，最多到跳350的距离其实就已经超过30000了 $ (\dfrac {350\times \left( 350+1\right) }{2} = 61425 > 30000) $ ，所以把数组 $ f[1005][1005] $ 改成 $ f[30005][705] $ 就A了。

int gd,n,m,d,f[30005][1405],mx,have_gold[30005];

int dfs(int pos,int last)
{
    if (pos>mx) return 0;
    if (f[pos][last]!=-1) return f[pos][last];
    f[pos][last]=have_gold[pos];
    int maxx=max(dfs(pos+last,last),dfs(pos+last+1,last+1));
    if (last>1) maxx=max(maxx,dfs(pos+last-1,last-1));
    f[pos][last]+=maxx;
    return f[pos][last];
}

int main()
{
    n=read(); d=read();
    memset(f,-1,sizeof(f));
    for (int i=1;i<=n;i++) gd=read(),have_gold[gd]++,mx=max(mx,gd);
    printf("%d",dfs(d,d));
    return 0;
}

upd:经lsq大佬提醒，如果d很大的话last也会很大，所以其实只维护偏移值才是正解，不过数据很水我那样也就过了。

这里放一个我后来参照std写的代码，其实原程序改一下应该就行了，但我懒的改。

int gd,n,m,d,f[30005][705],mx,have_gold[30005];

int main()
{
    n=read(); d=read();
    for (int i=1;i<=n;i++)
    {
        gd=read();
        have_gold[gd]++;
        mx=max(mx,gd);
    }
    for (int i=mx;i>=d;i--)
    {
        for (int j=0;j<=700;j++)
        {
            int k=j-350;
            if (d+k<=0) continue;
            f[i][j]=have_gold[i];
            int nxt=i+d+k;
            if (nxt<=mx) f[i][j]+=max(f[nxt][j],max(f[nxt][j-1],f[nxt][j+1]));
        }
    }
    printf("%d",max(f[d][350],max(f[d][349],f[d][351])));
    return 0;
}

总结

总的来说这套题打的还不错，有60+100+70=230分，不过第三题那30分确实很可惜。还是应该多分析一下题，不要无脑写完就跑，自己认为的暴力没准就是正解。

以上。

本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
This work is licensed under a CC BY-NC-SA 4.0 International License.
本文链接：https://llf0703.com/p/contest-summary-3.html