7-1 Forever (20分)

这个题是我想复杂了，一时半会没明白，导致只能拿半分。
最开始我用dfs，写出来堆栈溢出，于是便放弃了原来的思路，转而找规律，未果，，，，
后来发现还是dfs+剪枝 给力，我之前一直不注重剪枝的作用，只是在边界情况下才会使用，不曾想被这个题目狠狠抽了一巴掌。
3000ms的题竟然最大只需要6ms…

剪枝就是挨个讨论，从最高位开始，由于最高位不能为0(不然就是K-1位了），然后每次dfs需要讨论两种情况：

1.剩余位都取最大，组成的数能否加起来等于 sum
2.当然组成的位值，是否小于等于sum
若不是，则剪枝，return;

直接附代码：

#include
#include
#include
#include
#include
using namespace std;
int N, K, sum;
int gcd(int a, int b) {return b == 0 ? a : gcd(b, a%b);
}
bool isprime(int a) {if (a <= 2)return false;for (int i = 2; i*i <= a; i++) {if (a%i == 0)return false;}return true;
}
vector<int>tmp;
vector<vector<int>>ans;
void dfs(int K, int tsum) {if (K * 9 < tsum)return;if (K == 0 && tsum == 0) {ans.push_back(tmp);return;}int cnt = 0;for (int i = 0; i < tmp.size(); i++) {cnt += tmp[i];}if (cnt > sum)return;for (int i = 0; i <= 9; i++) {tmp.push_back(i);dfs(K - 1, tsum - i);tmp.pop_back();}
}
int vtoint(vector<int>t) {int cnt = 0;for (int i = 0; i < t.size(); i++) {cnt = cnt * 10 + t[i];}return cnt;
}
int getnum(int x) {int cnt = 0;while (x != 0) {cnt += x % 10;x /= 10;}return cnt;
}
int main() {scanf("%d", &N);for (int i = 0; i < N; i++) {scanf("%d%d", &K, &sum);int flag = 0;printf("Case %d\n", i + 1);if (sum >= K * 9) {printf("No Solution\n");continue;}map<int, vector<int>>Ma;for (int i = 1; i <= 9; i++) {ans.clear();tmp.clear();tmp.push_back(i);dfs(K-1,sum-i);for (int j = 0; j < ans.size(); j++) {int y = vtoint(ans[j]);int t = getnum(y+1);if (isprime(gcd(t, sum))) {Ma[t].push_back(y);}}}if (Ma.size() == 0)printf("No Solution\n");else {for (auto it = Ma.begin(); it != Ma.end(); it++) {for (int j = 0; j < it->second.size(); j++) {printf("%d %d\n", it->first, it->second[j]);}}}}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！