1.最长公共子序列
#include<iostream> #include<bits/stdc++.h> using namespace std; // dp[i,j]=0 i=0 j=0 // dp[i-1,j-1]+1 ai==bj // max(dp(i,j-1),dp(i-1,j)) int main() { int N; while(cin>>N) { vector< vector<int> >dp(N+1,vector<int>(N+1,0)); string a=""; string b=""; char c; for(int i=0;i<N;i++) { cin>>c; a.push_back(c); } for(int i=0;i<N;i++) { cin>>c; b.push_back(c); } for(int i=0;i<N;i++) { dp[i][0]=0; dp[0][i]=0; } for(int i=1;i<=N;i++) for(int j=1;j<=N;j++) { if(a[i-1]==b[j-1]) dp[i][j]=dp[i-1][j-1]+1; else dp[i][j]=max(dp[i][j-1],dp[i-1][j]); } int max_length=0; for(int i=0;i<=N;i++) max_length=max(max_length,*max_element(dp[i].begin(),dp[i].end()) ); double result=double(max_length)/double(N); cout.setf(ios::fixed); if(result<=0.5) { cout << setprecision(2) << result; cout<<" "<<"Yes"<<endl; } else { cout << setprecision(2) << result; cout<<" "<<"No"<<endl; } } }
2.。回文素数
#include <algorithm> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <ctime> #include <iostream> #include <map> #include <queue> #include <set> #include <stack> #include <unordered_map> #include <vector> #define fir first #define se second #define ll long long #define pb push_back #define mp make_pair #define ull unsigned long long #define cl(a, b) memset(a, b, sizeof(a)) #define quickio(a) ios::sync_with_stdio(a) #define datatest() freopen("data.in", "r", stdin) #define makeans() freopen("data.out", "w", stdout) #define makedata() freopen("data.in", "w", stdout) #define pii pair<int, int> #define pll pair<ll, ll> #define pdd pair<double, double> using namespace std; const int maxn = 1e6 + 10; const int maxm = 1e6 + 10; const int inf = 0x3f3f3f3f; const ll mod = 1e9 + 7; const int maxblock = sqrt(maxn) + 10; const double eps = 1e-7; const ll INF = 1e16; bool vis[maxn]; int prime[maxn], cnt; void init() { cnt = 0; memset(vis, 0, sizeof vis); for (int i = 2; i < maxn; i++) { if (!vis[i]) { prime[cnt++] = i; } for (int j = 0; j < cnt; j++) { if (1LL * i * prime[j] >= maxn) break; vis[i * prime[j]] = 1; if (i % prime[j] == 0) { break; } else { } } } } bool check(std::string str) { for (int i = 0; i < str.size(); i++) { if (str[i] != str[str.size() - i - 1]) return false; } return true; } int n, m; int is[maxn]; int sum[maxn]; void build() { init(); for (int i = 0; i < cnt; i++) { if (check(to_string(prime[i]))) { is[prime[i]] = 1; } } for (int i = 11; i <= m; i++) { string str = to_string(i); for (int j = 0; j < str.size(); j++) { int num = 0; for (int k = 0; k < str.size(); k++) { if (k == j) continue; num = num * 10 + str[k] - '0'; } // cout << "i=" << i << " num=" << num << endl; if (is[num]) { sum[i] = 1; break; } } // cout << i << " " << sum[i] << endl; } for (int i = 1; i < maxn; i++) sum[i] += sum[i - 1]; } int main() { scanf("%d %d", &n, &m); build(); printf("%d\n", sum[m] - sum[n - 1]); return 0; }
全部评论
(2) 回帖