sicily 1002

这题没什么说的。。就是深搜，只不过我搞了一个小时，原因：刚昨晚马的周游问题，数字之间用空格分开。。谁知道这题是用逗号，一改，AC了

#include <iostream> #include <cstring> #include <vector> using namespace std; int n, m, d; bool isPrime[9956]; vector<int> ans; bool isVis[1001]; bool isPass() {int maxIndex = ans.size() - 1;int sum = ans.back();for(int i = 1; i < d && i < ans.size(); i++) {sum += ans[maxIndex - i];if(isPrime[sum]) return false;}return true; } bool dfs() {if(ans.size() == m - n + 1){if(isPass()) return true;else return false;}for(int i = n; i <= m; i++) {if(!isVis[i]) {ans.push_back(i);isVis[i] = true;if(ans.size() > 1) {if(isPass() && dfs()) return true;isVis[i] = false;ans.erase(ans.begin() + ans.size() - 1);}else if(dfs()) return true;else {isVis[i] = false;ans.erase(ans.begin() + ans.size() - 1);}}}return false; } void setPrime() {memset(isPrime, true, sizeof(isPrime));isPrime[0] = isPrime[1] = false;for(int i = 2; i * i <= 9956; i++) {if(isPrime[i]) {for(int k = 2; k * i < 9956; k++) isPrime[k * i] = false;}} } int main() {setPrime();while(cin >> n >> m >> d && n != 0 && m != 0 && d != 0) {ans.clear();memset(isVis, false, sizeof(isVis));if(dfs()) {bool isFirst = true;for(vector<int>::iterator iter = ans.begin();iter != ans.end(); iter++) {if(isFirst) {cout << *iter;isFirst = false;}else cout << "," << *iter;}cout << endl;}else cout << "No anti-prime sequence exists./n";} } 

无意中在网上看到陈泽裕.aspx的卡时战略，我也用用，哇，太神奇了，之前没卡时的时候用了1.05s，卡时后才用了0.01s，这什么差距啊。。。代码如下：

#include <iostream> #include <cstring> #include <vector> using namespace std; int n, m, d; bool isPrime[9956]; vector<int> ans; bool isVis[1001]; int count; bool mark; bool isPass() {int maxIndex = ans.size() - 1;int sum = ans.back();for(int i = 1; i < d && i < ans.size(); i++) {sum += ans[maxIndex - i];if(isPrime[sum]) return false;}return true; } bool dfs() {if(count++ > 4000) {mark = true;return false;}if(ans.size() == m - n + 1){if(isPass()) return true;else return false;}for(int i = n; i <= m; i++) {if(mark) return false;if(!isVis[i]) {ans.push_back(i);isVis[i] = true;if(ans.size() > 1) {if(isPass() && dfs()) return true;isVis[i] = false;ans.erase(ans.begin() + ans.size() - 1);}else if(dfs()) return true;else {isVis[i] = false;ans.erase(ans.begin() + ans.size() - 1);}}}return false; } void setPrime() {memset(isPrime, true, sizeof(isPrime));isPrime[0] = isPrime[1] = false;for(int i = 2; i * i <= 9956; i++) {if(isPrime[i]) {for(int k = 2; k * i < 9956; k++) isPrime[k * i] = false;}} } int main() {setPrime();while(cin >> n >> m >> d && n != 0 && m != 0 && d != 0) {ans.clear();memset(isVis, false, sizeof(isVis));count = 0;mark = false;if(dfs()) {bool isFirst = true;for(vector<int>::iterator iter = ans.begin();iter != ans.end(); iter++) {if(isFirst) {cout << *iter;isFirst = false;}else cout << "," << *iter;}cout << endl;}else cout << "No anti-prime sequence exists./n";} } 

sicily 1002

这题没什么说的。。就是深搜，只不过我搞了一个小时，原因：刚昨晚马的周游问题，数字之间用空格分开。。谁知道这题是用逗号，一改，AC了

#include <iostream> #include <cstring> #include <vector> using namespace std; int n, m, d; bool isPrime[9956]; vector<int> ans; bool isVis[1001]; bool isPass() {int maxIndex = ans.size() - 1;int sum = ans.back();for(int i = 1; i < d && i < ans.size(); i++) {sum += ans[maxIndex - i];if(isPrime[sum]) return false;}return true; } bool dfs() {if(ans.size() == m - n + 1){if(isPass()) return true;else return false;}for(int i = n; i <= m; i++) {if(!isVis[i]) {ans.push_back(i);isVis[i] = true;if(ans.size() > 1) {if(isPass() && dfs()) return true;isVis[i] = false;ans.erase(ans.begin() + ans.size() - 1);}else if(dfs()) return true;else {isVis[i] = false;ans.erase(ans.begin() + ans.size() - 1);}}}return false; } void setPrime() {memset(isPrime, true, sizeof(isPrime));isPrime[0] = isPrime[1] = false;for(int i = 2; i * i <= 9956; i++) {if(isPrime[i]) {for(int k = 2; k * i < 9956; k++) isPrime[k * i] = false;}} } int main() {setPrime();while(cin >> n >> m >> d && n != 0 && m != 0 && d != 0) {ans.clear();memset(isVis, false, sizeof(isVis));if(dfs()) {bool isFirst = true;for(vector<int>::iterator iter = ans.begin();iter != ans.end(); iter++) {if(isFirst) {cout << *iter;isFirst = false;}else cout << "," << *iter;}cout << endl;}else cout << "No anti-prime sequence exists./n";} } 

无意中在网上看到陈泽裕.aspx的卡时战略，我也用用，哇，太神奇了，之前没卡时的时候用了1.05s，卡时后才用了0.01s，这什么差距啊。。。代码如下：

#include <iostream> #include <cstring> #include <vector> using namespace std; int n, m, d; bool isPrime[9956]; vector<int> ans; bool isVis[1001]; int count; bool mark; bool isPass() {int maxIndex = ans.size() - 1;int sum = ans.back();for(int i = 1; i < d && i < ans.size(); i++) {sum += ans[maxIndex - i];if(isPrime[sum]) return false;}return true; } bool dfs() {if(count++ > 4000) {mark = true;return false;}if(ans.size() == m - n + 1){if(isPass()) return true;else return false;}for(int i = n; i <= m; i++) {if(mark) return false;if(!isVis[i]) {ans.push_back(i);isVis[i] = true;if(ans.size() > 1) {if(isPass() && dfs()) return true;isVis[i] = false;ans.erase(ans.begin() + ans.size() - 1);}else if(dfs()) return true;else {isVis[i] = false;ans.erase(ans.begin() + ans.size() - 1);}}}return false; } void setPrime() {memset(isPrime, true, sizeof(isPrime));isPrime[0] = isPrime[1] = false;for(int i = 2; i * i <= 9956; i++) {if(isPrime[i]) {for(int k = 2; k * i < 9956; k++) isPrime[k * i] = false;}} } int main() {setPrime();while(cin >> n >> m >> d && n != 0 && m != 0 && d != 0) {ans.clear();memset(isVis, false, sizeof(isVis));count = 0;mark = false;if(dfs()) {bool isFirst = true;for(vector<int>::iterator iter = ans.begin();iter != ans.end(); iter++) {if(isFirst) {cout << *iter;isFirst = false;}else cout << "," << *iter;}cout << endl;}else cout << "No anti-prime sequence exists./n";} }