#创作计划# 手写栈
2025-02-05 12:16:08
发布于：浙江
199阅读
0回复
0点赞
深搜想必大家都不陌生，例如选数一题,大家肯定会很快地写出如下代码。
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,k,a[21];
struct Node{
int idx,cnt,sum;
};
bool isprime(int x){
if(x<=1) return 0;
for(int i=2;i<=x/i;i++) if(x%i==0) return 0;
return 1;
}
int dfs(int idx,int cnt,int sum){
if(idx>n || cnt>=k || n-idx+1<(k-cnt)){
if(cnt==k) ans+=isprime(sum);
continue;
}
return dfs(idx+1,cnt,sum+a[idx])+dfs(idx+1,cnt,sum);
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin>>n>>k;
for(int i=1;i<=n;i++) cin>>a[i];
cout<<dfs(1,0,0);
return 0;
}
没错，这样是正解。
可还记得我初学深搜时，老师说过：“像这样的dfs使用的是系统栈，如果dfs层数过多，就会RE，适得其反。”，这是候，老师就引出了递推。课后我问老师：”你说的是‘这样的dfs使用的是系统栈’，那有没有‘那样的dfs使用的是别的栈’“，老师说有，是手写栈。老师当场教了我，我当场学了。
不过后来我发现手写栈不怎么实用，渐渐忘了。
今年CSP，大家应该都知道，不少人J组T2写深搜only 60 ，遗憾一年，我同学也是其中之一。
为了避免这类事发生，我想还是要讲一下。（当然，如果你看得出如何递推也可以）
回到那个代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,k,a[21];
struct Node{
int idx,cnt,sum;
};
bool isprime(int x){
if(x<=1) return 0;
for(int i=2;i<=x/i;i++) if(x%i==0) return 0;
return 1;
}
int dfs(int idx,int cnt,int sum){
if(idx>n || cnt>=k || n-idx+1<(k-cnt)){
if(cnt==k) ans+=isprime(sum);
continue;
}
return dfs(idx+1,cnt,sum+a[idx])+dfs(idx+1,cnt,sum);
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin>>n>>k;
for(int i=1;i<=n;i++) cin>>a[i];
cout<<dfs(1,0,0);
return 0;
}
为了修改它，我们可以定义一个栈
stack<int>s;
可我们的dfs有三个参数，一个int肯定不够。
So
struct Node{
int idx,cnt,sum;
};
stack<Node>s;
接下来要在主函数内调用，即压栈。
s.push({1,0,0});
然后是深搜部分
while(!s.empty()){//系统栈也是这样，空了就退出
intidx=s.top().idx,cnt=s.top().cnt,sum=s.top().sum;s.pop();//取出栈顶元素并弹出
if(idx>n || cnt>=k || n-idx+1<(k-cnt)){//边界判断,和深搜一样（加了剪枝）
//也可以不剪枝，记搜，条条大路通罗马
if(cnt==k) ans+=isprime(sum);
continue;
}
s.push({idx+1,cnt,sum+a[idx]});//调用函数，等同于压栈
s.push({idx+1,cnt,sum});
}
那么，最后代码就是这样的
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,k,a[21],ans;
struct Node{
int idx,cnt,sum;
};
stack<Node>s;
bool isprime(int x){
if(x<=1) return 0;
for(int i=2;i<=x/i;i++) if(x%i==0) return 0;
return 1;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin>>n>>k;
for(int i=1;i<=n;i++) cin>>a[i];
s.push({1,0,0});
while(!s.empty()){
int idx=s.top().idx,cnt=s.top().cnt,sum=s.top().sum;s.pop();
if(idx>n || cnt>=k || n-idx+1<(k-cnt)){
if(cnt==k) ans+=isprime(sum);
continue;
}
s.push({idx+1,cnt,sum+a[idx]});
s.push({idx+1,cnt,sum});
}
cout<<ans;
return 0;
}
总结，能者多劳，多学必好。祝大家 ++;
然后关于练习~~(练写深搜就好了)
有帮助，赞一个