题解：P16806 [蓝桥杯 2026 国 Python A] 糖分极限

· · 题解

前言：还没有搜索的题解，交一手。

solution

题意很清楚了，不再赘述。因为只有两种增加和一次减少情况较少，考虑动态规划或搜索。因为题解已经有动规了，所以我来讲一下搜索。（其实本质并无区别，但是主包觉得搜索更好想一点）

关于参数，包括两个：一个表示可以组成的数，一个表示是否使用过一次开合跳，如果使用开合跳显示为 1，否则为 0。如果没有使用过就可以进入第三个情况。最后，对于所有凑出来的情况取 \max。值得注意的是，因为每一个数可能被凑出很多次，所以我们对每种情况打个标记，就可以做到 90pts->100pts。

#include <bits/stdc++.h>
using namespace std;
int n,a,b,ans=0;
const int N=1e6+10 ;
bool vis[N][2] ;
void dfs(int cnt,bool used) {
    if(cnt>n) return ;
    if(vis[cnt][used]) return ;
    vis[cnt][used]=1;
    ans=max(ans,cnt);
    dfs(cnt+a,used); dfs(cnt+b,used) ;
    if(used!=1) dfs(cnt/2,1) ;
}
signed main() {
    ios::sync_with_stdio(0);cin.tie(0); cout.tie(0) ;
    cin>>n>>a>>b; 
    dfs(0,0) ;
    cout<<ans ;
    return 0;
}

真的对吗？实则不然。

主包在写题解时构了一个hack，把自己代码跑RE了。
下面是hack：（正确性显然） 

1000000 1 1
1000000

所以在经过一秒的思考以后，我发现此时的代码会因跑了 10^6 次而爆栈。遂改为广搜，因为队列的空间的不会算入函数里，所以就安全啦。

queue<pair<int,bool> > q;
q.push({0,0});
while(!q.empty()){
    auto[cnt,used]=q.front(); q.pop();
    if(cnt>n)continue;
    if(vis[cnt][used]) continue;
    vis[cnt][used]=1;
    ans=max(ans,cnt);
    q.push({cnt+a,used});
    q.push({cnt+b,used});
    if(!used) q.push({cnt/2,1});
}

最后警示后人：大家在写搜索时一定要考虑函数栈的问题，不然很可能赛时挂分啊。