双重回文数（复杂版）
题目链接：
#include#include using namespace std;int a[20];bool check(int x, int k) { int p = 0; memset(a, 0, sizeof(int) * 20); while (x) { a[p++] = x % k; x /= k; } int i = p - 1, j = 0; while (i > j) { if (a[i--] != a[j++]) return 0; } return 1;}int main() { int N, S, count = 0; cin >> N >> S; for (int i = S + 1; count < N; i++) { int t = 0; for (int j = 2; j <= 10; j++) { if (check(i, j)) t++; if (t == 2) { count++; cout << i << endl; break; } } } return 0;}
获取一个字符串的全部回文子串
第一种思想：得到字符串的全部子串，判断。
vectorv;bool check(string s) { string s1 = s; reverse(s.begin(), s.end()); if (s.compare(s1) == 0)return 1; return 0;}void get_all_sub(string s,string help,int n) { if (n == s.length()) { if (!help.empty() && check(help)) { v.push_back(help); cout << help << endl; } return; } get_all_sub(s, help, n + 1); get_all_sub(s, help + s[n], n + 1);}
第二种思想：DP
（dp [ i ] [ j ] 表示 i 到 j 是否是回文串，二维的话 只需要数组的一般就可以了，用的是左下部分，所以 i , j 其实是反过来的）
转换方程： dp[i][j] = dp[i + 1][j - 1] && s[i] == s[j];
二维数组：
#include#include #include using namespace std;//i,j 表示i到j是否是回文串int dp[1000][1000];string s;void print(int i,int j) { while (i <= j) { cout << s[i++]; } cout << endl;}int main() { cin >> s; for (int i = 0; i < s.length(); i++) { dp[i][i] = 1; } for (int i = 0; i < s.length() - 1; i++) { dp[i + 1][i] = (s[i] == s[i + 1]); } for (int i = 2; i < s.length(); i++) { for (int j = 0; j < s.length(); j++) { if (i <= j + 1)continue; dp[i][j] = dp[i - 1][j + 1] && (s[i] == s[j]); } } for (int i = 0; i < s.length(); i++) { for (int j = 0; j < s.length(); j++) { if (i < j)continue; if (dp[i][j])print(j, i); } } return 0;}