本文共 8434 字，大约阅读时间需要 28 分钟。
感觉不会再爱了。
/* ID: thestor1 LANG: C++ TASK: prime3 */#include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;struct Trie{ Trie* next[10]; Trie() { for (int i = 0; i < 10; ++i) { next[i] = NULL; } }};void insert(Trie *trie, string str){ for (int i = 0; i < str.size(); ++i) { if (!trie->next[str[i] - '0']) { trie->next[str[i] - '0'] = new Trie(); } trie = trie->next[str[i] - '0']; }}bool search(Trie *trie, string str){ for (int i = 0; i < str.size(); ++i) { if (!trie->next[str[i] - '0']) { return false; } trie = trie->next[str[i] - '0']; } return true;}bool isPrime(string str){ if ((str[4] - '0') % 2 == 0) { return false; } int num = 0; for (int i = 0; i < str.size(); ++i) { num = num * 10 + str[i] - '0'; } int upbound = sqrt(num); for (int i = 3; i <= upbound; ++i) { if (num % i == 0) { return false; } } return true;}void alltuples_recur(int index, string partial, int partialsum, std::vector &tuples, const int sum, const int leftcorner){ if (partialsum > sum) { return; } if (index == 5) { if (partialsum != sum) { return; } if (!isPrime(partial)) { return; } tuples.push_back(partial); return; } char start = '0'; if (index == 0) { start = '1'; } for (char c = start; c <= '9'; ++c) { string tmp = partial; tmp.push_back(c); // partial.push_back(c); alltuples_recur(index + 1, tmp, partialsum + c - '0', tuples, sum, leftcorner); // partial.pop_back(); }}bool check(std::vector square, Trie *trie, const int sum){ std::vector strs(6, ""); // 5 columns, 1 diagonals int diagonalsum = 0; for (int i = 0; i < square.size(); ++i) { for (int j = 0; j < square[i].size(); ++j) { strs[j].push_back(square[i][j]); if (i == j) { strs[5].push_back(square[i][j]); } if (i + j == 4) { diagonalsum += square[i][j] - '0'; if (diagonalsum > sum) { return false; } } } } for (int i = 0; i < strs.size(); ++i) { if (!search(trie, strs[i])) { return false; } } if (square.size() == 5) { string diagonal = ""; for (int i = square.size() - 1; i >= 0; --i) { for (int j = 0; j < square[i].size(); ++j) { if (i + j == 4) { diagonal.push_back(square[i][j]); } } } return search(trie, diagonal); } return true;}void printSquare(std::vector square){ for (int i = 0; i < square.size(); ++i) { for (int j = 0; j < square[i].size(); ++j) { cout< > &squares, const std::vector &tuples, Trie* trie, const int sum, const int leftcorner){ vector square(5, string(5, '0')); string tmp(5, '0'); int N = tuples.size(); for (int i1 = 0; i1 < N; ++i1) { if (tuples[i1][0] - '0' != leftcorner) { continue; } // upperleft-lowerright diagonal for (int r = 0, i = 0; r < 5; ++r, ++i) { square[r][r] = tuples[i1][i]; } // printSquare(square); for (int i2 = 0; i2 < N; ++i2) { if (tuples[i2][2] != square[2][2] || tuples[i2][0] % 2 == 0) { continue; } // lowerleft-upperright diagonal for (int r = 4, i = 0; r >= 0; --r, ++i) { square[r][4 - r] = tuples[i2][i]; } // printSquare(square); for (int i3 = 0; i3 < N; ++i3) { if (!(tuples[i3][1] == square[1][1] && tuples[i3][3] == square[3][1])) { continue; } // 2nd column for (int r = 0, i = 0; r < 5; ++r, ++i) { // cout<<"[debug]square["< <<"][1]:"< <<", tuples[i3]["< <<"]:"< < = '0' && square[0][2] <= '9')) { continue; } if (!search(trie, square[0])) { continue; } // 1st row square[4][2] = sum + '0' - (square[4][0] - '0') - (square[4][1] - '0') - (square[4][3] - '0') - (square[4][4] - '0'); // printSquare(square); if (!(square[4][2] >= '0' && square[4][2] <= '9')) { continue; } if (!search(trie, square[4])) { continue; } // 3rd row for (char c31 = '1'; c31 <= '9'; ++c31) { for (char c35 = '1'; c35 <= '9'; c35 += 2) { square[2][0] = c31; square[2][4] = c35; if (!search(trie, square[2])) { continue; } // for (set ::iterator iter5 = tuples.begin(); iter5 != tuples.end(); ++iter5) // { // if (!((*iter5)[1] == square[2][1] && (*iter5)[2] == square[2][2] && (*iter5)[3] == square[2][3])) // { // continue; // } // 3rd row // for (int c = 0, i = 0; c < 5; ++c, ++i) // { // square[2][c] = (*iter5)[i]; // } // printSquare(square); // 1st column for (char c21 = '0'; c21 <= '9'; ++c21) { for (char c41 = '0'; c41 <= '9'; ++c41) { square[1][0] = c21; square[3][0] = c41; // string tmp(5, '0'); for (int r = 0; r < 5; ++r) { tmp[r] = square[r][0]; } if (!search(trie, tmp)) { continue; } // for (set ::iterator iter6 = tuples.begin(); iter6 != tuples.end(); ++iter6) // { // if (!((*iter6)[0] == square[0][0] && (*iter6)[2] == square[2][0] && (*iter6)[4] == square[4][0])) // { // continue; // } // 1st column // for (int r = 0, i = 0; r < 5; ++r, ++i) // { // square[r][0] = (*iter6)[i]; // } // printSquare(square); // 5th column for (char c25 = '0'; c25 <= '9'; ++c25) { for (char c45 = '0'; c45 <= '9'; ++c45) { square[1][4] = c25; square[3][4] = c45; // string tmp(5, '0'); for (int r = 0; r < 5; ++r) { tmp[r] = square[r][4]; } if (!search(trie, tmp)) { continue; } // for (set ::iterator iter7 = tuples.begin(); iter7 != tuples.end(); ++iter7) // { // if (!((*iter7)[0] == square[0][4] && (*iter7)[2] == square[2][4] && (*iter7)[4] == square[4][4])) // { // continue; // } // 5th column // for (int r = 0, i = 0; r < 5; ++r, ++i) // { // square[r][4] = (*iter7)[i]; // } // printSquare(square); // 2nd row square[1][2] = sum + '0' - (square[1][0] - '0') - (square[1][1] - '0') - (square[1][3] - '0') - (square[1][4] - '0'); // printSquare(square); if (!(square[1][2] >= '0' && square[1][2] <= '9')) { continue; } if (!search(trie, square[1])) { continue; } // 4th row square[3][2] = sum + '0' - (square[3][0] - '0') - (square[3][1] - '0') - (square[3][3] - '0') - (square[3][4] - '0'); // printSquare(square); if (!(square[3][2] >= '0' && square[3][2] <= '9')) { continue; } if (!search(trie, square[3])) { continue; } // // 5th row // square[4][2] = sum + '0' - (square[4][0] - '0') - (square[4][1] - '0') - (square[4][3] - '0') - (square[4][4] - '0'); // // printSquare(square); // if (!(square[4][2] >= '0' && square[4][2] <= '9')) // { // continue; // } // if (!search(trie, square[4])) // { // continue; // } // string tmp(5, '0'); for (int i = 0, r = 0; r < 5; ++r, ++i) { tmp[i] = square[r][2]; } if (!search(trie, tmp)) { continue; } squares.push_back(square); } } } } } } } } } }}void square_recur(vector > &squares, std::vector square, const std::set &tuples, const set &firstlines, Trie* trie, const int sum){ // printSquare(square); if (square.size() > 1 && square.size() < 4 && !check(square, trie, sum)) { return; } else if (square.size() == 4) { string tmp(5, sum + '0'); for (int r = 0; r < 4; ++r) { for (int c = 0; c < 5; ++c) { tmp[c] -= square[r][c] - '0'; } } for (int i = 0; i < 5; ++i) { if (!(tmp[i] >= '0' && tmp[i] <= '9')) { return; } } if (!search(trie, tmp)) { return; } square.push_back(tmp); if (check(square, trie, sum)) { squares.push_back(square); } return; } if (square.size() == 0) { for (set ::iterator iter = firstlines.begin(); iter != firstlines.end(); ++iter) { square.push_back(*iter); square_recur(squares, square, tuples, firstlines, trie, sum); square.pop_back(); } } else { for (set ::iterator iter = tuples.begin(); iter != tuples.end(); ++iter) { square.push_back(*iter); square_recur(squares, square, tuples, firstlines, trie, sum); square.pop_back(); } }}// void alltuples(int sum, int leftcorner)// {// std::set tuples, firstlines;// alltuples_recur(0, "", 0, tuples, firstlines, sum, leftcorner);// cout<<"tuples:"< ::iterator iter = tuples.begin(); iter != tuples.end(); ++iter)// {// cout<<*iter< ::iterator iter = firstlines.begin(); iter != firstlines.end(); ++iter)// {// cout<<*iter< &square1, const std::vector &square2){ for (int r = 0; r < 5; ++r) { if (square1[r] < square2[r]) { return true; } else if (square1[r] > square2[r]) { return false; } } return false;}int main(){ // clock_t start, end1, end2, end3, end; // start = clock(); FILE *fin = fopen("prime3.in", "r"); FILE *fout = fopen("prime3.out", "w"); // alltuples(11, 1); int sum, leftcorner; fscanf(fin, "%d", &sum); fscanf(fin, "%d", &leftcorner); std::vector tuples; alltuples_recur(0, "", 0, tuples, sum, leftcorner); // end1 = clock(); // cout<<"alltuples:"<<(double) (end1 - start) / CLOCKS_PER_SEC< > squares; // square_recur(squares, std::vector (), tuples, firstlines, trie, sum); fill_square(squares, tuples, trie, sum, leftcorner); // end3 = clock(); // cout<<"square_recur:"<<(double) (end3 - end2) / CLOCKS_PER_SEC<
转载地址：http://kbxli.baihongyu.com/