剪枝例题一道

例题一

Code force round 我的思路，DFS遍历所有x，y，然后用set记录所有k，但是TLE了，最后发现，可以应用剪枝，如果一个x，y得出的k已经在set中存在了，那么不用再继续DFS后续了。

#include "bits/stdc++.h" using namespace std; using ll = long long; #define For for(int i=1;i<=n;i++) #define Whole(x) for(auto item:x) const int N = 2e5; set<int> ans; int l,a,b; void dfs(int sa,int sb){ int k=l; k/=sa;k/=sb; if(ans.find(k!=ans.end())//这两行 return;//是剪枝，避免重复DFS ans.emplace(k); if(k%a==0) dfs(sa*a,sb); if(k%b==0) dfs(sa,sb*b); } void inline solve() { cin>>a>>b>>l; ans.clear(); dfs(1,1); cout<<ans.size()<<endl; } int main() { ios::sync_with_stdio(0); cin.tie(0), cout.tie(0); int num = 1; cin >> num; while (num--) { solve(); } return 0; }

还有暴力遍历法 令l/a=la l/b=lb(余数此处不显示0) 则遍历l除以的a的次数从0到la次，分别看能除以b几次，得到不同的x y组合，从而得到不同的k加入到set里面。

#include "bits/stdc++.h" using namespace std; using ll = long long; #define For for(int i=1;i<=n;i++) #define rFor for(int i=n;i>0;i--) #define Whole(x) for(auto item:x) const int N = 2e5; void inline solve() { int a,b,l; cin>>a>>b>>l; set<int> ans; while(1){ int x=l; while(1){ ans.emplace(x); if(x%b!=0){ break; } x/=b; } if(l%a!=0){ break; } l/=a; } cout<<ans.size()<<endl; } int main() { ios::sync_with_stdio(0); cin.tie(0), cout.tie(0); int num = 1; cin >> num; while (num--) { solve(); } return 0; }