P9234 [蓝桥杯 2023 省 A] 买瓜 题解

· · 题解

upd on 2025/7/20：攻克了 hack 数据，申请再次通过。

已在文末给出最新代码。

https://www.luogu.com.cn/record/225727835

题意简（？）述：

经过上一次惨痛的经历后，郝哥痛改前非，不再卖生瓜蛋子，秤也没有了吸铁石。然而刘华强并不打算放过他。

有一个人再来买瓜。

郝哥望着那辆熟悉的摩托车，没等华强发话，便喊道：“10^{{10}^{-9961}} 块钱一斤！没有大棚瓜！保熟！”

“给我挑亿个！”

郝哥刚转过身，看个架子上 n 个分别重 a_i 斤的瓜，刚想挑瓜，华强又说：“今天我要请宋大哥吃答辩，得买 m 斤西瓜，你这瓜保够吗？”

郝哥明白，华强又来找茬了。

华强拿起了上次他劈西瓜和郝哥的刀，对郝哥说：“你这瓜要是管够我肯定要啊，那它要是不够怎么办啊？”

郝哥知道，华强刀功了得，他可以把任何瓜劈成完全等重的两份，不过每个瓜只劈一刀，尽管华强可以以很短的时间劈开一个瓜（<10^{{10}^{-9961}} s），不过他不想白费力气，他想让郝哥在 1s 之内告诉他最少需要劈几个瓜，否则就要劈了郝哥。

郝哥不想再被劈一刀，所以他找到了你。

如果郝哥无论如何都会被劈（没有任何一种可行方案能让华强买到他想要重量的瓜）。输出 -1。

part one：

直接爆搜加一个人人都会的剪枝就行了，时间复杂度 O(3^n)。

#include<iostream>
using namespace std;
int n,a[31],ans=114514;
long long m;
void LHQ(int G,int P,int J,long long sum){
    if(sum>m) return;
    if(G>n){
        //cout<<sum<<endl;
        if(sum==m) ans=min(ans,J);
        return;
    }
    if(P==0) sum+=a[G]*2;
    else if(P==1) sum+=a[G],J++;
    for(int i=0;i<3;i++) LHQ(G+1,i,J,sum);
}
int main(){
    cin>>n>>m;
    m*=2;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=0;i<3;i++) LHQ(1,i,0,0);
    cout<<ans;
}

这个怎么样？

………外卖……萨日朗……郝哥萨日朗……

part two：

考虑折半搜索，时间复杂度 O(3^{\frac n 2})。

#include<iostream>
#include<unordered_map>
using namespace std;
int n,N,a[31],ans=114514;
long long m;
unordered_map <int,int> PII;
void LHQ(int G,int P,int J,long long sum){
    if(sum>m) return;
    if(sum==m){
        PII[sum]=J;
        return;
    }
    if(G==N+1){
        if(sum<=m) PII[sum]=J;
        return;
    }
    if(P==0) sum+=a[G]*2;
    else if(P==1) sum+=a[G],J++;
    for(int i=0;i<3;i++) LHQ(G+1,i,J,sum);
}
void HG(int G,int P,int J,long long sum){
    if(sum>m) return;
    if(sum==m){
        ans=min(ans,PII[sum]+J);
        return;
    }
    if(G==n+1){
        //cout<<sum<<endl;
        if(sum<=m&&PII.count(m-sum)) ans=min(ans,PII[m-sum]+J);
        return;
    }
    if(P==0) sum+=a[G]*2;
    else if(P==1) sum+=a[G],J++;
    for(int i=0;i<3;i++) HG(G+1,i,J,sum);
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>m;
    N=n/2;
    m*=2;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=0;i<3;i++) LHQ(1,i,0,0);
    for(int i=0;i<3;i++) HG(N+1,i,0,0);
    if(ans>100000) cout<<-1;
    else cout<<ans;
}

这个怎么样？

………外卖……萨日朗……郝哥萨日朗……

part three：

时间复杂度肯定是没假的，不可能比这更低了。

考虑剪枝优化。

最优性剪枝：当现在劈瓜的个数已经比目前最优的个数多了，就不用再继续搜下去了。

#include<iostream>
#include<unordered_map>
using namespace std;
int n,N,a[31],ans=114514;
long long m;
unordered_map <int,int> PII;
void LHQ(int G,int P,int J,long long sum){
    if(sum>m) return;
    if(sum==m){
        PII[sum]=J;
        return;
    }
    if(G==N+1){
        if(sum<=m) PII[sum]=J;
        return;
    }
    if(P==0) sum+=a[G]*2;
    else if(P==1) sum+=a[G],J++;
    for(int i=0;i<3;i++) LHQ(G+1,i,J,sum);
}
void HG(int G,int P,int J,long long sum){
    if(sum>m||J>ans) return;
    if(sum==m){
        ans=min(ans,PII[sum]+J);
        return;
    }
    if(G==n+1){
        //cout<<sum<<endl;
        if(sum<=m&&PII.count(m-sum)) ans=min(ans,PII[m-sum]+J);
        return;
    }
    if(P==0) sum+=a[G]*2;
    else if(P==1) sum+=a[G],J++;
    for(int i=0;i<3;i++) HG(G+1,i,J,sum);
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin>>n>>m;
    N=n/2;
    m*=2;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=0;i<3;i++) LHQ(1,i,0,0);
    for(int i=0;i<3;i++) HG(N+1,i,0,0);
    if(ans==114514) cout<<-1;
    else cout<<ans;
}

这个怎么样？

………外卖……萨日朗……郝哥萨日朗……

part four：

很明显不能再进一步剪枝了，我们考虑其它的优化。

优化搜索顺序：把 a 数组进行排序后再搜索。

减少传参：容易发现当前搜索的这个瓜是否被劈不重要，只关心最后总共劈几个就行。

预处理：对 a 数组进行一个后缀和，方便判断超过下界的无解情况。

调整块长折半的长度：这个需要注意一下调完的长度可能会 >n 或 <0，需要避免。

卡时：这个不用我多说了吧！

#include<bits/stdc++.h>
using namespace std;
int n,N,ans=114514,m,a[32],b[32],cnt;
unordered_map <int,int> PII;
void LHQ(int G,int J,int sum){
    cnt++;
    if(cnt>7e6) return;
    if(sum>m) return;
    if(G==N+1){
        if(PII[sum]) PII[sum]=min(PII[sum],J+1);
        else PII[sum]=J+1;
        return;
    }
    LHQ(G+1,J,sum+a[G]);
    LHQ(G+1,J+1,sum+a[G]/2);
    LHQ(G+1,J,sum);
}
void HG(int G,int J,int sum){
    cnt++;
    if(cnt>1.5e7){
        cout<<ans<<endl;
        return;
    }
    if(sum>m||J>ans) return;
    if(sum==m){
        ans=min(ans,PII[sum]+J);
        return;
    }
    if(G==n+1){
        if(PII[m-sum]) ans=min(ans,J+PII[m-sum]-1);
        return;
    }
    HG(G+1,J,sum+a[G]);
    HG(G+1,J+1,sum+a[G]/2);
    HG(G+1,J,sum);
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    N=n/2;
    m*=2;
    for(int i=1;i<=n;i++) cin>>a[i],a[i]*=2;
    sort(a+1,a+1+n);
    LHQ(1,0,0);
    HG(N+1,0,0);
    if(ans==114514) cout<<-1;
    else cout<<ans;
}

这个怎么样？

满意了吧？

part five：

What's up，你是故意找茬是不是？你要不要吧！

你瞅瞅现在哪有瓜？

大棚。

#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
int n,N,ans=114514,m,a[32],cnt;
long long b[32];
cc_hash_table <int,int> PII;
void LHQ(int G,int J,int sum){
    if(sum>m) return;
    if(sum+b[G]<m) return;
    if(sum==m){
        PII[sum]=J;
        return;
    }
    if(G==N+1){
        if(PII[sum]) PII[sum]=min(PII[sum],J+1);
        else PII[sum]=J+1;
        return;
    }
    LHQ(G+1,J,sum+a[G]);
    LHQ(G+1,J+1,sum+a[G]/2);
    LHQ(G+1,J,sum);
}
void HG(int G,int J,int sum){
    if(sum>m||J>ans) return;
    if(sum==m){
        ans=min(ans,PII[sum]+J);
        return;
    }
    if(G==n+1){
        if(PII[m-sum]) ans=min(ans,J+PII[m-sum]-1);
        return;
    }
    HG(G+1,J,sum+a[G]);
    HG(G+1,J+1,sum+a[G]/2);
    HG(G+1,J,sum);
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    N=min(n/2+1,n-2);
    m*=2;
    for(int i=1;i<=n;i++) cin>>a[i],a[i]*=2;
    sort(a+1,a+1+n);
    for(int i=n;i>=1;i--) b[i]=b[i+1]+a[i];
    LHQ(1,0,0);
    HG(N+1,0,0);
    if(ans==114514) cout<<-1;
    else cout<<ans;
}

这个怎么样？

满意了吧？

写在最后：

这题从我第一次提交到第一次 AC 共提交了 135 次。

upd：149 次，被 hack 了就不算 AC。

感谢@waauto 对我的一些帮助。

最新代码：

#include<bits/stdc++.h>
#include<bits/extc++.h>
#define int long long
using namespace std;
using namespace __gnu_pbds;
int n,N,ans=114514,m,a[32],cnt,b[32];
cc_hash_table <int,int> PII;
void LHQ(int G,int J,int sum){
    if(sum>m) return;
    if(sum+b[G]<m) return;
    if(sum==m){
        PII[sum]=J;
        return;
    }
    if(G==N+1){
        if(PII[sum]) PII[sum]=min(PII[sum],J+1);
        else PII[sum]=J+1;
        return;
    }
    LHQ(G+1,J,sum+a[G]);
    LHQ(G+1,J+1,sum+a[G]/2);
    LHQ(G+1,J,sum);
}
void HG(int G,int J,int sum){
    if(sum>m||J>ans) return;
    if(sum==m){
        ans=min(ans,PII[sum]+J);
        return;
    }
    if(G==n+1){
        if(PII[m-sum]) ans=min(ans,J+PII[m-sum]-1);
        return;
    }
    HG(G+1,J,sum+a[G]);
    HG(G+1,J+1,sum+a[G]/2);
    HG(G+1,J,sum);
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    N=min(n/2+1,n-2);
    m*=2;
    for(int i=1;i<=n;i++) cin>>a[i],a[i]*=2;
    sort(a+1,a+1+n);
    for(int i=n;i>=1;i--) b[i]=b[i+1]+a[i];
    LHQ(1,0,0);
    HG(N+1,0,0);
    if(ans==114514) cout<<-1;
    else cout<<ans;
}