基因问题
#include <iostream> #include <vector> #include <string> #include <cstdio> using namespace std; int solution(const string& s1, const string& s2){ if(s1.empty() || s2.empty()) return 0; int N = s1.size(); vector<vector<int>> dp(N+1, vector<int>(N+1, 0)); for(int i=0; i<N; ++i){ for(int j=0; j<N; ++j){ if(s1[i] == s2[j]){ dp[i+1][j+1] = dp[i][j] + 1; }else{ dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1]); } } } return dp[N][N]; } int main() { int len; while(cin >> len){ char c; string s1, s2; for(int i=0; i<len; ++i){ cin >> c; s1 += c; } for(int i=0; i<len; ++i){ cin >> c; s2 += c; } int common = solution(s1, s2); printf("%.2f ", (double)common/len); if(common > len/2) cout<<"No "<<endl; else cout<<"Yes "<<endl; } } 回文素数, 纯暴力。。。不带任何技巧的那种#include <iostream> #include <vector> #include <string> #include <cstdio> #include <cmath> using namespace std; class Solution{ public: int solution(int low, int high){ int ans = 0; for(int i=low; i<=high; ++i){ if(helper(i)){ ++ ans; } } return ans; } bool helper(int num){ for(int k=1; k<=num; k*=10){ int t = (num/k/10*k + num%k); if(isHuiwen(t) && isSushu(t)){ return true; } } return false; } bool isSushu(int num){ if(num<=1) return false; int sqt = sqrt(num); for(int i=2; i<=sqt; ++i){ if(num % i == 0) return false; } return true; } bool isHuiwen(int num){ string s = to_string(num); for(int i=0, j=s.size()-1; i<j; ++i, --j){ if(s[i] != s[j]) return false; } return true; } }; int main(){ Solution sol; int low, high; while (cin>>low>>high){ cout<<sol.solution(low, high)<<endl; } }
全部评论
(8) 回帖